The structure of the binary state tree

binary

How the binary state tree solves the complexity brought by RLP encoding
For the past few months, I have been working on transitioning trie from a hexadecimal tree structure to a binary tree structure. I have written an article (Chinese translation) on how to convert the state tree format, but I did not fully explain the structure of the state tree. I will write a series of articles to explore the trade-offs that need to be made when designing new structures. This article is the first in the series.

When designing a hexadecimal trie, some design choices sounded great at the time, but after 5 years of practice, it proved to bring a lot of complexity. Given that ETH 1.x wants to switch to binary trie, we can take this opportunity to study the storage method of state.

The root of the problem

When redesigning the storage format, we can make improvements in at least five aspects.

Merging account trie and storage trie: Maintaining multiple structures will increase complexity. A typical example is that nodes must first traverse the account trie to get the root of the storage trie, and then get data on the storage trie.

Extension nodes: This is a special node that is responsible for prefixing all keys on a specific subtree. The role of these nodes is to limit the number of nodes that need to be hashed, but they also introduce complexity because the keys involved must be packaged in a specific way.

The RLP encoding format is designed to efficiently encode arbitrary structures. Because of its complexity, it also brings a lot of trouble: you have to pack key chunks with all your hard work. In addition, since the structure of each node is quite fixed, a simpler serialization method can be used instead of RLP.

Related to the first two questions, the hexadecimal prefix can also bring complexity and confusion.

The proof of the hexadecimal trie [ie, “witness”] is about 4 times larger than the proof of the binary trie. (For details, please read this article. (Chinese translation))

RLP —— Ramble, Lose yourself and Pester?

(Translator’s Note: “RLP” is the abbreviation of “Recursive Length Prefix”, but the author here uses several words starting with R, L, P “Aimless, lost in self, and chattering”, which is a criticism Meaning.) In this article, we will discuss how to solve RLP problems.

If RLP is replaced, most core developers will not feel sad. This is because RLP is too complicated.

In fact, the only reason I have heard to support RLP is: “RLP is too complicated. Don’t risk choosing a new format to avoid repeating the same mistakes.” The basic principle of RLP is to use a simple size + data format. This is the origin of complexity.

First of all, size can be any integer (in fact, it cannot exceed 2 bytes, but in principle it is possible, so you must ensure that you can support a size exceeding 2 bytes). How do we know where the size part ends and where the data part starts?

In most cases, a header is added at the beginning. This header is a value h, and then a size value is added: Therefore, the RLP encoding is [length(data)+h] [data]

If length(data)+h <256, the RLP encoding is as shown above.

What should I do if the data is too large and the value of h exceeds one byte? That’s right, you also need to add another byte, that is, introduce the h’value to indicate that you are using the second storage scheme. In this case, the RLP encoding is [h’+length(length(data))] [length(data)] [data]. For “convenience”, h’is selected as 56.

If the data size is one byte, you find yourself having to add another byte before this byte. Is it possible not to do this? Yes in some cases, but it will add complexity! If data[0]< h, then there is no need to increase the header. Correspondingly, any byte payload starting with a value less than h must have only one byte.

Can it be sour? of course! RLP involves two types of “objects”: structure lists and byte arrays.

Byte array: header=128, overflow_header=183

Structure list: header=192, overflow_header=247

Please note that the maximum size of the data size part is 8 bytes, which is a number of 64 bits (the original text is “64-bytes”, which should be incorrect). Indeed, no matter what data, 18014398509481984 KB should be enough. Although there are still many tricky details to go into, the main point seems clear: RLP is difficult to tame. Let’s take a look at how it is intertwined with the state tree.

Merkelization rule

How do we apply RLP encoding and its boring logic to our Merkelization rules? Let’s start with the leaf nodes at the bottom of the Merkel tree.

Leaf nodes and their hexadecimal prefix

The leaf node saves a value, and there is a key with an unknown number of digits in front of the value.

This key is definitely different from the keys of other leaf nodes. Therefore, we have a tuple (key, value), which is a list with two elements, including key and value, both of which are byte arrays. RLP should theoretically help us encode these two data, right?

Not so much. The key on a hexadecimal tree is nibble-based, so if we take out a key, it may stop at the nibble, then the problem is:

I should How to align the data? There must be a design choice. As a result, we use a function called “hex prefix method” to read the key data, it will add a header to tell us whether the length of the key read is an even number or an odd number and a half byte.

The hexadecimal prefix encoding method uses the first half byte of the first byte (the “head byte” above) to store the length of the key (whether it is an odd or even number of nibbles). -The hexadecimal prefix method also requires us to adjust the position of the nibbles. For example, if the length of the key is an odd number of nibbles, put the first nibble to the last nibble of the head byte.

binary

Similarly, if the length is odd, but not byte-aligned with the end position of the byte, then each nibble must be shifted so that it can be stored with one byte less length.

If the length is even but odd-aligned, all nibbles must be shifted by 4 bits. -So, the leaf nodes are finally encoded in the form of RLP(HP(key_chunk), value).

Branch nodes and child nodes that are too small

A branch node (branch node) has 16 child nodes (childeren), and each byte point occupies half a byte.

According to the rules of RLP, a branch node is just a list of the hash values ​​of its child nodes, that is, a list containing 16 byte arrays.

If a child node is empty, it is represented as an empty array (just use a separate 128 to mark an array with a length of 0).

In the world, there is still the 17th entry in the list, which is the value of the branch node itself, but because it is not used in practice, the last entry in the list is always 128. Yes, as you might expect, there will be a lot of trouble here.

In order to avoid creating entries for objects that are too small in the database, a node with too small RLP encoding value will not calculate the hash value.

In this case, the RLP encoding will be directly stored as a list of original data, rather than the hash value of this list.

The result is that you rarely find the beginning of the array (128) in the list, but often find another beginning of the list (192), which creates a lot of problems for developers.

If the total size of the RLP data of a branch node is greater than 32, it will be counted as a hash value.

This is the case most of the time, because if it is not counted as a hash value, it means that the RLP data size of a child node has reached the maximum: 16 bytes.

Extended node

There is a third type of node on the state tree, called extension node, which we will focus on in the next article. Fortunately, fortunately, at this point in RLP encoding, it did not give us any trouble.

Do we really need RLP?

Are all these optimizations useful? Not necessarily. For example, if we don’t use the rule of rlp <32 bytes, how much storage space do we need to take up?

binary

Compared with the approximately 300 GB of storage space required by today’s fully synchronized nodes, it is simply insignificant. Similarly, not using hexadecimal prefix encoding will only result in an additional 100 MB of storage, which is 0.03% more. As long as you choose the binary trie encoding format carefully, this gap can be made up.

Binary trie: Send RLP to the earth for safety

On the secondary trie, the branch node becomes much simpler: a node has at most two child nodes, which can be indicated by its hash value. A Keccak256/Sha256 hash value, which is 32 bytes. At the moment, the obvious thing is that we don’t need a universal coding scheme that can encode arbitrary-length values. For example, suppose that each node of the new binary tree species has the following fields:

The hash value of the left child node, used as a pointer;

The hash value of the right child node, used as a pointer;

Value (optional), which is the value stored at the key used to get to this node

Prefix (optional), the purpose is to replace the extended node in the hexadecimal trie

The tree in the example stores key-value pairs (0xcafe, 0x00) and (0xcaff, 0x01): the root node is prefixed by the key data “0xcafe” and a number; this number means that only 7 bits in the last byte are used Store the prefix. Then the node has two pointers to its two child nodes, and does not contain values. Each child node is prefixed with a null value (marked by 0x00), has a value, and has no child nodes. -The client can encode the data of this node with a header that only occupies two bytes:

binary

Intermediate Node Serialization Header Proposal-This mode requires only two extra bytes, compared to RLP which requires at least 5 bytes. The first byte contains the following tags:

If the #7 bit is present, the first 32 bytes of the data following this header is the hash value of the left child node. If the bit is empty, the hash value of the left child node is also empty.

If #6 bit is present, the following 32 bytes represent the hash value of the right child node. If the bit is empty, the hash value of the right child node is also empty.

If #4 bit is present, the header will have an extra byte to give the number in the prefix bit; the prefix bit is placed following the hash value of the left/right child node;

If #5 bit is present, the remaining bytes of the payload after the header are used to represent the value

An important point of this method is that it also covers the function of hexadecimal prefix encoding, so the latter can also be cancelled.

in conclusion

I admit that when explaining the working model of RLP, I have been venting the frustration accumulated when using RLP. Objectively speaking, this design is not bad, and it has undoubtedly achieved its design purpose in the past five years of use. But over time, it has become more and more clear that its complexity is an overly expensive price. I hope to convince you that replacing RLP in the storage tree-related part has more advantages than disadvantages. The storage tree format described in this article is far from complete, and we will introduce more aspects in the future. Thank you Sina Mahmoodi and Martin H. Swende for their feedback.

Comments

Leave a Reply