What’s a Sparse Merkle Tree?

If you’ve been around the Ethereum research community lately, you might’ve heard of something called a sparse Merkle tree. They might sound scary, but they’re really quite simple. This post will explain exactly what a sparse Merkle tree is, why they’re cool, and what they’re currently being used for.

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.

That ends up looking like this:

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.

I went ahead and highlighted the siblings in blue. With just A, H(B), and H(H(C)+H(D)), we can recompute the original root hash. This is an efficient way to show that A is part of this tree without having to provide the entire tree!

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.

Let’s say we have a Merkle tree with four leaves. We’ll populate this tree with some letters (A, D) to demonstrate. The letter A is the first letter of the alphabet, so we should put it at the first leaf. Similarly, we can put D at the fourth leaf.

So what happens in the second and third leaves? We just leave them empty. More precisely, we put a special value (like null) instead of placing a letter.

The tree ends up looking like this:

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:

Again, we’re just providing the siblings, H(null) and H(H(null)+H(D)), and checking that it matches the root.

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.

All we need is a standard Merkle proof showing the third leaf is null!

This looks just like a standard Merkle proof, except that we’re proving the leaf contains null instead of C.

The best part of a sparse Merkle tree is that they’re really representing key-value stores, inside of a Merkle tree!

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.

Luckily, there are some techniques to efficiently generate Merkle trees. The key to these techniques is that these giant sparse Merkle trees are mostly… sparse. H(null) is a constant value, and so is H(H(null)), etc. etc. Huge chunks of the tree can be cached!

Use Cases

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

Plasma Cash makes use of sparse Merkle trees to store information about deposited assets. Every Plasma Cash asset has a unique ID. Whenever an asset is transferred to a new user, a transaction is included in the sparse Merkle tree at the asset’s index! Proofs of inclusion (or non-inclusion!) are used to prove that a given transaction history is valid.

Sparse Merkle trees might even make their way into Ethereum! Ethereum researchers are looking into sparse Merkle trees as a replacement for the Merkle Patricia tries currently used to store Ethereum state.

As always, feedback/comments/questions are more than welcome. If you spot any typos, or you think anything needs clarification, let me know!