Verkle state transition via an overlay tree

Abstract

This EIP proposes a method to switch the state tree tree format from hexary Merkle Patricia Tree (MPT) to a Verkle Tree (VKT): the MPT tree is frozen, and new writes to the state are stored in a VKT “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 VKTs offer a good mitigation strategy to stem this growth and enable weak statelessness. Owing to the difficulty of translating contracts with large storage while they are being accessed, proposals for migrating the current MPT state are complex and will require client teams to undergo a long process of refactoring their code to handle this conversion.

The bigger the state, the longer any conversion process will take. This has an impact both while the conversion is happening, as well as when full-syncing the chain if the conversion is part of consensus. Fullsync is used extensively by core dev teams to test the performance of new code. A conversion longer than a month will impact the release schedule of client teams who typically release at this rate. Nodes that cannot follow the conversion will need to wait longer to rejoin. The conversion will also make reorgs slower, so reducing its duration is desirable.

This current proposal suggests to stop the MPT state growth in its tracks by activating a new “overlay” VKT, that all new state updates are written to. The “base” MPT 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.

Whenever the block that freeze the MPT is finalized, internal node data can be deleted, in order to free up disk space.

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

Helper functions

# 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:
        basicdata = bytes(0) # Version
        basicdata += bytes(4) # Reserved
        basicdata += len(account.code).to_bytes(3, 'big')
        basicdata += account.nonce.to_bytes(8, 'big')
        basicdata += account.balance.to_bytes(16, 'big')
        tree.set(key, basicdata)
        ckkey = key
        ckkey[31] = CODEHASH_LEAF_KEY
        tree.set(ckkey, account.code_hash)

# Reads an account from the verkle tree
def verkle_get_account(tree: VerkleTree, key: Bytes32) -> Optional[Account]:
    basicdata_leaf = tree.get(key)
    if basicdata_leaf is not None:
        cs = int.from_bytes(basicdata_leaf[5:8], 'big')
        nonce = int.from_bytes(basicdata_leaf[8:16], 'big')
        balance = int.from_bytes(basicdata_leaf[16:32], 'big')
        ckkey = key
        ckkey[31] = CODEHASH_LEAF_KEY
        ck = tree.get(ckkey)
        cskey = key
        cskey[31] = CODE_SIZE_LEAF_KEY
        cs = tree.get(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:

@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:

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)

Add the following function which is used when storing a contract in the tree:

def state_set_codechunk(state: State, addr: Address, chunk_num: int, chunk: Bytes):
    state._overlay_tree.set(get_tree_key_for_code_chunk(addr, chunk_num), chunk)

Changes to the block header

At FORK_TIME the block header state root is changed from the MPT root to the VKT root.

Rationale

This approach doesn't convert the state, which is left to a subsequent EIP. This is meant as a stopgap in case we decide to push the conversion itself to a later time. It has the advantage of simplicity, which 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

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

Needs discussion.

Copyright

Copyright and related rights waived via CC0.