Differences between Merkle DAG and Merkle tree

Merkle DAG and Merkle Tree The difference between

• about IPFS,Merkle DAG and Merkle Tree Are two very important concepts .

• Merkle DAG yes IPFS Data structure for storing objects , Merkle Tree It is used for the verification of blockchain transactions .

• Merkle Tree It is also commonly referred to as a hash tree （Hash Tree）, Is a tree that stores Hashi values ; and Merkle DAG It is short for Merkel's directed acyclic graph . There are similarities between the two , There are also some differences .

• From the object format , Merkle Tree The leaves of are data blocks （ for example , file 、 transaction ） Hash value of . A non leaf node is the hash value of the concatenated string of its corresponding child nodes .Merkle DAG The node of consists of two parts ,Data and Link;Data For binary data ,Link contain Name、Hash and Size These three parts . From the perspective of data structure ,Merkle DAG yes Merkle Tree More general situation , let me put it another way ,Merkle Tree It's special Merkle DAG. functionally , The latter is often used to verify data integrity , The former is mostly used for file systems .

Merkle Tree

​ Merkle Tree Can be seen as Hash List Generalization （Hash List It can be seen as a special kind of Merkle Tree, That is, the height of the tree is 2 Multi fork Merkle Tree）.

​ At the bottom , Same as Hash list , We divide the data into small data blocks , There is a corresponding hash corresponding to it . But go up , It is not directly to calculate the root hash , Instead, two adjacent hashes are merged into a single string , And then hash the string , So every two hashes get married and have children , I got a ” Sub hash “. If the total number of the lowest hash is singular , There must be a single hash in the end , In this case, hash it directly , So we can also get its sub hash . So push up , Still the same way , You can get a smaller number of new level hashes , It will eventually form an upside down tree , At the root of the tree , This generation has only one root hash , Let's call this Merkle Root[3].

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.

Merkle Tree and Hash List The main difference is , 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 All very well , 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

• The application case

​ 1. digital signature

first Merkle Tree The aim is to efficiently handle Lamport one-time signatures. every last Lamport key Can only be used to sign a message , But with the Merkle tree The combination can be used to sign multiple pieces Merkle. This method has become an efficient digital signature framework , namely Merkle Signature Scheme.

2. P2P The Internet

stay P2P In the network ,Merkle Tree It is used to ensure that data blocks received from other nodes are not damaged and are not replaced , Even check that other nodes won't cheat or publish fake blocks . What you are familiar with BT Download is to use P2P Technology to enable data transmission between clients , This can speed up data download , Second, reduce the burden of downloading servers .BT namely BitTorrent, It is a kind of central index P2P File analysis communication protocol [7].

To download, you must obtain a file with the extension... From the central index server torrent The index file of （ That is what we call the seed ）,torrent The file contains information about the file to be shared , Include the file name , size , Of documents Hash Information and a point Tracker Of URL[8].Torrent In the document Hash Information is an encrypted summary of the contents of each file to be downloaded , These summaries can also be run for verification at the time of download . Big torrent File is Web The bottleneck of the server , And it cannot be directly included in RSS or gossiped around( Spread with rumor spreading protocol ). A related problem is the use of large data blocks , Because in order to keep torrent The size of the file is very small , So the data block Hash And the number of , This means that each data block is relatively large . Large data blocks affect the efficiency of transactions between nodes , Because only when all the big data blocks are downloaded and verified , To trade with other nodes .

To solve the above two problems, a simple Merkle Tree Instead of Hash List. Design a full binary tree with enough layers , Leaf nodes are data blocks Hash, Insufficient leaf nodes are 0 Instead of . The nodes in the upper layer are connected in series with their corresponding child nodes hash.Hash Algorithm and general torrent Use the same SHA1. The data transmission process is similar to that described in Section 1

​ 3. BitCoin and Ethereum

Merkle Proof The earliest applications were Bitcoin, It was created by Nakamoto in 2009 Described and created in .Bitcoin Of Blockchain utilize Merkle proofs To store transactions for each block .

And the benefits of doing so , That's what Nakamoto described “ Simplify payment verification ”（Simplified Payment Verification,SPV） The concept of : One “ Light client ”（light client） You can download only the block header of the chain, that is, the header in each block 80byte A block of data , Contains only five elements , Instead of downloading every transaction and every block ：

• Hash value of the previous block header
• Time stamp
• Mining difficulty value
• Workload proof random number （nonce）
• Contains the of the block transaction Merkle Tree The root of the

If the client wants to confirm the status of a transaction , It simply initiates a Merkle proof request , This request shows that this particular transaction is Merkle trees One of the , And this Merkle Tree The root of the tree is in a block of the main chain .

however Bitcoin The lightweight client has its limitations . One limitation is , Although it can prove that the transactions involved , But it cannot prove the current state （ Such as the holding of digital assets , Name registration , Status of financial contract, etc ）.

Bitcoin How to query how much money you currently have ？ A bitcoin light client , A protocol can be used , It involves querying multiple nodes , And I believe that at least one of the nodes will notify you , About any specific transaction expenses in your address , And this allows you to implement more applications . But for other more complex applications , These are far from enough . The exact nature of the impact of a transaction （precise nature）, It can depend on previous transactions , And these transactions themselves depend on more previous transactions , So eventually you can verify every transaction in the whole chain . To solve this problem ,Ethereum Of Merkle Tree The concept of , It's going to go a step further .

Ethereum Of Merkle Proof

Each Ethereum block does not include one Merkle Trees , But three trees designed for three objects ：

• transaction Transaction
• Receipt Receipts( In essence, it is multiple pieces of data that show the impact of each transaction )
• state State

Merkle DAG

• Merkle DAG The full name is Merkle directed acyclic graph（ Merkel directed acyclic graph ）. It's in Merkle Tree On the basis of construction , Very similar to it , But not exactly , such as Merkle DAG There is no need to balance the tree 、 Non leaf nodes contain data, etc .Merkle DAG yes IPFS Core concept of , It's also Git、Bitcoin and dat And so on . The hash tree consists of content blocks , Each content block is identified by its encrypted hash .IPFS add The command will create... From the data of the file you specify Merkle DAG . When performing an operation , It follows unixfs data format . This means that your file is broken down into blocks , And then use “ Link nodes ” Arrange in a tree structure , To connect them together . Of a given document “ hash ” It's actually DAG Root node （ At the top ） Hash of .

• Merkle DAG The function of

​ • Content addressing ： Use multiple hashes to uniquely identify the contents of a data block

​ • tamper-proof ： It is convenient to check the hash value to confirm whether the data has been tampered

​ • duplicate removal ： Because the data block hash with the same content is the same , It can easily remove duplicate data , Save storage space

Article 3 is IPFS In the system , The most important feature , stay IPFS In the system , Every Block The size is limited to 256KB（ It can be selected through parameters ）, Those same data can be passed Merkle DAG To filter out , Just add a file reference , Without taking up storage space

• Data object format

​ stay IPFS It defines Merkle DAG Object format for .IPFS Object Storage structure , We mentioned earlier IPFS Will limit the size of each data to 256KB within . stay IPFS Object In the object , We save two parts , One is Link, A reference used to store other chunked data ; Another one is data, Content for this object .Link It mainly includes 3 Parts of , Namely Link Name 、Hash and Size, As shown in the following code . ad locum Link Just for one IPFS Object References to , It no longer stores one... Repeatedly IPFS Object .

type IPFSObject struct {
    
    links []IPFSLink     //link Array 
    data  []byte         // The data content 
}

type IPFSLink struct {
    
    Name string          //link Name 
    Hash  Multihash      // Encrypted hash value of data 
    Size int             // data size 
}

Use Git and Merkle DAG The collection of will greatly reduce the storage space consumption , Because if the modification of the source file uses Merkle DAG To store , Then the modified content may be a small part . We no longer need to make a backup of the entire modified file . This is the same. IPFS Reasons for saving storage space .