Science | What is a sparse Merkel tree multivalued proof

Translator's Note: The Ethereum network is a stateful world computer. Its state includes state balance, transaction nonce, contract code, and contract storage contents. Technically, these state data are organized by a structure called "Merkel Tree", so the state of the Ethereum world and its access and updates can be expressed as a Merkel tree and its access, Update. Similarly, all data verification and verification operations related to the Merkel tree can be understood as state verification and verification operations in the context of the Ethereum protocol. In fact, the Merkel tree is an integral part of our understanding, utilization and improvement of the Ethereum protocol.

This article introduces a method that can prove that multiple values ​​exist on the same Merkel tree, so it can be said that this is how to prove that multiple Ethereum states belong to the world state at the same time.

What is Merkel truncation

Sparse Merkle multiproofs is an alternative to Merkle pollard, which can provide space for proving the existence of multiple values ​​on a Merkel tree. More economical proof. What is Merkel proof and Merkle tree truncation, I have explained in the previous article ; I recommend that you read and understand these concepts before reading this article. Next, the text will explain the multivalued proof using the Merkel tree as shown below:

• Weekly development of industrial blockchain
• QKL123 market analysis | Crude oil collapses, stock indexes fall, panic spread … Bitcoin has not been spared (0309)
• The most expensive ERC-1155 NFT ever released, worth $ 102,000

-Figure 1: A Merkel Tree-

The sparse multivalued proof was first proposed by Vitalik Buterin.

Multi-value proof

Multiproof is to pack a group of proofs in a Merkel tree together to save storage space. For example, here are three Merkel proofs of the Merkel tree shown in the figure above:

-Figures 2, 3, and 4: Merkel proofs for Banana, Peach, and Kumquat, respectively-

As can be seen from the above figure, the 3 proofs contain a total of 9 intermediate branch hashes (ie the parts marked in green): each proof has 3 hashes. Combining these 3 proofs into the structure shown in the figure below, becomes a multi-valued proof:

-Figure 5: Merkel multivalued proofs for Banana, Peach, and Kumquat-

Compared with the 9 intermediate branch hash values ​​required for a single proof, Merkel's multivalued proof only requires 7 hash values, which saves storage space.

Sparse multivalued proof

Although the multi-valued proof of the Merkel tree does save some storage space, some of the data can be obtained in other ways, so removing this data can further save storage space. (Translator's Note: Data that can be obtained by other means need not be stored in the certificate, as long as it can be obtained when needed)

The above Merkel tree multi-valued proof is taken as an example, and the hash values ​​of many intermediate branches can be calculated. For example, after the verifier calculates the known values ​​Banana and Peach through a hash function, they can get hash values ​​bc4F … 8d3f and 59a0 … 421d. The hash values ​​c0b7 … da30 and 6ff9 … 8e3d of the two nodes connected to the root node can be calculated from the hash values ​​of its child nodes (the nodes directly connected to the two nodes and above). Because the hash value of the child node is either included in the certificate, or it can be calculated by the hash value of the next level. The yellow nodes in the image below mark these 4 hash values ​​that can be calculated:

Figure 6: Hashes that can be removed in Merkel tree multi-valued proofs (see yellow mark)-

After removing these hashes, you can get sparse multivalued proofs in the Merkel tree , as shown in the following figure:

-Figure 7: Sparse Merkel tree multivalued proof-

The sparse Merkel tree multi-value proof reduces the number of hashes needed to be included from 9 to 3. Proving the same effect, sparse multivalued proof is also more effective than Merkel's truncation, because the latter requires 6 hashes.

After the verifier gets a sparse multi-valued proof, in order to verify that those values ​​are part of the Merkel tree, the following steps need to be performed (in the Merkel tree, from left to right, from top to bottom):

(Translator's Note: "Hash a value" means: use the value as the input of the hash function to get a random string of outputs)

• Hash Banana to bc4f … 8d3f
• Hash Peach to 59a0 … 421d
• Hash Kumquat to 2aab … 6f791
• Hash bc4f … 8d3f and 59a0 … 421d to get 9c15 … 5dec
• Hash 2aab … 6f79 and 45cf … 14d9 to get a6e4 … 87df
• Hash d596 … 66ef and 9c15 … 5dec to get c0b7 … da30
• Hash e336 … ed14 and a6e4 … 87df to get 6ff9 … 8e3d
• Hash c0b7 … da30 and 6ff9 … 8e3d to get d576 … ffd9

At this point, the final hash value can be compared with the root hash value of the Merkel tree. If the two are consistent, it is assumed that all values ​​are in the Merkel tree.

The following figure compares the Merkel tree truncation and the sparse multivalued proof in the Merkel tree when the median value of the Merkel tree changes and the number of proofs: The amount of storage space that can be saved when storing the Merkel proof:

Number of underlying values	Number of proofs	Truncation method savings	Multi-value proof savings rate (approximate)
1024	16	20%	44%
1024	32	29%	55%
1024	64	38%	64%
1024	128	48%	75%
4096	128	40%	61%
16384	128	34%	50%
65536	128	30%	42%

It is worth noting that the savings of multi-valued proof are approximate, because how much can be saved depends on the position of the proven value in the Merkel tree and the number of intermediate branch hash values ​​that can be removed.

Contrast sparse multivalued proofs with Merkel truncation

As can be seen from the table above, sparse multi-valued proofs save more storage space than Merkel truncation, so why use Merkel truncation? Because the sparse multi-valued proof has some different characteristics compared to the Merkle tree truncation, the main points are as follows:

• In the multi-valued proof method, all value proofs are generated together and verified together; while in the truncated method, the proofs for each value are generated and verified separately (Translator's Note: When generating and verifying In terms of truncation, which value is required, only this value and related proofs are required. For multi-valued proofs, multiple values ​​to be verified and the corresponding proofs for multiple values ​​are required.)
• Sparse multi-valued proofs require more memory and CPU cycles when generating and verifying proofs
• Sparse multi-valued proofs are difficult to generate and verify in parallel
• The size of a sparse multivalued proof is variable, and the Merkle tree truncation is given a fixed Merkel tree and the total number of proofs, and its proof size is fixed.
• In some cases, because the encoding system used to transmit information is different, it may cause sparse multi-valued proofs to require more space than the Merkle tree truncation; therefore, it is recommended to test before using

In general, it depends on the needs of the individual application to decide which is more appropriate. But both methods save more storage space than a single Merkel proof, so when you need to provide multiple proofs for the same Merkel tree, you can consider using these two methods.

Implementation example

https://github.com/wealdtech/go-merkletree/ provides an implementation of sparse Merkel tree multivalued proofs in Go.

Original link: https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/ Author: Jim McDonald Translation & proofreading: A sword & Pei Qi

This article was authored by the author for translation and republishing by EthFans.

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