EIP-6800 State transition to a unified Verkle tree (Ethereum state using a unified verkle tree)
No call decision · Scaling & data · EIP status Stagnant · created 2023-03-17
Adds a new Verkle tree alongside the existing Patricia tree, storing post-fork state changes and accessed data in the Verkle tree while freezing the Patricia tree. This is the first step toward reducing proof sizes for stateless clients.
Why it is needed
Currently, Ethereum's state is stored in a single hexary Patricia tree, and the proof (witness) needed to access a single account averages 3 kilobytes and can be up to three times larger in the worst case. Dividing a block's 15 million gas by 2500 gas per access allows up to 6000 accesses, during which the proof size could grow to about 18 megabytes. This is too large to safely propagate over the peer-to-peer network within a 12-second slot. A Verkle tree is therefore needed, which can reduce the average proof per account to about 200 bytes. This EIP leaves the Patricia tree in place while adding a new Verkle tree, laying the first step toward eventually replacing the tree entirely.
What changes
Today
- State proofs (witnesses) average 3 kilobytes per account and can be larger in the worst case
- Up to 6000 accesses per block can grow proofs to about 18 megabytes
- This size is difficult to propagate safely over P2P within a 12-second slot
- State is stored only in a single hexary Patricia tree
After EIP-6800
- A new Verkle tree is added alongside the Patricia tree, storing all post-fork changes and access data
- The Patricia tree is frozen and no longer modified
- Account access proofs shrink to about 200 bytes on average
- Code, storage, and account headers are unified into a single key-value tree structure
Who is affected
- Client teams: Both trees (Patricia and Verkle) must be maintained simultaneously while preparing for the eventual tree replacement.
- Smart contract developers: Gas costs for code chunk and storage access change, increasing or decreasing gas usage for some apps.
- Validators and full nodes: Affected by the structural changes made with stateless verification in mind, as proof sizes shrink.
- Wallet & app developers: Need to account for changes to the account data layout (version, balance, nonce, code_size).
In depth
Verkle tree structure
A Verkle tree is a single-layer key-value tree whose root is computed from Pedersen commitments over the Bandersnatch curve. For each stem (31 bytes), extension_and_suffix_tree groups 256 values into two sub-commitments C1 and C2 (128 each), and the leaf is formed by committing again to the extension marker (1), the stem, group_to_scalar_field(C1), and group_to_scalar_field(C2). VERKLE_NODE_WIDTH is 256, and a position holding the value 0 is encoded differently from an empty position (a value of 0 is distinguished by adding 2**128).
Tree embedding parameters
Constants for placing account headers, code, and storage into a single tree are defined as BASIC_DATA_LEAF_KEY=0, CODE_HASH_LEAF_KEY=1, HEADER_STORAGE_OFFSET=64, CODE_OFFSET=128, VERKLE_NODE_WIDTH=256, MAIN_STORAGE_OFFSET=256**31. VERKLE_NODE_WIDTH > CODE_OFFSET > HEADER_STORAGE_OFFSET must hold, and MAIN_STORAGE_OFFSET must be a power of VERKLE_NODE_WIDTH. get_tree_key feeds address and tree_index into pedersen_hash to obtain 31 bytes, then appends sub_index as the last byte to form the key.
Account header encoding
The value pointed to by get_tree_key_for_basic_data packs version (offset 0, 1 byte), code_size (offset 5, 3 bytes), nonce (offset 8, 8 bytes), and balance (offset 16, 16 bytes) in big-endian. Offsets 1 to 4 are reserved. If any account header field is set, version is also set to 0, and codehash and code_size are set at contract or EOA creation time. For EXTCODEHASH backward compatibility, the code hash is stored separately at CODE_HASH_LEAF_KEY (1).
Code chunking
Code is stored in chunks of 31 bytes via get_tree_key_for_code_chunk. Within each chunk's 32-byte value, byte 0 indicates the number of leading bytes in that chunk that continue as PUSHDATA, and bytes 1 through 31 are the actual 31 bytes of code. The chunkify_code algorithm computes this by tracking the length of push data following PUSH1 through PUSH32 (opcodes 0x60 to 0x7f), and the code length is padded with zero bytes to a multiple of 31.
Storage slot mapping
get_tree_key_for_storage_slot stores at HEADER_STORAGE_OFFSET + storage_key if storage_key is less than CODE_OFFSET - HEADER_STORAGE_OFFSET, and at MAIN_STORAGE_OFFSET + storage_key otherwise. Slots within the same VERKLE_NODE_WIDTH (256) range are grouped into a single commitment, except across the HEADER_STORAGE_OFFSET boundary, making proofs more efficient when accessing related slots together. It is noted that Solidity already lays out slots this way.
Gas recalibration
The new gas costs are calibrated against WITNESS_CHUNK_COST of 6.25 gas/byte (for chunks), WITNESS_BRANCH_COST of roughly 13.2 gas/byte on average (assuming 144-byte branches), and a worst case of about 2.5 gas/byte where an attacker deliberately fills the tree. The key changes versus Berlin are: a new 200 gas charge per 31-byte code chunk (estimated to raise average gas usage by about 6 to 12 percent), access to an adjacent storage slot within the same group of 256 dropping from 2100 to 200 except for the first access, and access to storage slots 0 through 63 dropping from 2100 to 200 including the first access.
Backwards compatibility and mitigations
The introduction of gas costs for code chunk access could make some applications less economical, and the change in tree structure means existing logic that proves past state within the EVM will no longer work. The former can be mitigated by raising the block gas limit at the same time this EIP is adopted, reducing the risk that a transaction's gas usage exceeds the block gas limit.
Future transition and current status
This EIP only freezes the Patricia tree; the actual tree replacement happens in a later hard fork described in EIP-7612. At that point, because the Patricia tree is fixed, the replacement Verkle tree can be precomputed off-chain, unlike the EIP-2584 approach where clients had to recompute it in real time. The detailed gas rules for access events are described in EIP-4762, and this EIP assumes EIP-6780. The Security Considerations section in the source text only says 'Needs discussion,' the test cases are still TODO, and the current status is Stagnant.