Struct Cmt 

pub struct Cmt { /* private fields */ }

The Canonical Mutable Tree over the Merkle Spine.

Positional and dense: cells are addressed by flat index 0..len. The tree shares the spine’s proof-spine index space, so an inclusion proof generated here verifies with spine::verify_inclusion against the trusted (index, tree_size, arity, root) topology. Unlike the append-only CML it has no frontier and no consistency proofs — interior cells mutate, which the frontier’s left-subtrees-sealed assumption cannot model.

Single-algorithm structurally, but the materialization holds one {hasher, root, cache} view per registered algorithm, so a node may be addressed under many algorithms (per-node multi-hash) and an algorithm may be added after the fact with the root recomputed in O(log n) along the changed node’s ancestors only (Cmt::set, retroactive add). The cross-tree binding of those per-algorithm roots is the polydigest combinator’s concern, not the CMT’s — the CMT exposes each algorithm’s raw member root and the structural seal, never a binding/combined root.

Implementations

impl Cmt

pub fn new(config: Config) -> Result<Self>

Create an empty tree.

Fails with Error::InvalidArity if config.arity is outside the spine’s 2..=256 range.

pub fn register_algorithm( &mut self, alg_id: u64, hasher: Box<dyn Hasher>, ) -> Result<()>

Register an algorithm under alg_id, hashing every existing cell under it. This is the bulk registration cost (O(n) over n existing cells), distinct from the per-node retroactive add below.

Fails with Error::DuplicateAlgorithm if alg_id is already registered.

pub fn set( &mut self, index: u64, payload: Vec<u8>, metadata: Vec<u8>, ) -> Result<()>

Set the payload (and opaque metadata) of cell index.

Indices extend the tree densely: setting index == len appends a cell; setting an existing index overwrites it. A gap (index > len) is rejected with Error::IndexGap — the tree is positional and dense, not sparse.

Overwriting an existing cell recomputes only that cell’s ancestor path in every registered algorithm: O(log n) per algorithm. Appending may change the spine shape and is recomputed against the new shape.

pub fn get(&self, index: u64) -> Option<&[u8]>

Read the payload of cell index, or None if out of range.

pub fn metadata(&self, index: u64) -> Option<&[u8]>

Read the opaque metadata of cell index, or None if out of range.

The bytes are returned verbatim; the library never parses them (INV-METADATA-AGNOSTIC).

pub fn len(&self) -> u64

Number of cells in the tree.

pub fn is_empty(&self) -> bool

Whether the tree holds no cells.

pub fn arity(&self) -> u64

The configured proof-spine arity.

pub fn root(&self, alg_id: u64) -> Option<Vec<u8>>

The current per-algorithm member root under alg_id — the raw root the leaves authenticate against — or None if the algorithm is unregistered or the tree is empty.

This is the structural per-algorithm root. The cross-tree binding / combined root that folds every algorithm’s member root together is the polydigest combinator’s derived view, not the CMT’s (D9/D12); the CMT exposes the raw member roots it materializes and leaves the binding to polydigest.

pub fn member_roots(&self) -> Vec<(u64, Vec<u8>)>

The set of registered algorithm IDs paired with their current member root, sorted by algorithm ID, skipping any with no root (empty tree).

The polydigest combinator reads these raw member roots as the children of its binding/combined-root fold; the CMT itself never folds them.

pub fn hasher(&self, alg_id: u64) -> Option<&dyn Hasher>

The hasher registered under alg_id, or None if unregistered.

The polydigest combinator needs the algorithm’s own hash to fold the binding root over the member roots; the CMT materializes the per-algorithm roots but never folds them, so it lends the hasher rather than computing the binding root itself.

pub fn inclusion_proof( &self, alg_id: u64, index: u64, ) -> Option<(Vec<u8>, Vec<ProofStep>)>

Generate an inclusion proof for cell index under alg_id.

Returns the leaf digest and the proof path. The path verifies with spine::verify_inclusion against the trusted (index, len, arity, root) — the CMT shares the spine index space, so it generates paths the spine checks rather than running a second verifier. Returns None if alg_id is unregistered or index is out of range.

pub fn leaf_proof(&self, alg_id: u64, index: u64) -> Option<LeafProof>

Produce a self-contained spine::LeafProof for cell index under alg_id — the live “is this a legitimate leaf?” witness, peer of the inclusion proof. It bundles the leaf digest with its trusted positional parameters (index, len, arity) and the inclusion path, so a consumer verifies with one spine::LeafProof::verify call against an authenticated root. Returns None for an unregistered algorithm or an out-of-range index.

pub fn non_membership_proof( &self, alg_id: u64, index: u64, ) -> Option<(Vec<u8>, Vec<ProofStep>)>

Generate a non-membership proof for index under alg_id: an inclusion proof for the spine null constant (SAD §5, inclusion-of-null via collapse).

Succeeds only when cell index actually hashes to null() — i.e. the position carries no real value — returning the null leaf digest and the proof path. A cell with a real payload is present, so non-membership returns None. Returns None for an unregistered algorithm or an out-of-range index.

pub fn add_algorithm_at( &mut self, alg_id: u64, index: u64, hasher: Box<dyn Hasher>, ) -> Result<usize>

Add alg_id to a single cell index after the fact, recomputing the root in O(log n) along that cell’s ancestors only (D11, the “Post-Facto Digest” / retroactive algorithm addition).

This is the mutable tree’s incremental multi-hash operation: distinct from bulk filling (a polydigest operator, O(n), which re-derives a whole algorithm’s history). Here a node gains a digest under a newly seeded algorithm and only its ancestor path is touched; positions other than index contribute their already-materialized digests (the null constant for positions never hashed under this algorithm).

Returns the number of inner-node digests the per-node add recomputed — the cell’s ancestor depth, the O(log n) cost witness (the initial null seeding is the one-time O(n) materialization, not the per-node cost).

Fails with Error::DuplicateAlgorithm if alg_id is already registered and with Error::IndexGap if index is out of range.

pub fn seal(self) -> Result<Seal>

Consume the tree and seal it into the general structural spine::Seal (D13, the structural facet of the seal chain).

One-way: there is no unseal and no path back to a Cmt (C-SEAL-ONEWAY). The seal computes the resumable frontier — every registered algorithm’s frontier peaks (the digests of the perfect k-ary subtrees the spine topology names at this size). The Seal carries no committed epoch timeline and no binding root — those are the epoch facet, added by the polydigest combinator as a wrapper over this general Seal (polydigest(cmt)), never baked in here.

A live Cmt has no frontier stack — that absence is the mutable/append tell. Computing the peaks at seal erases the distinction, so every Seal uniformly carries a resumable frontier regardless of source kind, and the member root every consumer sees is the fold of those peaks (identical to the tree’s own root, since both fold the same perfect-subtree digests).

No from_seal — why a Seal cannot revive a Cmt

There is deliberately no Cmt::from_seal. A frontier is the complete continuation state of an append-only log (every future append folds against the peaks alone), but only partial state for a mutable tree: mutating an interior cell needs every cell’s digest along its ancestor path, and the seal dropped all of those, keeping only the peaks. Reviving arbitrary mutation over the committed positions would also un-seal the committed past — the one-way guarantee the seal exists to make. The way to a readable, mutable-or-append tree over the committed data is the polydigest combinator’s fill (data-required), which rebuilds and verifies against the committed binding root; the discarded frontier is simply unused when the fill target is a mutable tree.

Fails with Error::EmptySeal on an empty tree (nothing to seal) and propagates Error::MalformedSeal if the spine rejects the frontier.

Trait Implementations

impl Debug for Cmt

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.