What is a sparse Merkle tree multi-valued proof

Editor's Note: This article is from:Ethereum enthusiasts (ID: ethfans)Editor's Note: This article is from:

Ethereum enthusiasts (ID: ethfans)

, Author: Jim McDonald, translation & proofreading: Pei Qi & A Jian, reprinted with authorization by Odaily.

first level title

Popular Science | What is Merkel truncation

Sparse Merkle multiproofs (Sparse Merkle multiproofs) is an alternative to Merkle tree truncation (Merkle pollard), which can provide space for proving the existence of multiple values ​​on a Merkle tree. Evidence of savings. What is Merkle proof and Merkle tree truncated, I have explained in the previous article; I recommend you to read and understand these concepts before reading this article. Next, the text will use the Merkle tree in the figure below to explain multi-value proofs:

image description

Sparse multi-valued proofs were first proposed by Vitalik Buterin.

multi-valued proof

image description

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

As can be seen from the figure above, the 3 proofs contain a total of 9 hash values ​​of the intermediate branches (that is, the part marked in green): each proof has 3 hash values. Combining these three proofs into the structure shown in the figure below is a multi-valued proof:

image description

-Figure 5: Merkle multi-value proof corresponding to Banana, Peach and Kumquat-

Sparse Multivalued Proofs

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

image description

-Figure 6: Hash values ​​that can be removed in Merkle tree multi-valued proofs (see yellow marks)-

After removing these hash values, the sparse multi-value proof in the Merkle tree can be obtained, as shown in the following figure:

image description

-Figure 7: Sparse Merkle tree multi-value proof-

• Sparse Merkle multi-valued proofs reduce the number of hashes that need to be included from 9 to 3. Sparse multivalued proofs are also more efficient than Merkle truncated proofs, which require 6 hashes, for the same proof.

• After the verifier obtains the sparse multi-value proof, in order to verify that those values ​​are part of the Merkle tree, the following steps need to be performed (in the Merkle tree, in order 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, and get a random string of outputs)

• Hash Banana to get bc4f...8d3f

• Hash Peach to get 59a0…421d

• Hash Kumquat to get 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 Merkle tree. If the two are consistent, all the values ​​are determined to be in the Merkle tree.

The following figure compares the amount of storage space that Merkle tree truncated and sparse multi-valued proofs in Merkle tree can save when storing Merkle proofs when the number of values ​​and proofs in the Merkle tree changes:

• It is worth noting that the savings of multi-valued proofs are approximate, as the savings depend on the location of the proven value in the Merkle tree and the number of intermediate branch hashes that can be removed.

• Comparing Sparse Multivalued Proofs with Merkle Truncated

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

• In the multi-value proof method, the proofs for all values ​​are generated and verified together; in the truncated method, the proofs for each value are generated and verified separately. In terms of truncating, which value is the specific value, you only need this value and related proofs. For multi-value proofs, you need to take out the multiple values ​​to be verified and the proofs corresponding to the multiple values)

• Sparse multivalued proofs require more memory and CPU cycles to generate and verify proofs

Sparse multivalued proofs are hard to generate and verify in parallel

Sparse multi-valued proofs have a variable size, while Merkle tree truncation has a fixed proof size given a Merkle tree and the total number of proofs