Categories

Sparse Merkle trees

You are here:
< All Topics

A sparse Merkle tree (SMT) may have a practically unbounded number of data item positions. However, the storage required is only proportional to the number of data items inserted into the tree. The label on the leaf node of the SMT is initially NULL and therefore does not need to be stored. Similarly, the labels on internal nodes of the SMT all have fixed predictable values that can be re-computed as hashes of NULL values. When an item is added to a leaf of the tree, then all the labels along the path from this leaf to root are updated and stored. For a tree of size 250, each insertion increases the current storage by 1.6 KB. The inclusion proof of an item is similarly 1.6 KB.

 

There are two ways to use an SMT as a commitment to a key/value store:

 

  • Short keys: Every node is assigned a log N bit key. This is the best solution for a key/value store where keys are relatively short. A SMT with 240 nodes can encode 40-bit keys. A (key, value) data item is inserted into the SMT by setting the label on the leaf node at index key to the 32 byte SHA-256 hash of value.

 

  • Hash table: When the keys are longer than log N bits, the SMT can be used as a hash table of length N. A data item has a (key, value) pair and a standard hash table function is used to map the key to an index in {1,…,N} of the hash table, where again a 32-byte SHA-256 hash of value is stored. Collisions in the hash table are possible but happen infrequently. For example, if N = 240, then once a billion keys have been inserted, a new key causes a collision with probability 1/1000. Collisions do not break the integrity of the SMT commitment, but require the application to modify the key for a new insert into the SMT until it no longer causes a collision. If the application is not able to modify keys then the number of leaves in the SMT needs to be much higher (roughly N = M^2 to support M total key inserts).

 

 

In the above diagram, the sparse Merkle tree has empty positions for where an item has not been inserted before.

 

Previous Merkle trees
Next Bloom filter
Table of Contents