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.

Merkle Proofs

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.

How does Radix use Merkle Trees?

Radix uses logical clocks to provide a simple and reliable method for nodes to record and recall events in the order they have witnessed them. While these logical clocks are simple and reliable, they do not provide any security against nodes tampering with the logical clock values that it has assigned to events.

To ensure the assigned logical clock values are tamper-proof, nodes produce “Commitments” which are an ordered, cryptographically secure, compact representations of the events witnessed by a node.

A Merkle tree is constructed and populated with the hashes of all events witnessed by the node since its previous commitment, from which a Merkle root hash can be derived. A commitment is then created, consisting of the Merkle root hash, the node’s logical clock and wall clock, plus some other elements that are included in order to assure validity and authenticity. This commitment is then signed using the node’s private key.

These commitments form a linked sequence over time, where the first leaf of a commitments Merkle Tree references the previous commitment a node has submitted, unless it is the initial commitment to the Universe.

The commitments a node has produced and submitted to the network may be audited by other nodes at any time. When a node is the subject of an audit, it should deliver the leaf hashes in logical clock order, to the auditing node. The auditing node will then reconstruct the commitment hash and verify its integrity

For example, if the logical clock value of “Commitment 1” was 100 and logical clock value of “Commitment 2” was 200, then “Commitment 2” should represent 100 events. If an auditing node cannot find 100 hashes, or the Merkle root hash of the submitted commitment does not match the Merkle root hash of the reconstructed commitment, then the node being audited has either tampered with its logical clock, or has tampered with events, or both.

The possibility of an audit by other nodes at arbitrary times discourages tampering of logical clock values and commitment sequences as it is easily and cheaply detectable in all cases.

Conclusion

This post is intended to show how Merkle trees can be used to provide assurances of data integrity in a trustless environment, where not all data is available, and simple hashing will not be suitable.