feat(merkle): SeqHash uniquely-represented sequence tree (VerSum)

[hartsock]

Summary

Add SeqHash (van den Hooff et al., VerSum, CCS 2014): a deterministically shaped Merkle tree over a position-ordered sequence. Merge rounds are decided purely by a deterministic function of node hashes — no randomness, no builder state stored — so any two parties holding the same sequence build bit-identical block DAGs. Root-CID equality is sequence equality, with expected-O(log n) concatenation/splitting and O(log n) position-inclusion proofs. (All SeqHash shape bounds are expected / with-high-probability, with the profile hash modeled as random — the standard SeqHash analysis.)

Lands as src/seqhash.rs behind a new default-off seqhash cargo feature, bytes explicitly NON-FROZEN until Merkle conformance vectors land (same posture as src/merkle.rs). Scoped as one mergeable MVP under epic #17.

Why (the telescope)

The user need is verifiable sync and tamper-evident ordered logs, not tree plumbing:

• "Do we hold the same log?" in one comparison. Because the tree shape is a pure function of the sequence content, two independent builders — different machines, different languages, different insertion histories — produce the same root ContentId. Comparing one CID answers whole-sequence equality. No keyed structure (MST/prolly-tree) covers this niche: those canonicalize sets/maps, not positional sequences.
• Append-heavy audit logs. Append = concat with a singleton, minting only expected-O(log n) "seam" blocks — the exact VerSum log workload. A verifier can check that today's log extends yesterday's without replaying it.
• Automatic dedup as provenance. Common subsequences across versions share interior CIDs, so a CAS store holds shared history once — the storage layer becomes evidence of what changed and what didn't.
• Position-authenticated proofs. "Element x is at position i of the sequence with root r" is an O(log n) proof, authenticated by committed size annotations — the primitive behind verifiable event ordering.

This fills the canonical-sequence slot in the structure catalog and is the prior-art anchor for the invented persistent-merkle-vector entry (sibling issue in this epic).

Structure & CID linkage

Two block shapes, both ordinary ContentAddressable implementors whose ids are minted exactly like everything else in this crate — canonical_form() → to_canonical_dagcbor (src/canonical.rs) → ContentId::from_canonical_bytes (src/content_id.rs, frozen v1 profile: dag-cbor 0x71 + BLAKE3 0x1e, 32 bytes):

• Leaf — { item }: one sequence element (inline payload for the MVP; a ContentId link to out-of-band content is a follow-up). A leaf's element count is implicitly 1.
• Internal — { round, children }: children is an ordered Vec of { id, size } child links — each id a ContentId serializing via its frozen serde as a dag-cbor tag-42 link, each size the committed element count of that child's subtree. Per-child sizes are committed in the parent so that (a) size-guided descent costs one block fetch per level, and (b) an inclusion proof is self-contained: the path node bytes alone authenticate positions, with no sibling fetches. A node's total size is the sum of its children's committed sizes — derived, not stored, so there is no redundant field to keep consistent. round records the merge round that produced the node; merge decisions are a deterministic bit function of the adjacent nodes' hashes (digest_bytes()) and the round index, so a verifier can re-run the merge schedule over the leaf frontier and confirm both the recorded rounds and the whole tree shape — nothing about the shape is trusted.

The two shapes are domain-separated by their canonical map key sets ({"item"} vs {"children","round"}, strictly decoded), so a crafted leaf payload can never parse as an internal node — closing the classic leaf/interior type-confusion attack on Merkle inclusion proofs.

Why MerkleNode does not fit (and what does): MerkleNode<T> (src/merkle.rs, #11) deliberately uses BTreeSet<ContentId> parents — deduplicated, content-ordered causal-set semantics. SeqHash children are the opposite on every axis: positional, order-significant, and legitimately duplicate-bearing (the same element block can occur at many positions; [a, b] ≠ [b, a]). This is precisely the design seam src/merkle.rs's docs anticipate: sequence structures need a sibling node shape with ordered Vec children, sharing the same ContentAddressable derivation but not the parent-set container. No change to MerkleNode itself.

Discoverability from the root CID: the root CID plus a CID-resolving store reaches every element in order. Descent is size-guided: to reach position i, fetch the node, walk its child links left-to-right subtracting each committed size until i falls inside one, recurse — one fetch per level. Full-order traversal is left-to-right leaf enumeration. The unique-representation property upgrades this from "a" DAG to "the" DAG: independent builders of equal sequences produce byte-identical blocks, so interior CIDs collide (dedup) exactly when subsequences match.

API sketch (Rust)

src/seqhash.rs, gated by feature seqhash = [] (default-OFF, exercised in CI via --all-features, same as merkle). It does not enable the merkle feature: it reuses no MerkleNode code, only the core canonical/ContentId path.

use serde::{de::DeserializeOwned, Deserialize, Serialize};

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

/// Leaf block: one sequence element (inline for the MVP). Counts as size 1.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct SeqHashLeaf<T> {
    pub item: T,
}

/// One positional child link: subtree id + committed element count.
/// Sizes are committed IN THE PARENT so descent is one fetch per level and
/// inclusion proofs are self-contained (no sibling fetches to verify position).
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ChildLink {
    pub id: ContentId, // dag-cbor tag-42 link
    pub size: u64,     // committed element count of that child's subtree
}

/// Internal block: ORDERED, positional children — deliberately a Vec,
/// NOT MerkleNode's BTreeSet (see module docs / this issue). Total size is
/// derived as the sum of the children's committed sizes.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct SeqHashNode {
    pub round: u64,
    pub children: Vec<ChildLink>,
}

impl<T: Serialize> ContentAddressable for SeqHashLeaf<T> { /* to_canonical_dagcbor */ }
impl ContentAddressable for SeqHashNode { /* to_canonical_dagcbor */ }

/// Minimal CID-resolving store seam the operations traverse. To be unified
/// with the shared node-store trait when it lands (sibling issue in this epic).
pub trait SeqHashStore {
    fn get(&self, id: &ContentId) -> Result<Option<Vec<u8>>, ContentError>;
    /// `canonical_bytes` MUST be canonical dag-cbor (they come from
    /// canonical_form()), so the store may mint via
    /// ContentId::from_canonical_bytes.
    fn put(&mut self, canonical_bytes: &[u8]) -> Result<ContentId, ContentError>;
}

/// Handle: root CID + committed length. Display of root = base32-lower CID.
pub struct SeqHash {
    pub root: ContentId,
    pub size: u64,
}

pub fn build<T: Serialize, S: SeqHashStore>(
    items: impl IntoIterator<Item = T>, store: &mut S,
) -> Result<SeqHash, ContentError>;

/// Expected O(log n): mints only the "seam" blocks; shared canopy is reused by CID.
pub fn concat<S: SeqHashStore>(
    left: &SeqHash, right: &SeqHash, store: &mut S,
) -> Result<SeqHash, ContentError>;

/// Expected O(log n): the inverse seam operation.
pub fn split<S: SeqHashStore>(
    t: &SeqHash, at: u64, store: &mut S,
) -> Result<(SeqHash, SeqHash), ContentError>;

/// Append = concat with a singleton (the VerSum log workload).
pub fn push_back<T: Serialize, S: SeqHashStore>(
    t: &SeqHash, item: T, store: &mut S,
) -> Result<SeqHash, ContentError>;

/// Size-guided descent to position i — one store fetch per level.
pub fn get<T: DeserializeOwned, S: SeqHashStore>(
    t: &SeqHash, i: u64, store: &S,
) -> Result<T, ContentError>;

/// O(log n) proof that an element sits at position i under root; positions are
/// authenticated by the committed per-child `size`s along the path — the proof
/// is self-contained (path node bytes + child indices, no sibling blocks).
pub struct InclusionProof { /* position, leaf bytes, path of (node bytes, child index) */ }

pub fn prove_inclusion<S: SeqHashStore>(
    t: &SeqHash, i: u64, store: &S,
) -> Result<InclusionProof, ContentError>;

/// Mismatch = Ok(false), mirroring the frozen verify() contract (#8).
pub fn verify_inclusion(
    root: &ContentId, proof: &InclusionProof,
) -> Result<bool, ContentError>;

Merge decisions are recomputed by verifiers, not trusted: each is a deterministic bit function of the adjacent nodes' digest_bytes() and the round index, so re-running the merge schedule needs nothing but the blocks — no builder state, no randomness.

Proof obligations

Minimal law set (law minimalism — each is load-bearing for the "root equality means sequence equality" telescope). Laws name properties; the pinned v1 CID profile supplies the algorithms (the CID self-describes codec+hash, per multihash doctrine).

1. UNIQUE-REP [Lean] — The block DAG is a pure function of the sequence contents: for any sequence, every build history (direct build, any concat-of-splits, any append order reaching the same sequence) yields the identical set of blocks and the same root CID. (This is the strong history-independence of Blelloch–Golovin, instantiated for the SeqHash merge rule.)
2. CONCAT-COHERENCE [Lean] — concat(build(a), build(b)) = build(a ++ b); consequently concat is associative on canonical trees. This is the law that makes the expected-O(log n) seam construction correct, not just cheap.
3. ROOT-INJECTIVITY [Lean] — Modulo collision resistance of the profile hash (property, not algorithm): on canonically-built trees, equal root CIDs imply equal sequences. Together with UNIQUE-REP this yields root-CID equality ⟺ sequence equality.
4. INCLUSION-SOUND [Lean] — A proof accepted by verify_inclusion(root, proof) binds both the element bytes and the position i, under the per-child size annotations committed in the path node bytes, modulo hash collision resistance. (Leaf/internal domain separation via disjoint canonical key sets is a lemma here.)

No TLA+ obligation: the structure is purely functional over an abstract store with no concurrency protocol in scope; adding one would be ornamental. The Lean formalization itself is tracked separately (sibling issue in this epic) — this issue's obligation is to state the laws precisely in module docs and encode each as a property test.

Python exposure

Not in this PR (one-issue-one-PR ratchet). Intended parity surface for content-addressable-py (sibling issue in this epic): SeqHash handle with build, concat, split, push_back, get, prove_inclusion, verify_inclusion over a Python-visible store protocol, root exposed as the base32 CID string. Distribution rides the existing maturin + tag-driven Trusted Publishing pipeline (#14) — no new release machinery.

Acceptance criteria

• src/seqhash.rs behind new default-off seqhash feature; plain cargo build / cargo test compiles no new symbols; CI + pre-push exercise it via --all-features
• SeqHashLeaf<T> / SeqHashNode implement ContentAddressable via to_canonical_dagcbor; each child link's id serializes as a dag-cbor tag-42 link in committed order (test mirrors parents_encode_as_tag42_links in src/merkle.rs), and per-child sizes are committed in the parent's bytes
• build, concat, split, push_back, get operate over the SeqHashStore seam; a block-mint-counting test on random payloads shows concat/split mint expected-O(log n) new blocks, not O(n)
• prove_inclusion / verify_inclusion implemented; mismatch returns Ok(false) per the frozen verify contract (decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8); tampered element, position, path, or committed child size each verify false, and a leaf/internal type-confusion attempt (leaf payload crafted to resemble an internal node) verifies false (regression-style negative tests)
• Property tests (proptest or equivalent as dev-dependency only): (a) UNIQUE-REP — random sequences built directly vs. via random split/concat/append histories yield identical root CID and identical block sets; (b) root equality ⟺ sequence equality on generated pairs; (c) inclusion round-trip at random positions
• Module docs state laws 1–4 by name and carry the NON-FROZEN bytes disclaimer verbatim in spirit from src/merkle.rs: default-off feature, byte layout pinned only when Merkle conformance vectors land, changing bytes before then is not a breaking change
• No entries added to tests/vectors.json — that file is the frozen cross-language byte-parity gate and deliberately excludes experimental surfaces
• Rustdoc examples compile as doctests; new file stays under the soft 2,500-line cap
• Zero-warning gate: cargo clippy --all-features -- -D warnings, cargo fmt --check clean

Non-goals / follow-ups

• Slice/range proofs (covering canopy + boundary paths) and extension-consistency proofs (shared canopy between old and new roots) — natural next increments once inclusion proofs are in (follow-up on this issue or sibling issue in this epic)
• Byte freeze / conformance vectors — deferred to the Merkle conformance vectors follow-up already promised in src/merkle.rs module docs toward 0.1.0-rc1 (Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17)
• Python bindings — sibling issue in this epic (see Python exposure)
• Shared node-store trait — the local SeqHashStore seam is deliberately minimal; unification with a crate-wide CID-resolving store trait is a sibling issue in this epic
• Leaf item as ContentId link / content-defined chunking of large payloads — MVP keeps leaves inline
• Persistent merkle vector (radix-indexed, splice-capable) — separate invented-tier sibling issue in this epic; this issue is its prior-art anchor
• Lean mechanization of laws 1–4 — sibling issue in this epic; this issue ships the precise statements + property tests

References

• van den Hooff, Kaashoek, Zeldovich, "VerSum: Verifiable Computations over Large Public Logs", ACM CCS 2014 (SeqHash: §4) — authors' copy: https://pdos.csail.mit.edu/papers/versum:ccs14.pdf ; ACM DL: https://dl.acm.org/doi/10.1145/2660267.2660327
• Blelloch & Golovin, "Strongly History-Independent Hashing with Applications", FOCS 2007 — the unique-representation / strong history-independence frame behind law 1
• Epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17 (Road to 0.1.0-rc1) — this lands under it; feat: add feature-gated merkle module (MerkleNode DAG-node helper) #11 (MerkleNode, the causal-set sibling shape), decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (frozen verify contract), test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors — exclusion rationale), ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline)
• src/merkle.rs module docs — non-frozen-bytes posture and the ordered-children design seam this issue fills; src/content_id.rs — frozen v1 CID profile; src/canonical.rs — canonical dag-cbor

---

Part of #30 (Merkle structure catalog epic).