Merkle tree is a kind of binary tree. If the foundation of data structure is weak, it doesn’t matter. When reading the article, record the place that you don’t understand, and then search and study targeted. This paper will be divided into three parts to explain and demonstrate why “Merkle tree” can support the underlying trading system of Bitcoin:
● What is merkle tree
● Characteristics of The Mercer tree
● Application in Bitcoin
What is a Merkle tree? It consists of a root node, a set of intermediate nodes and a set of leaf nodes. The root node represents the final node, and there is only one. You can have a lot of leaves, but you can’t spread out any more so you have no children. Imagine a tree that grows from its roots into a trunk, branches from the trunk, and leaves from the branches. Okay! Charge! No more leaves will grow on the leaves. If you still don’t understand, take a look at this chart:
Illustration:
● Root: This is the Root node, where all the children come together, like an upside-down tree.
● Hash: An algorithm that can map a plaintext of any length into a short binary string, also called a Hash algorithm, such as MD5 and SHA. The result of the Hash is also called a Hash value.
Low Data0… Data3: These represent concrete raw data
B0, B1… B3: These are the hash values of the original data
At this time some students to shout, teacher! You just handed in “the leaf node can’t spread out any more, but what is the relationship between B0 and Data0 in the figure”. That’s a good question. Data0 corresponds to B0, which means that the hash of B0 corresponds to Data0, which is unique.
Now it’s important that a simple Merkle tree, as shown in the figure above, has the following three steps:
● The first step is to put the bottom layer Data0… Data3 each of the four data pieces is hashed separately to produce four hashes as leaf nodes.
● The second step is to Hash out the hashes of the two adjacent leaf nodes, for example, B0+B1 to get B4.
● Step 3 recursively performs the Hash operation until a root node is finally hashed.
This is how the Merkle tree works, as shown in the figure: B0+B1 Hash yields B4, B2+B3 Hash yields B5, and B4+B5 Hash yields Root. Since the content on each node is a hash value, it is also called a “hash tree”.
Characteristics of a Merkel tree:
Sensitive students will immediately think, “Since the Merkle tree, it must have something different.” Yes, it has three characteristics:
● The first feature: slight changes of any leaf node will lead to earth-shaking changes of Root node, which can be used to judge whether two encrypted data are exactly the same
● Second feature: fast location modification. If data in Data1 is modified, B1, B4, and Root will be affected. When the hash value of Root node Root changes, it takes O(logn) time to quickly locate the actual changed data block Data1 along Root – > B4 – > B1.
● Third property: zero-knowledge proof, which means that the prover is able to convince the verifier that an assertion is true without providing any useful information to the verifier. Like how to prove that someone owns Data0… What about Data3? Create a Merkle tree as shown in the figure, and then publish B1, B5, Root; The owner of Data0 hashes B0, generates B4 based on the published B1, and generates Root based on the published B5. If the resulting Root Hash is the same as the published Root Hash, the owner of Data0 can prove the possession of the data and does not need to publish Data1, Data2, and Data3. As shown in figure:
Application in Bitcoin:
Let’s start with a concept: merkle path. Root – > B4 – > B1 is a path that represents the path from the Root node to the leaf node. In Bitcoin, merkle trees are used to summarize all transactions in a block, generate a digital signature of the entire set of transactions, and provide an efficient way to verify the presence of a transaction in the block, called merkle path. Generating a Merkle tree involves recursively hashing each child node, inserting the newly generated hash node into the Merkle tree until there is only one hash node left, which is the root node of the merkle tree. , assume that a block of 16 deal O (logn) according to the above formula can calculate 16 logarithm is 4, is to find any transactions in this block, only need 4 times is ok, it’s Angela merkel path will hold four hash value, could the students didn’t feel to the efficient lookup, let’s look at a statistics, To stimulate:
● A transaction is about 250 bytes
● The number of paths represents the number of hashes. A path number of 4 means that the path contains four hashes of 32 bytes each
● Block size = Number of transactions x 250 Bytes
● Path size = Number of paths x 32 Bytes
It can be seen that as the block size increases from 16 transactions (4KB) to 262144 transactions (65MB), the merkle path length to prove the existence of transactions grows extremely slowly, from 128 bytes to 576 bytes. With Angela merkel, tree, a node can only download block header (80 bytes per block, containing the area size of the hash value, timestamps, dig the difficulty value, work proved that the random number, containing the block trading merkel) hash value is the root of the tree, and then from a full node back a small merkel path can certified the existence of a deal, Without the need to store or transfer the vast majority of the contents of the blockchain, which may be several gigabytes in size. Such nodes, also known as simple Payment Verification (SPV) nodes, do not require the maintenance of an entire blockchain, but verify the existence of a transaction via merkle path instead of downloading the entire block. Here is another graph drawn by V god, which finds out the Merkle path of TX3 in the Bitcoin network:
Conclusion:
It introduces what merkle tree is, its three features and its application in bitcoin. The core is to increase the distributed index performance by hashing large amounts of data, and manage large amounts of complex data by maintaining a small efficient index (The Merkerpath).
Refer to the link: https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/