feat(merkle): persistent Merkle vector (CID-RRB) — verifiable Vec

[hartsock]

Status: NOVEL / SPECULATIVE (tier: invented). RRB vectors are well-studied persistent sequences. Generic authenticated-data-structure compilers (Miller et al., POPL 2014 — see References) show any purely functional structure can be authenticated in principle, but we know of no concrete hash-linked RRB variant — let alone one profiled onto self-describing CIDs — and no known Merkle sequence structure supports efficient verifiable splice. This issue proposes inventing that structure on top of this crate's frozen ContentId spine. Labeled speculative on purpose: the MVP below is deliberately small so we learn whether the idea earns its keep before any byte freeze.

Summary

Add a Persistent Merkle Vector — an authenticated relaxed-radix-balanced (RRB) persistent vector in which every node is a canonical dag-cbor block, all child references are ContentId tag-42 links, and size tables are committed into the hash. It gives users a general-purpose verifiable Vec: O(log32 n) index access with compact inclusion proofs, structural sharing across snapshots, and (in follow-ups) O(log n) verifiable concat/slice/splice.

Scope of THIS issue (one-issue-one-PR MVP): node shapes + push_back/get/len/root_id + index-inclusion proofs with a verifier, behind a new default-off cargo feature. Concat/slice/splice and transition proofs are explicit follow-ups.

Why (the telescope)

The user need is provenance and tamper-evidence for ordered data — logs, event sequences, chunk lists, document revisions — not hashing for its own sake:

• "Prove item i is in this dataset, at position i, without shipping the dataset." A verifier holding only the root ContentId replays a ceil(log32 n) path and either confirms the element or refutes the claim. Out-of-range indices are refuted by the committed count — no exclusion machinery needed.
• Verifiable sync. Two holders of vector snapshots diff by CID: equal subtree CIDs short-circuit, so most snapshots share most blocks and sync ships only the changed spine. This is the sequence-shaped counterpart of what MerkleNode already gives DAG-shaped histories.
• A foundation primitive. Deque / priority-queue / recency-spine variants later derive by swapping the committed monoid annotation (follow-up, not this issue). Landing the vector settles the pattern once.

Chunked-DAG approaches (unixfs-style) can prove inclusion but cannot concat/slice without rewriting the index; the RRB shape is what makes verifiable splice plausible. That headline capability is the destination; this issue lands only the load-bearing floor.

Structure & CID linkage

Every node is a canonical dag-cbor block whose identity is its ContentId (src/content_id.rs — frozen v1 profile: dag-cbor 0x71 + BLAKE3 0x1e, 32-byte digest). Three node shapes, each implementing ContentAddressable (src/trait_def.rs) via to_canonical_dagcbor (src/canonical.rs), exactly the MerkleNode pattern in src/merkle.rs:

• Leaf — up to 32 inline values.
• Interior — level, up to 32 positional child links (Vec<ContentId>, serialized as an array of tag-42 links), and a sizes: Vec<u64> table present only when the node is relaxed (non-full left children after concat — MVP builds strict trees, but the field is in the shape from day one so relaxation is not a byte-shape change later).
• Root header — count, optional root link, tail link (RRB tail buffer for O(1) amortized push_back). The root header's ContentId is the vector's identity.

Why MerkleNode does not fit, per its own design seam: MerkleNode.parents is a BTreeSet<ContentId> — deduplicated, content-ordered causal-set semantics. Its docs reject Vec parents precisely so link order cannot affect the hash. A vector's children are the opposite contract: positional, order-significant, duplicate-bearing (the same leaf block legitimately appears twice in a vector containing a repeated run). So this structure introduces the positional sibling node shapes that seam calls for — Vec<ContentId> children where order IS the data — while keeping the identical ContentAddressable derivation: no bespoke canonicalization, no new hashing path.

Discoverability: because every inter-node reference is a real tag-42 IPLD link, the entire vector is walkable from the root CID by any generic IPLD traversal — root header → root/tail → interiors → leaves. count and the size tables are inside hashed bodies, so navigation itself is authenticated: a verifier re-derives each block's ContentId (via from_canonical_bytes_checked semantics) and checks it against the link in its parent, then replays the radix/size-table arithmetic.

API sketch (Rust)

New module src/merkle_vector.rs behind a new default-OFF feature that composes with the existing one:

[features]
merkle = []
merkle-vector = ["merkle"]   # default-OFF; CI exercises via the existing --all-features runs

// src/merkle_vector.rs — bytes NON-FROZEN (same banner discipline as src/merkle.rs)

/// Profile constant, not a law: laws below name properties; the profile pins radix 32.
pub const BRANCH: usize = 32;

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct VecLeaf<T> {
    pub values: Vec<T>,                 // field key strings are load-bearing, as in MerkleNode
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct VecInterior {
    pub level: u8,
    pub children: Vec<ContentId>,       // positional tag-42 links — Vec, NOT BTreeSet: order IS the data
    pub sizes: Option<Vec<u64>>,        // committed size table; Some only when relaxed
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct VecRoot {
    pub count: u64,
    pub root: Option<ContentId>,        // None while everything fits in the tail
    pub tail: ContentId,                // link to a VecLeaf
}

// Each shape: impl ContentAddressable { canonical_form = to_canonical_dagcbor(self) }

/// Narrow read-only CID-resolution seam for traversal/proving. Local to this module
/// for the MVP; a shared crate-wide store trait is a sibling issue in this epic and
/// this trait migrates to it when it lands.
pub trait BlockSource {
    fn get_block(&self, id: &ContentId) -> Result<Option<Vec<u8>>, ContentError>;
}

/// Builder/handle. Owns newly-minted blocks in memory; persistence is the caller's
/// job via `new_blocks()` — the crate stays storage-free (loosely coupled).
pub struct MerkleVector<T> { /* root header + pending block map */ }

impl<T: Serialize + DeserializeOwned> MerkleVector<T> {
    pub fn new() -> Self;
    pub fn len(&self) -> u64;
    pub fn push_back(&mut self, value: T) -> Result<(), ContentError>;
    pub fn root_id(&self) -> Result<ContentId, ContentError>;
    pub fn new_blocks(&self) -> impl Iterator<Item = (ContentId, &[u8])>;
    pub fn get(&self, store: &impl BlockSource, index: u64) -> Result<Option<T>, ContentError>;
    pub fn prove(&self, store: &impl BlockSource, index: u64) -> Result<IndexProof, ContentError>;
}

/// Root-to-leaf canonical blocks; the verifier re-hashes and replays navigation.
pub struct IndexProof { pub blocks: Vec<Vec<u8>> }

pub enum ProofOutcome<T> { Valid(T), OutOfRange, Invalid }

/// Mirrors the frozen verify() contract (#8): a well-formed-but-wrong proof is
/// Ok(Invalid), not Err — errors are reserved for encoding failures.
pub fn verify_index_proof<T: Serialize + DeserializeOwned>(
    root: &ContentId,
    index: u64,
    proof: &IndexProof,
) -> Result<ProofOutcome<T>, ContentError>;

MVP builds strict (non-relaxed) trees via push_back only; sizes stays None throughout, but verification logic handles both arms so the follow-ups don't touch the verifier's contract.

Proof obligations

Law minimalism: three laws, all Lean-shaped. No TLA+ obligation — the MVP is a pure functional structure with no protocol/temporal behavior; TLA+ enters only if a follow-up adds a multi-party sync protocol.

1. PO-VEC-1 (Lookup soundness) [Lean]. If verify_index_proof(root, i, p) yields Valid(v), then v is the element at position i of the sequence committed by root — assuming collision-resistance of the digest as a property (the CID self-describes the algorithm; the law never names BLAKE3).
2. PO-VEC-2 (Navigation determinism & bounds refutation) [Lean]. For a well-formed tree and any i < count, radix/size-table navigation defines exactly one root-to-leaf path, and the honest prover's proof verifies (completeness). For i >= count, no proof yields Valid: a proof whose root-header block authenticates against root yields OutOfRange — the committed count alone refutes, with no exclusion machinery — and any proof that fails authentication yields Invalid.
3. PO-VEC-3 (Structural binding) [Lean]. The root CID binds the entire committed sequence: canonical encoding is injective on well-formed node values (strict dag-cbor gives this), so any change to an element, a size table, count, or tree shape changes the root CID, modulo digest collisions.

Formalization lands as statements + proofs over an abstract model of the node shapes, tracked by a formal follow-up (a sibling issue in this epic — this crate carries no in-tree formal artifacts yet, so that issue introduces them). The Rust property tests below are the executable shadow of these laws.

Python exposure

Deferred to a sibling issue in this epic (Python parity is a standing requirement, not optional — it just isn't this PR). Target shape in content-addressable-py: a MerkleVector class with push_back / get / root_id / prove / verify_index_proof, values crossing via pythonize, CIDs in the same forms the bindings already expose. It rides the existing maturin + tag-driven Trusted Publishing pipeline (#14); no new distribution machinery. The non-frozen-bytes disclaimer must appear verbatim in the Python docs, as #16 established for MerkleNode.

Acceptance criteria

• New module src/merkle_vector.rs gated behind default-OFF feature merkle-vector = ["merkle"]; a plain cargo build / cargo test compiles none of it and no new symbols leak into the default (frozen, chore: freeze public API surface + MSRV/edition policy (gate #9/#10); drop dup dev serde; decide Cargo.lock #9) surface.
• Module docs carry the same ⚠️ BYTES ARE NON-FROZEN banner and rationale as src/merkle.rs, including: field key strings are load-bearing, bytes may change without a breaking change until vector conformance vectors land, and nothing is added to tests/vectors.json (frozen cross-language parity gate, test: golden conformance vectors + Rust↔Python byte-parity gate #12 — merkle-family bytes stay excluded).
• Docs state explicitly why MerkleNode's causal-set BTreeSet parents do not fit and why positional Vec<ContentId> children are required (the counterpart of the parents-are-a-set-not-a-list rationale in src/merkle.rs).
• Unit tests: determinism (same pushes ⇒ same root CID and bytes), get returns push order across node-split boundaries (n > 32, n > 32²), root CID changes on any element change, genesis/empty-vector behavior.
• Property tests (proptest as a dev-dependency): for arbitrary vectors and indices, prover→verifier round-trip yields Valid with the pushed element; any single tampered block or wrong-index claim yields Invalid, never Valid (executable shadow of PO-VEC-1); for i >= count, the honest prover's proof yields OutOfRange and no proof — tampered or honest — ever yields Valid (shadow of PO-VEC-2).
• verify_index_proof mismatch semantics follow the frozen verify() contract (decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8): wrong-but-well-formed ⇒ Ok(Invalid), not Err.
• Proof-obligation statements PO-VEC-1..3 recorded in the module docs with their Lean-shaped formalization tracked for the formal follow-up (sibling issue in this epic).
• CI and the pre-push hook exercise the feature via the existing --all-features runs; zero clippy warnings.
• New file stays under the soft 2,500-line cap (split proof/verify into src/merkle_vector/ submodules if needed).

Non-goals / follow-ups

• Verifiable concat / slice / splice and relaxed-node construction — the headline capability, deliberately deferred (sibling issue in this epic). The sizes field ships in the byte shape now so it is not a shape change later.
• Transition proofs (old-root → new-root differs only as claimed for update/push/concat) — sibling issue in this epic.
• Monoid-annotation variants (deque, priority queue, recency spine) — future siblings; this issue only avoids foreclosing them.
• CID-valued leaf elements / chunking policy — MVP leaves hold inline values only.
• Shared crate-wide store trait — sibling issue in this epic; BlockSource is intentionally minimal and migrates when it lands.
• Byte freeze / conformance vectors for this structure — follows the same road as the promised Merkle conformance vectors under epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17; nothing here expands the frozen surface (freeze minimally).
• Python bindings — sibling issue in this epic (see above).

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), 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), chore: freeze public API surface + MSRV/edition policy (gate #9/#10); drop dup dev serde; decide Cargo.lock #9 (API/MSRV freeze), ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release).
• Bagwell & Rompf, RRB-Trees: Efficient Immutable Vectors, EPFL tech report 169879 (2011) — https://infoscience.epfl.ch/record/169879
• Stucki, Rompf, Ureche & Bagwell, RRB Vector: A Practical General Purpose Immutable Sequence, ICFP 2015 — https://dl.acm.org/doi/10.1145/2784731.2784739
• Bolívar Puente, Persistence for the Masses: RRB-Vectors in a Systems Language, ICFP 2017 — https://dl.acm.org/doi/10.1145/3110260
• core.rrb-vector implementation notes — https://github.com/clojure/core.rrb-vector/blob/master/doc/rrb-tree-notes.md
• pvec-rs (unauthenticated RRB vector in Rust) — https://github.com/arazabishov/pvec-rs
• Miller, Hicks, Katz & Shi, Authenticated Data Structures, Generically, POPL 2014 — https://dl.acm.org/doi/10.1145/2535838.2535851 — generic ADS compilation shows authentication of functional structures is possible in principle; no concrete CID-profiled RRB instance exists.
• Prior art on history-independent Merkle sequences: SeqHash-style content-defined sequence hashing (no known variant supports verifiable splice; that gap is what makes this tier invented).

---

Part of #30 (Merkle structure catalog epic).