nim-eth icon indicating copy to clipboard operation
nim-eth copied to clipboard

Implement incremental hasher for computing txroot/etc without constructing database

Open arnetheduck opened this issue 1 year ago • 0 comments

When computing MPT roots, the current version of the code works by constructing a database of the full value and then hashing up to the root - this is extremely inefficient due to the many allocations involved as well as the cost of maintaining the full data in memory - instead, it's possible to build an incremental hasher that:

  • only stores hashes, not values
  • every time a branch is full (ie has 16 children) collapses those into a single hash

Examples of this can be found:

  • https://github.com/status-im/nim-ssz-serialization/blame/b5aa78cae197cc97277be050ba69ef9c5d33aad1/ssz_serialization/merkleization.nim#L42
  • https://github.com/alloy-rs/trie/tree/main/src/hash_builder

Also related is https://github.com/status-im/nim-eth/issues/698

arnetheduck avatar Aug 30 '24 10:08 arnetheduck