Crate fast_sparse_merkle_tree 

Fast SMT (Sparse Merkle Tree)

Constructs a new SparseMerkleTree<H, V, S>, using TurboSHAKE128 as default hash function. You always have the freedom of using your favourite hash function by implementing Hasher trait. We provide two Hasher implementations - TurboSHAKE128 and BLAKE3. As per benchmarks, both of them stand shoulder-to-shoulder - showing impressive performance, compared to SHA256 or SHA3_256.

Examples

use fast_sparse_merkle_tree::{
    turboshake_hasher::TurboShake128Hasher, default_store::DefaultStore,
    error::Error, MerkleProof,
    SparseMerkleTree, traits::Value, H256, Hash,
    traits::Hasher,
};

// Type define SMT
type SMT = SparseMerkleTree<TurboShake128Hasher, Hash, Word, DefaultStore<Hash, Word, 32>, 32>;

// Define SMT value
#[derive(Default, Clone, PartialEq)]
pub struct Word(String, H256);

impl Value for Word {
   fn as_slice(&self) -> &[u8] {
       self.1.as_slice()
   }
   fn zero() -> Self {
       Default::default()
   }
}

fn construct_smt() {
    let mut tree = SMT::default();

    for (i, word) in "The quick brown fox jumps over the lazy dog"
        .split_whitespace()
        .enumerate()
    {
        let key: Hash = {
            let mut hasher = TurboShake128Hasher::default();

            hasher.write_bytes(&(i as u32).to_le_bytes());
            hasher.finish().into()
        };

        let hash: H256 = if !word.is_empty() {
            let mut hasher = TurboShake128Hasher::default();

            hasher.write_bytes(word.as_bytes());
            hasher.finish().into()
        } else {
            H256::zero()
        };

        let value = Word(word.to_string(), hash);

        // insert <key, value> pair into the tree
        tree.update(key, value).expect("inserting into SMT must not fail");
    }

    println!("SMT root is {:?} ", tree.root());
}

Installation

Add this to your project’s Cargo.toml:

[dependencies]
fast-sparse-merkle-tree = "=0.1.2"
# or (minimal, just `turboshake` for faster hashing, no_std)
fast-sparse-merkle-tree = { version = "=0.1.2", default-features = false, features = ["turboshake"] }

For more see README in fast-sparse-merkle-tree repository @ https://github.com/itzmeanjan/fast-sparse-merkle-tree.

Re-exports

pub use h256::H256;

pub use h256::Hash;

pub use internal_key::InternalKey;

pub use merkle_proof::CompiledMerkleProof;

pub use merkle_proof::MerkleProof;

pub use traits::Key;

pub use tree::SparseMerkleTree;

Modules

blake3_hasher

default_store

error

h256

internal_key

merge

merkle_proof

traits

tree

turboshake_hasher

Constants

EXPECTED_PATH_SIZE

Expected path size: log2(256) * 2, used for hint vector capacity

KEY_LIMIT

Key limit size

TREE_HEIGHT

Height of sparse merkle tree