EIP-4881 Deposit Trie Optimization

[saolyn]

🦄 Feature Tracking

This feature stems from an idea of @nisdas on representing the deposit trie in a more space-efficient manner: #10179.

More details can be found in the design doc.

Feature Description

Currently, Prysm stores a deposits Merkle trie in memory, which is a massive cost on RAM given we keep the data of all the related deposits in the beacon node. On mainnet, this includes over 400,000 deposits, and beacon nodes also have the hidden costs of having to retrieve these 400k deposit logs from an associated execution client. However, this is not necessary for consensus. A few ideas have emerged on how to reduce the impact of handling deposits in beacon nodes.

Goals

• Minimize the memory footprint of our deposits trie and prune deposits older than the finalized ones from the perspective of the finalized execution client block hash
• To support finalized deposit trie snapshots via checkpoint sync, à la EIP-4881

Approach

We are to adapt the reference design of EIP-4881 to our current implementation of a sparse merkle trie and without recursion.

Tasks

• Raw implementation of the EIP
• Create a new package under beacon-chain/cache/depositsnapshot containing a sparse Merkle tree that supports “finalizing” and pruning branches that are not needed
• Implement the reference design of EIP-4881, but without recursion
• Implement MerkleTree with and without recursion
• Implement DepositTree
• Implement get_proof for both MerkleTree and DepositTree
• Implement DepositTreeSnapshot
• Implement the spec test
• Test that the resulting trees are as expected
• Add fuzz tests
• Define a common interface that both beacon-chain/cache/depositsnapshot and beacon-chain/cache/depositscache implement, so they can be swappable at runtime
• Benchmark both deposit tree implementations for some of their important methods
• Benchmark the new trie design
• Figure out what changes need to happen at the DB layer for this new design
• Create a feature flag for swapping between implementations at runtime
• Finally, implement the RPC endpoints required by EIP-4881

This issue should be closed after all of the above tasks are complete.

[saolyn]

Here is a branch containing the bare minimum raw Go implementation of the EIP-4881 algorithm.

[james-prysm]

closing as this feature is done, it can be enabled on the beacon node with --enable-eip-4881