EIP-2584 Transition to a trie based on an overlay tree (Trie format transition with overlay trees)

No call decision · Scaling & data · EIP status Stagnant · created 2020-04-03

Proposes a four-phase transition method for converting the hexary state trie into a binary trie, in which new values are written to a temporary overlay trie while the existing trie is converted in the background and then merged.

Why it is needed

Ethereum stores its state as a hexary Merkle Patricia Trie (MPT), and there has long been discussion of converting it to a binary trie to reduce proof size and storage size. The problem is that the total amount of state is too large to convert all at once within a time comparable to a block production interval. A 'full stop' approach that halts the chain to convert, or a 'copy on write' approach that converts a branch on the spot whenever its address is accessed, have both been discussed, but each has issues with availability or unpredictability, respectively. This EIP presents a method for converting the entire trie to binary format within a predictable time, while the chain keeps operating normally without stopping.

What changes

Today

After EIP-2584

Who is affected

In depth

Why the overlay approach

The methods discussed so far were the 'full stop' approach and the 'copy on write' approach. The full stop approach requires halting the chain for the long duration needed for conversion, while the copy-on-write approach converts branches only as they are accessed, making the completion time unpredictable. This EIP explains that its overlay approach has the advantage that the chain keeps operating normally while the entire trie is fully converted to binary format within a predictable time.

Definition of the binary trie

In this EIP, the binary trie is the same as an MPT except for the following. The byte sequence of a key I₀ is treated bit by bit, so that I₀[i] is the i-th bit, and the first element of an extension or leaf entry is expressed as a bit rather than a nibble. A branch consists of two entries, each corresponding to one of the two possible bit values (0 or 1) of the key at that point. Formally, c(𝕴,i) ≡ RLP((u(0), u(1)), where u(j) is computed recursively at i+1 over the set of I's for which I₀[i]=j. The function that converts a hexary trie into this format is denoted ß.

Phase 1: overlay writes and background conversion

From h₁ until before h₂, an overlay binary trie root Hₒ is added to the block header. The work of converting the hexary trie to binary begins in the background, with the goal of computing Hᵣ² ≡ ß(Hᵣ¹⁶). While conversion is incomplete, Hᵣ stays the same as the parent block. State reads first check the overlay trie and fall back to the existing base trie if not found there. State writes are recorded only in the overlay, leaving the base trie untouched. When an account is deleted, an empty hash H(∅) is recorded at that address to mark the deletion, and any subsequent read of that address is treated as having no account, regardless of the base trie's contents. h₂ is set with enough time for miners to finish the conversion.

Phase 2: incremental merging

At h₂, before ϒ executes, Hᵣ is replaced with Hᵣ² (the converted binary base trie root). The Hₒ field remains in the header, but the overlay contents can only be read or deleted. For every block with h≥h₂, before ϒ executes, the N accounts earliest in lexicographic order are selected from the overlay; if their value is an empty hash, the corresponding account is deleted from the base trie, otherwise the base trie is inserted or updated with that value. State writes in this phase go directly into the base trie, and if the same key remains in the overlay, it is deleted from the overlay. Once the overlay is empty, phase 2 ends and phase 3 begins.

Phase 3: transition complete

Phase 3 behaves the same as phase 2, except that the Hₒ field is removed entirely from the block header. With this, the trie is unified entirely into a single binary format.

Security considerations

The original text points out three possible attacks. First, a specific attack could make the overlay trie abnormally large, prolonging the period of elevated gas costs during the transition; this can be mitigated by raising the SSTORE cost during phase 1. Second, if h₂ arrives too early, a majority of miners may fail to produce the correct Hᵣ² value in time. Third, if a group of miners controlling more than 51% of the network reports an incorrect value, there is a risk that funds could be stolen with no one able to raise an objection.

Forking and current status

This change requires a hard fork because it alters the header format and hash values, and clients that do not implement the overlay tree or do not accept the new binary root will fork off. The original text proposes no separate mitigation for this. Community feedback included preliminary test results showing the conversion work takes about 30 minutes on a fast machine, and an earlier version's procedure for 'miners voting on the binary base root value' was removed due to complexity concerns and because the 'longest chain' rule already guarantees the same property. The original status of this EIP is Stagnant.

Original EIP · ← EIPs