Simplified Explanation Of the Merkle Tree in Bitcoin
Balogun Malik
What is a Merkle Tree?
A Merkle tree is a data structure used for data verification. According to the author of the Mastering Bitcoin book:
A Merkle tree, also known as a binary hash tree, is a data structure used for efficiently summarizing and verifying the integrity of large sets of data
How Merkle Tree Works
Merkle trees are depicted by an upside-down tree-like structure. In this tree, there are leaves known as leaf nodes. A leaf node on the Merkle tree is the hash output of an input (a bitcoin transaction in this case). The hash is done using a secure hash algorithm (SHA).
There are two possibilities when using the Merkle tree:
When the number of leaf nodes is even.
When the number of leaf nodes is odd.
When the number of leaf nodes is even, the hash outputs of the nodes are paired and hashed until one hash output is obtained. The output is unique for every input, and this enables fingerprinting of data. So, huge amounts of data can be easily identified through their hash.
When the number of leaf nodes is odd, the hash outputs are paired, but since the number of leaf nodes is odd, there will be one left, and this remaining node will be duplicated to make the number of leaf nodes even and then hashed till one hash output is gotten.
Merkle Root
Merkle root, or root hash, is obtained through the recursive hashing of pairs of leaf nodes in a Merkle tree until one hash is obtained. Previously, while explaining how the Merkle tree works, it was mentioned that Merkle tree leaf nodes are paired and hashed until one hash output is obtained. This output is known as the Merkle root or root hash.
When N data elements are hashed and summarized in a Merkle tree, you can check to see if any one data element is included in the tree with about log2(N) calculations, making this a very efficient data structure. - Andreas M. Antonopoulos
Merkle proofs are used to verify that the information is correct. A Merkle proof takes the piece of information you're looking for and searches all of the 'branches' of the tree that connect to it, all the way up to the root hash. If the hash is consistent from branch to root, it is true. If the root hash does not match, the data has been tampered with. The branches that were searched to get the data are called the Merkle path
Merkle Tree in Bitcoin
Merkle trees are used to store all transactions within a given block. The benefit of this system is that one node can easily demonstrate to another that a given transaction was contained in a specific block. This is useful for SPV nodes and light clients, which do not store the entire blockchain and are only interested in specific transactions or blocks.
For example, if Alice has a wallet and is waiting for her transaction to be confirmed but does not run a node, she can request a Merkle proof from Bob, who runs a full node. The proof convinces Alice that the transaction she is interested in is included in a valid block, without Bob having to share all of the transactions or the entire block with her.
The Merkle tree has the advantage of proving the presence of any given transaction without revealing the entire Merkle tree. For example, in a Merkle tree with eight transactions, only three hashes are required to demonstrate that one of the transactions was included in the tree. This is especially useful for light clients, which do not store the entire blockchain and must rely on other nodes to confirm specific transactions.
Summary
In this article, we talked about the Merkle tree and how it works. The Merkle tree is a useful data structure in Bitcoin. It is useful for verifying data consistency that is supposed to be available in many places. This makes verifying the Bitcoin blockchain transactions easier for SPV nodes.