Merkle trees explained – Part 2: How verification of presence works

In part 1 of this article, we tried to understand what merkle trees are and the concept behind. We know that merkle trees help us in verifying whether a particular data point is the part of the tree ( merkle root ) or not. In this part, let’s go through exactly how this process of verification works.

Let’s revisit the merkle tree from the last part again.

Let’s say we want to verify that transaction E is the part of this merkle tree, given the merkle root H_ABCDEFGH. We don’t want to loop over every leaf node of the Merkle Tree, as it can be quite large, so how can we do this in a more efficient way?

The main idea is as follows: We give the verifier function the value of leaf node for E ( H_E) along with all the relevant nodes from the tree that get hashed up together to build up the new root hash New-H_ABCDEFGH. The verifier function can compare New-H_ABCDEFGH against H_ABCDEFGH that we already have. If they are the same hash, it must mean that E was in fact present in the Merkle Tree, as you could not have generated the same Merkle Root hash with different input data.

Lets try to understand this with an example. In the above example, following values need to be given to verifier function in order to prove that E is the part of the merkle tree.

• Value of E itself (so the function can compute H_E on it’s own)
• H_F, so the verifier can compute H_EF.
• H_GH so the verifier can compute H_EFGH
• H_ABCD so the verifier can compute H_ABCDEFGH

As shown in the above diagram, we only need to provide values in yellow, in order to prove that E is a part of the tree.

Again it is important to remember that only one given combination of nodes can generate this unique root r because the Merkle tree is a collision-resistant hash function which means it is a hash function that given two inputs is almost impossible to produce the same output.

This concept of verification using merkle trees is used by miners in validating the blocks. However, merkle trees are also used in Git, IPFS and other places where we want to check if something has been changed in a large chunk of the data. We can also use merkle proofs in smart contracts to verify the validity of an entity e.g. account interacting with the function, if a particular transaction hash is valid. Lets go through how we can use merkle proofs in smart contracts in the next post. Until then, you know where to find me for questions, discussions and anything else. ( Hint: footer of my blog )