History of Merkle Tree:
Merkle tree (also called hash tree) is similar to the binary tree structure, the root node, intermediary nodes, and a set of leaf nodes. Merkle tree was first proposed by Merkle Ralf in 1980 and was generally used in file systems and P2P systems.
Main features of Merkle Tree:
There are two main features of Merkle tree are as follows:
- The bottom leaf node contains the stored data or its hash value.
- Non-leaf nodes (including intermediate nodes and root nodes) are the hash values of the contents of its two child nodes.
Further, the Merkle tree can be extended to the case of a multi-branch tree, where the content of a non-leaf node is the hash value of the content of all its child nodes.
The Merkle tree records the hash value layer by layer, giving it some unique properties. For example, any changes in the underlying data will be passed to its parent node, layer by layer along the path all the way to the root of the tree. This means that the value of the tree root represents a “digital summary” of all the underlying data.
The following figure is an example, and the Merkle tree is constructed based on data D0…D3. If the data in D1 is modified, it will affect N1, N4 and Root.
The above figure is an example, how to prove to others that they own certain data D0 without revealing other information. The challenger provides random data D1, D2 and D3, or generated by the prover (specific information needs to be added to avoid being reused by the proof process).
The prover constructs the Merkle tree as shown in the figure and announces N1, N5, and Root. The verifier calculates the Root value by himself and verifies whether it is consistent with the provided value, then it is easy to detect the existence of D0. During the whole process, the verifier cannot obtain additional information related to D0.
Why use Merkle Tree?
Since the Merkle tree is essentially a tree-like data structure composed of hash values, it also inherits the functions of hash values to ensure data security and privacy and verify the accuracy and integrity of data. It is mainly used for point-to-point downloads, such as BT download, open-source distributed control system Git, Bitcoin and Ethereum blockchain and other scenarios. Because it is difficult for us to guarantee that each node in these decentralized systems will provide true and reliable data, and it is difficult to avoid data loss or damage during transmission, it is necessary to introduce data encryption and verification mechanisms.
Seeing this, you may have realized that the Merkle tree is a tree-like data structure constructed by dividing the data into multiple small pieces and performing multiple hash operations. Then why split the data and calculate multiple hash values for verification? Doesn’t this increase the workload? However, in fact, this is done to improve the flexibility of data verification. The greater the amount of data, the more obvious this advantage of the Merkle tree will be.
Imagine if we do not split the data, but calculate the whole into a hash value. When there is a problem with the data verification, it is difficult for us to distinguish where the problem is, and we can only go back and investigate the entire data. , If the amount of data is huge, then this error troubleshooting process is tantamount to finding a needle in the sea.
However, in the Merkle tree, the data is split into multiple small blocks to form multiple branches. Part of the data can be verified according to the specific situation without verifying the entire data, thereby improving the flexibility and flexibility of data verification efficient.
Merkle Tree in Bitcoin
The Merkle binary tree is used in the Bitcoin blockchain system. Its major function is to speedily summarize and verify the reliability of the block data. It will hash the data packets in the blockchain and perform continuous recursive operations upwards. Generate new hash nodes, and finally only one Merkle root is left in the block header. Each hash node always contains two adjacent data blocks or their hash values.
The use of Merkle trees in the Bitcoin system has many advantages: First, it greatly improves the operational efficiency and scalability of the blockchain, so that the block header only needs to contain the root hash value without encapsulating all the underlying data, which makes the hash Operations can be efficiently run on smart phones and even IoT devices; secondly, the Merkle tree can support “Simplified Payment Verification Protocol” (SPV), that is, transaction data can be performed without running a complete blockchain network node test. Therefore, it is very meaningful to use the Merkle tree data structure in the blockchain.
Finally, key points of Merkle trees:
- Tree data structure composed of hash values
- Used to verify the complete accuracy of data in decentralized systems such as blockchain
- Has the advantage of flexible and efficient data verification