Spare Merkle Tree Map (SMT-Map)

A Spare Merkle Tree Map (SMT-Map) is a map from uint to uint backed by Sparse Merkle Tree (SMT), which supports proving the value of a key with Merkle Proof. In particular it can prove that a key is unset (has never been set to a non-zero value or has been reset to zero).

SMT has a form of full binary tree. Therefore an SMT of, for example, uint256 always has 2**256 leaf node. Each leaf node corresponds to a key-value pair of the SMT-Map: the value is stored on the node, and the key is the uint representation of the path from the root to the leaf.

See the documentation and references for more details.

References:

[1] Revocation Transparency

[2] Data availability proof-friendly state tree transitions

Library Status

Pre-alpha. Basically tested and documented. The APIs are subject to change.

Pull requests and feature requests are welcome.