What is Merkle proof and why do we need it?

In the last article, we discussed the Merkle tree and how we can use that to ensure integrity, that is, to make sure that no transaction got added to the block after a miner mined the block. In this article, we will be looking at Merkle proof and how we use that in blockchain.

We have seen when creating a Merkle root, we pair transactions, hash them, pair the hashes, and hash them again until we end up with just one hash, which we call the Merkle root. This Merkle root serves as proof that all the transactions in the block have been verified. Further, it proves that no transaction was added to the block after a miner mined the block. A blockchain node can confirm this simply by repeating the process of generating the Merkle tree from the transactions in the block and comparing the obtained Merkle root with the Merkle root in the block header.

Why do we need to hash transactions in pairs?

Now, the question is why bother creating the Merkle root by pairing transactions, when we can hash all the transactions together? By the look of it, hashing all the transactions together seems like an easier process than generating the Merkle root. So, why do we still use the Merkle root?

Blockchains will be still functional even if we hash all the transactions together. But this can result in performance issues. In order to verify a block, a node has to download all the transactions in a block before hashing them together. Then, the node has to compare the hash to the hash in the block header. This may be too much work for nodes that lack resources.

Let’s try to see this with the bookshop example we used in our previous articles. In that example, we saw how we sent a transaction to a bookshop to buy a book. Now, the bookshop’s blockchain client needs to check if the block containing my transaction addressed to it is valid. To do so, it will have to download the whole block along with all the transactions to verify the block.

Merkle proof

However, if the client has limited resources, then this could be a very difficult task. Here is where the Merkle root becomes extremely useful. When we use Merkle Root, the client needs to download only the Merkle proof. But what is Merkle proof? The Merkle Proof is the hash of the concerned transaction, its sibling transaction’s hash, its parent hash, and the parent’s sibling hash, up to the root hash.

It’s a bit too much to grasp, I know. So, let’s look at an example. Consider this Merkle tree that we created in the previous article.

If we assume that A is the transaction that we sent to the bookshop, then the Merkle Proof will consist of the hash of B (hB), h(hA, hB), h(hC, hD), h(h(hA, hB), h(hC, hD)), h(h(hE, hF), h(hG, hH)), h(h(h(hA, hB), h(hC, hD)), h(h(hE, hF), h(hG, hH))), and (h(h(hI, hI), h(hI, hI)), h(h(hI, hI), h(hI, hI))).

Now, to confirm that transaction A is a part of the block, the client just needs to hash A, pair the hash with hB and climb up the tree until the root hash is obtained. The advantage here is that you don’t need to download and hash all the transactions and create the whole tree. If the hash we obtain thus is equal to the Merkle Root, then that means the transaction is reliable. This way we can confirm that the transaction is valid without downloading all the transactions and hashing them.

Simplified Payment Verification

This becomes extremely useful in Simplified Payment Verification (SPV). Clients using SPV download only the block headers leaving behind the transactions found in the block. This greatly reduces the download size of a blockchain. And to verify a transaction, the SPV clients can simply obtain the Merkle proof.

To see how game-changing this is, consider this data. An SPV client only needs around 50 Mb to be functional whereas a normal client will require several gigabytes of space to be functional. This allows less powerful devices such as mobile phones to accept and perform blockchain transactions.

In this article, we talked about the Merkle proof and how it helps us reduce the amount of data we need to download to verify a blockchain transaction. We also saw how we use the Merkle proof in Simplified Payment Verification (SPV) clients that run on low-powered devices.

Thus far in our previous articles, we have discussed the Proof-of-Work consensus algorithm, how it helps establish blockchain consensus, the structure of a block, and the Merkle root. Now, have you ever wondered why anyone would want to take great pains to mine a block? What do they get in return? How are transactions packed into a block? In the upcoming articles, let’s elaborate on the process of mining in detail and try to answer these questions.