Merkle Trees are a fundamental component of Blockchain technology and allow them to function with transaction integrity.
To develop an understanding of decentralized systems and their efficient functionality, let us start from the basics.
What is a cryptographic hash function?
A cryptographic hash function is a function which takes an input and gives an output of fixed length. The resulting hash from the arbitrary input is not only fixed in length, it is also completely unique to the input and the function itself is deterministic, i.e. if you run the function on the same input, the output will always be the same.
Notice how in the first and second examples, even though the difference of the inputs is only one word, the resulting outputs are completely different. This is very important as it allows for “fingerprinting” of data.
Since the output of the hash function is always fixed, huge amounts of data can be identified by their hash function.
Merkle Trees
Now, Merkle Trees are basically data structures where each non-leaf node is the hash of its respective child nodes. The leaf nodes are the lowest tier of nodes in the tree. Merkle trees are binary and therefore require an even number of leaf nodes. If the number of transactions is odd, the last hash will be duplicated once to create an even number of leaf nodes.
Essentially, Merkle Trees are data structures that can take ‘n’ number of hashes and represent it with a single hash. In blockchain terms, a Merkle Tree summarizes all the transactions in a block by producing a single fingerprint of the entire set of transactions. It maintains the integrity of the data. If a single detail in any of the transactions or the order of the transactions changes, so does the Merkle Root. Using a Merkle tree allows for a quick and simple test of whether a specific transaction is included in the set or not.
The single code that a Merkle Tree produces is called the Merkle Root. Each block in a blockchain has exactly one. The Merkle Root is a crucial piece of data because it allows computers to verify information with incredible speed and efficiency.
Now let’s look at a bigger Merkle Tree
Now let’s suppose we want to validate a transaction ID in this tree.
Fred says that he paid George a certain sum of Bitcoin.
He says “Ask me no questions and I’ll tell you no lies ”.
HAHA, I’m sorry, Fred, that’s not how it works, we need to verify whether you actually sent Bitcoins to George.
Fred obliges and tells us that the transaction ID to be verified is HE.
We already have the block’s Merkle Root, so Fred doesn’t need to send us that. He also sends us 4 hashes: HF, HGH, HABCD and HIJKLMNOP. That’s all the information that needs to be sent or received to verify Fred’s payment to George. These 4 nodes are collectively known as the “Authentication Path” of HE. Let’s see how we verify the transaction using the Authentication Path of HE.
We start by hashing the first code HF with the transaction ID HE, which gives us the result HEF. Fred didn’t send us this code but he didn’t need to because we’re using the same hashing algorithm as him. Therefore, we receive the exact same results.
We then take the second code Fred sent us, HGH, and hash it with the new code HEF we just derived. This, of course, produces the number HEFGH .
Then, we hash the third code Fred gave us, HABCD, with the other new code we received, HEFGH, and we end up with the correct Merkle Root: HABCDEFGH.
Finally, we hash the fourth code Fred gave us, HIJKLMNOP, with the other new code we received, HABCDEFGH, and we end up with the correct Merkle Root: HABCDEFGHIJKLMNOP.
This procedure is sufficient to verify that Fred actually paid George and didn’t just lie that he did.
Notice that we only need 4 nodes from Fred and only had to run the hashing algorithm 4 times to see that Fred’s transaction is valid. That means our computer has done less than half the work that would’ve been required to verify the entire Merkle Tree. But more than half of the tree isn’t necessary to verify Fred’s transaction! In this example, the number of transactions is only 15, while in reality, blocks in a Blockchain contain several thousands of transactions.
It’s easy to see how Merkle Trees increase efficiency so dramatically.
– Nishanth Subramanian