SMTree :: Paddable Sparse Merkle Tree

SMTree is a flexible sparse tree accumulator that can support various tree types via traits for custom node-merging and tree-padding logic. The api supports inclusion proofs for a single or multiple leaves (batch proofs), efficient logN padding to hide number of leaves (implied by tree height) and random sampling by returning the closest leaf to the input index.

The above functionality is required by applications utilizing sparse Merkle trees for hiding the leaf-population in a tree-based accumulator, such as the HashWires range proof and DAPOL auditing proof constructions. Similarly, one can easily implement tree constructions like Maxwell liability trees in Bitcoin, simple summation, XOR or alphabetically merged Merkle trees and try performance comparison with different hash functions.

Documentation

To construct a SparseMerkleTree object, you need to first define the value type for the tree nodes, and implement Clone, Default, Mergeable, Paddable, ProofExtractable traits for it. You also need to implement Debug, Clone, Default, Eq, Mergeable, Serializable traits for your proof node type ProofExtractable::ProofNode.

Assuming your node value is simply a hash, and the merge function is classic, to hash the concatenated hashes of two child nodes. Therefore the proof node type is the same as the tree node type.

You can find reference implementations for various tree types in node_template.rs.

If you want to enable random sampling for your sparse Merkle tree, you need to further implement the PaddingProvable trait. We provide a reference implementation in the HashNodeSmt struct in node_template.rs.

Now you are all prepared to build your sparse Merkle tree!

Contributors

The original authors of this code are Konstantinos Chalkias (@kchalkias) and Yan Ji (@iseriohn), with contributions from Kevin Lewi (@kevinlewi) and Irakliy Khaburzaniya (@irakliyk). To learn more about contributing to this project, see this document.

License

This project is MIT licensed.