nim-eth
nim-eth copied to clipboard
Implement incremental hasher for computing txroot/etc without constructing database
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