EIP-7748 State Transition to the Verkle Tree (State conversion to Verkle Tree)
No call decision · Scaling & data · EIP status Draft · created 2024-07-23
Defines a conversion procedure that moves a fixed number of key-value pairs per block from the existing Merkle Patricia Tree (MPT) to the Verkle Tree (VKT). Once the conversion is complete, state can be accessed using only the VKT, without an overlay tree.
Why it is needed
Ethereum stores all account and contract data in a data structure called the Merkle Patricia Tree (MPT), and a transition to a new data structure called the Verkle Tree (VKT) is being prepared. Earlier, EIP-7612 introduced an intermediate mechanism called the Overlay Tree, so that only data newly written by transactions is recorded in the VKT. However, the total state is too large, and simply waiting for transactions to naturally touch the data will not move everything over. So this EIP proposes a procedure that mechanically moves a fixed amount of data from the old tree to the new tree every block. The goal is to finish the conversion within a reasonable time and, once complete, remove the intermediate overlay tree mechanism so that all state access goes directly through the VKT.
What changes
Today
- The entire state resides in the MPT, and only data touched by transactions is recorded in the VKT via the overlay tree
- Data that transactions do not touch remains in the MPT
- Clients must maintain the overlay tree abstraction that views the two trees as overlaid
After EIP-7748
- Starting from CONVERSION_START_TIMESTAMP, a conversion step runs automatically before transaction execution in every block
- Up to CONVERSION_STRIDE conversion units (storage slots, account data, and code) are moved to the VKT per block
- Once the entire conversion is complete, the overlay tree is removed and state can be accessed using only the VKT
Who is affected
- Client teams: A conversion step must be added to apply_body, and new functions such as a conversion-progress tracking structure and trie_get_next_at_key must be implemented. The preimage resolution requirement must also satisfy one of three conditions.
- Node operators: During the conversion period, additional write operations occur in every block. Clients without a flat DB may need to download a preimage database that will be distributed before the conversion starts.
- Users and app developers: The way transactions are sent does not change. The conversion is a procedure that proceeds automatically inside the protocol.
In depth
Definition of the constants and the conversion unit
Two constants are defined, but both values are TBD. CONVERSION_START_TIMESTAMP is the timestamp at which the conversion starts, and CONVERSION_STRIDE is the maximum number of conversion units that can be converted per block. There are two kinds of conversion units: one contract storage slot, and account data (balance, nonce, code hash, etc.) together with code (if any). The rationale explains that the CONVERSION_STRIDE value is set via performance benchmarking, balancing not making the per-block additional load excessive, keeping the load manageable during a long but tolerable reorg, and finishing the conversion as quickly as possible.
The conversion step runs before transaction execution
In apply_body(...), if the block timestamp is at or after CONVERSION_START_TIMESTAMP and state._conversion_finished is false, state_convert(state, CONVERSION_STRIDE) is called. This call happens before transaction execution. According to the rationale, placing the conversion after transaction execution would require handling within-block stale cases where a transaction's writes overlap with converted key-values in the same block, whereas with the proposed ordering, staleness can only arise from writes in a previous block. This also reduces the complexity of optimizations such as performing the conversion ahead of time before the next block arrives.
The data structure that tracks conversion progress
Fields _conversion_curr_account (Optional[CurrentConvertingAccount]) and _conversion_finished (bool) are added to the State class. CurrentConvertingAccount holds an address and a phase, where phase is either StoragePhase or AccountDataPhase. StoragePhase continues the conversion from the storage slot whose key is at or above next_key, and moves on to AccountDataPhase once there is no such slot left. The new function trie_get_next_at_key(trie, key_seek) returns the first (key, value) whose trie key is at or above key_seek, along with the smallest next trie key greater than that, and is used only on tries with secured=True. The concrete implementation is left to each client's architecture. The rationale explains that processing storage first and account data afterward, in that order, dovetails with the flat DB structure of several execution clients and minimizes random disk I/O.
The state_convert algorithm and prevention of stale values
state_convert loops while n < stride and the conversion is not yet finished. For storage conversion, it uses the only_if_empty parameter newly added to set_storage, so that nothing is written if the overlay tree already has a value. This is a safeguard against overwriting a value already recorded in the VKT by a previous block's transaction with a stale MPT value. Account data is read with get_account and written back with set_account: if the data is still in the MPT, it is read from the MPT and written to the VKT, and if it is already in the VKT, the same value is written back as a no-op, so stale data is never written in either case. Code is split into chunks with chunkify_code and inserted all at once. An alternative CodePhase that would consume one unit per chunk was also considered but was not adopted in order to reduce algorithmic complexity, and it is noted that, under the current maximum code size, a single block can in the worst case exceed the CONVERSION_STRIDE limit by about 24k/31≈793 units.
Handling of EIP-7610 and EIP-161 special accounts
The 28 accounts mentioned by EIP-7610 have a nonce of 0 and no code, yet have a non-empty storage tree. Because these storage slots are unreachable, they are excluded from the conversion process. In the algorithm as well, an account with a nonce of 0 and empty code skips the storage phase and goes directly to AccountDataPhase. In addition, accounts targeted by EIP-161 are not counted toward the CONVERSION_STRIDE limit, because an EIP-158-style batch deletion is attempted on the remaining accounts. If a thousand such accounts were concentrated in a single block, it might seem risky to iterate over them without a limit, but the source explains that this is not a problem because the number of accounts to delete is only on the order of a few dozen and they are not even contiguous.
Preimage requirements and reference implementation
An execution client must satisfy at least one of the following three conditions: have a proper flat DB design that does not require preimage resolution; have a full preimage database that can look up preimages from trie keys (which may perform poorly); or download a preimage database image that will be distributed before the conversion starts. The reference implementation is on the transition-post-genesis branch of gballet's go-ethereum repository, and it works by setting --override.overlay-stride to a nonzero value on the command line.
Draft status and remaining work
This EIP is in Draft status, so its contents may still change. Both core constant values are TBD, and while there is an estimate for the expected conversion completion time, it is noted that this will need to be recalculated using the latest state size as the fork date approaches. Test cases are only noted as existing in an external document, and the security considerations section explicitly states that it needs discussion. To date there is no record of a core developer call deciding to include this EIP in a fork.