Crypto Intro: Merkle Trees
Note: This article was produced for RadixDLT and the original can be found here.
We have previously looked at hash functions, exploring how they increase the efficiency of DLTs by allowing us to quickly check transacted data. In this article we turn our attention to Merkle Trees, another fundamental component of many protocols and which are built on the use of hash functions.
What are Merkle Trees?
Merkle Trees are a means of organizing data and allow for large amounts of data to be ordered and verified quickly. They are named after Ralph Merkle, who conceived of them in 1979. Although there are a number of different types of Merkle Trees, they are most commonly represented by an illustration such as the below which sets out how Merkle Trees are ordered.
This diagram also illustrates how Merkle Trees are formed. At the top sits the root hash. In Bitcoin and other blockchains for example, this root hash would be the hash of the block header. This root hash is derived from hashing together the two child hashes underneath it. These are in turn derived from hashing together the pairs underneath them, and so on.
This works by pairing up all transactions in a block, with each transaction represented by their hash. If there is an odd number of transactions in a block then the last one left would be initially paired with itself. Therefore 2048 transactions would become 1024 pairs, which when hashed would become 512 pairs and so on until only one, known as the Merkle Root, is left. This process means that no matter how many original transactions there are, we can use Merkle Trees to reduce them to just one. Therefore, whether the original number of inputs is a small or large amount, the ultimate result will always be the same.
A Merkle proof is a subsection of a Merkle tree that can be used to prove that a given piece of data is a part of a Merkle tree. Take for example, the data blocks TD through TH shown in the image below.
If Alice was to send data block Td to Bob and wanted to provide assurance to Bob that the data in the block was correct and undamaged/untampered, she could also send the parts of the Merkle tree Hc, Hab and Hefgh. Bob could then use these pieces of information as follows:
Calculate Hash(Td), giving Hd
Calculate Hash(Hc || Hd), giving Hcd. Note that Hc was provided by Alice.
Calculate Hash(Hab || Hcd), giving Habcd. Note that Hab was provided by Alice.
Calculate Hash(Habcd || Hefgh), giving Habcdefgh, which is the Merkle root hash. Note Hefgh was provided by Alice.
Bob compares the calculated Merkle root hash to his Merkle root hash.
Note that it is easy to see that the size of the proof is proportional to the height of the Merkle tree, and therefore logarithmic with the total size of the data.
Why are Merkle Trees important?
As has been touched upon, Merkle Trees play an important role in DLTs. They allow networks to use hash functions in a scalable fashion, owing to the pairing and tree format they adopt. Although the image above portrays a limited Merkle Tree, they can run to hundreds and thousands of pairs. This is where they are indispensable, as they allow for data integrity to remain while increasing the speed at which it can be verified, even when they are having to process extremely large sets of data.
Given the number of transactions in a block, and the number of blocks processed over time, the impact of Merkle Trees on reducing the amount of data to be processed is hard to overstate. This data saving Is important, because it increases efficiency and thus means the network is more scalable.
By reducing these large sets of data to an ultimately much smaller amount, Merkle Trees make the verification of data a less resource-intensive process. This is why the original Bitcoin whitepaper notes that Merkle Trees can be used for Simple Payment Verification (SPV) nodes, because it means SPV nodes don’t need to download the entire blockchain, but rather can take the Merkle Proof and check that it is present in a Merkle Tree with the correct block header. Operators can run the SPV rather than ‘full’ node, while still allowing such nodes to swiftly check that provided information is correct as they allow for SPV nodes to quickly check that a transaction that Bob is claiming was included in block X actually was.
Furthermore, it means that we can subsequently verify transactions much faster. We only need to know a few of the hashes to be able to verify that the hash we are verifying is correct. This is because of the nature of hash functions, as we previously explained, which means that if one bit of data is changed it will change the resulting hash drastically.