The bitcoin network has been running non-stop since 2009 and at the time of writing this blog post, the whole blockchain occupies more than 500GB. Verifying information in that huge amount of data is not an easy task. Luckily, as many other computer science problems, this can be solved by using the correct data structure. In our case, that data structure is the Merkle tree.

What is a Merkle Tree (a.k.a Hash Tree)?

As the name suggests, the Merkle tree is a data structure in form of a tree (usually binary) where:

• Each leaf contains a hashed piece of information we want to save and later on verify.
• Each internal node contains the hash of its two children.

What and where are they used for?

The Merkle Tree usage transcends the blockchain space:

• Git version control system: Git stores everything as a blob (for files) or a tree (for directories, that are also Merkle trees), creating a Merkle tree of the whole project directory. Each blob and tree is part of the outermost tree, meaning that they have assigned a unique hash.

  By representing all the project structure in a Merkle tree, Git is able to quickly evaluate which files were changed by comparing hashes and, with this information, make diffs, pull and push operations more efficient by only performing them on the files that changed.

• AWS DynamoDB: A high-performance NoSQL key-value store developed by Amazon, it uses Merkle trees to detect inconsistencies between replicas and minimize the amount of transferred data.

• BitTorrent protocol: BitTorrent is a famous peer-to-peer file sharing protocol that uses Merkle Trees for verifying the integrity of the data being downloaded.

  The data is divided into chunks of equal size and then each chunk is hashed. After that a Merkle tree is calculated from the data hashes and the root is included in the torrent file.

  Integrity of data pieces can be verified by calculating their hash and constructing the merkle path all the way up to the root. If the constructed root is different from the original contained in the torrent file, then we can be sure that that piece of data is corrupted and the protocol can efficiently download that chunk again.

  This is still a draft proposal.

In this article we will focus on the Blockchain use cases.

How is it used in Blockchain?

In the Bitcoin whitepaper, Merkle trees are used in several places to solve different problems. Before talking about how Merkle trees are used in Bitcoin, first we need to know how a Bitcoin’s block is composed

A block contains a list of all the transactions included in that block.Transactions in a Bitcoin’s block are sorted in an specific order and using their transaction id, a Merkle tree from all the transactions contained in that block is generated. It also contains a header with some useful information about the block itself such as block version, transaction’s Merkle tree root, etc. You can check all the fields here.

Blocks are uniquely identified through their block hash. The block hash is nothing else than the block header hashed twice with the SHA256 hash function. It is important to remember that the previous block hash is included in the block header and that is what creates the chain.

Data Integrity and Immutability

As we have seen, the transactions’s Merkle tree root and the previous block hash is included in all the chain’s blocks.

Imagine now that a malicious actor tries to change the n’th block of the chain by changing a transaction contained in it. Every transaction has a unique transaction hash, so, the malicious transaction will have a different transaction hash than the original:

This alteration will cause the intermediate nodes and the root to change, resulting in the block header and block hash changing as well. Since the (n+1)th block uses the previous block hash to calculate its own hash, and the previous hash has changed, new block hashes must be recalculated for all subsequent blocks.

This is a very complicated thing to accomplish for two reasons:

• Computing a single block hash takes around 10 minutes: Block hashes should have a certain number of zeros at the beginning. This is done by searching for a particular value for the nonce field in the header. If the Merkle root changes, there is a very, very low probability that recomputing the same block hash with the same nonce will be a hash that fulfills the condition of having a certain amount of zeros at the beginning, and, if this happened, there is an even lower probability that all the next blocks won’t need to change the nonce.
• You’ll need to overpower the network to convince honest nodes that the modified chain is the real one. This is known as the 51% attack.

As a result, blocks in a blockchain are immutable.

Simplified Payment Verification

By using Merkle Trees, payment verifications can be made in a more efficient way. A verifier can run a node that does not save all the transactions, just the block headers. To verify that a payment was made, it needs to verify that the transaction that backs up that payment is contained in some block of the chain.

Imagine we need to verify that Tx 6 is present in a block. The first thing to do is to retrieve from a full node the block where the transaction is located and some specific nodes (marked in green), known as “Merkle path”¹ from the Merkle tree. After that the verifier can compute the Merkle branch of Tx 6 (marked in blue) up to the root and validate that the transaction is included in the block n.

The whole verification process is very fast to compute and uses very little data, saves up disk space, and eliminates the need of transferring large amounts of data.

NOTE: Ethereum widely uses a variation of the Merkle Tree known as Patricia Merkle Trie. Check this for more information.

Conclusion

Although the Merkle tree is a simple data structure, its simplicity doesn’t make it any less powerful. Using simple yet clever solutions is one of the reasons that makes computer science a beautiful discipline.

If you ever find yourself in a situation where you need to verify data integrity or identify where data has changed, a Merkle tree is a good and efficient candidate that can help solve that problem.

Blockchain space is full of these kinds of solutions and many more will come in the future, let’s not forget that we are at the beginning of this journey and new applications for this technology are yet to be discovered. There is space for introducing clever solutions in those yet-to-be-discovered new applications!