Sparse Merkle Tree

A performance oriented implementation of a binary SMT with parallel update, node batching and storage shortcuts.

While researching a high-performance Merkle tree for state authentication at AERGO, one of the first design iterations led us to implement a standard Sparse Merkle Tree which this article is about.

The implementation of the standard SMT can be found here : https://github.com/aergoio/SMT

Sparse Merkle Tree

A sparse Merkle tree is a tree that contains a leaf for every possible output of a cryptographic hash function. Some of the features of the AERGO implementation of a standard sparse Merkle tree are:

• Efficient Merkle proof verification (binary tree structure)
• Compressed Merkle proofs
• Efficient database reads and storage (node batching)
• Reduced data storage (shortcut nodes for subtrees containing one key)
• Simultaneous update of multiple keys with goroutines

Figure 1. An example sparse Merkle tree of height=4 (4-bit keys) containing 3 keys. The 3 keys are shown in red and blue. Default nodes are shown in green. Non-default nodes are shown in purple.

The values (non-default keys) are stored at the leaf of the tree at height 0. If the default value is D0 then every default node at height 1 will have a value of D1 = Hash(D0,D0). The root of an empty tree is the default hash of height 4. When keys are inserted in the trie the value of the leaf node changes from the default value D0 to the specified value, and only the modified part of the tree has to be recomputed.

EDIT : We choose not to implement Hash(0,0) = 0 (equivalent to D0=D1…=D256) at this time because it would require a different format of the non-inclusion proofs. For a more efficient implementation that uses H(0,0)=0, you may use the following : https://github.com/aergoio/aergo/tree/master/pkg/trie

For example, adding the red value to a tree already containing the blue keys only requires the computation of H1, H2, H3, and Root to get the new root of the tree. The red value was added to the left side of the tree so h3 is not modified.

For a hash function outputting 256 bits, the tree has 256 levels; or in other words, 2²⁵⁶ possible keys, which makes it impossible to represent.

The tree is said sparse because if the tree contains only random keys (sparsely distributed) then most of the nodes it contains have default values that are determined based on the height of the node. We can, therefore, simulate the tree by only storing the default nodes once, and the rest of the non-default nodes.

Storage size optimization

In a tree with N random keys, the first log(N) bits will be common to all keys and need only to be stored once. This reduces the number of nodes to store, but it is still not enough because each branch for a key would contain Height — log(N) nodes.

We, therefore, implemented shortcut nodes defined as follows: the highest subtree root that contains only one key should store the key-value pair instead of its children (the shortcut is still the value of the subtree root that contains 1 non-default value at height 0). With this storage rule, we don’t have to store branches in a sparse tree which significantly reduces the quantity of data to be stored.

In the above example, only the following nodes need to be stored: Root, H3, h3, h2, h1. In the database, H3 will point to the single non default node contained in it’s subtree. Note that the blue nodes are not sparse as they are located at the bottom of the tree which is why h2 and h1 have to be stored thus showing the importance of using random keys.

Node batching for efficient database reads and storage

When storing each node as root with 2 children, the quantity of nodes to store grows quickly, and a bottleneck happens due to multiple threads loading nodes from memory. A hex Merkle tree would solve this problem as each key has 16 children and a smaller height of 64 (256/4) but we want the tree to be binary. We can achieve the same features as a hex tree by using node batching.

Instead of storing 2 children for one node, we store the subtree of height 4 for that node. A tree of height 4 has 16 leaves at height 0 (like hex). So the value of a node is an array containing all the nodes of the 4-bit tree. And the children of a node at index i in the tree can be found at index 2*i+1 and 2*i+2.

A node is encoded as follows:

{ Root : [ [ byte(0/1) to flag a shortcut ], 3–0, 3–1, 2–0, 2–1, 2–2, 2–3, 1–0, 1–1, 1–2, 1–3, 1–4, 1–5, 1–6, 1–7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f ] }

For example, to get the children of node 3–0 at index id=1 in the array, we can access the left child 2–0 at index (2 * id + 1) = index 3 and the right child 2–1 at index (2 * id + 2) = index 4.

To each node, we append a byte flag to recognize the shortcuts. Since the nature of Root is not know ahead of time, the byte flag is stored at the first index of the nodes array.

Figure 2. A visual representation of node batching. The first batch is blue and all 16 leaves of a batch are roots to other batches (green). A batch contains 30 nodes.

Node batching has two benefits: (1) it reduces the number of database reads and (2) it allows for concurrent update of the height 4 subtrees without the need for a lock.

Merkle proofs

Using a binary tree gives us very simple and easy to use Merkle proofs. In a Patricia tree, a Merkle proof is composed of all the nodes in the path of a key. Since each node has 16 children the quantity of data is larger and not as straightforward to verify as in binary.

The sparse Merkle tree also provides convenient proofs of non-inclusion: the proof that a key is not included in the tree is simply a proof that the value for the key is default (D0).

EDIT : there is another way to prove non-inclusion which is by proving that a default node is on the path of the non-included key. However for this standard SMT implementation, we choose not to use it as the proof would have a different format, adding complexity and little efficiency.

In Figure 2, the Merkle proof of the red key is composed of the nodes in a red circle : [D0, D1, D2, h3]. The size of the proof is equal to the height of the tree. The verifier of the proof will compute H1, then H2, H3, and Root and check that the Root is as expected.

Compressed Merkle proofs: Since most of the nodes in the Merkle proof are default, we can use a bitmap and set a bit for every index that is not default in the proof.

The proof [D0, D1, D2, h3] can be compressed to 0001[h3]. The verifier of the compressed Merkle proof should know to use D0 to compute H1 because the first index of the bitmap is 0, and D1 for the second proof element, etc.

Simultaneous update of multiple keys with goroutines

Instead of updating keys one by one, it is possible to update any number of keys with one update call that will concurrently update different parts of the tree. The keys should be sorted in an array, and the corresponding values should be at the same index in a separate array (see Usage).

To delete a key from the tree, simply set it’s value to the default value of height 0 (D0).

Usage

• NewSMT

func NewSMT(root []byte, hash func(data …[]byte) []byte, store db.DB) *SMT {

When creating an empty tree, set root to nil. A nil root means that it is equal to the default value of its height. Use a custom hash function or use the Hasher in utils and specify a database if you plan to commit nodes.

• DefaultHash

func (s *SMT) DefaultHash(height uint64) []byte {

Returns the default node of the specified height.

• Update

func (s *SMT) Update(keys, values [][]byte) ([]byte, error) {

Update will recursively go down the tree and split the keys and values according to the side of the tree they belong to: multiple parts of the tree can be simultaneously updated.

‘keys [][]byte’ is a sorted array of keys, ‘values [][]byte’ contains the matching values of keys.

If update is called several times before Commit, only the last state is committed.

• AtomicUpdate

func (s *SMT) AtomicUpdate(keys, values [][]byte) ([]byte, error) {

AtomicUpdate updates the tree with sorted keys and values just like Update. But unlike update, if AtomicUpdate is called several times before Commit, all the intermediate states from AtomicUpdate calls will be recorded. This can be useful when authenticating the state of each block, but not committing to the database right away.

• Get

func (s *SMT) Get(key []byte) ([]byte, error) {

Get gets the value of a key stored in the tree, if a key is default (i.e not stored), return nil.

• Commit

func (s *SMT) Commit() error {

Commit commits the updated nodes to the database. When update is called, the new nodes are stored in smt.db.updatedNodes. Commit stores them to disk.

• Stash

func (s *SMT) Stash() error {

Use the Stash function to revert the update without committing (if a block verification is invalid for example).

• Revert

func (s *SMT) Revert(toOldRoot []byte) error {

When Revert is called, the trees to rollback (between the current tree and toOldRoot) are deleted from the database. This process can be slow so for a quick rollback, manually set the Root to the state you want to revert to and reload the cache.

• MerkleProof

func (s *SMT) MerkleProof(key []byte) ([][]byte, error) {

MerkleProof creates a Merkle proof of inclusion/non-inclusion of the key. The Merkle proof is an array of hashes.

• MerkleProofCompressed

func (s *SMT) MerkleProofCompressed(key []byte) ([]byte, [][]byte, error) {

MerkleProofCompressed creates the same Merkle proof as MerkleProof but compressed using a bitmap.

• VerifyMerkleProof

func (s *SMT) VerifyMerkleProof(ap [][]byte, key, value []byte) bool {

VerifyMerkleProofverifies that the key-value pair is included in the tree at the current Root.

• VerifyMerkleProofCompressed

func (s *SMT) VerifyMerkleProofCompressed(bitmap []byte, ap [][]byte, key, value []byte) bool {

VerifyMerkleProofCompressedverifies that the key-value pair is included in the tree at the current Root.

Conclusion

We have provided many optimizations to the Sparse Merkle Tree implementation, but there is one limitation that cannot be prevented due to the nature of the SMT. It is that values are stored at height 0 of the tree which requires 256 hashing operations to update one key in the tree.

For state authentication of the AERGO blockchain, which requires high-speed updates, we designed a modified version of a Sparse Merkle Tree where instead of storing the values at height 0 the values are stored at the highest subtree containing only 1 key. Effectively in the same position as the shortcut node mentioned above. This means that on average, in a tree containing N random keys, only log(N) hashes are required to update a key in the tree.

Aergo State Trie Introduction :

Releasing StateTrie: A hash tree built for high-performance interoperability

The Aergo State Trie implementation can be found here : https://github.com/aergoio/aergo/tree/master/pkg/trie

Related articles and other implementations :

Efficient Sparse Merkle Trees paper : https://eprint.iacr.org/2016/683.pdf

The implementation of the Sparse Merkle Trees paper : https://github.com/pylls/gosmt

(While this implementation offers efficient caching strategies, it is not appropriate for blockchain states containing millions of keys. The implementation relies on a sorted array of all the data stored in memory which is simply too large in case of blockchain applications).

A clear explanation of the SMT by Kelvin Fichter : https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837

Python implementation by Vitalik Buterin : https://github.com/ethereum/research/tree/master/trie_research/bintrie2

Loom Project implementation : https://github.com/loomnetwork/mamamerkle

The Aergo implementation of a Sparse Merkle Tree : https://github.com/aergoio/SMT

If you know of other interesting implementations please share in the comments below.