What is Merkle Pollard?

星球君的朋友们

Odaily资深作者

2019-04-13 11:08 (UTC+8)

This article is about 2552 words, reading the full article takes about 4 minutes

The Merkle Tree principle as part of stark.

AI Summary

The Merkle Tree principle as part of stark.

, reprinted by Odaily with authorization.medium, reprinted by Odaily with authorization.

secondary title

hash function

image description

-hash-

Merkle tree

Merkle tree refers to the combination of multiple input values and their hash values to compress into a fixed-length value.

image description

-Merkel tree-

The Merkle tree shown above has 8 input values and is divided into 4 layers. The root node is 0xd576...ffd9 at the very end.

image description

-The effect of a change on the entire Merkle tree (as shown in the gray shaded part)-

secondary title

Merkel path

image description

-"Peach"secondary title

Merkel proof

image description

-Merkel Proof-

A Merkle proof requires three things: an input value (marked in red), hashes of intermediate branches (marked in green), and a Merkle root node (marked in blue). The set of intermediate branch hash values corresponding to each input value is different.

Blockchain systems often use Merkle proofs to prove that a certain input value exists in a data set, so that the entire data set does not need to be stored on the blockchain. Assume that there is a whitelist list in an Ethereum contract, and only accounts in the list are allowed to purchase Ethereum. If the information of each account in the whitelist is stored on the blockchain, it is bound to pay a high cost. In this case, just create a Merkle tree and store the root node on the blockchain.

For example, if the root node is stored on a smart contract, the smart contract can easily prove that an account is included in the whitelist: the account needs to provide an intermediate branch hash (provided by the contract owner through some off-chain means). to the account holder), the smart contract performs hash calculation on the hash value of this account and the hash value of the intermediate branch in turn. If the final result is consistent with the Merkel root node, it proves that the account is indeed in the whitelist.

Note the relationship between the Merkle path and the hash of the Merkle proof in the last two figures. In the same level of the same tree, the hash value of the Merkle proof is correlated with the hash value of the Merkle path. From this, it can be seen that a Merkle proof is able to reshape the Merkle path of the input value, which is why the final result is a Merkle root node.

So far, it can be seen that the Merkle proof has the following characteristics:

Storing Merkle proofs on-chain requires far less space than storing input values directly
Publicly storing Merkle proofs on-chain also does not expose the entire set of input values
secondary title

duplicate proof

In the above example, each account only needs to send a Merkle certificate to verify whether it is on the whitelist.

In addition, Merkle trees can also be used as probabilistic proofs of knowledge (often called STARKs), each proof of knowledge can make us (ie "verifier, challenger") more convinced: the creator of the Merkle tree (i.e. the "prover") knows all the constituent values. In this case, the prover typically generates hundreds of proofs based on Merkle trees containing dozens or even hundreds of input values. These proofs are sent to validators along with Merkle root nodes to verify their validity.

image description

-Duplicate Proof of the Same Merkle Root-

It can be seen that a total of one Merkle root node and three certificates are sent, adding up to a total of 10 hash values: one for the root node and three for each of the remaining three certificates.

image description

-Duplicate Proof of Extended Merkle Root Node-

secondary title