feat(merkle): persistent authenticated dictionary (treap-profile MVP)

[hartsock]

Summary

Add a persistent authenticated dictionary — a path-copying, hash-linked binary search tree — as a new module src/auth_dict.rs behind a new default-off cargo feature auth-dict (composing with the existing merkle feature). Every update mints O(log n) new nodes and a new root ContentId; all prior versions keep resolving unchanged because unchanged subtrees are shared by CID. Membership is provable against any version's root CID.

The MVP pins one profile: the deterministic Merkleized treap (Cartesian Merkle Tree), where the balance priority is derived from the key by hashing and recomputed by verifiers — never stored — so equal maps produce equal root CIDs regardless of insertion order. The other folded families from the catalog (authenticated red-black/2-3, IAVL, rank-augmented skip list) are explicit follow-ups (sibling issues in this epic). Scope: node shape, insert / get, inclusion proofs + verification, and a MerkleNode-based version chain. Lands under epic #17; bytes are NON-FROZEN until conformance vectors land, exactly like src/merkle.rs.

Why (the telescope)

This is not about treaps. It is about three things a user of a content-addressed store actually needs:

• Verifiable sync. Two replicas holding the same key-value map should be able to prove it by comparing one root CID. With the deterministic-treap profile, set equality upgrades to plain CID equality — no tree walk, no trusted coordinator.
• Tamper-evident history. Path copying means an update can only add blocks; every historical root CID keeps denoting exactly the map it always did. Auditing version 12 after version 400 exists is a read, not an archaeology project.
• Proofs without trust. A light client asking "does key K map to V in version N?" gets an O(log n) chain of hashes it can check against the root CID alone — the crate's thesis ("data carries its own proof of integrity, intrinsically") extended from a single blob to an ordered map with a past.

Path copying is CAS structural sharing: the structure a content-addressed store natively wants to be.

Structure & CID linkage

Tree nodes need a sibling node shape — MerkleNode does not fit. MerkleNode<T> (src/merkle.rs) holds its links in a BTreeSet<ContentId>: deduplicated, content-ordered causal-set semantics. BST children are the opposite: positional and order-significant — left and right are distinct roles (left subtree keys < node key < right subtree keys), and a BTreeSet would collapse and reorder them, destroying the search-tree invariant. So this issue introduces the named-link sibling shape:

DictNode<V> { key, value: V, left: Option<ContentId>, right: Option<ContentId> }

• Each child link serializes through ContentId's frozen serde (src/content_id.rs): a dag-cbor tag-42 IPLD link, or CBOR null when absent. Large values link by CID simply by instantiating V = ContentId; small values inline.
• DictNode<V> implements ContentAddressable with canonical_form deferring to canonical::to_canonical_dagcbor, the same one-liner as MerkleNode. A node's id therefore binds key, value, and both child links — the standard Merkle argument makes the root CID authenticate the entire tree, every version.
• Balance metadata: the treap profile stores none. The priority is derived by hashing the key and recomputed by verifiers, which is exactly what makes the shape canonical and the root CID a set fingerprint. Profiles that must store metadata in the hashed bytes (IAVL heights, red-black colors) get their own node shapes in sibling issues — they are deliberately not smuggled into this one.
• Version chain reuses MerkleNode as-is. The snapshot index is MerkleNode<VersionEntry> with VersionEntry { version: u64, root: Option<ContentId> } and parents = {previous head} — "previous version" genuinely is a causal parent, so dedup + content-ordering are the correct semantics and no new shape is needed.
• Discoverability/traversal: hand someone a root CID plus a block source and they can do everything: get/prove walk the search path fetching one DictNode per level by CID; every historical version is reachable from its own root CID; the version-chain head CID makes all snapshots enumerable by walking parents.

API sketch (Rust)

src/auth_dict.rs, gated #[cfg(feature = "auth-dict")], with auth-dict = ["merkle"] in Cargo.toml (default-off; CI covers it via the existing --all-features runs).

/// One search-tree node. Positional named links — a deliberate sibling of
/// MerkleNode, whose causal-set parents cannot express left/right.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct DictNode<V> {
    pub key: Vec<u8>,             // opaque, byte-ordered
    pub value: V,                 // inline; use V = ContentId to link big values
    pub left: Option<ContentId>,  // tag-42 link | null
    pub right: Option<ContentId>, // tag-42 link | null
}

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

/// Narrow read seam for traversal. MVP-local; converges with the shared
/// CID-resolving store trait (sibling issue in this epic) when that lands.
pub trait BlockSource<V> {
    fn get(&self, id: &ContentId) -> Result<DictNode<V>, ContentError>;
}

/// Result of a path-copying update: the new root plus ONLY the new blocks.
pub struct Update<V> {
    pub root: ContentId,
    pub new_blocks: Vec<(ContentId, DictNode<V>)>, // O(log n) expected
}

pub fn insert<V, S: BlockSource<V>>(
    store: &S, root: Option<&ContentId>, key: &[u8], value: V,
) -> Result<Update<V>, ContentError>;

pub fn get<V, S: BlockSource<V>>(
    store: &S, root: Option<&ContentId>, key: &[u8],
) -> Result<Option<V>, ContentError>;

/// Inclusion proof: the root-to-node path (sibling ids travel inside each
/// serialized node, so the path alone is checkable against the root CID).
pub struct InclusionProof<V> { /* path of DictNode<V> */ }

pub fn prove<V, S: BlockSource<V>>(
    store: &S, root: &ContentId, key: &[u8],
) -> Result<InclusionProof<V>, ContentError>;

/// Mirrors the frozen verify contract (#8): Ok(false) on mismatch, never Err.
pub fn verify_inclusion<V: Serialize>(
    root: &ContentId, key: &[u8], proof: &InclusionProof<V>,
) -> Result<bool, ContentError>;

/// Snapshot index entry; the chain itself is MerkleNode<VersionEntry>.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct VersionEntry { pub version: u64, pub root: Option<ContentId> }
pub type VersionNode = MerkleNode<VersionEntry>;

Priority derivation is an internal function of the key's digest — recomputed during insert and by any well-formedness check, never serialized.

Proof obligations

Law minimalism: four laws, each load-bearing for a claim the docs make.

1. [Lean] History independence (treap profile). For any finite set of (key, value) pairs, every insertion order yields the same root ContentId. This is the law that upgrades "same map?" to CID equality — the whole verifiable-sync story rests on it. (Inductive proof over the derived-priority treap shape.)
2. [Lean] Inclusion-proof soundness. verify_inclusion(root, k, proof) = Ok(true) implies (k, v) is in the map denoted by root, assuming collision resistance of the digest. Per the multihash doctrine, the law names the property; the v1 profile pins BLAKE3, which the CID already self-describes.
3. [Lean] Functional correctness + well-formedness. get(insert(m, k, v), k) = Some(v), other keys unaffected, and insert preserves the invariant (BST key order + heap order on derived priorities) — the invariant a verifier can check from bytes alone.
4. [TLA+] Persistence frame. Modeled over block-store actions: an update only appends blocks (expected O(log n)), never mutates or deletes; consequently every previously minted root CID remains resolvable and denotes an unchanged map. This is the tamper-evident-history claim as a checkable temporal invariant.

Acceptance here is that the laws are stated in module docs with their obligation tags; mechanization lands as a formal follow-up (sibling issue in this epic).

Python exposure

Not in this MVP. A sibling parity issue exposes the dictionary through content-addressable-py (an AuthDict-style facade over insert/get/prove/verify, root ids surfacing as the existing ContentId binding) once the byte layout stabilizes toward its conformance vectors. Distribution is unchanged: cargo + pip via the existing maturin build and tag-driven Trusted Publishing pipeline (#14).

Acceptance criteria

• src/auth_dict.rs behind default-off auth-dict = ["merkle"]; a plain cargo build / cargo test compiles nothing new; --all-features CI and the pre-push hook exercise it.
• Module docs carry the same ⚠️ BYTES ARE NON-FROZEN disclaimer pattern as src/merkle.rs: layout pinned only when dictionary conformance vectors land; until then byte changes are not breaking.
• No entries added to tests/vectors.json — that file is the frozen cross-language parity gate and excludes experimental surfaces (test: golden conformance vectors + Rust↔Python byte-parity gate #12).
• Unit tests: insert/get roundtrip; child links serialize as tag-42 (and null when absent); verify_inclusion returns Ok(true) on honest proofs and Ok(false) — never Err — on tampered ones (mirrors decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8).
• Property-style tests (seeded randomization or a proptest dev-dependency): permuted insertion orders over random key sets converge to identical root CIDs (law 1); Update.new_blocks growth is O(log n)-shaped.
• Persistence regression test: after further inserts, an old root CID still resolves and get against it returns the historical values (law 4, test-shaped).
• Version-chain test: MerkleNode<VersionEntry> chain walks from head to genesis and reaches every snapshot root.
• Rustdoc states all four proof obligations with [Lean]/[TLA+] tags; mechanization tracked in a formal follow-up (sibling issue in this epic).
• New file stays under the ~2,500-line soft cap; BlockSource documented as converging with the shared store seam (sibling issue in this epic).
• Zero-warnings gate: fmt, clippy -D warnings, all tests green under --all-features.

Non-goals / follow-ups

• Delete / remove, and treap split/join set algebra — follow-up on the same node shape.
• Exclusion (non-membership) proofs via search-path termination / adjacent keys — promised follow-up, same proof plumbing.
• Cross-version diff by parallel descent pruning equal subtree CIDs (O(changes × log n)) — follow-up.
• Other folded families (sibling issues in this epic): authenticated red-black/2-3 trees (worst-case bounds but not history-independent — equal sets can yield different root CIDs, which must be documented as a profile trade-off); an IAVL-style profile with stored heights, range scans, and ICS-23-style proofs (dropping the creating version from node bytes to restore structural dedup); the rank-augmented authenticated skip list (position-addressed select/rank proofs).
• Keyed-hash priority profile to blunt adversarial key grinding — profile hook noted, not built here.
• Byte freeze / conformance vectors and Python parity — separate follow-ups as described above.
• No changes to any frozen surface: ContentId params/serde, canonical, the verify contract, and tests/vectors.json are untouched.

References

• Anagnostopoulos, Goodrich, Tamassia, "Persistent Authenticated Dictionaries and Their Applications", ISC 2001
• Crosby & Wallach, "Authenticated Dictionaries: Real-World Costs and Trade-Offs", ACM TISSEC 2011
• Chystiakov et al., "Cartesian Merkle Tree", arXiv:2504.10944
• https://github.com/cosmos/iavl
• 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 / frozen parity gate); decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (verify contract); ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline)

---

Part of #30 (Merkle structure catalog epic).