search

ferranbt / fastssz

Fast Ethereum2.0 SSZ encoder/decoder
MIT License
73 stars 44 forks source link

Tree Optimization #120

Closed claravanstaden closed 1 year ago

claravanstaden commented 1 year ago

The current implementation of the FastSSZ tree fills empty nodes of the tree so that the number of tree leaves are to the power of 2. However, if the max capacity of a the tree leaves is very large (like BeaconState Validators, max capacity is 1 099 511 627 776), Go cannot preallocate such a large slice (see issue https://github.com/ferranbt/fastssz/issues/119#issuecomment-1380956176). Even if it could allocate the slice, adding all the empty nodes isn't necessary and slows down the tree creation since it needs to populate all the empty leaves, plus their parents.

This PR changes the tree implementation to only add nodes that have values, and adds precomputed zero order hashes where the adjacent sibling requires a right-node sibling in order to hash the two nodes together.

Taking @protolambda's SSZ diagram as an example, in the current version of this library, nodes 7, 14 and 15 would be added as part of the tree. In this PR, only node 7 is added.

Screenshot 2023-02-06 at 14 57 06

This improves the performance of GetTree significantly and enables the successful testing of all the spectests, where BeaconBlock, BeaconState and ExecutionPayload were previously skipped because of performance issues.

ferranbt commented 1 year ago

This looks amazing! I will need a bit of time but It will most likely land by the end of the week. Could you regenerate the testcases (make generate-testcases) to pass the CI?

claravanstaden commented 1 year ago

Thanks @ferranbt, that sounds good. CI should pass now, I tested on our fork: https://github.com/Snowfork/fastssz/actions/runs/4106825072/jobs/7085540042

I had to add go mod vendor to the CI to download stretchr, not sure why it isn't necessary for the other go vendor dependencies.