Discussion topic for EIP-7864
This EIP is a renewed take on a Binary tree proposal for the Ethereum state. Compared to EIP-3102 it proposes a single balanced tree and pulls other ideas similar to EIP-6800 which are agnostic to Verkle (e.g. packing of account data, storage-slot, and code chunks).
Hash-based state-trees have renewed interest due to:
- Potential PQ concerns
- Proving systems advancing quickly and getting closer to viable proving state via SNARK/STARKs.
There are two main open questions about a Binary Tree design:
- Sparse vs Non-Sparse
- Which hash function to use for merkelization
Reg 1., the ideal design for a spec would be a Sparse Merkle tree due to its simplicity. There’s a doc summarizing previous research to deal with drawbacks.
Reg 2., this depends on evolving provers performance and potential security concerns of the considered options.
The current draft proposal decided:
- For 1., use a non-sparse Merkle tree only compressing branches at the stem-level (stem is defined in the EIP). This aims to avoid complex extension nodes rules, while also trying to lower the amount of hashing done for merkelization. The latter is required since today we’re very tight on proving performance for commodity hardware.
- For 2., use BLAKE3, which is a real (~optimistic) candidate. The current draft does this since it can help EL clients want to experiment with the implementation without much friction. If Poseidon2 is proven secure, the EIP can be easily adjusted by describing a
32-byte→[Field]encoding without much impact on the rest of the design. Using Poseidon2 could also re-open the “sparse tree” discussion since the proving performance is very high.
The above aren’t final decisions, but the current proposal allows a solid ground for further discussions, research, PoC, or analysis on how this would look in mainnet. There’s a python implementation for this EIP here.
We welcome anyone in the community (e.g. core devs, app developers, L2s) to provide feedback and collaborate!
Extra notes:
- We haven’t gone all-in in some other potential “Rationale” sections, such as expected Merkle proof sizes, implement them in the Python spec, and other potential ones. The main goal for now is to gain more confidence in the overall picture, and we’ll expand on that front later.
- EL clients might be interested in a useful trick to handle an arity-N tree regarding the number of internal nodes overhead (note that the doc explains this for an SMT, but the same idea applies to any arity-N tree).
- Gas remodeling is EIP-4762. It might need constant adjustments, but the overall approach would be the same.
The proposed state-conversion strategy (EIP-7748) for moving from MPT to VKT/Binary is the same since it is agnostic to the target tree.
As mentioned, today’s main blocker is finding a secure cryptographic hash function with a proving system with enough proving throughput in recommended hardware (i.e. in-circuit performance).
Although out-of-circuit performance isn’t the primary decision factor, I’ll soon share some benchmarks on the different hash alternatives run on a machine with the recommended hardware. This information would be a first step in understanding tree update and (non-snark) proof creation performance.
For in-circuit performance benchmarks, please refer to the following doc.