What’s a Sparse Merkle Tree?

Merkle Trees

First, let’s start with a quick refresher on Merkle trees. Merkle trees give us a way to cryptographically commit to a set of data. We start by hashing each piece of data in the set, and then keep hashing our way up the tree until we get to the root node.

Proving Inclusion

The root of this tree is just a hash — it tells us nothing about the contents of the tree. We can use something called a “Merkle proof” to show that some content is actually part of this tree. For example, let’s prove that A is part of the above tree. All we need to do is provide each of A’s siblings on the way up, recompute the tree, and make sure everything matches.

Proving Non-inclusion

So we can easily prove that something is part of the Merkle tree, but what if we want to prove that something isn’t part of the tree? Unfortunately, standard Merkle trees don’t give us any good way to do this. We could reveal the entire contents, but that’s sort of defeating the point of using a Merkle tree in the first place.

Sparse Merkle Trees

Here’s where sparse Merkle trees come into play. A sparse Merkle tree is like a standard Merkle tree, except the contained data is indexed, and each datapoint is placed at the leaf that corresponds to that datapoint’s index.

Proving Inclusion

Just like in a standard Merkle tree, we can use a Merkle proof to prove that A is part of this tree. This proof looks just like your standard Merkle proof:

Proving Non-inclusion

Here’s where the magic happens. What happens if we want to prove that C is not part of this Merkle tree? It’s easy! We know that if C were part of the tree, it would be at the third leaf. If C isn’t part of the tree, then the third leaf must be null.

Drawbacks

Sparse Merkle trees are really cool because they give us efficient proofs of non-inclusion. However, this can also mean they get really, really big. 26 letters isn’t much, but most of the time we’re talking about 2²⁵⁶ hashes! That’s just way too many indices to generate a tree manually.

Use Cases

Sparse Merkle trees are already being used in the wild to do some cool blockchain stuff.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store