Ethereum core developer: MPT hex tree will be replaced

Write in front:

Imagine that you are translating a 5000-page book. The author keeps calling to tell you that he has adjusted the story. This will affect the pages you have translated … and this may continue forever. This is Ethereum. A similar dilemma encountered in the transition from the currently used MPT hex tree to the binary tree structure. In this regard, Ethereum core developer Guillaume Ballet proposed a solution that can complete this conversion operation in 3 steps in about a few days.

(Picture from: tuchong.com)

• BKS officially logs in LBANK! Airdrop candy show!
• KPMG 2019 Global Fintech Pulse Report: Blockchain is still a key investment area, large companies and governments have already acted
• The annual salary is as high as that of Goldman Sachs. The screen launches a battle to grab people. The first blockchain cloud recruitment will ignite "Golden Three Silver Four"

Regarding the proposal, vitalik, co-founder of Ethereum commented:

"An important research foundation from Ballet, which will make Ethereum stateless friendly, while creating an opportunity to greatly simplify the protocol. Looking forward to better developers from Ethereum 1.x in the coming months Work and results. "

Here is the translation:

One of the many issues affecting Ethereum is the way in which account and contract data is stored. The structure currently chosen by Ethereum is called the Merkle Patricia Tree (MPT). Although theoretically it makes sense, in practice it brings more problems than it solves. Core developers have been discussing the transition to a binary tree for many years, and in this article I will clarify my views on this issue and then give a solution to it.

The proposed process introduces a transition period during which both tree structures will exist. The advantage of this is that the main chain can keep running when the tree structure is transformed, and it can also ensure that all accounts are converted to the binary tree format.

background

Currently, Ethereum's account is stored in a hex tree. The so-called sixteen fork means that a node has 16 children, which is theoretically very good, because it means that you need fewer "stages" to store all your data.

For example, this is the process of representing the key-value pair （170，v） in the form of a hex tree. In hexadecimal, 170 represented as 0xaa , so you only need two layers: one for the first a and the other for the second a .

Figure 1: This is an example of a hex trie tree showing how the value " v " is stored at the key 0xaa . This tree is only 2 bytes long and is only expanded along the subtree of the 0xaa key. For brevity, unrelated subtrees are replaced with "…".

Note that this tree is very shallow and wide. It is then compared to the following binary tree representation of the same key and value pairs. In binary, 170 represented as 10101010 .

Figure 2: The same key-value pairs as in Figure 1, stored as a binary tree. For brevity, irrelevant subtrees are denoted as "…".

You can see that this tree is much deeper and much narrower.

In stateRoot , each block contains a stateRoot field, which is a hash of the MPT root. All in all, this hash is obtained by hashing the hash list of the 16 children of the root. Each of these subhash columns, in turn, is a hash of its subhash list, and so on.

Every time a new block is generated, the miner updates the account tree and recalculates its root hash. The hash is stored in the stateRoot field of the new block, and then the new block is sealed.

Figure 3 The state root field in the block header points to the root of the hex tree.

The problem is here: it takes too long to recalculate the hash root by hashing all nodes. Therefore, in order to calculate the root node, the miner will retrieve the sibling hash from the database. Although it takes little time to get all the cotyledons from the database and hash the entire tree, this operation still takes a lot of time. This is because each hash must be obtained from the database.

In a hexadecimal tree, 15 sibling hashes are usually obtained at each stage. In the example above, this is 30 hashes.

Even deeper, a binary tree requires only one sibling hash at each stage. In the example above, there are only 8 hashes! This is why binary trees are actually better in practice.

Cover conversion

Unfortunately, switching Ethereum from a hex tree to a binary tree is not an easy task. There is a lot of data that needs to be converted and it takes more than 15 seconds to perform the changes .

In addition, imagine that you are translating a 5000-page book, and the author keeps calling to tell you that he has made adjustments to the story, which will affect the pages you have translated … and this may continue forever .

This is the current problem with Ethereum, because users can update the converted address, which means you have to restart the conversion process.

The suggestion to solve this problem is to set a transition period, during which a covering binary tree is placed on top of the hexadecimal tree, and its role is to save all changes in the state until the base tree is converted to a binary tree.

This transition occurs in three steps:

Step 1-conversion

In this method, it is determined that at block height H1 , the block has two stateRoot s: one for the "base" hex tree and one for "covering" the binary tree.

Figure 4: During the conversion process, the block has two state roots: one is the read-only root of a traditional hex tree, and the second is the root that "covers" the binary tree.

Hex trees are considered read-only, so any update to the state will be an update to the overlay tree.

When a transaction reads or updates an account, the system first searches the overlay tree. If the account cannot be found there, the system searches for the value in the old hex tree.

At the same time, the hex tree is transitioning in the background. Don't worry about inserts now, as all changes are stored in the top tree.

Step 2-base conversion

After the background conversion process is complete, miners will announce that they are ready to switch by replacing the read-only hex-tree base root with the conversion results. The read and write operations to the status are the same as in step 1.

Figure 5: In the second phase of the transformation, the block header replaces the hexadecimal tree root with its binary tree transformation root to send a signal to the network that they are ready.

When a sufficiently large sequence block has the same value for the transformed root, this means that most miners have completed the transformation and reached a consensus on the appearance of the transformed tree. Next, you will enter the merge process.

Step 3-merge the two trees

The merging process will proceed gradually: each time a new block is generated, n keys are removed from the overlay and then re-inserted into the base tree. This process continues until all keys are removed from the overlay. At this stage, the covering state root is removed from the block header.

In addition to this, if a transaction execution writes to a key found in the overlay tree, that key will be removed from the overlay tree and written directly to the underlying tree.

Next step

We have created a preliminary prototype to estimate the time required to complete the conversion. We believe that the entire process can be completed in a reasonable time (about a few days). As the algorithm improves, I will post more details.

Thanks

This proposal benefited from the valuable input provided by Alexey Akhunov, Vitalik Buterin, Anna George, Sina Mahmoodi, Tomasz Stanczak and Martin H. Swende.

Related discussion: https://ethresear.ch/t/overlay-method-for-hex-bin-tree-conversion/7104

We will continue to update Blocking; if you have any questions or suggestions, please contact us!