In the field of computer ,Merkle Trees are mostly used for integrity verification . In application scenarios dealing with integrity verification , Especially in the distributed environment when such verification ,Merkle Tree will greatly reduce the amount of data transmission and computational complexity .

Merkle Hash tree is a kind of binary tree or multi tree based on hash value , The value on the leaf node is usually the hash value of the data block , The value on the non leaf node is the hash value of the combined result of all the child nodes of the node .

As shown in the figure below is a Merkle Hash tree , node A The value of must pass through the node C、D It is calculated from the value of . Leaf node C、D Separate storage blocks 001 and 002 Hash value of , Not leaf nodes A It stores its child nodes C、D The hash value of the combination of , The hash value of this kind of non leaf node is called path hash value , The hash value of the leaf node is the hash value of the actual data .

When data from A End to end B End time , To test the integrity of the data , Just need to verify A、B Constructed on the end Merkle Whether the root nodes of the tree are consistent or not . If it's the same , Indicates that the data has not changed during transmission . If it's not the same , Indicates that the data is modified during transmission . And through Merkle The tree can easily locate the tampered nodes . The time complexity of location is O(log(n)).

Bitcoin's lightweight node uses SPV Verification is the use of Merkle The advantage of trees .

In the blockchain Merkle A tree is a binary tree , Used to store transaction information . Pairing each transaction , constitute Merkle The leaf node of the tree , And then generate the whole Merkle Trees .Merkle The tree allows users to get the Merkle The tree root and the list of intermediate hash values provided by other users are used to verify whether a transaction is included in the block . Users who provide intermediate hashes don't need to be trusted , Because it's expensive to forge a block , If the middle hash value is forged, the verification will fail .

Usually , Encrypted hash Method image SHA-2 and MD5 Used to do Hash. But if only to prevent data from being deliberately damaged or tampered with , We can use some low security but high efficiency check sum algorithm , Such as CRC.

Second Preimage Attack: Merkle tree The root of a tree is not the depth of the tree , This may lead to second-preimage attack, In other words, the attacker creates a system with the same Merkle Fake documents at the root of the tree . A simple solution is Certificate Transparency In the definition of : When calculating the number of leaf nodes hash when , stay hash Add... Before the data 0x00. When computing internal nodes is , Add... To the front 0x01. Other implementation limitations hash tree The root of the , By means of hash Value is prefixed with depth . therefore , Prefixes decrease with each step , The prefix is still positive only when it reaches the leaf , Extracted hash Chain is defined as effective .

Merkle tree operation :

1. establish Merckle Tree

Joining the bottom is 9 Data blocks .

step1:( Red thread ) Do... On data blocks hash operation ,Node0i = hash(Data0i), i=1,2,…,9

step2: ( Orange Line ) Two adjacent hash Block series connection , Then I do hash operation ,Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7; about i=9, Node1((i+1)/2) = hash(Node0i)

step3: ( Yellow line ) repeat step2

step4:( Green line ) repeat step2

step5:( Blue line ) repeat step2, Generate Merkle Tree Root

Easy to get , establish Merkle Tree yes O(n) Complexity ( Here it means O(n) Time hash operation ),n Is the size of the data block . obtain Merkle Tree The height of the tree is log(n)+1.

2. Retrieve data blocks

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 , The files are f1 f2 f3 ....f8. 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: :

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 .

The theoretical complexity of the above process is Log(N).

3.  to update , Insert and delete

Although there's a lot on the Internet about Merkle Tree Information , But most of them don't involve Merkle Tree Update 、 Insert and delete operations , Discuss Merkle Tree Search and traversal of more . obviously , A tree like operation certainly involves more than just finding , It also includes updates 、 Insert and delete . Later, it was found that The dance of the wind 555 A summary of the article , Little insight , The following reference The dance of the wind 555 Tell me about :

about Merkle Tree The update operation of data block is very simple , Update the data block , And then update it to the tree root path Hash The value will do , It won't change Merkle Tree Structure . however , Insert and delete operations are bound to change Merkle Tree Structure , Here's the picture , An insertion operation is like this :

Insert data block 0 after ( Consider the location of the data block ),Merkle Tree This is the structure of :

And some students are considering an insertion algorithm , Meet the following conditions :

  • re-hashing The number of operations is controlled at log(n) within
  • The check of data block is in log(n)+1 within
  • Unless the original tree n It's even , There are no orphans in the inserted tree , And if there are orphans , So orphans are the last data block
  • The order of data blocks is consistent
  • Inserted Merkle Tree balance

And then the insert above will look like this :

therefore ,Merkle Tree The insertion and deletion of is actually an engineering problem , Different problems have different insertion methods . If you want to make sure the tree is balanced or the height is log(n) Of , You can use any standard balanced binary tree pattern , Such as AVL Trees , Red and black trees , Stretch the tree ,2-3 Trees, etc . These update patterns of balanced binary trees can be found in O(lgn) Time to insert , And make sure the height of the tree is O(lgn) Of . So it's easy to see all the updates Merkle Hash Can be in O((lgn)2) Within time ( For each node, to update from it to the root of the tree O(lgn) Nodes , In order to meet the requirements of tree height, it needs to be updated O(lgn) Nodes ). If you analyze it carefully , Update all hash You can actually O(lgn) Within time , Because all the nodes to be changed are associated , That is, if they are not all on a path from a leaf node to the root of the tree , Or it's similar .

actually Merkle Tree Structure ( Is it balanced , How much is the tree height limit ) It doesn't matter in most applications , And maintaining the order of data blocks is not necessary in most applications . therefore , According to the specific application situation , Design your own insert and delete operations . A generic Merkle Tree There's no point in inserting or deleting .


Expand knowledge :

Hash List And Merkle tree What are the similarities and differences ?

Tell me ~~~~~~~

When the network transmits data ,A received B It's a document that's coming from me , Need to confirm whether the received documents are damaged . How to solve ?

: One way is B Before transferring the file, first put the file's hash Result to A,A After receiving the file, calculate the hash again, and then compare it with the received hash to know if the file is damaged .

But when the file is big , It is often necessary to split the file into many data blocks and transfer them separately , At this time, we need to know the hash value of each data block . What shall I do? ?

: This situation , You can download a Hash list before downloading data (hash list), Each item in this list corresponds to the hash value of a data block . For this hash list After splicing, a root can be calculated hash. Practical application , We just need to make sure we get the right root from a credible source hash, You can make sure you download the right file .

But based on hash list This is a problem : When there are a lot of data blocks , Often traverses all data blocks of Hash List It costs a lot .

Is there a way to go through part of Hash You can verify the integrity of the entire file ?

: The answer is yes !Merkle Tree It can be done !

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 It's big , 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 .


【 Hasty time , If there is a mistake , Welcome to correct ! ||    Welcome to leave your comments !   Let's discuss 、 Learn blockchain !】

【 Reprint please indicate the source !http://www.cnblogs.com/X-knight/


REFERENCE

1.Merkle Tree Study  http://www.cnblogs.com/fengzhiwu/p/5524324.html

2. Merkle Tree Add or delete data http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

3.Merkle Tree、Hash List https://blog.csdn.net/pony_maggie/article/details/74538902

[ Blockchain ] cryptography ——Merkle More about trees

  1. [ Blockchain ] In cryptography Hash Algorithm ( Basics )

    Introducing Hash Algorithm before , Let's first give you a data structure of hash surface ( Hash table ) A simple explanation of , Then I'll go deeper and deeper , Explain hash Algorithm . One .Hash principle —— The basic chapter 1.1 Concept Hash table is a kind of table key - value (key-i ...

  2. [ Blockchain ] cryptography —— ECC algorithm (ECC)

    I'm learning elliptic curve cryptography today (Elliptic Curve Cryptography,ECC) Algorithm , I lack of professional books to introduce the algorithm , So I searched a lot of blogs and books on the Internet , But most blogs are really about ... You'll see ... Really not ...

  3. cpp Blockchain simulation example ( 7、 ... and ) Add Merkle Trees

    Merkle Trees Complete bitcoin database ( That's blockchain ) Need to exceed 140 Gb Of disk space . Because of the decentralized nature of bitcoin , Each node in the network must be independent , Self sufficient , That is, each node must store a complete copy of the blockchain . along with ...

  4. Cryptography in blockchain ( Four )- Merkle Trees and SPV node

    What is? Merkle Tree? Merkle Tree It's named after American cryptographers Ralph C. Merkle , About his profile : Portal https://en.wikipedia.org/wiki/R ...

  5. Blockchain ~Merkle Tree( Ms merkel tree ) Algorithm analysis ~ Reprint

    Reprint ~Merkle Tree( Ms merkel tree ) Algorithm analysis /* Recently in to see Ethereum, One of the important concepts is Merkle Tree, Never heard of before , So I checked some information , To study the Merkle Tree Knowledge , because ...

  6. Blockchain - Ms merkel tree (Merkle Tree)

    chapter Blockchain – Introduce Blockchain – The development history Blockchain – The currency Blockchain – Application development stage Blockchain – Asymmetric encryption Blockchain – Hash (Hash) Blockchain – dig Blockchain – Link blocks Blockchain – work ...

  7. Blockchain learning 1:Merkle Trees ( Ms merkel tree ) and Merkle root

    * ░ Go to the old ape Python Blog Directory ░ One . brief introduction Ms merkel tree (Merkle tree,MT) Merkel tree , It's a hash binary tree , The root of a tree is Merkle root . About Merkle Tree ape recommends reading <M ...

  8. From the beginning of blockchain to the actual combat (12) The blockchain – Ms merkel tree (Merkle Tree)

    Purpose : Because the blockchain is too long , Causes the node hard disk to be unable to save the question . Method : Just keep the hash value of the transaction . Blockchain as a distributed ledger , In principle, every node in the network should contain all the blocks in the whole blockchain , As blockchains get longer , The node's hard disk may not fit ...

  9. Bitcoin block structure Merkle Tree and simple payment verification analysis

    In the bitcoin network , Not every node has the ability to store complete blockchain data , Limited by storage space , Many nodes are based on SPV(Simplified Payment Verification Simple payment verification ) Wallet connected to bitcoin network , through ...

Random recommendation

  1. iOS Realization app File sharing

    The solution is as follows , In the application of Info.plist Add... To the file UIFileSharingEnabled key , And set the key value to YES. Put the files you want to share in the Documents Catalog . Once the device is plugged into user computing ...

  2. stl Preliminary use

    1.sort and  lower_bound for example     marble      https://uva.onlinejudge.org/index.php?option=com_onlinejudg ...

  3. What is? mixin

    from :http://guangboo.org/2013/01/28/python-mixin-programming http://en.wikipedia.org/wiki/Mixin http:/ ...

  4. python web Development encounters socket.error[errno 10013]

    socket.error[errno 10013], Port occupied Change the port again , Or close the program that occupies the port

  5. VS Extended development framework

    VsSharp: One VS Extended development framework ( On ) Part 1 : Design One . Introduction since 2008 It has been developed since SSMS plug-in unit SqlSharp(er) In the process of , One day it turned out that most of the code was the same , Just like this. . Commands2 comm ...

  6. onPostCreate——Activity The callback after it runs completely

    Remember that I wanted to be in Activity Layout complete , After a thorough run , Get the current Activity In the window of , Some View The width and height of , The way I used to do it was very rustic , Get a Handler, Send out Message come out , Use sendMessage ...

  7. 【Android Developers Training】 79. Connect to the network

    notes : This article is translated from Google Official Android Developers Training file , The translator's skill is average , Because I love Android, I have the idea of translation , It's just a personal hobby . Link to the original text :http://developer ...

  8. React Environment configuration

    Now start to configure a foundation project . Create project folder :C:\Users\Danny\Desktop\React npm init establish package.json file All installations below , All are --save-dev, because ...

  9. centos 7 mariadb Startup issues

    Installed mariadb after One day, restart the machine and find It won't start mariadb.service systemctl start mariadb.service // And then I found the following problem job for ma ...

  10. Database cluster MySQL Master slave copy

    MySQL Master slave copy In this section, we use MySQL Configuration of master-slave replication function of Master and Slave node , Validation data MySQL Data synchronization function . Because you have to use multiple MySQL database , So it is not recommended to install multiple MySQ ...