EIP-7748: State conversion to Verkle Tree

Abstract

This EIP proposes a procedure to convert, on each block, a fixed number of key-values from the existing Merkle Patricia Tree (MPT) to the Verkle Tree (VKT).

Motivation

The accounts state is too large to wait for transactions to organically move all of them to the VKT through the Overlay Tree. Thus, we need a strategy to convert all the state within a reasonable time. The state conversion completion allows removing the Overlay Tree abstraction introduced in EIP-7612 and use directly the VKT for all state access.

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

A conversion unit is:

• A contract storage slot.
• A contract code. (i.e. all the code is a single conversion unit)
• An account data. (e.g. balance, nonce, code-hash)

Changes to the execution spec

Include the following code in the existing apply_body(...) function:

Before executing txs, it calls block_state_conversion(...) (described below) which performs a state conversion step for this block.

In state.py, add the following code:

These new structures allows State to track where we're in the conversion process.

Modify the State class by adding the following attributes:

Define a function with the following signature:

Add or modify the following functions:

As mentioned previously, the next function is called by apply_body(...) to perform the conversion step for a block:

Rationale

State conversion step position in block execution

Performing the conversion step before the block txs execution has some benefits:

• If the state conversion step is done after txs execution, there's a possibility that txs execution writes overlap with converted key-values, having to care about them becoming stale in the same block. With the proposed ordering, they can only become stale by writes of previous blocks.
• It can reduce the complexity of optimizations, such as frontrunning the state conversion for the next block before it arrives.

CONVERSION_STRIDE proposed value

Performance benchmarks were done to achieve the right balance between:

• Don't overload the clients with too much extra work per block.
• Don't create an unmanageable load in clients during feasible long reorgs.
• Finish the conversion as fast as possible.

Account code chunking done in a single step

If an account has code, this is chunked and inserted in the VKT in one go. An alternative is including a CodePhase and let each inserted chunk consume one unit of CONVERSION_STRIDE.

We decided to not do this to reduce the algorithm complexity. Considering the current maximum code size, the wost case scenario for a block could overflow the CONVERSION_STRIDE limit by 24k/31~=793 units.

Expected time for the conversion to finish

TODO: We have an estimation, but it might be worth recalculating it closer to the proposed fork having a more up to date state size estimate.

Missed slots

The conversion logic runs at the start of each block, so missed slots don't create special situations.

Accounts storage->account-data order

The proposed order synergizes with many EL client flat-db architectures, minimizing random disk-IO.

Not counting EIP-161 accounts for CONVERSION_STRIDE limit

The CONVERSION_STRIDE parameter tries to limit the load of effective writes. These special accounts are skipped since we try to perform a bulk EIP-158 deletion of the remaining accounts.

This might sound dangerous since if there were 1k of these accounts and all corresponded to be converted in the same block, we'd be forcing the clients to iterate 1k accounts without counting any quota from CONVERSION_STRIDE. The number of remaining accounts to delete is very low (i.e.: dozen) and also not contiguous, so this shouldn't be a concern.

MPT preimage resolving

EL clients are expected to satisfy at least one of these conditions:

• They have a proper flat-db design, which doesn't require preimage resolving.
• They have a full preimage database which can resolve trie_key->preimage (but this can have poor performance).
• They have downloaded the preimage database image that will be distributed before the conversion starts.

Backwards Compatibility

No backward compatibility issues found.

Test Cases

TODO: currently described in an external document.

Reference Implementation

• transition-post-genesis branch in github.com/gballet/go-ethereum implements this when setting --override.overlay-stride to a non-zero value on the command line.

Security Considerations

Needs discussion.

Copyright

Copyright and related rights waived via CC0.