EIP-7736 Verkle tree leaf state expiry (Leaf-level state expiry in verkle trees)

No call decision · Scaling & data · EIP status Stagnant · created 2024-07-05

A simple state expiry scheme for Ethereum's Verkle tree that deletes only long-unused leaf nodes (an extension-and-suffix tree), reducing state size while allowing proofs to be issued and recovery performed when needed.

Why it is needed

Ethereum state keeps growing, increasing the burden of running a node. Earlier state expiry attempts required major structural changes such as address space extension (ASE), oil, and multiple per-epoch trees, so complexity grew quickly and progress stalled. This proposal uses a simple approach that expires only the extension-and-suffix tree, the leaf level of the verkle trie. The tree structure itself is left unchanged; only the values and sub-commitments of leaves that have not been used for a long time are deleted, and they can be revived with a simple proof when needed. The goal is to reduce state size without the complex changes that would hurt the user and developer experience.

What changes

Today

After EIP-7736

Who is affected

In depth

Constants

FORK_TIME is the fork activation time and is TBD. EPOCH_LENGTH is 15,778,800 seconds (six months), and INITIAL_EPOCH_COUNTER is 0, the epoch number ending at FORK_TIME. NUM_ACTIVE_EPOCHS is 2, the number of epochs retained without expiring at once. RESURRECT_TX_TYPE is the type ID of the resurrection transaction and is TBD.

Change to the verkle trie structure

A last_epoch field is added to the extension_and_suffix_tree function and is included in the extension node commitment calculation. When a read or write event occurs, the condition current_epoch < last_epoch + NUM_ACTIVE_EPOCHS is checked; if true, processing continues, and if false, it reverts. last_epoch is updated to the current_epoch value only when a write event is processed.

Expiry handling

At the start of block processing, check_epoch_end runs, and if the timestamp exceeds the threshold, current_epoch is incremented and schedule_expiry(current_epoch-NUM_ACTIVE_EPOCHS) is called. The actual behavior of schedule_expiry is left to the client implementation. Before expiry, the stem value and commitment C are kept as a keepsake for later use in sibling node insertion or resurrection. Actual deletion must not occur before the first block of the corresponding epoch is finalized, otherwise there must be a way to recover the data in case of a reorg.

Resurrection transaction

A resurrection transaction has the format RESURRECT_TX_TYPE|ssz(Vector[stem,last_epoch,values]). At the start of validation, resurrect_gas_cost (WITNESS_BRANCH_COST + SUBTREE_EDIT_COST + WITNESS_CHUNK_COST + CHUNK_EDIT_COST + CHUNK_FILL_COST for each value), calculated using EIP-4762 constants, is charged first. validate_subtree checks whether the commitment computed from the submitted stem, values, and last_epoch matches the stored keepsake.C, and if it matches, creates a new commitment using the current epoch value and restores the tree.

Design rationale

This approach requires no address space extension, uses a single tree instead of multiple per-epoch trees, and the resurrection proof is small since providing the data is sufficient. Gas costs are explicit, and only cold data expires while hot data remains untouched. It is also compatible with later extension to ASE or multiple trees. The exponentiation and addition operations used in the current_epoch calculation only need to be paid once per epoch, so they amortize quickly. The reason reads alone do not update last_epoch is that doing so would either raise the cost of reads to write-level cost or treat writes at read-level cost, which could increase gas fees further or create a denial-of-service (DoS) vector.

Backward compatibility

In EIP-6800, the fourth (zero-indexed) evaluation point value defaults to 0, which is the same as the INITIAL_EPOCH_COUNTER value. This EIP is therefore compatible with the existing verkle structure.

Current status and limitations

This EIP is in Stagnant status and may still change. Test cases and the reference implementation are both marked TODO, and the Security Considerations section is marked "Needs discussion," indicating that security has not yet been discussed. No decision on fork inclusion has been found in the call records.

Original EIP · ← EIPs