Ethereum core developer: MPT hexadecimal tree will be replaced

Written in front:

Imagine you are translating a 5,000-page book, and the author keeps calling you to tell you that he has made adjustments to the story, which will affect the pages you have already translated... and this may continue forever. This is a similar dilemma encountered by Ethereum in its transition from the currently used MPT hexadecimal tree to a binary tree structure. In response, Ethereum core developer Guillaume Ballet proposed a solution that can complete this conversion surgery in about a few days in 3 steps.

(Photo from: tuchong.com)

Regarding the proposal, Ethereum co-founder Vitalik commented:

“This is important research groundwork from Ballet that will make Ethereum stateless friendly while creating an opportunity to greatly simplify the protocol. Looking forward to more great work and results from Ethereum 1.x developers in the coming months.”

Here is the translation:

One of the many issues affecting Ethereum is the way account and contract data is stored, and the structure currently chosen by Ethereum is called the Merkle Patricia Tree (MPT for short). Although it makes a lot of sense in theory, in practice it creates more problems than it solves. For many years, core developers have been discussing the transition to a binary tree, and in this article, I will explain 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. This has the benefit of allowing the main chain to remain operational while the tree structure is being converted, and also ensures that all accounts are converted to the binary tree format.

background

Currently, Ethereum accounts are stored in a hexadecimal tree. Hexadecimal means that a node has 16 child nodes, which is good in theory because it means you need fewer "stages" to store all your data.

For example, this is how you represent a key-value pair (170, v) in a hexadecimal tree. In hexadecimal, 170 is represented as 0xaa, so you only need two levels: one for the first a and another for the second a.

Figure 1: This is an example of a hexadecimal trie showing how the value "v" is stored at key 0xaa. This tree has only 2-byte long keys, and only the subtree along the 0xaa key is expanded. For brevity, irrelevant subtrees are replaced with "...".

Notice that this tree is shallow and wide. Then compare it to the following binary tree representation of the same key and value pairs. In binary, 170 is represented as 10101010.

Figure 2: The same key-value pairs as in Figure 1, stored as a binary tree. For brevity, unrelated subtrees are represented as “…”.

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

In Ethereum, each block contains a stateRoot field, which is the hash of the MPT root. In summary, this hash is obtained by hashing the hash list of the root's 16 children. Each of these child hash lists is in turn the hash of its child hash 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 the new block is then sealed.

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

Here comes the problem: recalculating the hash root by hashing all the nodes takes too long, so to calculate the root node, the miner retrieves the sibling hash from the database. Although it doesn't take much time to get all the sub-leaves 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 hex tree, you typically fetch 15 sibling hashes per stage. In the example above, that's 30 hashes.

Even going deeper, a binary tree only needs one sibling hash per stage. In the example above, that's only 8 hashes! This is why binary trees are actually better in practice.

Covering transformation method

Unfortunately, switching Ethereum from a hexadecimal tree to a binary tree is not an easy task. There is a lot of data to convert, and it takes more than 15 seconds of block time to perform the change.

Beyond that, imagine you’re translating a 5,000-page book, and the author keeps calling to tell you he’s made a tweak to the story that will affect the pages you’ve already translated… and this could go on and on.

This is the problem Ethereum currently has, because users can update addresses that have already been converted, which means you have to start the conversion process all over again.

The proposed solution to this problem is to have a transition period during which an overlay binary tree is placed on top of the hexadecimal tree, which serves to store all changes to the state until the base tree is converted to a binary tree.

This transition will take place in three steps:

Step 1 - Convert

In this approach, it is determined that at block height H1, the block has two stateRoots: one for the "base" hexadecimal tree and one for the "cover" binary tree.

Figure 4: During the transition, a block has 2 state roots: one is the read-only root of the traditional hexadecimal tree, and the second is the root of the "overlay" binary tree.

The hex tree is 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 is not found there, the system searches the old hexadecimal tree for the value.

Meanwhile, the hex tree is being converted in the background. Now you don't have to worry about insertions, because all changes are stored in the top tree.

Step 2 - Basis Conversion

Once the background conversion process is complete, miners will announce that they are ready to switch by replacing the read-only hextree base root with the conversion result. Reading and writing state is the same as in step 1.

Figure 5: In the second phase of the conversion, block headers replace their hexadecimal base roots with their binary conversion base roots to signal to the network that they are ready.

When a large enough sequence of blocks has the same value for the converted base root, it means that most miners have completed the conversion and reached a consensus on what the converted tree should look like. Next, it enters the merging process.

Step 3 - Merge the two trees

The merging process happens gradually: every time a new block is generated, n keys are removed from the overlay and reinserted into the base tree. This process continues until all keys are removed from the overlay. At this stage, the overlay state root is removed from the block header.

In addition to this, if a transaction performs a write to a key found in the overlay tree, the key is removed from the overlay tree and written directly to the base tree.

Next step

We have created a preliminary prototype in order to estimate the time it will take to complete the conversion. We believe that the entire process can be completed in a reasonable amount of time (on the order of a few days). I will release more details as the algorithm improves.

Acknowledgements

This proposal benefited from valuable comments from 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