#data-structure #merkle-tree #merkle #tree #map

nightly smt_map

A uint-to-uint map backed by Sparse Merkle Tree (SMT), which supports generating Merkle Proofs of key-values

5 releases

0.0.5 May 8, 2019
0.0.4 Apr 22, 2019
0.0.3 Apr 22, 2019
0.0.2 Apr 8, 2019
0.0.1 Jan 13, 2019

#9 in #merkle-tree

23 downloads per month

MIT license

495 lines

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.


[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.