Sparse Merkle Trees

Merkle Trees. Great for proving inclusion but useless for saying what isn't included

In a previous section we described how a Merkle Tree proof of inclusion works. It is a fantastic tool for proving that a specific piece of data is part of a tree. Something that may have come to mind however is whether or not it is possible to prove that a piece of data is not contained within a Merkle Tree. With a standard tree this is not possible but it turns out that a Sparse Merkle Tree does precisely that!

Sparse Merkle Tree

A Sparse Merkle Tree is similar to a standard one but there is a key difference in the fact that the nodes are indexed. Proof of inclusion is possible in this implementation but so is proof of non-inclusion. To prove that a value is not contained within a tree we must prove that the leaf where the value would be contains the value null

A Sparse Merkle Tree is contains null values where values have not been inserted