feat(imt): zk-friendly append-only trees — frontier IMT MVP

[hartsock]

Summary

Add the circuit-oriented append-only tree family to the merkle catalog, scoped to a mergeable MVP: a frontier incremental Merkle tree (IMT) — fixed depth, O(depth) appends touching only a frontier of per-level ContentIds, precomputed universal zero-subtree nodes, constant-shape inclusion proofs, and a recent-roots ring buffer. This is the store-side mirror of the trees used by the Ethereum deposit contract, Semaphore, and Tornado. The two folded successors — LeanIMT (dynamic depth) and the indexed Merkle tree (sorted linked leaves for one-proof exclusion) — are explicitly deferred to sibling issues.

New module src/imt.rs behind a new default-off cargo feature imt = ["merkle"]. Bytes are NON-FROZEN until Merkle conformance vectors land (per the freeze doctrine in src/merkle.rs and epic #17); nothing is added to tests/vectors.json.

Why (the telescope)

The user need is proving membership in a growing log without shipping the log. An append-only tree gives a tamper-evident accumulator: one root ContentId commits to every leaf ever appended, an O(depth) constant-shape proof convinces a verifier a leaf is in it, and — because appends never rewrite history — two parties can sync by comparing roots and exchanging only the subtrees they don't share. That is provenance, tamper-evidence, and verifiable sync in one structure; the tree is just the instrument.

The CAS-native win this crate uniquely adds: every zero-subtree of height k is ONE universal node, stored once, shared by CID across every tree of every application at that depth. In a content-addressed store the empty halves of a sparse append-only tree cost nothing per tree — they deduplicate globally by construction. And because appends share every untouched subtree CID with the previous state, structural persistence is free: the full audit history of tree states costs only the O(depth) nodes each append actually minted.

Structure & CID linkage

Every node in the structure derives its identity through the existing frozen pipeline: implement ContentAddressable (src/trait_def.rs) with the one-line canonical_form deferring to to_canonical_dagcbor (src/canonical.rs), so each node's id is a frozen-parameter ContentId (src/content_id.rs) and every ContentId field inside a node lands on the wire as a dag-cbor tag-42 link — exactly the pattern MerkleNode established (#11).

MerkleNode's causal-set parents do NOT fit the tree body — a sibling node shape is required. src/merkle.rs documents parents: BTreeSet<ContentId> as deduplicated, content-ordered causal-set semantics. A binary tree's children are positional (left vs right is load-bearing for the path recomputation) and may be equal — the canonical case being a zero parent hash(z, z), whose two identical children a BTreeSet would collapse into one link, silently changing the node's arity and id. This is precisely the seam the merkle module docs anticipated. The MVP therefore introduces:

• ImtInner { left: ContentId, right: ContentId } — the positional sibling shape. Two ordered named links; left == right is representable and meaningful.
• ImtState { depth, next_index, frontier: Vec<ContentId> } — the O(depth) mutable state, itself ContentAddressable (its frontier entries are tag-42 links), so every tree state has a CID.
• MerkleNode<ImtState> for the audit chain — where the causal-set shape DOES fit. Each state snapshot is chained to its predecessor with parents = {prev_state_id} (a 0-or-1-element causal set), giving a prev-chained, tamper-evident history of the accumulator itself. This is why the feature composes as imt = ["merkle"].

Discoverability / traversal by root CID: the root is an ImtInner id. Any consumer holding the root CID and a CID-resolving lookup walks root → ImtInner → left/right → … down to the leaves; branches into empty territory terminate at the universal zero-subtree CIDs, which resolve to the same shared nodes for every tree. The head CID of the MerkleNode<ImtState> chain likewise makes the entire state history discoverable. The MVP keeps the crate store-free: append emits the newly minted (ContentId, ImtInner) pairs for the caller to persist in whatever store it owns, and proof construction takes a caller-supplied resolver closure — the narrow seam a shared node-store trait (sibling issue in this epic) will later formalize.

API sketch (Rust)

// src/imt.rs — cargo feature "imt" (default-OFF), declared as: imt = ["merkle"]
// ⚠️ BYTES NON-FROZEN until Merkle conformance vectors land (see src/merkle.rs).

/// Positional inner node: ORDERED left/right children (sibling shape to
/// merkle::MerkleNode — children may be EQUAL, e.g. zero parents).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ImtInner {
    pub left: ContentId,   // tag-42 link via the frozen ContentId serde
    pub right: ContentId,  // tag-42 link; left == right is meaningful
}

impl ContentAddressable for ImtInner {
    fn canonical_form(&self) -> Result<Vec<u8>, ContentError> {
        canonical::to_canonical_dagcbor(self)
    }
}

/// Universal zero-subtree ids: zeros[0] = id of a fixed, documented
/// empty-leaf sentinel; zeros[k+1] = ImtInner{ zeros[k], zeros[k] }.id().
/// One node per height, shared by CID across ALL trees.
pub struct ZeroSubtrees { /* Vec<ContentId> */ }
impl ZeroSubtrees {
    pub fn new(max_height: u8) -> Result<Self, ContentError>;
    pub fn id(&self, height: u8) -> Option<&ContentId>;
}

/// O(depth) append-only accumulator state (fixed depth; no update/delete —
/// spent-ness lives in external nullifier structures, out of scope here).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ImtState {
    pub depth: u8,
    pub next_index: u64,
    pub frontier: Vec<ContentId>, // one per level; tag-42 links
}
impl ContentAddressable for ImtState { /* same one-liner */ }

impl ImtState {
    pub fn new(depth: u8, zeros: &ZeroSubtrees) -> Result<Self, ContentError>;
    pub fn root(&self, zeros: &ZeroSubtrees) -> Result<ContentId, ContentError>;
    /// Append one leaf id. Touches ONLY the frontier; returns the new root
    /// plus the O(depth) newly minted inner nodes so the CALLER persists
    /// them — the crate stays store-free.
    pub fn append(&mut self, leaf: ContentId, zeros: &ZeroSubtrees)
        -> Result<AppendOutcome, ContentError>;
}

pub struct AppendOutcome {
    pub root: ContentId,
    pub minted: Vec<(ContentId, ImtInner)>,
}

/// Constant-shape inclusion proof: exactly `depth` sibling ids.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ImtProof {
    pub leaf_index: u64,
    pub siblings: Vec<ContentId>,
}
impl ImtProof {
    /// PURE verification: recompute the path, compare roots.
    /// Mismatch is Ok(false), never Err — mirroring the frozen
    /// ContentAddressable::verify contract (#8).
    pub fn verify(&self, leaf: &ContentId, root: &ContentId)
        -> Result<bool, ContentError>;
}

/// Build a proof by walking down from the root through a caller-supplied
/// resolver (the node-store seam): CID -> canonical node bytes.
pub fn prove(
    root: &ContentId, depth: u8, leaf_index: u64,
    resolve: &mut dyn FnMut(&ContentId) -> Result<Option<Vec<u8>>, ContentError>,
) -> Result<ImtProof, ContentError>;

/// Fixed-capacity recent-roots ring: slightly-stale proofs still verify.
pub struct RecentRoots { /* capacity + ring of ContentId */ }
impl RecentRoots {
    pub fn new(capacity: usize) -> Self;
    pub fn push(&mut self, root: ContentId);
    pub fn contains(&self, root: &ContentId) -> bool;
}

// Audit chain (composes with the merkle feature): each state snapshot chained
// causally — MerkleNode::new(state, [prev_state_id]) — head CID makes the
// whole accumulator history discoverable and tamper-evident.

Proof obligations

Law minimalism: four laws, each load-bearing for the structure's purpose, none ornamental. Laws name properties; the CID profile (src/content_id.rs, frozen v1 params) pins the algorithms.

1. Frontier correctness [Lean] — for every leaf sequence, the O(depth) frontier fold yields the same root as the naive full-tree reference fold over the leaves padded with zeros[0]. (The root is a deterministic function of the leaf sequence alone; the frontier is a faithful compression of the tree, not a new semantics.)
2. Zero-subtree universality [Lean] — zeros[k] depends only on k and the mint pipeline: zeros[k+1] = id(ImtInner{zeros[k], zeros[k]}). Hence one universal node per height, shared by CID across all trees and applications.
3. Proof soundness modulo collision resistance [Lean] — if verify(proof, leaf, root) = Ok(true) and root is the root of state S, then leaf occupies leaf_index in S, or a collision of the digest (the collision-resistance property, algorithm pinned by the profile) has been exhibited.
4. Append-only safety + recency window [TLA+] — over the state machine of appends: (a) the only transition is leaves(S') = leaves(S) ++ [l] — no update, no delete; (b) RecentRoots accepts exactly the roots produced by the last capacity transitions, never a root outside the append history.

Mechanization is tracked by the formal work (sibling issue in this epic); this issue's deliverable is the laws stated in the module docs with these tags, plus the executable evidence below.

Python exposure

Deferred, per the parity doctrine: once the Rust surface stabilizes, content-addressable-py grows ImtState / ImtProof / ZeroSubtrees wrappers through the same PyO3 + pythonize path as the existing bindings, shipped by the existing tag-driven cargo + pip pipeline (#14). Because the bytes are non-frozen, no cross-language byte-parity vectors are added until the Merkle conformance-vector freeze — Python exposure lands as a follow-up (sibling issue in this epic) after that freeze, matching how merkle itself is staged.

Acceptance criteria

• New cargo feature imt, default-OFF, declared as imt = ["merkle"]; plain cargo build / cargo test compiles nothing new; CI and the pre-push hook exercise it via --all-features (same treatment as merkle in Cargo.toml)
• Single module src/imt.rs (soft cap 2,500 lines), module docs carrying the same BYTES ARE NON-FROZEN disclaimer block as src/merkle.rs, including the explicit "do NOT add vectors to tests/vectors.json" instruction
• ImtInner positional-shape tests: swapping left/right changes the id; left == right is representable and hashes correctly (the exact case BTreeSet parents would collapse — cite src/merkle.rs's design note in the test docstring)
• Tag-42 link tests for ImtInner and ImtState fields, mirroring parents_encode_as_tag42_links in src/merkle.rs
• Differential test: frontier root() equals a naive in-test reference fold, across sizes including 0, 1, and power-of-two boundaries (property-style, many sizes)
• append is O(depth): minted.len() <= depth asserted; appends touch only the frontier
• Zero-subtree universality test: two independently built trees (and different depths sharing a prefix) produce identical zeros[k] CIDs
• prove/verify round-trip through an in-memory map resolver (no real filesystem in unit tests); wrong leaf / wrong root / truncated siblings ⇒ Ok(false), never Err (mirrors the frozen verify contract, decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8)
• Structural-persistence test: after an append, every untouched frontier entry and subtree CID is byte-identical to the prior state's
• Audit-chain test: MerkleNode<ImtState> with parents = {prev_state_id} — history walkable from the head CID, and tampering with an earlier state changes every descendant id
• RecentRoots: a proof against a root within the window verifies; roots beyond capacity are evicted
• The four proof obligations recorded in the module docs with their [Lean] / [TLA+] tags
• Rustdoc examples compile as doctests; zero warnings (cargo clippy -- -D warnings, cargo fmt --check) with and without the feature

Non-goals / follow-ups

• LeanIMT (dynamic depth; a single-child parent adopts the child value verbatim — CAS mirror: the parent slot holds the child CID directly, keeping the CID DAG isomorphic to the digest tree) — (sibling issue in this epic)
• Indexed Merkle tree (Aztec-style nullifier tree: leaves (value, next_index, next_value) thread a sorted linked list; exclusion = one low-leaf inclusion proof + two comparisons; the list must use logical (index, value) pointers, never next-CID links — successor-CID churn would cascade rewrites) — (sibling issue in this epic)
• Dual-digest leaf binding (Poseidon/keccak digest in-circuit, CID in-store, bound per node) — follow-up leaf-payload shape minted through ContentAddressable normally. Explicitly not via ContentId::from_blake3_content_digest: that door's precondition is a BLAKE3-over-canonical-dag-cbor digest, which a circuit digest is not.
• No circuit code and no Poseidon dependency — this module is the store-side companion of circuit trees, not the in-circuit tree; laws name properties, the CID profile pins algorithms
• No store implementation — the resolver closure is the seam; a shared CID-resolving node-store trait is (sibling issue in this epic)
• No nullifier / spent-ness tracking — external by design in the frontier IMT model
• No byte freeze — these bytes join the Merkle conformance-vector freeze already promised toward 0.1.0-rc1 under epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17; until then, changing them is not a breaking change

References

• src/content_id.rs — frozen v1 ContentId mint pipeline, tag-42 serde, presentation contract
• src/merkle.rs — MerkleNode, causal-set parents rationale, the non-frozen-bytes doctrine this module inherits
• src/trait_def.rs, src/canonical.rs — ContentAddressable / canonical dag-cbor seams
• Epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17 (Road to 0.1.0-rc1); feat: add feature-gated merkle module (MerkleNode DAG-node helper) #11 (MerkleNode); test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors + Rust↔Python parity); decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (verify contract)
• Eth2 book, "The deposit contract" — https://eth2book.info/latest/part2/deposits-withdrawals/contract/
• ZK-Kit, "LeanIMT" — https://zkkit.org/leanimt-paper.pdf
• Aztec docs, "Indexed Merkle Tree (Nullifier Tree)"
• Nomos, "Designing Nullifier Sets: Sparse vs Indexed Merkle Trees"

---

Part of #30 (Merkle structure catalog epic).