Understanding Merkle Tree

Why is it important in Blockchain?

Merkle tree, also known as the hash tree was named after Ralph Merkle who patented it in 1979. Merkle tree is a binary tree which helps in an efficient and secure record validation in any network irrespective of the amount of data in the network. Because of this unique property, Merkle tree plays a significant role in the blockchain network where the transaction records in the ledger are boundless and no one can delete it. In a Merkle tree, the nodes store cryptographic hashes instead of data values and this is actually the underlying technology which makes it work. For understanding how exactly Merkle trees work and what makes them so important we first need to get an idea of what cryptographic hash functions are.

Cryptographic hash functions

Cryptography or hashing, in general, is something which is largely used in any blockchain system. To understand it in simple terms, cryptographic hash functions can be thought of as a black box to which we provide input and receive an output which is fixed in length. This fixed length output is termed as a cryptographic hash or hash.

The output of a particular data value will always provide the same hash but if any change is made to the value, a new hash gets generated. So even if a record is changed only by a character, the difference can be spotted by the changed hash of the data value. The hashing algorithm used in a cryptographic hash function is open for choices but the most widely used hashing algorithm is the SHA-2 (Secure Hash Algorithm-2).

Now, since we have a basic understanding of how cryptographic hash functions work, we are good to move forward to understand the working of a Merkle tree.

Understanding Merkle Tree

As stated earlier, the Merkle tree is a binary tree. The leaf nodes in a Merkle tree contains the hash of the transaction data and every other node is a hash of its underlying nodes. The Merkle tree is created by repeatedly hashing the pair of nodes until we are left with only one hash. This hash is called the Root Hash or the Merkle Root. Since Merkle trees are binary, they need an even number of leaf nodes but in case the number of transactions is odd, then the last node is replicated to create an even number of leaf nodes.

Let’s look at an example for better understanding: Let us consider that we have 4 transaction records namely — txA, txB, txC and txD. These transaction records are hashed and stored in leaf nodes A, B, C and D respectively. The consecutive pair of leaf nodes is then supplied to a cryptographic hash function to form another single hash. Let’s say the leaf nodes A and B form a node AB and the leaf nodes C and D forms another node CD. These two hashes AB and CD are then supplied to the cryptographic hash function and we obtain the final hash. Since this is the last hash of this Merkle tree, we call it the Merkle root (ABCD). This is how a Merkle tree is generated.

Merkle tree in blockchain

As stated earlier Merkle tree plays a significant role in the blockchain network, let us try to understand the why behind it. A blockchain is a continuously growing list of records or blocks which are linked to each other. Each block in the blockchain contains a hash pointer to its previous block, transaction data and timestamp. These transaction data can be stored in blocks, which are actually the leaf node of a Merkle tree and the root hash can then be stored in the block. So these continuously growing records in the blockchain network can be stored in an efficient manner. Bitcoin was the first blockchain network to use the merkle tree. It uses the SHA-256 hash function for creating the hashes and hence the Merkle tree. The created Merkle root is 32 bytes in size.

Merkle tree helps in checking whether a transaction is tampered or not. If anyone tries to change the transaction then as discussed earlier its hash also changes. Now, the change in a hash of this specific transaction will lead to changes in the subsequent hash generated with the previous nodes and hence the Merkle root will differ from the original Merkle root and therefore not even a slightest of change can be performed.

Apart from providing a tamper-proof network, Merkle tree also helps in verifying a transaction. With the help of the merkle tree, we can verify whether a particular transaction has been included in a block of our network or not without having to download the entire blockchain. If Merkle tree would not have been there then to check whether a transaction belongs to a block or not we would need to download the whole copy of the ledger and compare it with every record. But luckily with the Merkle tree, the scenario is much simpler and efficient. We only need to check the lightweight hashes for verifying a transaction, to validate whether a transaction was a part of the ledger or not we will only need the nodes which will be helping to make the Merkle root/root hash rather than requiring each and every node.

Conclusion

Merkle trees are an efficient and secure method to organize large data records. Its application in the blockchain world is very powerful as one of the important features of blockchain the immutability of the ledger can be handled well by maintaining the records in a much efficient manner. Imagining the blockchain to have the same power without the existence of the Merkle tree is not even possible.