The Ethereum state is growing fast and left unchecked, chain management will only be accessible to a handful of big players. At his request, this article describes my interpretation of Alexey’s turboproof proof system, which is to be applied to several light client approaches.
The state of the Ethereum blockchain is stored as a hexary patricia tree, or trie for short. The data is stored at two levels:
- The address trie is a mapping from addresses to account data.
- A contract’s storage is also stored in a trie, which then represents a mapping from a 32-byte memory addresses to the 32–byte value stored at this address.
These trees store (key, value) pairs. Note that the keys’ base unit is the nibble (4 bits), not the byte.
The trees have 3 types of nodes:
- Leaves these are a (key suffix, value) pair, and they are always terminal nodes of the tree.
- Branch nodes these are internal nodes, and this node and all its subnodes share the same prefix. Each branch node has 17 entries. The first 16 entries correspond to the first nibble of the subnode’s key suffix. If present, the 17th entry is the value associated with the key prefix
- Extension nodes are “shortcut nodes” in case all the children share a common prefix. It is used to avoid creating a series of branch nodes, each with only one child.
As an example, the following tree has a collection of leaves, branch and extension nodes:
In practice, this model is the source of many efficiency issues in Ethereum, but it has also proven its resilience.
Some use cases require passing (key, value) tuples between users. For example, in order to save space light clients only store the root of their tree. So in order to interact with the state, the user needs to tell the light client what their share of the state looks like, so that the light client can perform operations and calculate the new root. The construction must allow for grouping several accounts into one single proof, for compression purposes.
Building on the previous example, here is the proof that both
(0x1234, 0x0000) and
(0x4567, 0x2222) are present in the tree:
Calculating the hash of the tree in figure 2 will yield the same root as the tree in figure 1, since the hashes provided in the proof have the same value as what would be provided if the tree was complete.
The question is how to serialize the data: given a list of hashes and a list of (key, value) pairs, how does one find the structure of the tree? For instance, given only the following input:
- (key, value) pairs (key and value lengths are shortened to make the resulting pictures more readable) for
- Hashes representing the subtrees.
One could reconstruct the following tree:
Or this tree:
As a result, there is a need to somehow encode structural information.
The proposal by Alexey Akhunov is still in the works, and this independent writeup is part of the effort to define it entirely. The solution presented here corresponds to the rust implementation that Sina Mahmoodi and I worked on.
A turboproof is broken into three parts:
- The list of leaves
- The list of hashes, corresponding to untouched branches of the tree
- “Structural information”, that is, a list of instructions explaining how the tree can be rebuilt using only the hashes and leaves provided.
The last part is encoded as a list of instructions for a stack machine, to be executed to reconstruct the tree:
LEAFindicates that a leaf should be popped from the proof’s sequence of leaves;
BRANCH(i)stipulates that a new branch node needs to be created, and the node that was constructed before should be stored as the ith child of the new branch node. The new node is then stored on the stack;
ADD(i)stipulates that given a branch node and any other node, the latter should be set as the ith child of the branch node. When one of the nodes isn’t a branch node, the order doesn’t matter. When both are branch nodes, the parent node will be the one that is on top of the stack;
EXTENSION(ext)stipulates that the node of top of the stack should be set as the child of an extension node (a.k.a
shortNodein geth parlance), whose prefix for the subtree is represented by the sequence of nibbles
HASHis a node that represents the hash of a subtree
Let’s suppose that the entire state consists of the following 4 (key, value) pairs:
[(0xcafecafe, 0x0303030303030303), (0xcafedeca, 0x0202020202020202), (0xdeadbee0, 0x0404040404040404), (0xdeadbeef, 0x0101010101010101)]
(For clarity, keys are shortened to 4 bytes instead of the usual 32 bytes, and values are 8 bytes long, instead of having their size unrestricted)
The tree representation of these values is as follows:
Our proof will only include keys
0xcafedeca. The two leaves that aren’t needed are hashed. The proof is then serialized as such:
- The nodes are serialized in a depth-first order:
- The hashes are also serialized in a depth-first order. There’s only one hash, representing the
- The set of instructions used to rebuild the tree:
EXTENSION([0xa, 0xf, 0xe])
The user now has the proof that they know the current state of the tree. They send it to the relayer or whoever wants to ensure that the user knows the part of the state they manage.
Reconstructing the tree
At first, the node and hash lists are received, and the stack is initialized to be empty
Let’s follow the program:
EXTENSION([0xa, 0xf, 0xe])
The program has now terminated, and the top of the stack has the final version of the tree. This tree and the tree in figure 6 have the same root hash and it is trivial to verify that both keys are present.
The Ethereum state is growing. At the time of this writing, we’re dealing with about 20 GB of state data (not including all the indices and other necessary features, which inflate this 10 fold). This is already too much for a cell phone to handle, so for the network to remain accessible be everyone, there is a need to let underpowered machines participate.
With such proofs, it is possible for a user to only store the data they are interested in, and to prove ownership when they want to interact with the blockchain. This is known as a light client.
Pushing the concept further, one can envision a “stateless” future for the main chain (independently of what happens with Serenity), where users only keep the proof of their part of the state on the blockchain, and publish these information when they need to use it. This will help stop the inflation of the state and keep Ethereum accessible to all.
There’s still work to be done in order to keep the proof sizes small and quick to process, and hopefully making the use of these more common will help.
This work would not have been possible without the input and feedback from Alexey Akhunov and Sina Mahmoodi. This version has been edited after publication, to include the remarks of JosephC and gumb0 🙇