What is a Merkle Tree?

In the early 1980s, Ralph Merkle, a renowned computer scientist in the field of public-key cryptography, proposed the concept of the Merkle tree.

The Merkle tree structure effectively verifies the integrity of datasets and is particularly useful in peer-to-peer networks where participants need to share and independently verify information.

Hash functions are the core of the Merkle tree structure. Therefore, we recommend understanding what hash operations are before continuing with this article.

How Does a Merkle Tree Work?

Suppose you want to download a large file. When downloading open-source software, you typically need to check whether the hash value of the downloaded file matches the one publicly provided by the developers. If they match, the files are identical.

If the hash values do not match, you’re in trouble. Either you’ve downloaded a malicious file disguised as software, or the download was incorrect, rendering the file unusable. If the download was incorrect, you’d likely feel frustrated, especially after spending a long time waiting for the download. Now, you’d have to start over and hope the same issue doesn’t recur.

Have you ever wondered if there’s a simpler way to solve this problem? This is where the Merkle tree comes into play. The Merkle tree can break a file into multiple data chunks. For example, a 50GB file can be split into 100 parts, each 0.5GB in size. You can then download them one by one. This is the principle behind torrent files.
The source of the file is now represented by a single hash value, called the Merkle root. This single hash value represents all the data chunks that make up the file. Moreover, the Merkle root simplifies data verification.

Why Is the Merkle Root Used in Bitcoin?

The Merkle tree has many use cases, but this article focuses on its critical role in blockchain. Bitcoin and many other cryptocurrencies rely on the Merkle tree. The Merkle tree is a component of every block, typically located in the block header. The leaves of the tree are obtained from the transaction hash (TXID) of each transaction in the block.

In this context, the Merkle root serves multiple purposes. Let’s explore its applications in cryptocurrency mining and transaction verification.

Mining

A Bitcoin block consists of two parts. The first part is the block header, which has a fixed size and contains block metadata. The second part is the block body, which is variable in size but usually much larger than the header and contains a list of transactions.

Miners must repeatedly hash the data until they produce a result that meets specific conditions to mine a valid block. To achieve the correct result, they need to make trillions of attempts. For each attempt, miners change the nonce value in the block header to generate a different result. However, the rest of the block remains unchanged, and the thousands of transactions within it still need to be hashed each time.

The Merkle root greatly simplifies this process. When mining begins, all transactions are queued, packaged, and structured into a Merkle tree. The resulting 32-bit root hash is placed in the block header. After that, there’s no need to hash the entire block—only the block header needs to be hashed.

This method prevents data tampering and is highly effective, allowing all transactions in the block to be efficiently summarized in a compact form. The transaction list in a valid block header cannot be modified, as doing so would change the Merkle root. When the block is sent to other nodes, the root hash is recalculated from the transaction list. If it doesn’t match the value in the block header, the block can be rejected.

Verification

Another interesting property of the Merkle root relates to lightweight clients (nodes that don’t store a full copy of the blockchain). If you’re running a node on a device with limited resources, you wouldn’t want to download all transactions in a block and hash them. Instead, you can request a Merkle proof—evidence provided by a full node that a transaction is included in a specific block. This proof is better known as “Simplified Payment Verification” (SPV), as detailed by Satoshi Nakamoto in the Bitcoin whitepaper.

Conclusion

The Merkle tree has proven its importance in computer science applications, and as we’ve seen, it’s also highly valuable in blockchain. The Merkle tree makes information verification in distributed systems more convenient and avoids congestion from redundant data in the network.

Without the Merkle tree and Merkle root, Bitcoin and other cryptocurrency blocks wouldn’t be as compact as they are today. Although lightweight clients lack advantages in privacy and security, Merkle proofs enable users to verify whether a transaction is included in a block at minimal cost.