feat(merkle): entangled Merkle forest (Snarl parity + version chain)

[hartsock]

Summary

Add an entangled Merkle forest module — src/entangled.rs behind a new default-OFF entangled cargo feature (which enables merkle) — folding two literature-grounded senses into one CID-link structure family:

1. Snarl-sense parity entanglement: XOR parity strands woven through a set of content-addressed blocks, described by an EntangledManifest so that a single root CID makes both the protected structure and its repair lattice discoverable. A missing block is reconstructed from lattice neighbors, and the reconstruction is self-proving: the recovered bytes are accepted only if they re-hash to the block's known ContentId.
2. Version-forest sense: per-version roots that share unchanged subtree CIDs (free in a CAS), walked by a version-chain node that is a plain MerkleNode<T> reuse — shared CIDs become cheap, checkable cross-version non-modification evidence.

Bytes are explicitly NON-FROZEN (same disclaimer discipline as src/merkle.rs), scoped as one mergeable MVP under epic #17.

Why (the telescope)

This is not about erasure codes or XOR arithmetic. It is about two things an archive owner actually needs:

• Loss must not orphan truth. In a plain Merkle tree, losing an interior node orphans every leaf beneath it — the data may survive while the proof structure dies. An entangled forest keeps leaves reachable and interior nodes reconstructible without full replication, and — because this is a CAS — every repair carries its own proof of honesty: reconstructed bytes either re-hash to the CID they claim, or they are rejected. Trust is intrinsic, not operational.
• History must be auditable at a glance. When versions of a structure share subtrees by literal CID identity, "this part did not change between v3 and v9" is not an assertion, it is an equation between two identifiers. Multi-version auditing becomes CID comparison instead of byte diffing.

Target uses: resilient archives (provenance stores, event logs, artifact caches) where partial loss is expected, and multi-version file/record auditing where non-modification evidence should be cheap.

Structure & CID linkage

Every node in both senses derives its identity the one crate-standard way: implement ContentAddressable (src/trait_def.rs) with canonical_form deferring to canonical::to_canonical_dagcbor (src/canonical.rs), yielding a ContentId (src/content_id.rs — frozen v1 profile: CIDv1, dag-cbor 0x71, BLAKE3 0x1e, 32-byte digest). Every inter-node reference is a ContentId, which serializes as a frozen dag-cbor tag-42 IPLD link, so the whole forest is traversable by any IPLD-aware walker.

Sense 1 — parity lattice: a sibling node shape is REQUIRED, MerkleNode does not fit.
MerkleNode's BTreeSet<ContentId> parents are deliberate causal-set semantics: deduplicated, content-ordered, insertion-order-independent (src/merkle.rs documents rejecting Vec<ContentId> for that role). A parity strand is the opposite: its covers list is positional and order-significant — position in the strand is the XOR window position, the same block may appear in multiple windows, and reordering covers is a different lattice that must hash differently. So the manifest family is a sibling shape using Vec<ContentId> and named links:

• EntangledManifest { root: ContentId, lattice: LatticeParams, strands: Vec<Strand> } — the single entry point; its own ContentId is the root of the whole entangled structure.
• Strand { parity: ContentId, covers: Vec<ContentId> } — parity names a ParityBlock node; covers is the ordered list of protected block CIDs.
• ParityBlock { data } — parity bytes wrapped as a canonical dag-cbor node so parity is itself content-addressed under the frozen profile (exact byte-string encoding settled in the PR; bytes non-frozen).

Discoverability from one CID: hold the manifest's ContentId → resolve it → the root link gives the protected structure, and strands[*].parity / strands[*].covers give the entire repair lattice. Layout tree AND repair lattice hang off one identifier, as in Snarl.

Sense 2 — version forest: MerkleNode fits as-is.
The version chain is genuinely causal: prev is a causal parent, deduplication and content-ordering are correct semantics. So the chain node is a plain reuse (no new hashing rules):

• VersionNode = MerkleNode<VersionMeta> where VersionMeta { version_root: ContentId, label: Option<String> }; parents = the previous version's node id (empty via MerkleNode::genesis for v1). The version_root link inside the payload serializes as tag-42 through ContentId's frozen serde.

Traversal: hold the chain head's CID → walk parents() back through history; each payload's version_root names that version's structure (or its EntangledManifest, composing both senses). Subtrees unchanged between versions are the same node — literal CID identity — which is the sharing-as-evidence property made mechanical.

Store seam: traversal and repair are written against a minimal read-only lookup seam (a narrow BlockSource trait, below), keeping the module loosely coupled. A shared CID-resolving store trait is a broader concern (sibling issue in this epic); this module keeps its local minimal bound until that lands, then migrates.

API sketch (Rust)

// src/entangled.rs — feature = "entangled" (default-OFF; enables "merkle").
// ⚠️ BYTES NON-FROZEN until entangled conformance vectors land.

use serde::{Deserialize, Serialize};

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

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct LatticeParams { pub alpha: u8, pub s: u8, pub p: u8 }

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Strand {
    pub parity: ContentId,        // tag-42 link to a ParityBlock
    pub covers: Vec<ContentId>,   // POSITIONAL — order is the XOR window order
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ParityBlock {
    /// Parity bytes. Exact dag-cbor byte-string encoding settled in the PR
    /// (bytes non-frozen).
    pub data: Vec<u8>,
}

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct EntangledManifest {
    pub root: ContentId,          // the protected structure's root
    pub lattice: LatticeParams,
    pub strands: Vec<Strand>,     // ordered; order is identity-bearing
}

impl ContentAddressable for EntangledManifest { /* to_canonical_dagcbor */ }
// Strand / LatticeParams / ParityBlock likewise; VersionNode gets it via MerkleNode.

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct VersionMeta { pub version_root: ContentId, pub label: Option<String> }
pub type VersionNode = MerkleNode<VersionMeta>;

/// Narrow read-only lookup seam (local until the shared store trait lands).
pub trait BlockSource {
    fn get(&self, id: &ContentId) -> Result<Option<Vec<u8>>, ContentError>;
}

impl EntangledManifest {
    /// Weave parity strands over an ordered list of already-addressed blocks.
    pub fn entangle(
        root: ContentId,
        blocks: &[(ContentId, Vec<u8>)],
        lattice: LatticeParams,
    ) -> Result<(Self, Vec<ParityBlock>), ContentError>;

    /// Reconstruct the block named by `want` from lattice neighbors.
    /// Self-proving: returns bytes ONLY if they re-hash to `want`
    /// (via ContentId::from_canonical_bytes equality); otherwise
    /// Err(ContentError::VerificationFailed).
    pub fn repair(
        &self,
        want: &ContentId,
        src: &impl BlockSource,
    ) -> Result<Vec<u8>, ContentError>;
}

MVP operations: entangle, repair, and version-chain construction/walking via the existing MerkleNode API (new, genesis, parents, id). XOR windowing/padding details are settled in the PR under the non-frozen-bytes umbrella.

Proof obligations

Law minimalism: four laws, each load-bearing. Laws name properties; the frozen v1 profile pins the algorithms (the CID self-describes codec + hash).

1. L-EF-1 Link-binding determinism [Lean] — a manifest's ContentId is a function of (root, lattice, strands in order, each strand's parity + covers in order): equal structures ⇒ equal canonical bytes ⇒ equal ids, provable outright; and any changed link or reordered/duplicated cover provably changes the canonical bytes — hence the id, under the pinned hash's collision resistance (the same assumption L-EF-2 and L-EF-4 name explicitly). (The positional counterpart of MerkleNode's order-independence law.)
2. L-EF-2 Repair soundness [Lean] — repair yields bytes b for target c only if b re-hashes to c under the profile; assuming collision resistance of the pinned hash, b is byte-identical to the original block. Corruption anywhere in the lattice can cause VerificationFailed, never silently wrong bytes.
3. L-EF-3 Loss-tolerance safety [TLA+] — model blocks as {present, lost, repaired}; invariant: no accepted block ever differs from its CID preimage; and for loss patterns within the lattice's (alpha, s, p) tolerance, repair from the root manifest reaches every covered block.
4. L-EF-4 Sharing-as-evidence [Lean] — subtree-root CID equality across two version roots ⇔ canonical-byte equality (⇐ by determinism, ⇒ by the collision-resistance assumption): "shared CIDs are cheap non-modification evidence," made precise.

MVP ships each law stated in module docs with a property-test shadow; Lean/TLA+ mechanization is deferred (sibling issue in this epic).

Python exposure

Eventually surfaced through content-addressable-py (PyO3 + pythonize, maturin-built): dict-shaped EntangledManifest/VersionMeta views, entangle/repair entry points, and byte-parity tests against Rust — deferred until the bytes approach freeze (sibling issue in this epic). Distribution stays cargo + pip via the existing tag-driven Trusted Publishing pipeline (#14). Nothing in this issue changes the Python wheel.

Acceptance criteria

• New module src/entangled.rs behind default-OFF feature entangled = ["merkle"]; plain cargo build / cargo test unchanged; CI and the pre-push hook exercise it via --all-features. The frozen default surface does not grow.
• EntangledManifest, Strand, LatticeParams, ParityBlock implement ContentAddressable via canonical::to_canonical_dagcbor; VersionNode is a MerkleNode<VersionMeta> reuse with no new hashing rules.
• Identity tests (TDD, property tests where apt): the manifest id binds root, lattice, and every strand link; reordering covers changes the id (positional-semantics test, explicitly contrasted with src/merkle.rs's btreeset_ordering_makes_id_insertion_order_independent); duplicate covers are legal and preserved.
• Repair self-proving test: repair returns bytes only when they re-hash to the requested ContentId; a property test corrupting parity or neighbor bytes must produce ContentError::VerificationFailed, never wrong bytes.
• Round-trip tests: all node shapes survive to_canonical_dagcbor → from_canonical_dagcbor; every link lands as a dag-cbor tag-42 head (mirroring parents_encode_as_tag42_links).
• Version-forest test: genesis version, chained versions via parents, and a shared-subtree test showing an unchanged subtree yields the identical CID under two different version roots.
• All traversal/repair goes through the BlockSource seam; unit tests use in-memory maps only (no real filesystem).
• Module docs lead with the user need and carry the explicit "bytes NON-FROZEN until entangled conformance vectors land" disclaimer, mirroring src/merkle.rs; entangled bytes are NOT added to tests/vectors.json (that file stays the frozen cross-language parity gate).
• The four laws stated in module docs, each mapped to its property-test shadow.
• Zero warnings (cargo clippy -- -D warnings, cargo fmt --check); new file stays under the soft 2,500-line cap (split the module if exceeded).

Non-goals / follow-ups

• No availability-aware fetch planning (choosing data-vs-parity paths by cost/latency) — follow-up once a real store exists behind the seam.
• No O(log n) inclusion-proof machinery — generic Merkle proof objects are their own structure (sibling issue in this epic).
• No chunking policy / file import — the MVP entangles an already-addressed, ordered block list; how a file becomes that list (ordered sequence/chunk-list node shape) is a sibling issue in this epic.
• No shared CID-resolving store trait — local BlockSource only; migrate when the shared seam lands (sibling issue in this epic).
• No Python bindings in this PR — sibling issue in this epic.
• No conformance vectors yet — bytes stay non-frozen; entangled vectors follow the pattern of the promised Merkle conformance vectors (epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17) once the shape has soaked.
• Not an erasure-coding storage system — no Reed–Solomon, no replication policy; alpha-entanglement per Snarl only, MVP-simple.
• No Lean/TLA+ mechanization in this PR — laws + property-test shadows only; mechanization is a sibling issue in this epic.

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 layer); test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors + Rust↔Python parity — entangled bytes deliberately excluded); ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline).
• src/content_id.rs (frozen ContentId v1 profile), src/merkle.rs (causal-set MerkleNode + non-frozen-bytes discipline), src/canonical.rs, src/trait_def.rs.
• Nygaard, Estrada-Galiñanes, Meling — Snarl: Entangled Merkle Trees for Improved File Availability and Storage Utilization, Middleware 2021 — https://dl.acm.org/doi/10.1145/3464298.3493397 (open-access mirror: https://www.researchgate.net/publication/356759481_Snarl_entangled_merkle_trees_for_improved_file_availability_and_storage_utilization)
• Bappy, Zaman, Islam, Rizvee, Park, Hasan — Towards Immutability: A Secure and Efficient Auditing Framework for Cloud Supporting Data Integrity and File Version Control (introduces the node-sharing "Entangled Merkle Forest" — the version-forest sense) — https://arxiv.org/abs/2308.04453 (architecture figure: https://www.researchgate.net/figure/Entangled-Merkle-Forest-Architecture_fig1_373016284)

---

Part of #30 (Merkle structure catalog epic).