Crate cmtree 

Deterministic Cartesian Merkle Tree implementation.

This crate provides a no-std friendly version of the Cartesian Merkle Tree described in https://arxiv.org/pdf/2504.10944. A Cartesian Merkle Tree combines binary-search-tree ordering, heap balancing, and Merkle hashing. For each key we derive a deterministic priority from its hash, producing a unique tree layout regardless of insertion order. Every node carries an aggregated Merkle hash, enabling succinct membership and non-membership proofs.

Complexity

The structure behaves similarly to a treap whose priorities are derived from the key material. Assuming a strong digest and random-looking priorities, the tree remains balanced with high probability, yielding:

• CMTree::insert, CMTree::remove, CMTree::contains – O(log n) expected time.
• CMTree::generate_proof – O(log n) time and proof size.
• CMTree::root_hash – O(1) time (hashes are cached on each node).

Space consumption is O(n) for n stored keys, with a single node allocated per entry plus cached digests for child subtrees.

Structs

CMTree

Deterministic Cartesian Merkle Tree backed by a cryptographic digest.

Proof

Membership or non-membership proof for a Cartesian Merkle Tree.

ProofNode

Authentication data for a single step in a Merkle proof.

Traits

Priority

Trait describing a priority type derived from hashed key material.

Type Aliases

Sha256Hash

Digest output for the default Sha256 hasher used by CMTree.