Table of contents
What is a Merkle Tree?
How do Merkle trees work?
Why is Merkle Root used in Bitcoin?
Mining
verify
Summarize
What is a Merkle Tree?
In the early 1980s, Ralph Merkle, a famous computer scientist in the field of public key cryptography, proposed the concept of Merkle tree.
The Merkle tree structure can effectively verify the integrity of a data set and is more effective in peer-to-peer networks that require participants to share and independently verify information.
The hash function is the core of the Merkle tree structure. Therefore, we recommend that you first understand what hashing is before continuing to read this article.
How do Merkle trees work?
Let's say you want to download a large file. When downloading with open source software, you usually need to check whether the hash of the downloaded file matches the one made public by the developer. If they match, then the two files are identical.
If the hashes don't match, you're in trouble. Either you downloaded a malicious file disguised as software, or you downloaded it incorrectly, and the result is that the file is unusable. If you downloaded it incorrectly, you'll be annoyed because you've already spent so much time waiting for the file to download. Now you have to start over again and hope that the same problem doesn't occur again.
Have you ever thought about whether there is a simpler way to solve this problem? This is where Merkle trees come in. Merkle trees break files into chunks. For example, a 50GB file can be broken into 100 pieces, each of 0.5GB in size. Then, each piece can be downloaded one by one. This is how torrents work.
The source of the file at this point is a hash value, called a Merkle root. This single hash value represents all the data blocks that make up the file. Moreover, the Merkle root makes data verification easier.
To make it easier to understand, let's take an example. An 8GB file is divided into eight parts, and each part is named A to H. Then, each part is substituted into the hash function to obtain eight different hash values.
The hash values of the eight fragments are calculated through the hash function.
Hopefully, the above example explanation is understandable. We have hash values for all the segments, and if one of them is wrong, can we find the problem by comparing it to the original file? Perhaps, but this is still extremely inefficient. If the file has thousands of segments, do we need to hash all of them and then compare the results carefully?
No. We simply combine a pair of hashes and do a merge hash. That is, we hash hA + hB, hC + hD, hE + hF, and hG + hH. This results in four hashes. We then do another round of merge hashing until we get two hashes. These two hashes are then merged together to give us the master hash, which is the Merkle root (also called the root hash).
The structure looks like an inverted tree, with a row of leaves at the bottom, which combine to form nodes and finally the root.
Now we have a Merkle root that represents the downloaded file. Compare the root hash to the source file's value, and if they match, everyone is happy! If the hashes are different, it proves that the data has been tampered with. In other words, one or more pieces have generated a different hash value. Therefore, even the smallest modification of the data will completely change the Merkle root.
Fortunately, it is easy to check which fragment is wrong. Let's assume that the error is hE. First, we ask others for the two hash values (hABCD and hEFGH) used to generate the Merkle root. Our hABCD values should match theirs, which proves that the subtree is correct. If hEFGH does not match, we can correct the error from here. Then ask others for their hEF and hGH hash values and compare them with our own. If hGH is fine, it means that hEF is the culprit. Finally, we compare the hash values of hE and hF. Once we find that the source of the error is hE, we can re-download the data block.
In summary, the function of the Merkle tree is to divide the data into multiple parts, and then repeatedly hash them to form a Merkle root, which can effectively verify where the wrong data appeared. In the next section, we will introduce other interesting applications.
Want to start your cryptocurrency journey? Buy Bitcoin on Binance now!
Why is Merkle Root used in Bitcoin?
There are many use cases for Merkle trees, but this article focuses on the important role it plays in blockchain. Bitcoin and many cryptocurrencies are inseparable from Merkle trees. The Merkle tree is a component of each block and is usually located in the block header. Through the transaction hash value (TXID) of each transaction in the block, we can get the leaves.
In this context, Merkle roots have multiple uses. Let’s look at the use of Merkle roots in cryptocurrency mining and transaction verification.
Mining
A Bitcoin block consists of two parts. The first part is the block header, which is of fixed size and contains block metadata. The second part is the block body, which is of variable size but is usually much larger than the block header and contains a list of transactions.
Miners need to repeatedly hash data until they produce a result that meets certain conditions in order to mine a valid block. In order to get the correct result, they need to make trillions of attempts. With each attempt, miners change the random number in the block header, the Nonce value, to generate a different result. However, the rest of the block remains unchanged, and the thousands of transactions in it still need to be hashed each time.
Merkle root greatly simplifies this process. When mining starts, all transactions are queued and packaged into a Merkle tree, and the generated 32-bit root hash value is placed in the block header. After that, there is no need to hash the entire block, only the block header.
This approach is effective because it prevents data tampering and allows all transactions of a block to be efficiently summarized in a compact form. The transaction list of a valid block header cannot be modified, otherwise the Merkle root will be changed. After the block is sent to other nodes, the root hash is calculated from the transaction list. If it does not match the value in the block header, the block can be rejected.
verify
There is another interesting property of the Merkle root that we can use, and it has to do with the use of lightweight clients (nodes that do not keep a full copy of the blockchain). If you are running a node on a machine with limited resources, you certainly don’t want to download all the transactions in a block and hash them. Instead, you only need to ask for a Merkle proof, which is a proof provided by a full node that a transaction was included in a specific block. This proof is better known as “Simplified Payment Verification” or SPV, and was detailed by Satoshi Nakamoto in the Bitcoin whitepaper.
To check hD, just verify the hash value in red.
Suppose we want to get information about a transaction with TXID hD. If hC is known, hCD can be calculated. Then, from hAB, hABCD can be calculated. Finally, referring to hEFGH, we can check whether the calculated Merkle root is consistent with the root hash value in the block header. If it matches, it proves that the transaction was included in the block, because it is almost impossible to generate the same hash value with different data.
In the example above, we only did three hash operations. Without Merkle proofs, it would take seven. Today’s blocks contain thousands of transactions, and Merkle proofs save us a lot of time and computing power.
Summarize
Merkle trees have proven themselves to be important in computer science applications, and as we have seen, they are also valuable in blockchains. Merkle trees make it easier to verify information in distributed systems and avoid clogging up the network with redundant data.
Without Merkle trees and Merkle roots, Bitcoin and other cryptocurrency blocks would not be as compact as they are today. While lightweight clients lack the advantages of privacy and security, Merkle proofs allow users to verify that a transaction was included in a block with minimal fees.