Change the format of the Ethereum state tree using an overlay

Editor's Note: This article comes fromEthereum enthusiasts (ID: ethfans)Editor's Note: This article comes from

Ethereum enthusiasts (ID: ethfans)

The way accounts and contracts store data is one of many issues affecting Ethereum. The Ethereum protocol uses Merkle Patricia Tree (MPT, Merkle Patricia Tree) to organize account and contract data. While this data structure works well in theory, in practice it creates more problems than it solves. The core developers have been discussing for years that they want to replace this data structure with a binary tree. In this article, I will explain my views on this problem and how to achieve this conversion.

background

My proposed approach involves a transition period during which the network maintains both tree structures. The advantage of this is that the process of converting the tree structure will not affect the operation of the chain, and it can ensure that all accounts are converted into binary format.

background

Currently, Ethereum's state tree is hexadecimal. Hex means that each node has 16 child nodes. In theory, this is fine, because having more children means fewer "levels" (ie tree heights) are needed to store all the data.

image description

- Figure 1. Example of a hex tree showing how the value v is stored at the corresponding key 0xaa. The key length of this tree is only 2 bytes, and only the subtree along 0xaa is represented. For brevity, irrelevant subtrees are replaced by "..." −

It can be seen that the tree in the picture above is very short and wide. Given the same key-value pair, the following figure shows the situation of binary tree storage. 170 is represented as 10101010 in a binary tree.

image description

As can be seen from the figure, the binary tree is much deeper and narrower.

In Ethereum, each block contains a stateRoot field, which is the root hash value of the MPT representing the global state of Ethereum after the block is processed. In general, this hash value is obtained by hashing the list of hash values ​​of the root node's 16 child nodes. The hash values ​​of these child nodes are obtained by hashing the list of the child's 16 child node hash values, and so on.

Every time a packaged transaction generates a new block, the miner will update the account tree and recalculate the root hash. The root hash is stored in the stateRoot field of the new block, and then the new block is consensused.

image description

Here's the problem: recalculating the root hash would take too long if all nodes were to be hashed, so to compute the hash of the root node, the miner would retrieve sibling hashes from the database (sibling hashes). Although the latter (miners retrieve sibling hashes from the database) does not take as much time as the former (miners get all leaf nodes from the database and hash them), this operation is still time-consuming. Because each hash has to be fetched from the database.

In a hex tree, you usually need to take out 15 sibling hash values ​​at each level. In the example I constructed above (Figure 1), (recomputing the root hash) would require 30 hashes.

Although the binary tree is a bit deeper, only one sibling hash is needed at each level. In the above example (Figure 2), only 8 hashes are needed! That's why binary trees are better in practice.

first level title

Unfortunately, converting to a binary tree is not trivial. There is so much data to convert that it will take more than the 15 second block generation time to perform the conversion.

Besides, imagine you are translating a 5000 page book and the authors keep telling you that they have made some changes to the story and these changes affect the pages you have already translated...then the process is endless up. Converting the format of the state tree is the same problem: maybe you have just completed the format conversion of an address, and the user uses the address (thus updating the state of the address), then you have to convert it again from the beginning (because the state of an address Updates also affect the entire state tree).

secondary title

Step 1 - Conversion

Under this method, when the block height is H1, there must be two state roots: one is the "basic layer" hexadecimal state root, and the other is the "overlay layer" binary tree state root.

image description

The hex tree is made read-only, so any updates to the state will be made on the overlay tree.

When a transaction reads or updates an account, the system first searches the overlay tree. If the account is not found in the overlay tree, then the old hex tree will be searched for the value.

secondary title

Step 2 - Base Tree Switching

image description

- Figure 5. In the second stage of conversion, miners replace the hexadecimal root with the root of the converted binary tree in the block header, signaling to the network that they are ready -

When enough series of blocks give the same value to the root of the converted binary base tree, it means that most miners have completed the conversion and approve the converted tree. The merging process then begins. (Translator's Note: The merge at this time is for the read-only binary base tree and the read-write binary cover tree)

The merging process proceeds continuously: every time a new block is generated, n keys are removed from the overlay tree and reinserted into the binary base tree. This process continues until all keys have been removed from the overlay tree. When this step is reached, the block header no longer holds the root of the overlay state tree.

Next step

secondary title

Next step