feat(merkle): verifiable-map head chain (key transparency spine)

[hartsock]

Summary

Add src/verifiable_map.rs behind a new default-OFF cargo feature verifiable-map: the head-chain spine of a Trillian-style verifiable map. The MVP is one new node shape, MapHead — {revision, map_root, mutation_log_root, prev_head}, all links as ContentId — plus verified chain traversal over a minimal CID-resolving store seam and an equivocation check (two distinct heads claiming the same revision). Bytes are explicitly NON-FROZEN until Merkle conformance vectors land (same posture as src/merkle.rs). Lands under epic #17 as one mergeable ratchet; the interior authenticated map (SMT/prefix tree) and the append-only mutation log are sibling structures, linked here only by CID.

This is the composition spine for the transparency family: Trillian's verifiable map, the CONIKS/SEEMless/Parakeet key-transparency lineage, and Merkle² all hang their interior trees off exactly this kind of signed-head chain.

Why (the telescope)

The crate already answers "are these bytes the bytes I was promised?" — immutable data carrying its own proof. What it cannot yet answer is the mutable-view question users actually have of any directory, package index, or key server:

• "Is the value I fetched for this key the same one everyone else sees?" — a split-view (equivocating) server is the attack; detecting it needs comparable, content-addressed heads.
• "Can the operator quietly rewrite history?" — no: every head binds its predecessor by CID, so the entire past is fixed by the newest head's id.
• "Can an auditor reconstruct exactly how revision n became revision n+1?" — yes: each head binds the mutation-log root, so full-map correctness is checkable by replay.

One head CID becomes the entire trust surface for a mutable dataset: current contents, full history, and the exact mutation sequence between revisions are all reachable from it. That is provenance for state, not just for blobs — the same user need Kyln-class provenance tooling serves, delivered as a small content-addressed structure rather than a service.

Structure & CID linkage

Three linked DAGs under one head object, every edge a ContentId (src/content_id.rs — frozen CIDv1, dag-cbor 0x71, BLAKE3 0x1e, serialized via the frozen tag-42 serde):

MapHead(rev=n) ──map_root──────────▶ authenticated-map root   (sibling issue in this epic)
      │        ──mutation_log_root─▶ append-only log root     (sibling issue in this epic)
      └──────────prev_head─────────▶ MapHead(rev=n-1) ─ … ─▶ MapHead(rev=0, prev_head=None)

Why MerkleNode does not fit here. MerkleNode<T> (src/merkle.rs) carries parents as a BTreeSet<ContentId> — deduplicated, content-ordered, causal-set semantics. A map head's links are named and role-significant: map_root, mutation_log_root, and prev_head mean different things, and a dedup'd set would erase the roles entirely (and collapse links whenever two roots happen to coincide, e.g. an empty-map root recurring across revisions). So MapHead is a stated sibling node shape: a struct with named tag-42 links, deriving its identity through the same path as MerkleNode — ContentAddressable::canonical_form deferring to to_canonical_dagcbor (src/canonical.rs), no bespoke canonicalization. Same derivation, different link discipline.

Discoverability from one root CID. Given a head CID and a get-by-CID store, a client resolves the head, verifies bytes-vs-CID with the existing ensure_content_id() contract (#8), then walks: map_root for current contents, mutation_log_root for the mutation sequence, prev_head repeatedly for history. In the sibling interior-map structure (opaque roots from this issue's perspective), a revision re-mints only the interior nodes along each mutated key's path — O(log n) per touched key — while unchanged subtrees are shared by CID across revisions. That structural sharing keeps total storage near-linear in total mutations and makes the aZKS-style "old CIDs remain reachable" claim a structural fact rather than an operator promise.

Design decision — no sig field in the MVP head. Trillian's SignedMapHead embeds a signature. Here the head's identity must be exactly its four semantic fields: if signature bytes lived inside the hashed body, re-signing the same logical head would mint a new CID and read as a false equivocation. Signatures therefore travel in a detached envelope (follow-up), and this crate stays free of signature-scheme dependencies. Per the multihash doctrine, laws below name properties; the frozen CID profile pins the algorithms.

API sketch (Rust)

// src/verifiable_map.rs — feature = "verifiable-map", default-OFF.
// ⚠️ BYTES NON-FROZEN until Merkle conformance vectors land (see src/merkle.rs banner).

use serde::{Deserialize, Serialize};

use crate::content_id::ContentId;
use crate::error::ContentError;
use crate::trait_def::ContentAddressable;

/// One revision head of a verifiable map. Field key strings are load-bearing
/// for the id and part of the (non-frozen) byte layout.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MapHead {
    pub revision: u64,
    /// Root of the authenticated map (interior shape: sibling issue).
    pub map_root: ContentId,
    /// Root of the append-only mutation log (interior shape: sibling issue).
    pub mutation_log_root: ContentId,
    /// Previous head; `None` exactly at revision 0.
    pub prev_head: Option<ContentId>,
}

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

impl MapHead {
    pub fn genesis(map_root: ContentId, mutation_log_root: ContentId) -> Self;
    /// revision = prev.revision + 1, prev_head = Some(prev_id).
    pub fn next(prev: &MapHead, prev_id: ContentId,
                map_root: ContentId, mutation_log_root: ContentId) -> Self;
    /// Alias for `content_id()`, mirroring `MerkleNode::id`.
    pub fn id(&self) -> Result<ContentId, ContentError>;
}

/// Minimal CID-resolving store seam. Local to this module for now; migrates to
/// the shared store trait when it lands (sibling issue in this epic).
pub trait NodeStore {
    fn get(&self, id: &ContentId) -> Result<Option<Vec<u8>>, VerifiableMapError>;
}

/// Errors are module-local — the frozen `ContentError` surface (#7) is not expanded.
pub enum VerifiableMapError { /* MissingNode, BadNode(ContentError), RevisionGap, … */ }

/// Walk prev-links from `head` to genesis. Every fetched node is verified
/// against its CID (ensure_content_id semantics) before being trusted, and
/// revisions must step down by exactly 1 to 0.
pub fn walk_head_chain<S: NodeStore>(store: &S, head: &ContentId)
    -> Result<Vec<MapHead>, VerifiableMapError>;

pub enum HeadRelation {
    /// One head is an ancestor of the other (or they are equal).
    Consistent { ancestor: ContentId, descendant: ContentId },
    /// Same revision, different CIDs — the split-view smoking gun
    /// (for `revision: 0`, see the `compare_heads` contract below).
    Equivocation { revision: u64, a: ContentId, b: ContentId },
}

/// The MVP proof kind: chain-consistency-by-walk / equivocation detection.
///
/// Contract: meaningful only for two heads *claimed* to be views of the same
/// logical map. For valid chains the result is exhaustive: equal or
/// ancestor-related heads are `Consistent`; otherwise the chains disagree at
/// some shared revision, which is `Equivocation`. The edge case
/// `Equivocation { revision: 0, .. }` means the chains share no genesis at
/// all — a split view from birth *or* simply two unrelated maps. Telling
/// those apart requires binding a chain to an operator/map identity, which
/// is exactly the detached signature-envelope follow-up; until then the
/// rustdoc states this caveat explicitly.
pub fn compare_heads<S: NodeStore>(store: &S, a: &ContentId, b: &ContentId)
    -> Result<HeadRelation, VerifiableMapError>;

The feature is independent of merkle (no MerkleNode reuse — loose coupling); CI's existing --all-features runs cover both. Estimated well under the 2,500-line soft cap.

Proof obligations

Minimal law set — each names a property; the frozen CID profile (#4) pins the algorithms:

1. [Lean] Head identity binds the view. canonical_form on MapHead is deterministic, and any change to revision, map_root, mutation_log_root, or prev_head changes the CID, up to the collision-resistance property assumed of the pinned multihash profile.
2. [Lean] Chain tamper-evidence. If head H_n reaches H_m via prev-links, the full sequence of (revision, map_root, mutation_log_root) between them is determined by H_n's CID alone; altering any reachable head forces a different H_n CID (or a hash collision).
3. [TLA+] Append-only head chain. Honest-operator spec: each published head has revision = prev.revision + 1. Invariant: along any prev-chain, revisions strictly step down to 0 with no gaps; walk_head_chain accepts exactly the chains satisfying the invariant.
4. [TLA+] Equivocation detectability. For two heads claimed to belong to the same map: no honest chain contains two heads with equal revision and unequal CIDs; compare_heads reports Equivocation in exactly those cases and Consistent on ancestor-related (or equal) pairs. A revision-0 disagreement is reported the same way but is documented as "equivocation or unrelated maps" until the signature envelope binds map identity (follow-up).

Python exposure

Follow-up (sibling issue in this epic), after the Rust surface settles: expose MapHead construction, id(), walk_head_chain, and compare_heads through content-addressable-py (PyO3 + pythonize), with the store seam as a Python callable resolving CID → bytes. Ships through the existing maturin build and tag-driven Trusted Publishing pipeline (#14) — distribution stays cargo + pip. Cross-language byte-parity tests arrive only with the conformance-vector freeze; until then this family stays out of the frozen parity gate, like the rest of the merkle surface.

Acceptance criteria

• New module src/verifiable_map.rs gated by default-OFF feature verifiable-map; plain cargo build / cargo test output is unchanged (no new symbols in the default surface).
• MapHead implements ContentAddressable via to_canonical_dagcbor; links serialize as dag-cbor tag-42 ContentId links (test asserts tag heads, mirroring parents_encode_as_tag42_links in src/merkle.rs).
• Module docs carry the ⚠️ NON-FROZEN-bytes banner mirroring src/merkle.rs, including the field-key-strings-are-load-bearing note and the explicit "do NOT add to tests/vectors.json" rule; tests/vectors.json is untouched.
• No frozen surface expands: src/content_id.rs, src/canonical.rs, ContentError (Stabilize the ContentError public contract before freezing 0.1.0 #7), and the serde forms (contract: freeze ContentId serde representation (gate item 1) with golden vectors #3) are unmodified; errors are module-local.
• Tests (TDD, property-style where apt): id determinism; each of the four fields independently changes the id; genesis vs next linkage; round-trip through from_canonical_dagcbor plus verify() / ensure_content_id(); walk_head_chain verifies every fetched node against its CID and rejects revision gaps, missing nodes, and bytes/CID mismatches; compare_heads positive (equivocation) and negative (ancestor / equal) cases, including a revision-0 mismatch exercising the documented same-map contract. Store mocked in-memory — no real filesystem.
• NodeStore stays a one-method get-by-CID seam, with a doc note that it migrates to the shared store trait (sibling issue in this epic).
• Rustdoc for every public item, including the compare_heads same-map contract; README feature list gains a verifiable-map entry with the non-frozen disclaimer.
• Zero warnings (clippy -D warnings), cargo fmt clean, one-issue-one-PR under epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17.

Non-goals / follow-ups

• Interior authenticated map (SMT / prefix tree behind map_root) and append-only mutation log (behind mutation_log_root), including compressed inclusion/exclusion proofs and O(log n) log-consistency proofs — sibling issues in this epic; this issue treats both roots as opaque CID links, which is exactly what the head binds.
• Signature envelope — detached, scheme-agnostic operator signatures over a head CID (restoring full SignedMapHead semantics without polluting head identity, and giving chains the map/operator identity that disambiguates the revision-0 compare_heads case) — follow-up.
• CONIKS/SEEMless/Parakeet privacy fold — VRF-keyed leaf positions and aZKS append-only auditing; needs a VRF seam, deliberately outside this crate's dependency budget for now — follow-up (sibling issue in this epic).
• Merkle² fold — chronological-tree nodes each embedding a prefix-tree root over their leaf span, for O(log² n) epoch-free monitoring — follow-up once log + prefix-tree siblings exist.
• Byte freeze — the promised Merkle conformance vectors toward 0.1.0-rc1 (Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17) freeze this family's bytes; not this issue.
• Networking, gossip, or auditor services — this crate ships structures and proofs, not servers.

References

• 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), decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (verify contract), freeze: lock CID parameters (v1 / dag-cbor 0x71 / BLAKE3 0x1e) as the v1 contract #4 (CID params freeze), test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors — merkle bytes deliberately excluded), ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release).
• Trillian, Verifiable Data Structures: https://github.com/google/trillian/blob/master/docs/VerifiableDataStructures-Latest.md
• Melara et al., CONIKS: Bringing Key Transparency to End Users, USENIX Security 2015.
• Facebook auditable key directory (SEEMless/Parakeet lineage, deployed in WhatsApp): https://github.com/facebook/akd
• Hu et al., Merkle²: A Low-Latency Transparency Log System, IEEE S&P 2021 — https://eprint.iacr.org/2021/453

---

Part of #30 (Merkle structure catalog epic).