Merkle tree

White paper introduction

Merkel A tree is a data structure

   chart 1-1： Illustration of bitcoin white paper  

Generate a Merkel Trees

  chart 1-2： From Wikipedia illustrations

  analysis ： Bottom up

1. We have four documents （ Bitcoin system is trading , This data structure can be used in various ways ）：L1、L2、L3、L4
2. Four documents passed hash Algorithm （ Two hash values are combined ） Get their respective blocks ：0-0、0-1、1-0、1-1
3. Between two blocks hash The algorithm gets a new block ：0-0 On 0-1 Generate 0、1-0 On 1-1 Generate 1
4. Repeat step 3, Get the final root node

Be careful ：hash Function maps any type of data of any length to a fixed size output . Merkel tree summarizes all transactions in a block , And generate the hash verification value of the whole block , Allow the user to verify whether the transaction is included in the block  

hash Algorithm

Hash Is a function that maps arbitrary length data to fixed length data .

for example , For data integrity verification , The simplest way is to do the whole data Hash Calculate to get a fixed length Hash value , And then put the Hash The value is posted online , In this way, after the user downloads the data , Do the data again Hash operation , Compare the calculation results with those published online Hash Value comparison , If two Hash The values are equal , It indicates that the downloaded data is not damaged . This can be done because a slight change in the input data will cause Hash The result of the operation is beyond recognition , And according to Hash It is difficult to deduce the characteristics of the original input data .

hash list

It is suitable for point-to-point network data transmission ：
When transmitting data in a peer-to-peer network , Data will be downloaded from multiple machines at the same time , And many machines can be considered unstable or untrustworthy . To verify the integrity of the data , A better way is to divide large files into small data blocks . The advantage of this is , If a small piece of data is damaged during transmission , Then just download this fast data again , Don't download the whole file again . How to determine which small data block is wrong ？ see “Merkel Tree retrieval ”

Merkel tree and hash list The difference between

Merkel tree It can be downloaded directly and verified immediately Merkle Tree A branch of . Because the file can be divided into small data blocks , So if a piece of data is damaged , Just download the block again . If the file is very large , that Merkle tree and Hash list almost , however Merkle tree You can download one branch at a time , Then verify the branch immediately , If the branch verification passes , You can download the data . and Hash list Only download the whole hash list To verify .

Merkel Tree retrieval

For better understanding , We assume that there is A and B Two machines ,A Need and B There are... In the same directory 8 File . At this time, we can pass Merkle Tree To make a quick comparison . Let's say that when we create a file, each machine builds a Merkle Tree. The details are as follows:

  chart 1-3： Network diagram reference

As you can see from the picture above , Leaf node node7 Of value = hash(f1), yes f1 Of documents HASH; And its father node node3 Of value = hash(v7, v8), That is, its child nodes node7 node8 It's worth it HASH. This is how to represent a hierarchical operation relationship .root Node value It's all leaf nodes value The only characteristic of .

　　 If A File on 5 And B It's not the same on the Internet . How do we get through two machines merkle treee Information found in different files ? The comparison process is as follows :

　　Step1. Compare first v0 Are they the same? , If different , Search for their children node1 and node2.

　　Step2. v1 identical ,v2 Different . retrieval node2 The children of node5 node6;

　　Step3. v5 Different ,v6 identical , Search comparison node5 The children of node 11 and node 12

　　Step4. v11 Different ,v12 identical .node 11 Is a leaf node , Get its directory information .

　　Step5. Retrieval and comparison completed .

 Merkel The irreversibility of trees

stay p2p Network before downloading the network , First get the file's from a trusted source Merkle Tree The root . Once you get the roots , You can get it from other untrusted sources Merkle tree. Check the received through the trusted tree root Merkle Tree. If Merkle Tree Is damaged or false , Just get another one from another source Merkle Tree, Until you get one that matches the root of the trusted tree Merkle Tree.

Modified any data in the tree , Will cause the value of the root node to change

 Merkel The efficiency of trees

The complexity of retrieval theory is Log(N)