#incremental #zcash #merkle #tree #append-only #implementation

incrementalmerkletree

Implementation of an Incremental Merkle Tree

1 unstable release

0.1.0 Jun 24, 2021

MIT/Apache

73KB
1.5K SLoC

incrementalmerkletree

This is a Rust crate that provides an implementation of an append-only Merkle tree structure called an "incremental merkle tree", with built-in support for checkpoints and rewinds intended for use in Blockchain projects, such as Zcash.

Documentation

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.


lib.rs:

incrementalmerkletree

Incremental Merkle Trees are fixed-depth Merkle trees with two primary capabilities: appending (assigning a value to the next unused leaf and advancing the tree) and obtaining the root of the tree. Importantly the tree structure attempts to store the least amount of information necessary to continue to function; other information should be pruned eagerly to avoid waste when the tree state is encoded.

Witnessing

Merkle trees are typically used to show that a value exists in the tree via an authentication path. We need an API that allows us to identify the current leaf as a value we wish to compute authentication paths for even as the tree continues to be appended to in the future; this is called maintaining a witness. When we're later uninterested in such a leaf, we can prune a witness and remove all unnecessary information from the structure as a consequence.

Checkpoints and Rollbacks

The structure is not append-only in the strict sense. It is possible to identify the current state of the tree as a "checkpoint" and to remove older checkpoints that we're no longer interested in. It should be possible to roll back to any previous checkpoint.

Dependencies

~0.6–1.2MB
~28K SLoC