If the word ‘Merkle’ brings out suppressed memories of drawing pyramids of meticulously-labeled connected boxes on Post-it notes, you’re probably familiar with a diagram like this:
To quickly cover terminology, a ‘leaf’ is one of the bottom boxes, which contain some representation of source data, and a ‘node’ is any other box. Leaves are also technically nodes—but who cares.
Each node contains some representation of its children, which is generated by some function that can take the children, perform some math, and spit out a repeatable, irreversible output for each pair of children. As it turns out, hashing functions do exactly this, with some added bonuses of fixed-length output and (hopefully) enough collision resistance to make even self-driving cars jealous.
Say we have some hash function defined as H(message), where H takes one argument (often called a ‘message’), and spits out one output. The ‘+’ sign is the concatenation operator, however almost any method of combining children would be valid.
It’s important to note that the top box in the above diagram wouldn’t calculate H(H(AB + CD) + H(EF + GH)), instead it would calculate H(child0 + child1), as H(AB + CD) has been stored as child0 and H(EF + GH) has been stored as child1. For any traditional Merkle Tree with n elements, generation of the full tree requires n – 1 hashes.
Any Merkle Tree concerned with maintaining the secrecy of leaves during verification can use a modification where each leaf is hashed before being used, so for a tree of n elements, 2n – 1 hashes are required. In both cases, the work required to generate a Merkle Tree scales linearly with the number of leaves.
In order to save the tree for later use, generally everything except the original leaves are saved. In some instances, saving and transmitting only the very top hash (the ‘Merkle Root’) is required.
Verification involves tracing a path back up the tree—if your original leaf when followed up the tree produces the same Merkle Root, the leaf is identical to the original leaf used in building the tree. However, if the leaf has been altered, the Merkle Root won’t match the original.
In order to store a Merkle Tree with the above hashed leaf structure, all elements besides the input leaves are stored. Flat files for each layer or layers separated by some form of delimiter are popular choices. Now, our tree structure looks like this:
All stored boxes are shown above in blue. Merkle trees are generally numbered starting from 0 (on the left) and counting up, starting over for each row.
Layers are generally numbered starting from zero:
Now that we’ve defined a Merkle Tree, we can actually use one! It’s June, and Jane wishes to prove that she has 8 files (numbered 0 through 7) at this time, without revealing the contents of the files. She builds a Merkle Tree, putting each file as a leaf on layer 0. She computes 15 hashes (2(8) – 1), and generates her final Merkle Root, which sits at (4, 0). She then tells this Merkle Root to the world (or anyone that wants to listen in her crypto IRC channel). Maybe these documents are market predictions that she won’t reveal until they expire. Maybe she’s organizing a lottery of some sort. Perhaps she is publishing an identity she can use to sign future communications (more on that in the next post, Lamport Signatures can’t be squeezed into two paragraphs).
Three months pass, and she wants to prove that file number 4 was part of her original Merkle Tree. She then reveals (1, 5), (2, 3), and (3, 0), and anyone who cares to check can follow her file back up the tree and verify that it was the original file—if the Merkle Root of the new tree match the original Merkle Root, the file must have been the original file (unless the hashing function produces a collision. Use a good hashing function!).
Anyone interested in verifying her file doesn’t need to (and can’t!) recalculate the entire tree. However, they can calculate the ‘authentication path’ she provides. Due to the one-way nature of good hashing functions, Jane can’t create a fake authentication path.
As someone who wishes to verify Jane’s claim that file 4 was a file that existed at or before the time she published the original Merkle Root, I follow file 4 back up the tree:
–>1.) Hash file 4
–>2.) Concatenate result of 1.) with element (1, 5)
–>3.) Hash result of 2.)
–>4.) Concatenate result of 3.) with element (2, 3)
–>5.) Hash result of 4.)
–>6.) Concatenate result of 5.) with element (3, 0)
–>7.) Hash result of 6.)
–>8.) If the result of 7.) matches the original Merkle Root Jane published in June, file 4 must have existed when she published the original Merkle Root!
Great, how are they useful? Aside from an interesting optimization exercise, Merkle Trees have found their way into databases, networking, file systems, and cryptocurrencies. They provide a quick way to represent large quantities of data with a small set of data. Generally, a hash function is applied to a file, and can be applied at a later point in time. If the digest (or output) doesn’t change, the file hasn’t changed. In a similar fashion, Merkle Trees can make sure a collection of files haven’t changed—and can be used to discover which files, if any, have been modified.
Similar behavior can be created from a variety of other cryptography methods, such as a hash list, however Merkle Trees offer data size and processing requirement advantages. With a hash list, ALL data (or hashes of all data, depending on organization) must be available and ordered, and a hash over all of this data must be computed. With Merkle Trees, only small sections of the tree must be sent and climbed to provide similar verification.
Additionally, Merkle Trees serve as the backbone for the Merkle Signature Scheme, which I’ll cover extensively in other blog posts. Dragging you through an explanation of Lamport Signatures and Merkle Tree Signatures in this post is probably prohibited somewhere in the Geneva Conventions.