Deterministic, no-std friendly Cartesian Merkle Tree for Rust. cmtree blends binary-search ordering, heap-based balancing, and Merkle authentication so every node carries useful state and proofs remain compact.

• 🚀 Deterministic treap – keys derive their priority from a configurable digest, so the resulting shape is independent of insertion order.
• 🔐 Merkle authentication – generate membership and non-membership proofs for any key in O(log n) time, with hash ordering that matches the research paper.
• 🧵 No-std first – uses alloc only; works in embedded and wasm contexts.
• 🧩 Pluggable hashers – swap Sha256 for any Digest + Clone such as blake3 or sha3.
• 📦 Batch insertion – amortize rotations by feeding entire slices to insert_batch.
• 🗂️ Key/value map – use CMMap when you need authenticated values, not just membership.
• 🧪 Tested – extensive unit, doc, and large-structure tests plus a CI pipeline covering cargo fmt, clippy, doc, and test.

[dependencies]
cmtree = "0.1"

use cmtree::CMTree;

fn main() {
    let mut tree = CMTree::<Vec<u8>>::new();

    tree.insert(b"alice".to_vec());
    tree.insert(b"bob".to_vec());
    tree.insert(b"carol".to_vec());

    // Or populate in a single pass when you already have the collection:
    tree.insert_batch([
        b"alice".to_vec(),
        b"bob".to_vec(),
        b"carol".to_vec(),
    ]);

    assert!(tree.contains(&b"bob".to_vec()));
    assert_eq!(tree.len(), 3);

    let root = tree.root_hash();
    println!("Root digest: {:02x?}", root);
}

use cmtree::CMTree;

let mut tree = CMTree::<Vec<u8>>::new();
for key in [b"x".to_vec(), b"y".to_vec(), b"z".to_vec()] {
    tree.insert(key);
}

let root = tree.root_hash();
let proof = tree.generate_proof(&b"y".to_vec()).unwrap();

assert!(proof.existence);
assert!(proof.verify(&b"y".to_vec(), &root));

let missing = b"not-here".to_vec();
let proof = tree.generate_proof(&missing).unwrap();
assert!(!proof.existence);
assert!(proof.verify(&missing, &root));

use cmtree::CMMap;

let mut map = CMMap::<Vec<u8>, Vec<u8>>::new();
map.insert_batch([
    (b"alice".to_vec(), b"pubkey-alice".to_vec()),
    (b"bob".to_vec(), b"pubkey-bob".to_vec()),
]);

let root = map.root_hash();
let membership = map.generate_proof(&b"bob".to_vec()).unwrap();
assert!(membership.existence);
assert!(membership.verify(&b"bob".to_vec(), Some(&b"pubkey-bob".to_vec()), &root));

let missing = map.generate_proof(&b"carol".to_vec()).unwrap();
assert!(!missing.existence);
assert!(missing.verify::<Vec<u8>, Vec<u8>>(&b"carol".to_vec(), None, &root));

Proofs follow the definition in Cartesian Merkle Tree (Chystiakov et al., 2025), storing an ordered prefix of parent key digests and sibling hashes alongside the queried node’s children.

• insert, remove, contains, generate_proof: expected O(log n) for n stored keys (treap balancing).
• root_hash: O(1) thanks to cached node hashes.
• Proof length: O(log n).
• Space: O(n); one node (with cached key digest) per key.

Determinism stems from hashing the key to produce the heap priority. Using a strong digest ensures priorities act like random values, maintaining balance with high probability.

• Alternative digests – instantiate CMTree::<Vec<u8>, sha3::Sha3_256>::new(), CMTree::<Vec<u8>, Sha512>::new(), or any other Digest + Clone hasher.
• Smaller priorities – use CMTree::<Vec<u8>, Sha256, u64>::new() (or any Priority implementer) when memory pressure outweighs collision resistance.
• Generic keys – keys only need Clone + Ord + Hash; the tree hashes them into priorities and Merkle payloads.
• No-std environments – enable alloc, disable default features of your digest crate if necessary.

The library is production-ready, enforced by:

• exhaustive unit suite (including large-tree stress tests),
• doc tests that mirror README examples,
• cargo fmt, clippy -- -D warnings, doc, and test checks in CI.

Planned enhancements:

• optional serde support for proofs,
• benchmarking utilities to compare digests,
• safe concurrency primitives for read-mostly workloads.

Feedback and contributions are welcome! Open an issue or pull request to discuss ideas or report edge cases.

Criterion benches cover inserts, removals, proofs, and the batch-loading workloads mentioned in the paper (including 5k and 10k batches applied to structures that already store 1 million keys). Run them with:

cargo bench -- merkle_structs

The million-element batch benchmarks are intentionally heavy; expect a few minutes on slower machines.