Only recompute changed portion of SSZ consensus object Merkle hash trees

[tersec]

Currently, hash_tree_root(...) recomputes from scratch every time. This generally isn't necessary, and for BeaconState quite expensive (0.05 seconds currently for me). Rather, some of the arrays, and portions of arrays might simply not have to be hashed. This has been reported by other clients to produce orders-of-magnitude performance improvements in state hashing in practice.

For reference, @mratsim has provided the following links (any errors in annotations are mine):

https://gist.github.com/protolambda/db363b10911db0a93172a207bdb24419 illustrates a simple copy-on-write approach.

prysmaticlabs/go-ssz#91 illustrates the specific case of sub-array-granularity Merkle tree updating, when, e.g., specific validators need to have their balances updated.

https://github.com/tobgu/pyrsistent provides a fuller-featured back-end in Python generalizing such an immutable and persistent data structure which can support this sort of caching.

nim-lang/Nim#10819 provides one example mechanism by which one might implement this functionality.

https://forum.nim-lang.org/t/4771 suggests further improvements inspired by the https://www.unisonweb.org/ towards such incremental compilation.

[tersec]

https://github.com/protolambda/remerkleable elaborates upon that CoW demo that protolambda illustrates above.

[protolambda]

The gist is quite old, since then I implemented it in Go as library with a bunch of fixes (github.com/protolambda/ztyp/) and I iterated on the pattern more and documented that here: https://github.com/protolambda/eth-merkle-trees/blob/master/typing_partials.md
And since then I implemented it as "pymerkles", which then evolved in "re-merkle-able", iterating on it even more. The eth2 spec on the dev branch runs on it, and much faster than the previous spec implementation, and very readable thanks to python.
If anyone is around at ethdenver, SBC, or ethCC I'm happy to go through the ideas and implementation questions.

[tersec]

#722 would increase the priority of this.

[protolambda]

Just got a notification of this. Some update on where I'm at: remerkleable is mostly feature complete, used in the spec, and quite easy to script things with. It represents data as binary tree, and creates views as needed around it when you modify. Mutability is in the view, the underlying tree is persistent.

However, binary trees can be slow to traverse, and temporary views slow things down too. The result is that although hashing and memory stay super low (since copying state is just a new reference to old data), traversals/lookups/serialization become more expensive. A trade-off you can code around in many places, and get pretty good speed. Proof of concept here: github.com/protolambda/eth2fastspec

Currently I'm in the process of updating "ztyp" (yes, I'll rebrand away from zABC after this, name suggestions welcome), the Go version of remerkleable, but it's more verbose, and goes deeper into optimizing the internals. It will take some time to catch up with usability of remerkleable there.

If you want to ship fast, a hybrid approach like Prysm and Lighthouse are implementing works well enough: cache intermediate hash-tree-roots of bigger balanced structures in a flat array, and try your best to minimize the total amount of full state copies. Then consider handling parts of the state as immutable trees, like the validator registry,
along the way.

BeaconState quite expensive (0.05 seconds currently for me)

How many validators? Try that with 50 or a 100 thousand to compare with Prysm/Lighthouse. You definitely need some kind of caching there.

[arnetheduck]

#1084 implements the hybrid, fast ship version ;) A major consideration of the tree-based approaches is how hard it is to analyse their overhead in terms of overhead: memory, reference counting, data sharing, their stress on the garbage collector etc etc.

The fast-ship version is more or less bounded and trivial to reason about - in our implementation in particular, it leads to essentially minimal or no unpredictable memory allocation and usage.