Sparse merkle tree

Docs

An optimized sparse merkle tree.

Features:

• Generate / Verify multi-leaves merkle proof
• Customize hash function
• Rust no_std support

This article describes details of the tree An optimized compacted sparse merkle tree

Notice this library is not stable yet; API and proof format may changes. Make sure you know what you are doing before using this library.

Construction

A sparse merkle tree is a perfectly balanced tree contains 2 ^ N leaves:

# N = 256 sparse merkle tree
height:
255                0
                /     \
254            0        1

.............................

           /   \          /  \
2         0     1        0    1
1        / \   / \      / \   / \
0       0   1 0  1 ... 0   1 0   1 
       0x00..00 0x00..01   ...   0x11..11

The above graph demonstrates a sparse merkle tree with 2 ^ 256 leaves, which can mapping every possible H256 value into leaves. The height of the tree is 256, from top to bottom, we denote 0 for each left branch and denote 1 for each right branch, so we can get a 256 bits path, which also can represent in H256, we use the path as the key of leaves, the most left leaf's key is 0x00..00, and the next key is 0x00..01, the most right key is 0x11..11.

We use a root H256 and a map map[(usize, H256)] -> (H256, H256) to represent a tree, the key of map is parent node and height, values are children nodes, an empty tree represented in an empty map plus a zero H256 root.

To update a key with value, we walk down from root, push every non-zero sibling into merkle_path vector, since the tree height is N = 256, we need store 256 siblings. Then we reconstruct the tree from bottom to top: map[(height, parent)] = merge(lhs, rhs), after do 256 times compute we got the new root.

A sparse merkle tree contains few efficient nodes, and lot's of zero nodes, we can specialize the merge function for zero value. We redefine the merge function, only do the actual computing when lhs and rhs are both non-zero values, otherwise if one of them is zero, we just return another one as the parent.

fn merge(lhs: H256, rhs: H256) -> H256 {
    if lhs.is_zero() {
        return rhs;
    } else if rhs.is_zero() {
        return lhs;
    }

    // only do actual computing when lhs and rhs both are non-zero
    merge_hash(lhs, rhs)
}

This optimized merge function still has one problem, merge(x, zero) equals to merge(zero, x), which means the merkle root is broken, we can easily construct a conflicted merkle root from different leaves.

To fix this, instead of update key with an H256 value, we use hash(key | value) as the value to merge, so for different keys, no matter what the value is, the leaves' hashes are unique. Since all leaves have a unique hash, nodes at each height will either merged by two different hashes or merged by a hash with a zero; for a non-zero parent, either situation we get a unique hash at the parent's height. Until the root, if the tree is empty, we get zero, or if the tree is not empty, the root must merge from two hashes or a hash with a zero, we already proved the root hash is unique.

License

MIT