Trie format transition with overlay trees

Simple Summary

This EIP proposes a method to convert the state trie format from hexary to binary: new values are directly stored in a binary trie “laid over” the hexary trie. Meanwhile, the hexary trie is converted to a binary trie in the background. When the process is finished, both layers are merged.

Abstract

This EIP describes a four phase process to complete the conversion.

• In the first phase, all new state writes are made to an overlay binary trie, while the hexary trie is being converted to binary. The block format is changed to have two storage roots: the root of the hexary trie (hereafter called the "base" trie) and the root of the overlay binary trie.
• After enough time has been given to miners to perform the conversion, the second phase begins. The overlay tree is progressively merged back into the newly converted binary base trie. A constant number of entries are deleted from the overlay and inserted into the base trie.
• The third and final phase begins when the overlay trie is empty. The field holding its root is removed from the block header.

Motivation

There is a long running interest in switching the state trie from a hexary format to a binary format, for reasons pertaining to proof and storage sizes. The conversion process poses a catch-up issue, caused by the sheer size of the full state: it can not be translated in a reasonable time (i.e. on the same order of magnitude as the block time).

Specification

This specification follows the notation introduced by the Yellow Paper. Prior to reading it is advisable to be familiar with the Yellow Paper.

Binary tries

This EIP assumes that a binary trie is defined like the MPT, except that:

• The series of bytes in I₀ is seen as a series of bits and so ∀i≤256, I₀[i] is the ith bit in key I₀
• The first item of an extension or a leaf is replacing nibbles with bits;
• A branch is a 2 item structure in which both items correspond to each of the two possible bit values for the keys at this point in their traversal;
• c(𝕴,i) ≡ RLP((u(0), u(1)) at a branch, where u(j) = n({I : I ∈ 𝕴 ⋀ I₀[i] = j}, i+1)

Let ß be the function that, given a hexary trie, computes the equivalent representation of that trie in the aforementioned binary trie format.

Phase 1

Let h₁ be the previously agreed-upon block height at which phase 1 starts, and h₂ the block at which phase 2 starts. For each block of height h₁ ≤ h < h₂:

0. A conversion process is started in the background, to turn the hexary trie into its binary equivalent. The end goal of this process is the calculation of the root hash of the converted binary trie, denoted Hᵣ². The root of the hexary trie is hereafter called Hᵣ¹⁶. Formally, this process is written as Hᵣ² ≡ ß(Hᵣ¹⁶).
1. Block headers contain a new Hₒ field, which is the root of the overlay binary trie;
2. Hᵣ ≡ P(H)ᵣ¹⁶, i.e. as long as the conversion from hexary to binary is not complete, the hexary trie root is the same as that of its parent block.

The following is changed in the execution environment:

• Upon executing a state read, ϒ first searches for the address in the overlay trie. If the key can not be found there, ϒ then searches the base trie as it did at block heights h' < h₁;
• Upon executing a state write, ϒ inserts or updates the value into the overlay tree. The base tree is left untouched;
• If an account is deleted, ϒ inserts the empty hash H(∅) at the address of that account in order to mark its deletion; reads from such an address behave the same as a missing account, regardless of what is present in the base trie.

Phase 1 ends at block height h₂, which is set far enough from h₁ to offer miners enough time to perform the conversion.

Phase 2

This phase differs from the previous one on the following points:

• At block height h₂, before the execution of ϒ, Hᵣ ≡ Hᵣ², i.e. the value before the execution of the transition function is set to the root of the converted binary base trie;
• Hₒ is still present in the block tree, however the overlay trie content can only be read from or deleted;
• At block height h ≥ h₂, before the execution of ϒ, N accounts are being deleted from the binary overlay trie and inserted into the binary base trie;
• Upon executing a state write, ϒ will insert or update the value into the base trie. If the search key exists in the overlay trie, it is deleted.

Account deletion is performed according to the following rules:

• The first N accounts (in lexicographic order) remaining in the overlay tree are selected; For each of these accounts:
• If the value is the empty hash, remove the account at the same address from the binary base trie;
• Otherwise, insert/update the account at the corresponding address in the base trie with its overlay trie value.

When the overlay trie is empty, phase 2 ends and phase 3 begins.

Phase 3

Phase 3 is the same as phase 2, except for the following change:

• Hₒ is dropped from the block header

Rationale

Methods that have been discussed until now include a "stop the world" approach, in which the chain is stopped for the significant amount of time that is required by the conversion, and a "copy on write" approach, in which branches are converted upon being accessed. The approach suggested here has the advantage that the chain continues to operate normally during the conversion process, and that the tree is fully converted to a binary format, in a predictable time.

Backwards Compatibility

This requires a fork and will break backwards compatibility, as the hashes and block formats will necessarily be different. This will cause a fork in clients that don't implement the overlay tree, and those that do not accept the new binary root. No mitigation is proposed, as this is a hard fork.

Test Cases

• For testing phase 1, it suffices to check that every key in the hexary trie is also available in the binary trie. A looser but faster test picks 1% of keys in the hexary trie at random, and checks that they are present in the binary trie;
• TBD for phase 2 & 3

Implementation

A prototype version of the conversion process (phase 1) is available for geth in this PR.

Security Considerations

There are three attack vectors that I can foresee:

• A targeted attack that would cause the overlay trie to be unreasonably large. Since gas costs will likely increase during the transition process, lengthening phase 2 will make Ethereum more expensive during an extended period of time. This could be solved by increasing the cost of SSTORE during phase 1.
• Conversely, if h₂ comes too soon, a majority of miners might not be able to produce the correct value for Hᵣ² in time.
• If a group of miners representing more than 51% of the network are reporting an invalid value, they could be stealing funds without anyone having a say.

Community feedback

• Preliminary tests indicate that a fast machine can perform the conversion in roughly 30 minutes.
• The initial version of this EIP expected miners to vote on the value of the binary base root. This has been removed because of the complexity of this process, and because this functionality is already guaranteed by the "longest chain" rule.

Copyright

Copyright and related rights waived via CC0.