fast_sparse_merkle_tree/
lib.rs

1//! # Fast SMT (Sparse Merkle Tree)
2//!
3//! Constructs a new `SparseMerkleTree<H, V, S>`, using TurboSHAKE128 as default hash function.
4//! You always have the freedom of using your favourite hash function by implementing `Hasher` trait.
5//! We provide two `Hasher` implementations - TurboSHAKE128 and BLAKE3. As per benchmarks, both of them stand
6//! shoulder-to-shoulder - showing impressive performance, compared to SHA256 or SHA3_256.
7//!
8//! # Examples
9//!
10//! ```
11//! use fast_sparse_merkle_tree::{
12//!     turboshake_hasher::TurboShake128Hasher, default_store::DefaultStore,
13//!     error::Error, MerkleProof,
14//!     SparseMerkleTree, traits::Value, H256, Hash,
15//!     traits::Hasher,
16//! };
17//!
18//! // Type define SMT
19//! type SMT = SparseMerkleTree<TurboShake128Hasher, Hash, Word, DefaultStore<Hash, Word, 32>, 32>;
20//!
21//! // Define SMT value
22//! #[derive(Default, Clone, PartialEq)]
23//! pub struct Word(String, H256);
24//!
25//! impl Value for Word {
26//!    fn as_slice(&self) -> &[u8] {
27//!        self.1.as_slice()
28//!    }
29//!    fn zero() -> Self {
30//!        Default::default()
31//!    }
32//! }
33//!
34//! fn construct_smt() {
35//!     let mut tree = SMT::default();
36//!
37//!     for (i, word) in "The quick brown fox jumps over the lazy dog"
38//!         .split_whitespace()
39//!         .enumerate()
40//!     {
41//!         let key: Hash = {
42//!             let mut hasher = TurboShake128Hasher::default();
43//!
44//!             hasher.write_bytes(&(i as u32).to_le_bytes());
45//!             hasher.finish().into()
46//!         };
47//!
48//!         let hash: H256 = if !word.is_empty() {
49//!             let mut hasher = TurboShake128Hasher::default();
50//!
51//!             hasher.write_bytes(word.as_bytes());
52//!             hasher.finish().into()
53//!         } else {
54//!             H256::zero()
55//!         };
56//!
57//!         let value = Word(word.to_string(), hash);
58//!
59//!         // insert <key, value> pair into the tree
60//!         tree.update(key, value).expect("inserting into SMT must not fail");
61//!     }
62//!
63//!     println!("SMT root is {:?} ", tree.root());
64//! }
65//! ```
66//!
67//! ## Installation
68//!
69//! Add this to your project's `Cargo.toml`:
70//!
71//! ```toml
72//! [dependencies]
73//! fast-sparse-merkle-tree = "=0.1.2"
74//! # or (minimal, just `turboshake` for faster hashing, no_std)
75//! fast-sparse-merkle-tree = { version = "=0.1.2", default-features = false, features = ["turboshake"] }
76//! ```
77//!
78//! For more see README in `fast-sparse-merkle-tree` repository @ <https://github.com/itzmeanjan/fast-sparse-merkle-tree>.
79
80#![cfg_attr(not(feature = "std"), no_std)]
81
82#[cfg(feature = "blake3")]
83pub mod blake3_hasher;
84
85#[cfg(feature = "turboshake")]
86pub mod turboshake_hasher;
87
88pub mod default_store;
89pub mod error;
90pub mod h256;
91pub mod internal_key;
92pub mod merge;
93pub mod merkle_proof;
94pub mod traits;
95pub mod tree;
96
97#[cfg(test)]
98mod tests;
99
100pub use h256::{H256, Hash};
101pub use internal_key::InternalKey;
102pub use merkle_proof::{CompiledMerkleProof, MerkleProof};
103pub use traits::Key;
104pub use tree::SparseMerkleTree;
105
106/// Expected path size: log2(256) * 2, used for hint vector capacity
107pub const EXPECTED_PATH_SIZE: usize = (256usize.ilog2() * 2) as usize;
108/// Height of sparse merkle tree
109pub const TREE_HEIGHT: usize = 256;
110/// Key limit size
111pub const KEY_LIMIT: usize = u32::MAX as usize;
112
113cfg_if::cfg_if! {
114    if #[cfg(feature = "std")] {
115        use std::collections;
116        use std::vec;
117        use std::string;
118        use std::vec as vec_macro;
119    } else {
120        extern crate alloc;
121        use alloc::collections;
122        use alloc::vec;
123        use alloc::string;
124        use alloc::vec as vec_macro;
125    }
126}
fast_sparse_merkle_tree/lib.rs

fast_sparse_merkle_tree/
lib.rs
