current position:Home>Chat blockchain (III)

Chat blockchain (III)

2022-02-03 15:24:10 Hades

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
image.png

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

copyright notice
author[Hades],Please bring the original link to reprint, thank you.
https://en.netfreeman.com/2022/02/202202031524059566.html

Random recommended