header-langage
简体中文
繁體中文
English
Tiếng Việt
Scan to Download the APP
Partnered With:

Stateless ethereum: binary state tree experiment

Read this article in 10 Minutes
A number of ideas have been proposed to reduce the size of witness data, one of which is to convert ethereum's merkeltree from hexadecimal to binary.

Title: stateless ethereum: the binary state tree experiment
Source: ethereum fan & black cake;
By Igor Mandrigin

The data and scripts used in this article are housed in the github repository:
https://github.com/mandrigin/ethereum-mainnet-bin-tries-data

What is "stateless ethereum"?


If you already know what "stateless ethereum" and "block witness data" are, you can skip this section.


To execute transactions and validate blocks, nodes in the ethereum network need to know the current state of the entire blockchain -- that is, the balances and stored data of all accounts and contracts. This data is typically stored in a DB (database file) and is only loaded into a merckle tree when needed for validation.

The stateless ethereum client works in a slightly different way. As the name implies, a stateless client is one that does not use the hard disk DB to execute a block (although the client may also maintain full state). Instead, stateless clients rely on "block witness" -- a particular piece of data that is propagated with the corresponding block; With this data, the client can recreate a (partial state) merckle subtree that can be used to execute all transactions in the block.

You can read about in this article a stateless client further description: https://blog.ethereum.org/2019/12/30/eth1x-files-state-of-stateless-ethereum/

Of course, the need to propagate block witness data means that the network of stateless clients is more demanding than normal nodes.

1
- witness data size polyline chart (block height: 5 million to 8.5 million) -

Many ideas have been proposed for reducing the size of the witness data: using validity/computational integrity proofs (including but not limited to zero knowledge proofs), adding more compression methods, and so on. One way to do this is to change ethereum's merkell tree (the merkell tree used to represent ethereum) from hexadecimal to binary.
This is the problem that this article wants to discuss.

Why use binary trees


One of the nice things about merckle trees is that verifying the root value (which is just a hash value) doesn't require you to have all the data for the tree. Just replace all the omitted non-empty paths with corresponding hash values.


So what's wrong with using a hexadecimal merckle tree?

Imagine that the entire tree is filled with data (that is, the nodes in the tree have almost no zero children). To validate a block, we need only a small amount of data from the merckle tree nodes. So, we can just replace the data of the other path with the hash value.

However, each additional hash is added to make the block witness larger.

This problem can be alleviated if we switch to a binary merckle tree -- since each node in the merckle tree has only two children, at most one byte point needs to be replaced by a hash value. (in other words, we can start "cutting" the path of the merckle tree much earlier because we have a grain size of 1 bit instead of 4 bits in hexadecimal.)

Doing so might drastically reduce the size of the witness data.

Let's do another example.

Assume that executing a block affects only one account: Acc1 (binary 0011 1011) under path 3B. The whole tree is full (no nodes on the tree have zero children).

2

3

- comparison of binary and hexadecimal state trees -

If the binary tree looks a little scary, it's only because I've drawn all the binary trees, but I haven't drawn all the nodes in the hexadecimal tree that are hashed instead.
Let's count the Numbers:

To create a binary state tree, the witness data needs to contain eight hash values, seven branch nodes, and one account node. That's 16 elements in your data.
To create a hexadecimal state tree, we only need one branch node, one account node, but we need 30 hashes. So we have 32 elements.


So, assuming that the hash and the branch nodes take up the same amount of space in the block witness data (the hash actually takes up a little more space), in our case, the size of the witness required to use a binary tree is only half that in hexadecimal. It looks good.


Well, that's the theory.

Let's see what happens. Let's take a look at the data from ethereum's main network.

Start the experiment


First things first: how do we know that our block witness data is useful?


The test is as follows: we use block witness data to generate a merckle subtree, run all transactions in the corresponding block on the tree, and verify that the results are consistent with what we know. As long as they have the same traces, we can conclude that this testimony is sufficient.

4

- test methods: 1. Execution block; 2. Extract the witness data from the state tree; 3. Construct a subtree with the witness data; 4. Disable DB access and use subtrees to execute blocks (see github for details)


Second, we need some baseline data. So, we also generated the witness data in hexadecimal merker-tree mode using blocks of 5 million to 8.5 million in height, and stored the witness size statistics in a super large CSV file.


The first step we tried was to assemble a hexadecimal tree after executing a block, turn it into a binary tree, and extract the witness data from the binary tree.

This approach has several advantages: it is easy to implement, and it is easy to verify the hexadecimal - binary conversion.

But we had two problems, and one of them was not small.

First, as we proved above, a hexadecimal tree contains more account nodes than a binary tree, and if we convert it to a hexadecimal tree, we get a different result than if we generate the witness directly in binary tree mode.

Why?

Because hexadecimal tree data always grows at the rate of 1/2 byte, and binary trees always grow at the rate of 1 bit, the length of keys can be odd bits.

In fact, the witness data contains some additional EXTENSION nodes that are slightly larger. But even for the more substantial blocks, which contain about 5,000 transactions, the difference in the size of the witness data is very small (less than 5 per cent).

The key is performance. As the tree grows in size, the rate of conversion slows down.

To put it in more concrete terms: on our Google Compute Engine virtual machine, the processing rate is about 0.16 blocks per second, which is less than 10 blocks per minute, and it takes more than three months to process a million blocks!

So we decided to take a more sophisticated approach and develop an experimental branch that USES binary merckle trees natively. In other words, we will replace all the hexadecimal state trees in the turbo-geth code base with binary trees, and then the blocks will be executed based on binary trees.

The downside of this approach is that some of the hash checks can only be ignored (block root hash, sometimes the account stores the root hash, because our block chain snapshot mechanism is lacking).

But the main verification mechanism remains the same: we need to be able to use binary trees to execute blocks and create merckle subtrees from the witness data.

Let's talk about key.

For simplicity's sake, the way we encode key is very inefficient: 1 byte per nibble; Each bit of a key takes up one byte. This greatly simplifies changes at the code level, but the "key" portion of block witness data is eight times larger than when we use bitset.

Therefore, in further analysis, I will assume that key is encoded optimally (using 1 bit to encode 1 bit of information).

Hex vs. Bin: results


My analysis was divided into two segments, analyzing a total of 2 million blocks on ethereum's main network.


Block heights range from 5 million to 6.5 million
I in this lot repository provides use python scripts to repeat this experiment of the command line: https://github.com/mandrigin/ethereum-mainnet-bin-tries-data

First, let's analyze the data set.

python percentile.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust

5

- a box diagram showing the data between the upper quartile and the lower quartile, and the line extending from left to right showing the data between 1% and the lower 1% (i.e. excluding the extreme and extremely small 1%)



Now we can generate some cool charts!

python xy-scatter-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust

6

-xy scatter plot (assuming key is encoded in the optimal way) (the horizontal axis is the size of the witness data under Hex, and the vertical axis is the size of the witness data under Bin) -

As you can see, the binary witness is always larger than the witness under the hexadecimal tree.
Let's add another parameter, the binary witness size divided by the hexadecimal witness size, and see how much we've improved.

python size-improvements-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust

7

- size of binary witness/hexadecimal witness (the smaller the value, the better) -

To better understand the chart, we also printed the mean and percentile values.
Mean = 0.51 (49% space saved on average)
P95 = 0.58 (in order of economy, save at least 42% of space for the first 95% of data)
P99 = 0.61 (in order of economy, save at least 39% space for 99% of data)

What does this mean in a real world scenario?

For 99 percent of blocks, the size of the witness data can be reduced by at least 39 percent.

For 95% of blocks, the size of the witness data can be reduced by at least 42%.

On average, witness data saves 49%.

We also have to consider the absolute value of the size of the witness data. To make the data readable, we took a sliding average for every 1024 blocks.

python absolute-values-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 adjust

8

- a time-ordered graph of the witness data size, with the vertical axis in MB-

Let's look at the latest block.
Block height 8 million to 8.5 million
python percentile.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust

9

- box diagram, box represents the data within the upper and lower quartile, line represents the data within 1% of the upper and lower quartile -




- percentile analysis of blocks 8 million to 8.5 million -

And the XY scatter plot.
python xy-scatter-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust

10

And economies of scale.

python size-improvements-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust

11

-xy scatter plot (assuming key is encoded in the optimal way) (the horizontal axis is the size of the witness data under Hex, and the vertical axis is the size of the witness data under Bin) -
Mean = 0.53 (47% space saved on average)
P95 = 0.61 (ranked by economy, saving at least 37% of space for the first 95% of data)
P99 = 0.66 (in order of economy, save at least 34% space for 99% of data)

Finally, let's look at the absolute size of the witness data.

python absolute-values-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 adjust

12

- a time-ordered graph of the witness data size, with the vertical axis in MB-


conclusion


After testing with ethereum main network data, we can see that switching to binary tree mode can significantly improve the efficiency of generating witness data (witness data size reduced by an average of 47-49%).


Another conclusion is that the improvement is not as dramatic as it should be in theory. The reason may be the actual data for the main network block (which is more complex than expected).

Perhaps, by analyzing some of the exceptions (that is, the ones where the binary tree gets the least boost), we can learn more about how to optimize the size of witness data.

Try to use other raw data to run the script of the lot: https://github.com/mandrigin/ethereum-mainnet-bin-tries-data

(after)

Text link:https://medium.com/@mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768
Source:https://ethfans.org/posts/stateless-ethereum-binary-tries-experiment



Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia

举报 Correction/Report
Choose Library
Add Library
Cancel
Finish
Add Library
Visible to myself only
Public
Save
Correction/Report
Submit