LeanIMT: A Lightweight Incremental Merkle Tree

A Lean implementation of an Incremental Merkle Tree (IMT). It supports insertion, deletion, and updating of leaves, all while maintaining the integrity and root hash of the tree. The tree is built using a customizable hash function.

Installation

To use LeanIMT, add the following to your Cargo.toml:

[dependencies]
lean_imt = "0.1.0"

Usage

1. Import the necessary modules

use std::collections::HashMap;
use lean_imt::{LeanIMT, IMTNode, IMTHashFunction};

2. Define a simple hash function

fn simple_hash(nodes: Vec<IMTNode>) -> IMTNode {
    nodes.join(",")
}

3. Create a new LeanIMT instance

let hash_function: IMTHashFunction = simple_hash;
let mut imt = LeanIMT::new(hash_function);

4. Insert a single leaf

let leaf = "leaf1".to_string();
match imt.insert(leaf.clone()) {
    Ok(root) => println!("New root: {}", root),
    Err(e) => println!("Error: {}", e),
}

5. Insert multiple leaves

let leaves = vec!["leaf1".to_string(), "leaf2".to_string(), "leaf3".to_string()];
match imt.insert_many(leaves.clone()) {
    Ok(root) => println!("New root after batch insert: {}", root),
    Err(e) => println!("Error: {}", e),
}

6. Update an existing leaf

let old_leaf = "leaf1".to_string();
let new_leaf = "leaf1_updated".to_string();
let sibling_nodes = vec![]; // You would populate this based on the Merkle proof
match imt.update(&old_leaf, new_leaf.clone(), &sibling_nodes) {
    Ok(new_root) => println!("Updated root: {}", new_root),
    Err(e) => println!("Error: {}", e),
}

7. Remove a leaf

let leaf_to_remove = "leaf1".to_string();
let sibling_nodes = vec![]; // Populate this based on the Merkle proof
match imt.remove(&leaf_to_remove, &sibling_nodes) {
    Ok(new_root) => println!("New root after removal: {}", new_root),
    Err(e) => println!("Error: {}", e),
}

8. Check if a leaf exists

if imt.has(&"leaf1".to_string()) {
    println!("Leaf exists in the tree.");
} else {
    println!("Leaf not found.");
}

9. Get the root of the tree

match imt.root() {
    Some(root) => println!("Current root: {}", root),
    None => println!("Tree is empty"),
}

10. Retrieve Tree Size and Depth

println!("Tree size: {}", imt.get_size());
println!("Tree depth: {}", imt.get_depth());

Example

Here's a full example using the library:

fn main() {
    let hash_function: IMTHashFunction = simple_hash;
    let mut imt = LeanIMT::new(hash_function);

    // Insert leaves
    imt.insert("leaf1".to_string()).unwrap();
    imt.insert("leaf2".to_string()).unwrap();

    // Check the root
    let root = imt.root().unwrap();
    println!("Root after insertion: {}", root);

    // Update a leaf
    let sibling_nodes = vec!["leaf2".to_string()];
    imt.update(&"leaf1".to_string(), "new_leaf1".to_string(), &sibling_nodes).unwrap();

    // Check updated root
    let updated_root = imt.root().unwrap();
    println!("Updated root: {}", updated_root);

    // Remove a leaf
    imt.remove(&"new_leaf1".to_string(), &sibling_nodes).unwrap();

    // Final root after removal
    let final_root = imt.root().unwrap();
    println!("Root after removal: {}", final_root);
}

Testing

To run the test suite, use the following command:

cargo test

Tests cover the basic operations of insertion, removal, and updates, as well as ensuring consistency across multiple tree operations.