Sparse Merkle Tree

Sparse Merkle Tree (SMT) is a variation of the Merkle Tree. In that tree, data is indexed and each data block is placed at the leaf that corresponds to that block’s index. It makes it easy to prove that some data doesn’t exist (proof of non-membership).

In fact, an SMT is an authenticate key-value map: the key of a leaf and the content of the leaf are bound to each other.

To create an SMT, you have to create each possible key of the key-value map even if there is no value for the key. So, imagine you have a 3 bits key, you will have the following keys: 000, 001, 010, 011, 100, 101, 110, 111. Now, we have to create one leaf for each key and each leaf node will have:

  • A key.
  • A value.
  • A hash obtained by hashing together the key and the value.

A very important point is that, if you don’t have a value, for example, for the key 011, you still have to create a leaf for 011 with null as associated data. Another important point is that the position of the leaf node in the tree is fixed by its key.

This is how it would look like for a 2 bits key:

graph TD SUM["Hash (00, 01, null, 11)"] SUM --> HASH00-01["Hash (00, 01)"] SUM --> HASH10-11["Hash (null, 11)"] HASH00-01 --> HASH01["Hash (00)"] HASH00-01 --> HASH02["Hash (01)"] HASH10-11 --> HASH03["Hash (null)"] HASH10-11 --> HASH04["Hash (11)"] HASH01 --> POSITION00["Position 00
Data"] HASH02 --> POSITION01["Position 01
Data"] HASH03 --> POSITION10["Position 10
Null (no data)"] HASH04 --> POSITION11["Position 11
Data"]

An SMT allow the following operations:

  • Look up: Returns the value associated with a certain key.
  • Insert: Inserts a certain key-value pair in the collection.
  • Update: Updates the value associated with a certain key.
  • Delete: Removes a certain key-value pair in the collection.