Zoned binary tree, a new state store that is light to prove

Strawmap I* (2028) · partitioned binary tree

Ethereum replaces the data structure that stores accounts, code and storage, currently a hexary Merkle Patricia Trie, with a single binary tree where each node has two branches. This is a preparatory step for verifying blocks lightly with proofs.

Why it is needed

Ethereum's long-term goal is to verify blocks with validity proofs so that anyone can check the chain lightly and quickly. To do that, the state read while executing transactions must be proven, and the current Merkle Patricia Trie (MPT) is not suited to this. It uses Keccak hashes and RLP encoding, which are expensive to prove, and it has a 'tree within a tree' structure in which a separate storage tree hangs under the account tree. It also cannot prove just part of a contract's code. To prove 1 byte of code, the entire code must be revealed, so in the worst case a single block needs about 1.8GB of proof. A binary tree with two branches minimizes proof size. Switching to a hash that is favorable for proving also improves the performance of the circuits that generate proofs. It uses only hash functions and no elliptic curves, so it is also safe against quantum computer attacks. However, the hash function has not been decided yet and the EIP is still at the Draft stage, so details may change.

How it works

  1. Zones are split by the first byte The first byte of every key marks the zone. 0x00 is the account header, 0x01 is a code chunk, and 0xFF is storage. Instead of keeping a separate storage tree under each account, everything goes into one tree.
  2. Assemble the key A key is built by joining the zone byte, a tree position determined by a hash, and a 1-byte sub-index. Key length is fixed within a zone, so no key is ever a prefix of another key. Contract code is also cut into chunks and inserted in the same way.
  3. The tree is built from two kinds of nodes A leaf node holds a complete key and a 32-byte value, and a branch node holds the bit range shared by the keys below it and its left and right children. Each set of keys has exactly one valid tree, so whoever builds it gets the same tree.
  4. Hash them together and summarize into one root Leaves and branches are each tagged, hashed, and combined upward into a single root. Because a leaf holds the complete key, a change to a branch elsewhere does not alter the hash of an unrelated leaf. The hash function is undecided among BLAKE3, Keccak and Poseidon2.

Related EIPs

← Roadmap