## Introduction to Merkle Trees

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.

## Introductions

Hey, I’m Max! I code. A lot. And, through a mix of trial-and-error, efficient Googling, and the occasional stroke of absolute luck, I end up solving problems, learning new things, and devising what some might politely call ‘unique’ solutions to a variety of challenges.

This blog serves primarily to document my discoveries, and act as a platform to publish semi-polished notes about whatever catches my interest. I’m the lead developer on the Curecoin project (a cryptocurrency aiming to provide a tradable store of value based on scientific computational contributions), so you’ll see content related to my development work on this blog.

I currently program primarily in Java, but have varying proficiencies in a variety of languages, and as time progresses this blog will document my journeys through them.

Many of the posts here will address some frequent problem or process in need of a simple tutorial which I will sprinkle with jaggedly Photoshopped supplemental images. Others will be some solution to an obscure issue I’m particularly particularly proud of, and the remainder will be some assortment of content that seemed at least moderately useful to preserve online.

Content will primarily encompass programming, networking, security, and the occasional, unnecessarily-complex meandering quest through Linux. This blog isn’t particularly geared towards any kind of consistent readership, and I’d expect the majority of my traffic to come from frustrated Google searches. But if reading a series of posts about solving problems you’re not having defines your version of fun, help yourself to the RSS feed on your left.

While not the focus of this blog, I also enjoy hiking, weightlifting, and casual gaming, so intermittent references to these might find their way into my posts.