EIP-7864 Unified binary state tree (Ethereum state using a unified binary tree)
No call decision · Scaling & data · EIP status Draft · created 2025-01-20
Introduces a new state tree that holds account information, contract code, and storage all in a single binary tree. The goal is to replace the existing hexary Merkle Patricia Trie to make proofs smaller and easier to construct.
Why it is needed
Ethereum's long-term goal is to verify that a block executed correctly simply and quickly using a validity proof. But the current state tree, the Merkle Patricia Trie (MPT), does not fit this goal. It uses RLP for node encoding and the circuit-unfriendly Keccak hash, has a tree-within-a-tree structure where storage trees are nested inside the account tree, and account code is not even included in the state tree. Proof size is also a problem. Because each node has 16 children, proving a single branch in a tree of size 2^32 requires about 3840 bytes on average, and the source document calculates that a worst-case block reading 1 byte each from different accounts' code at 30 million gas would require about 330MB. Switching to a binary tree with 2 children per node minimizes proof size and also opens the door to switching to a proof-friendly hash function.
What changes
Today
- A tree-within-a-tree structure where the account tree and each account's storage tree are separate
- Because each node has 16 children, a proof includes 15 sibling nodes each time, making it large
- Contract code is not included in the state tree
- RLP is used for node encoding
After EIP-7864
- Account header, code, and storage are all placed in a single binary tree
- Because each node has 2 children, proofs are smallest for a given tree size (768 bytes for a 2^24 tree)
- Code is split into 31-byte chunks and stored in the tree
- Nodes are merkleized using simple hashing rules alone, without RLP
Who is affected
- Client teams: The state tree needs to be reimplemented. However, because the tree is a single key/value store abstraction, the code for database reads/writes, caching, syncing, and proof generation/verification becomes simpler.
- Contract and app developers: Gas costs for accessing code chunks change, which could affect the economics of applications. The source document notes this can be mitigated by raising the gas limit. Also, the method previously used to prove past state within the EVM no longer works because the tree structure has changed.
- Zero-knowledge proof researchers: The simple branching rule without extension nodes and candidate proof-friendly hash functions (BLAKE3, Poseidon2, etc.) make it easier to build state proofs inside circuits.
- Ordinary users: Nothing changes immediately, but in the long term this becomes the foundation for light and fast chain verification that validates entire blocks using validity proofs.
In depth
Tree structure: stems and four node types
The tree is a key/value store where keys are byte strings and values are 32 bytes. The first byte of the key is the storage type, the portion before the last byte is the stem, and the last byte is the subindex. The 256 keys sharing the same stem are gathered under the same StemNode. There are four node types. InternalNode has left_hash and right_hash. StemNode has stem, left_hash, and right_hash, and LeafNode has a 32-byte value or is empty. EmptyNode represents an empty subtree. The path does not use all 248 bits; it creates only the minimum InternalNodes needed when another stem shares the same prefix. Unlike the MPT, this approach has no extension nodes along the path, and instead reduces depth this way.
Merkleization rules
The hash function hash has two special cases. If all 64 bytes are zero, the result is 32 bytes of zero; otherwise it uses the chosen cryptographic hash H(value) as is. Input length must be either 32 or 64 bytes. The per-node rules are: internal_node_hash = hash(left_hash || right_hash), stem_node_hash = hash(stem || 0x00 || hash(left_hash || right_hash)), leaf_node_hash = hash(value), empty_node_hash = 32 bytes of zero. The 256 values under a stem node are folded into a small Merkle tree by pairing up leaf hashes going up, then hashed together with the stem. RLP encoding is not used.
Tree embedding and basic data packing
State is divided by storage kind. HEADER_SUBTREE = 0, CODE_SUBTREE = 1, and STORAGE_SUBTREE = 255 form the first byte of the key, so each kind can be synced separately or treated differently. The account header stem bundles basic data (BASIC_DATA_LEAF_KEY = 0), the code hash (CODE_HASH_LEAF_KEY = 1), the first storage slots, and the first code chunks together, reducing branch opening for data that is frequently read together. In a single basic data leaf, version (offset 0, 1 byte), code_size (offset 5, 3 bytes), nonce (offset 8, 8 bytes), and balance (offset 16, 16 bytes) are packed in big-endian order, and bytes 1..4 are reserved. The 3 to 4 branch openings normally needed when fields are kept separate are reduced to 1, simplifying gas costs and witness generation.
Code chunking
Contract code is split into 31-byte pieces before entering the tree. Each chunk is a 32-byte value, where bytes 1 through 31 are the i-th 31-byte slice of the code and byte 0 is the number of bytes at the start of the chunk that belong to PUSHDATA. For example, if a chunk boundary falls in the middle of a PUSH4's data, the next chunk starts like 2 97 96 PUSH1 128 MSTORE, with the leading 2 marking that the first 2 bytes are data. Chunk placement works as follows: if chunk_id is less than CODE_CHUNKS_IN_HEADER = 16, it goes at the CODE_OFFSET + chunk_id position in the header stem; otherwise it is grouped under CODE_SUBTREE using hash(address + bytes([high])) as the stem, in units of STEM_SUBTREE_WIDTH = 256. Since code now lives in the state tree, code access can also be handled with Merkle proofs.
Storage layout and grinding prevention
The leading storage slots (based on STORAGE_CHUNKS_IN_HEADER = 4) are stored together in the account header stem, and the rest are grouped into units of 256 under STORAGE_SUBTREE. Slots within the same 256-sized range share the same stem, making it easy to prove adjacent slots together. The reason for using the form hash(address) + hash(address + int_to_bytes(high)) in key computation is also stated explicitly. It is meant to prevent denial-of-service (DoS) attack paths: even if a storage key is ground to concentrate at a specific position, it cannot be reused across different contracts. There is an invariant that MAIN_STORAGE_OFFSET = 256**31 must be a power of STEM_SUBTREE_WIDTH.
Hash function undecided, with post-quantum considerations
The current draft and reference implementation use BLAKE3, but the source text explicitly says this should not be treated as final. The candidates are BLAKE3 (good out-of-circuit performance, well-vetted security), Keccak (already used by Ethereum, but less efficient in circuit proving), and Poseidon2 (strong in-circuit performance; the Ethereum Foundation's cryptography initiative is still conducting security analysis, and choosing it would require an additional specification of field choice and encoding). The reasoning also cites expert estimates that quantum computers could become practical in the 2030s, and NIST guidance recommending phasing out elliptic curve cryptography by 2030. Unlike the Verkle Tree, which relies on elliptic curves, this design depends only on hash functions and is therefore quantum resistant. The source states that this tree is likely to become the protocol's final state tree.
Transition approach and backward compatibility
The new binary tree in this EIP starts empty and holds only new state changes. The existing MPT does not disappear; it is frozen. Migrating the frozen MPT data into the new tree is handled by a separate hard fork, EIP-7748. The fork activation method is defined in EIP-7612, and access events and gas rules are defined in EIP-4762. There are two compatibility issues. First, code chunk access gas costs could affect application economics, which can be mitigated by raising gas limits at implementation time. Second, because the tree structure changes, methods that previously proved historical state inside the EVM will no longer work. The text notes that state expiry strategies such as EIP-7736 could be applied via design changes such as adding an epoch field to StemNode or placing a metadata subtree within the 247-bit stem.
Draft status, subject to change
This EIP was created on January 20, 2025 and is in Draft status, so its content may still change. In particular, the hash function remains undecided among BLAKE3, Keccak, and Poseidon2, and the test vectors and Security Considerations section are marked as still empty or in need of discussion. No decision to include this EIP in a specific fork appears in the current record.