Merkel tree in the blockchain
In the previous section, we mentioned that the header information of the block contains a Merkel's field
Why does this field exist in the header information of the blockchain ? Why use the data structure of Merkel tree ? Next, let's explain .
Merkel tree is also often called binary hash tree . By Merkel in 1979 Put forward in , Merkel tree is often used in business scenarios to quickly compare data and check whether an element exists . The reason why Merkel tree is good at these scenes , It is inseparable from its own structural characteristics . Let's take a look at its data structure
This is Merkel's data structure stored in the block header information
We see the bottom data Tx0、Tx1、Tx2、Tx3 It is the transaction data on the blockchain , First, they will be hashed . In bitcoin , The hash algorithm uses sha256, And hashing is done twice , Is a double hash .
Then why use double hashing ? This can be studied separately later , At present, the more reliable statement , Bitcoin network uses double hash algorithm , In fact, it's not to avoid hash's birthday attack , The more convincing analysis is because double hashing is used to defend against length extension attacks ,
By hashing the transaction data , We got hash01 and hash23, This hash value is generated by connecting the hash values of two child nodes
such as hash01 = sha256(sha256(hash0+hash1))
In this way, we can generate any level of Merkel tree , The final hash value is a root node , We call it Merkel
We can easily compare whether the two groups of data are the same through Merck root , At the same time, if the associated data in the tree changes , Then we can quickly locate the modified data through the hash value .
Another important role is to have “ Proof of zero knowledge ” The ability of . What is? “ Proof of zero knowledge ”, according to wiki The explanation of zero knowledge proves that one side ( Certifier ) To the other side ( Inspector ) The method of proving a proposition , It is characterized by the addition of “ The proposition is true ” In addition to , Don't divulge any information . Go back to our blockchain network , If we need to verify TX0 Whether there is , We have nothing but TX0 In addition to their own information , We just need to get Hash1,Hash23 and Root hash Can prove TX0 Whether there is , There is no evidence of our reliance on other data in the course of the transaction .
Merkel tree provides the information summary of all transactions in the blockchain
Application of Merkel tree - Simplify the verification of payment
A major application of Merkel tree in bitcoin network is to simplify the verification of payment . One kind of nodes in tecoin is complete nodes , It maintains complete blockchain information . And some nodes are lightweight , Complete blockchain information will not be maintained , They are lightweight nodes , Such nodes will use simplified payment verification when verifying transactions (SPV)
The Merkel tree and this SPV What does it matter ? Let's see SPV The general process can be divided into the following steps :
First step : We get a transaction hash that needs to be verified , The blockchain message header and authentication path related to the transaction , The node is through a similar subscription merkleblock The message got ,merkleblock Simply put SPV The message of the relevant transaction of the address of interest is received through the bloom filter
The second step : We get the block header information of the longest blockchain , The block information of the longest chain can be queried from other nodes to ensure that the longest block information is obtained
The third step : We get the authentication path of the transaction , The authentication path is to pass X Nodes form a path from transaction to root . This X The confirmation formula is log2(T) = X,T It corresponds to the number of transactions . For example, we have 16 transaction , Then through the log2(16)=4 It only needs 4 One node can confirm the transaction . this 4 One node constitutes the authentication path . Compared with all node data , The amount of data is much smaller
Step four : Calculate Merkel root to prove that the transaction is indeed included in this block , Then confirm whether this block is in the longest blockchain , To verify the effectiveness of the transaction
So the verification based on Merkel tree , It greatly reduces the dependence of data and the complexity of logic , Lower storage costs , But at the same time, due to the lack of copies of all the information , There is also a risk of malicious attack on the false connection nodes , Convenience and risk are often a double-edged sword