--- title: State storage transition using an overlay tree description: Describes the use of an overlay tree to use the verkle tree structure, while leaving the historical state untouched. author: Guillaume Ballet (@gballet), Ansgar Dietrichs (@), Ignacio Hagopian (@jsign), Gottfried Herold (@GottfriedHerold), Jamie (@), Tanishq Jasoria (@tanishqjasoria), Parithosh Jayanthi (@parithosh), Gabriel Rocheleau (@gabrocheleau), Karim Taam (@matkt) discussions-to: <URL> status: Draft type: Standards Track category: Core created: 2024-01-25 requires: 4762, 6800, 7545 --- ## Abstract This EIP proposes a method to switch the state tree tree format from hexary MPT to a verkle tree: the MPT tree is frozen, and new writes to the state are stored in a verkle tree “laid over” the hexary MPT. The historical MPT state is left untouched and its eventual migration is handled at a later time. ## Motivation The Ethereum state is growing, and verkle trees offer a good mitigation strategy to stem this growth and enable weak statelessness. Proposals for migrating the current MPT state are however complex and will require client teams to undergo a long process of refactoring their code to be able to handle this conversion. Meanwhile, the state keeps growing, which makes the conversion process, whatever it is, much longer. This current proposal suggests to stop the MPT state growth in its tracks by activating a new "overlay" verkle tree, that all new state updates are written to. The "base" MPT tree is frozen in place, until all execution clients are ready to perform the full transition. Data is read first from the overlay tree, and if not found there, from the MPT. The MPT being frozen, internal node data can be deleted as soon as the merkle block reaches finalization. ## Specification The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 and RFC 8174. ### Constants |Parameter|value|Description| |-|-|-| |`FORK_TIME`|`TDB`|Time at which the verkle, overlay tree is activated.| ### Helper functions ```python3 # Determine if `block` is the fork activation block def is_fork_block(block): return block.parent.timestamp < FORK_TIME && block.timestamp >= FORK_TIME # Write an account in the verkle tree def verkle_set_account(tree: VerkleTree, key: Bytes32, account: Optional[Account]): if account is not None: versionkey = key tree.set(versionkey, 0) balancekey = key balancekey[31] = BALANCE_LEAF_KEY tree.set(balancekey, account.balance) noncekey = key noncekey[31] = NONCE_LEAF_KEY tree.set(noncekey, account.nonce) ckkey = key ckkey[31] = CODE_KECCAK_LEAF_KEY tree.set(ckkey, account.code_hash) cskey = key cskey[31] = CODE_SIZE_LEAF_KEY tree.set(cskey, len(account.code)) # Reads an account from the verkle tree def verkle_get_account(tree: VerkleTree, key: Bytes32) -> Optional[Account]: version_leaf = tree.get(key) if version_leaf is not None: balancekey = key balancekey[31] = BALANCE_LEAF_KEY balance = tree.get(balancekey, account.balance) noncekey = key noncekey[31] = NONCE_LEAF_KEY nonce = tree.get(noncekey) ckkey = key ckkey[31] = CODE_KECCAK_LEAF_KEY ck = tree.get(ckkey) cskey = key cskey[31] = CODE_SIZE_LEAF_KEY cs = tree.set(cskey) account = Account(0, balance, nonce, ck, cs) return account ``` ### Changes to the execution spec: In the execution spec, modify the `State` class as such: ```python3 @dataclass class State: """ Contains all information that is preserved between transactions. """ _main_trie: Trie[Address, Optional[Account]] = field( default_factory=lambda: Trie(secured=True, default=None) ) _storage_tries: Dict[Address, Trie[Bytes, U256]] = field( default_factory=dict ) _snapshots: List[ Tuple[ Trie[Address, Optional[Account]], Dict[Address, Trie[Bytes, U256]] ] ] = field(default_factory=list) _created_accounts: Set[Address] = field(default_factory=set) # Added in this EIP _overlay_tree: VerkleTree[Address, Bytes32] ``` And the state access functions are modified as such: ```python3 def get_account_optional(state: State, address: Address) -> Optional[Account]: account = verkle_get_account(state._overlay_tree, get_tree_key_for_version(addr)) if account is not None: return account return trie_get(state._main_trie, address) def set_account(state: State, address: Address, account: Optional[Account]) -> None: verkle_set_account(state._overlay_tree, get_tree_key_for_nonce(addr), account) def get_storage(state: State, address: Address, key: Bytes) -> U256: value = state._overlay_tree.get(get_tree_key_for_storage_slot(addr, slot)) if value is not None: return value trie = state._storage_tries.get(address) if trie is None: return U256(0) value = trie_get(trie, key) assert isinstance(value, U256) return value def set_storage( state: State, address: Address, key: Bytes, value: U256 ) -> None: state._overlay_tree.set(get_tree_key_for_storage_slot(addr, slot), value) ``` ## Rationale This method has the advantage of simplicity, compared to other methods, and its reduced complexity means that the verge fork could happen at the same time as other, simpler EIPs. It also requires no change at the consensus layer. ## Backwards Compatibility No backward compatibility issues found. ## Test Cases <!-- This section is optional for non-Core EIPs. The Test Cases section should include expected input/output pairs, but may include a succinct set of executable tests. It should not include project build files. No new requirements may be be introduced here (meaning an implementation following only the Specification section should pass all tests here.) If the test suite is too large to reasonably be included inline, then consider adding it as one or more files in `../assets/eip-####/`. External links will not be allowed TODO: Remove this comment before submitting --> ## Reference Implementation * `transition-post-genesis` branch in `github.com/gballet/go-ethereum` implements this when setting `--override.overlay-stride=0` on the command line. ## Security Considerations <!-- All EIPs must contain a section that discusses the security implications/considerations relevant to the proposed change. Include information that might be important for security discussions, surfaces risks and can be used throughout the life cycle of the proposal. For example, include security-relevant design decisions, concerns, important discussions, implementation-specific guidance and pitfalls, an outline of threats and risks and how they are being addressed. EIP submissions missing the "Security Considerations" section will be rejected. An EIP cannot proceed to status "Final" without a Security Considerations discussion deemed sufficient by the reviewers. The current placeholder is acceptable for a draft. TODO: Remove this comment before submitting --> Needs discussion. ## Copyright Copyright and related rights waived via [CC0](../LICENSE.md).