Merkle Proofs and Merkle Trees in Blockchain — Explained
If you have been learning basic cryptography and how a blockchain works, I am sure at some point of time you have come across the terms “Merkle Proofs and Merkle trees”. In this article, I will make an attempt to explain these two topics as simply as possible.
Merkle Tree or Hash tree are a type of Data Structure made up of hash number of various data blocks of transactions performed in the blockchain network.
- It acts as a summary of all the transactions in a block.
- It also enables quick and secure content verification across big data sets.
- It also acts as an efficient way of verifying the consistency and content of a particular dataset without storing the entire dataset.
Merkle Proofs are generated by hashing a hash’s corresponding hash together and climbing up the tree until you obtain the root hash.
In context of a Blockchain, how is the implementation of a Merkle tree useful?
Imagine that there are a bunch of transactions that are waiting to be included in a block. To create your cryptographic proof that these pending transactions are included in the next block, we first construct the merkle tree from these transactions and we include the merkle root hash into the block.
If Alice wants to know if her transaction was included in the block all she has to do is get these four hashes, compute the merkle root hash and then compare with the merkle hash that was committed to the block. If the two merkle root hashes are equal then she knows that her transaction was included in the block.
Another way to create a proof that a transaction was included in a block is to concatenate all of the transaction data and create a single hash from it. The problem with this approach is that in order to recompute the hash you need all the transaction data, so if there was 1,000 transactions in a block and if Alice wants to know if her transaction was included in the block then she will have to download all 1,000 transactions and then compute the hash. However, using the merkle tree she only needs to compute Log2(1000), i.e., only 10 hashes.
Merkle trees are one of the most essential fundamentals of blockchain and a direct implementation of a data structure. One of the most popular usecases of merkle trees in the recent years are NFT Merkle Airdrops.
Here is a basic implementation of a merkle tree for a NFT drop:
To get more familiar with the concept, you can also play around with MerkleTreeJS.
