The Tale of Merkle Tree in Bitcoin Blockchain
Good Day All,
This article is a continuation of my previous write-up on the Merkle tree intending quick gulp on the knotty topic. I have already explained what a Merkle tree is, how it is incredibly valuable when it comes to a record-keeping database like Blockchain. If you have missed my early piece of writing, do check it out here before proceeding.
With no further ado, let’s get to the agenda. The intention of this article is to explain the role of the Merkle tree in the blockchain, specifically saying Bitcoin blockchain.
We know, the blockchain data structure is a back-linked list of blocks of transactions, which is ordered. Blockchain, therefore, demands a robust data structure that can represent the whole set of transactions recorded in a block, also efficiently performing the search and retrieval operations. Let’s inquest has Merkle Tree got to do anything in this regard.
So before we proceed, let’s have a quick brief on what blockchain is as the term is to bother you often here.
What is blockchain?
In its simplest term, Blockchain is a distributed record-keeping technique, built on a peer-to-peer network. The transactions within the network are verified by the peers, grouped into blocks, which are chained together to form “blockchain”. Adding more sprinkles, every participant (node/peer) in the blockchain network holds a copy of the blockchain flagging it safe and transparent.
Going down the line, understanding a block in a blockchain, each block has two parts: header and body. While the transactions are recorded in the body part of the block, the header compliments holding certain pivotal information pertaining to the block.
While the field- timestamp stores the time at which the block got created, nonce seems to be a random number. Root hash value is a unique representation of all the transactions recorded in a block. Yes…..this value is computed using the Merkle tree. The transactions within the block are first converted to hash values using the SHA256 algorithm. Merkle tree is constructed on these hash values and the Merkle root is recorded in the root hash field.
Let’s get it better via an example. Consider a block containing 4 transactions. A Merkle tree is constructed and the block representation is shown below.
Now we know what a Block is.
Let’s see how are they’re “chained”?
The previous hash field is the binding force or the glue for chaining. Block stores the hash value of the previous block in the header, thereby acting as a pointer to the previous block. Adjacent blocks are linked by hash pointers, forming a chain of blocks.
If any changes are made to a block, subsequently its hash value will also change. If the hash value of a block changes, the previous hash value of the following blocks will become invalid, breaking the linkage of blocks.
Transaction Verification in Block
The decentralized, distributed nature of blockchain requires every node to keep a copy of the blockchain. Like any other distributed system, the peers in a blockchain network cannot be fully trusted. So we need an efficient mechanism to verify the transactions. Let us see how the Merkle tree can help.
For that let’s assume a scenario.
Imagine a group of people running a business. Assume the business is in the expansion stage resulting in a high number of transactions. To meet the requirement, the group is getting switched to a blockchain network.
Let’s see how blockchain does this job. In a blockchain, whenever a transaction occurs between two users, it will be broadcasted among all the nodes in the network. All of them will verify the transaction and add it to their copy of the blockchain.
Now the question is, how a user can keep track of thousands of transactions occurring per day?
Well! they can’t keep listening to the transaction alert every minute of the day. Also, all the transactions happening within the network will not be relevant for a user. This problem was solved by introducing a mobile app/mobile wallet for transactions. The app will notify a user whenever a transaction involving that particular user is broadcasted in the network. So a user will get an alert that includes the transaction and the header of the block which contains the transaction. This idea turned functional as it reduced the storage overhead as each user is keeping a copy of his/her personal transactions only.
Once, Amith transferred an amount of Rs. 10k to Sruthi via the mobile app. The transaction was successful and Amith got the confirmation in his mobile app. The block that recorded this transaction looked like below. The information which Amith got is highlighted
However, Amith is not sure whether his transaction is communicated properly among all the peers in the network. So he wants to verify whether his transaction is a part of the given block.
Who can help Amith?
Well… the Merkle tree can. Amith knows the Merkle root, which is stored in the root hash field of the header and also the transaction hash HK. One can re-calculate the root hash of the block based on this data. If they match, Amith can be sure of his transaction imprinted in the specified block.
We have already summarized the concept of the Merkle path in the previous article. In a blockchain, Merkle path or transaction proof for a transaction consists of siblings of all the nodes along the branch connecting Merkle root and leaf node representing the transaction. Here the Merkle path for Amith’s transaction(TK) is HL, HIJ, HMNOP, and HABCDEFGH.
Now the upcoming question is who provides the Merkle path for calculating the root hash?
Since every peer in the network has a copy of the blockchain, we can query the network for the missing values. So starting from HK, let us traverse the tree in an upward direction, recalculating the hash values on each node in the branch which connects Merkle root and HK. Finally, when we reach the root node, we will get the root hash value. If it is the same as the root hash value which Amith holds, we can assure him that his transaction is successfully recorded in the blockchain.
Now let’s get back to square one- Bitcoin. The task which we did for Amith is done by a special category of nodes called Simplified Payment Verification (SPV) nodes in the network. To brief, SPV nodes are special nodes in a blockchain network that helps in verifying any transactions are included in a block, without downloading the entire block. SPV nodes download only the block headers from the network. Using the Merkle path they can verify if a transaction is included in a block.
Why choose Merkle Tree for Bitcoin?
Bitcoin was the first blockchain that implemented Merkle trees effectively. Let us see how Merkle trees have helped Bitcoin.
- Search operations are performed on the hash values, instead of actual data. Even a small alteration in data can result in an entirely different hash value, which helps to identify the changes easily.
- In the example which we discussed, though the block contains 16 transactions, we required just 4 hash values to check whether a transaction is present in that block !! If we try to search the transaction records one by one, then we should go through 10 transaction records to reach TK, which is time-consuming. Merkle tree helps us to perform the verification faster.
- SPV nodes rely on Merkle trees and do the verification by downloading only the block headers. If Merkle trees are not used, nodes should download the entire copy of the blockchain for verification purposes. This will result in high network traffic and requires a larger storage capacity. Merkle tree enables verification of transactions to be done efficiently even on mobile devices having limited hardware and networking resources.
- As already mentioned, the hash representation also contributes to the storage efficiency and time efficiency of the Merkle tree. The integrity of data can be easily validated as any changes to the transaction data will change the hash values also. Any change in the root hash will make the previous hash fields of the following blocks invalid, resulting in a “break” in the blockchain.
In short, the Merkle tree proves to be an excellent choice to represent a distributed list of transactions. It performs data verification quickly without any storage overhead.
Hope this article turned useful. We’ll be bringing more relevant articles on Merkle Tree and Bitcoin, therefore stay tuned to our Medium Page. Also, subscribe to Kerala Blockchain Academy’s Youtube Channel for interesting blockchain videos.