#merkle-tree #state #leave #append #bridge #linear #marked


A space-efficient Merkle tree designed for linear appends with witnessing of marked leaves, checkpointing & state restoration

3 releases (breaking)

0.4.0 Sep 8, 2023
0.3.0 Jun 6, 2023
0.2.1 Jun 6, 2023
0.2.0 Dec 20, 2022
0.1.0 Jul 22, 2022

#152 in Data structures

Download history 2160/week @ 2023-12-12 1065/week @ 2023-12-19 436/week @ 2023-12-26 947/week @ 2024-01-02 1440/week @ 2024-01-09 1216/week @ 2024-01-16 1412/week @ 2024-01-23 1174/week @ 2024-01-30 1572/week @ 2024-02-06 1199/week @ 2024-02-13 1403/week @ 2024-02-20 907/week @ 2024-02-27 618/week @ 2024-03-05 1351/week @ 2024-03-12 1270/week @ 2024-03-19 580/week @ 2024-03-26

4,084 downloads per month
Used in 13 crates (3 directly)




This is a Rust crate that provides an implementation of an append-only Merkle tree structure. Individual leaves of the merkle tree may be marked such that witnesses will be maintained for the marked leaves as additional nodes are appended to the tree, but leaf and node data not specifically required to maintain these witnesses is not retained, for space efficiency. The data structure also supports checkpointing of the tree state such that the tree may be reset to a previously checkpointed state, up to a fixed number of checkpoints.

The crate also supports using "bridges" containing the minimal possible amount of data to advance witnesses for marked leaves data up to recent checkpoints or the the latest state of the tree without having to append each intermediate leaf individually, given a bridge between the desired states computed by an outside source. The state of the tree is internally represented as a set of such bridges, and the data structure supports fusing and splitting of bridges.



Licensed under either of

at your option.


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.