Hash functions solve the important problem of uniquely identifying a given digital message. Sometimes, however, a collection of messages needs to be identified and referenced as an ordered list. This problem can be solved through Merkle trees.
This post is part of the extended series Bitcoin from Scratch.
A Merkle tree is a tamper-evident data structure that allows a collection of messages to be identified and queried as a single unit. Adding, removing, editing, or reordering the collection’s members produces detectable changes. Merkle trees are used extensively in electronic cash systems as a way to ensure the integrity of a list of messages.
Construction of a Merkle tree follows a simple procedure. First, the list of messages is sorted in some way. For example, they may be sorted in order of receipt. Next, the hash value of each message is computed. This yields the bottom level of the tree. In order of appearance, each hash value is paired with its successor. If no successor exists due to odd level membership, then the last hash value is paired with itself. Appending the second member of a pairing to the first and hashing the result generates the next level.
Pairing and hashing continues until only one hash value remains — the Merkle root. The Merkle root is the top level hash value of a Merkle tree. Editing the collection of messages on which a Merkle tree is based changes the corresponding Merkle root. Even reordering messages changes the Merkle root. Given a Merkle root, a list of messages can be decompose, individually transmitted, and reassembled. The receiver can use the Merkle root to detect any changes during transmission.
The utility of Merkle trees may not be readily apparent. After all, a unique identifier for a collection can be generated naively by concatenating all members together and hashing. The resulting value will change if the underlying collection changes in any way.
This approach works best when lists are small and the entire list is required. However, these two conditions rarely hold in electronic cash systems. Often, we’d like to prove that a small number of messages belong to a much larger list. The reasons will become clear in later installments of this series.
For now, imagine trying to prove that a message belongs to a very large list using the naive approach. The only way to do so would be to request every message and confirm that the one to test is among them. Hashing the collection and comparing the result with its identifier would demonstrate that the message was a member. The main problem is that the expense of performing this test increases linearly with collection size. Although small collections could be handled with ease, larger collections may become impractical to query.
Merkle trees offer far more efficient membership checking when used together with a Merkle proof. A Merkle proof consists of the hash values needed to construct the branch (or path) of a Merkle tree containing a message of interest. Instead of requiring all items of a collection to test for membership, a Merkle proof can be completed with only some of them.
Merkle proofs for a given message are constructed using a modification of the procedure for constructing the full tree. First, the messages of a collection are sorted and paired as before. The hash value for the sibling of a message of interest is then added to the proof. The tree is then walked upward. At each level, the missing hash value is added to the proof until the Merkle root itself is added. These hashes, together with the index of the item of interest, are conveyed as the proof.
Given a Merkle proof and message, membership can be tested as follows. First, the message is hashed. The resulting hash value is then concatenated with the bottommost sibling hash value of the proof. The item’s index reveals whether it’s the right or left item of the pairing. The concatenation is hashed, yielding the parent hash value. Concatenation and hashing continues up the chain. Obtaining the Merkle root in the last step proves the message’s membership in the list.
Hash functions and Merkle trees enable messages to be grouped efficiently and securely. Many sophisticated behaviors that electronic cash systems exhibit can be traced to this simple principle.