feat(atlas): CID Indirection Atlas — cyclic graphs in a DAG-only CAS

[hartsock]

Status: NOVEL / SPECULATIVE (speculative label). This is an invented structure, not an implementation of a published design. IPLD's data model is DAG-only by construction and has no principled published answer for cyclic graphs; this issue proposes one and treats it as an experiment. Lands under epic #17's merkle-layer track, default-off, bytes non-frozen.

Summary

A two-layer encoding that stores arbitrary — including cyclic — graphs in this crate's DAG-only content-addressed world. Node blocks name their out-edges by local ordinals (never by CIDs that could point back), and one atlas block binds ordinal → ContentId for the whole component. The wire structure stays strictly acyclic (so every block is an ordinary immutable CAS object with a v1 ContentId), while full graph semantics — doubly-linked lists, dependency cycles, state machines — are restored on decode. The graph's root CID is the atlas CID.

Why (the telescope)

This crate is about trust: data that carries its own proof of integrity. Today that promise stops at DAGs. Real provenance data is frequently cyclic — dependency graphs with mutual dependencies, state machines, workflow graphs with retry loops, doubly-linked document structures, "A cites B cites A" knowledge graphs. Users who need to hand a peer one identifier and have them verify the whole structure offline currently have to mangle cyclic data: break the back-edges, stash them in mutable side-channels, and lose tamper-evidence exactly at the links that matter.

The atlas restores the core promise for those users: one root CID = one whole graph, tamper-evident, offline-verifiable, deduplicated in any CAS. The ordinal trick is the telescope's mirror, not the point — the point is that cyclic data stops being second-class in a content-addressed world.

Structure & CID linkage

Every block in the encoding is an ordinary member of this crate's existing identity system:

• Identity comes from src/content_id.rs. Both new block shapes implement ContentAddressable (src/trait_def.rs) with the same one-line canonical_form → canonical::to_canonical_dagcbor pattern MerkleNode uses, so each block gets a frozen-v1 ContentId (dag-cbor 0x71 + BLAKE3 0x1e, 32-byte digest) and content_id() / verify() / ensure_content_id() for free. The atlas's bindings serialize as dag-cbor tag-42 links via ContentId's frozen serde — real IPLD links, walkable by any IPLD tool.
• MerkleNode (src/merkle.rs) does NOT fit — two sibling shapes are required, and here is why. MerkleNode.parents is a BTreeSet<ContentId>: deduplicated, content-ordered, causal-set semantics. The atlas needs the opposite on both layers: (1) Atlas.bindings is positional — the index is the ordinal, so order is meaning and a BTreeSet would destroy it; (2) AtlasNode.out_edges are not ContentId links at all — they are (label, ordinal) pairs, order-significant and duplicate-bearing (multigraphs), and their exhaustiveness is load-bearing (non-edge proofs rely on it). So this issue introduces AtlasNode<T> and Atlas as sibling node shapes with Vec-based links, sharing only the ContentAddressable derivation path with MerkleNode.
• The wire shape is a two-level DAG regardless of the logical graph. The encoder writes no CIDs of graph peers into node blocks (an inline payload block contains no tag-42 links at all; a by-link payload is opaque external data whose intended discipline is to point outside the component into ordinary DAG data). Only the atlas references node blocks, and nothing references the atlas. A node's hash is therefore independent of any cycle it participates in — and block-level reference cycles are impossible regardless of payload discipline, because a block's CID cannot appear inside bytes its own hash depends on.
• Discoverability/traversal from the root CID: fetch the atlas by its CID → verify bytes against the CID → for each entry-point ordinal, look up bindings[ordinal] → fetch and verify that node block → follow each out-edge by looking its target ordinal back up in bindings. Everything (nodes, edges, payloads) is reachable from the atlas CID; every fetched block is re-verified with the existing verify() contract. Shared subgraphs between different atlases reuse identical node-block CIDs, so the CAS deduplicates them naturally.
• Proof story (MVP: one proof kind). Edge inclusion is a binding lookup plus the source node's committed out_edges list: a proof carries the atlas bytes and one node block's bytes; verification is pure (recompute both CIDs, check bindings[from], check the edge entry). The same committed exhaustive list proves a non-edge. Cycle witnesses (a path of edge proofs returning to its start ordinal) compose from this and are a follow-up.

API sketch (Rust)

New module src/atlas.rs behind a new default-off cargo feature atlas = [] (same pattern as merkle in Cargo.toml; deliberately not depending on the merkle feature — no MerkleNode reuse, see above; CI exercises it via --all-features). Soft cap ≤ 2,500 lines.

// src/atlas.rs — feature = "atlas". BYTES NON-FROZEN (see module docs).

/// Index into an `Atlas`'s bindings. Serializes as a plain dag-cbor
/// unsigned integer (smallest-form, per src/canonical.rs).
pub struct Ordinal(pub u64);

/// A labeled out-edge naming its target by ordinal — never by CID.
pub struct Edge { pub label: String, pub target: Ordinal }

/// One vertex block. Contains NO peer CIDs, so its ContentId is
/// independent of any cycle it participates in. `out_edges` is
/// positional, duplicate-bearing, and EXHAUSTIVE (non-edge proofs
/// depend on exhaustiveness). Use `T = ContentId` to link a payload
/// out-of-band instead of inlining it.
pub struct AtlasNode<T> { pub payload: T, pub out_edges: Vec<Edge> }

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

/// Ordinal-assignment policy, committed inside the atlas so the bytes
/// self-describe how ordinals were assigned (mirrors how the CID
/// self-describes codec+hash). MVP ships exactly one variant.
pub enum OrdinalPolicy { CreationOrder } // wire form: "creation-order/v0"

/// The one block that closes the loop: ordinal -> CID bindings for a
/// component. The graph's root CID IS this block's ContentId.
pub struct Atlas {
    pub bindings: Vec<ContentId>, // index = ordinal; tag-42 links; POSITIONAL
    pub entry_points: Vec<Ordinal>,
    pub policy: OrdinalPolicy,
}
impl ContentAddressable for Atlas { /* same one-liner */ }

/// Deterministic builder. `add_edge` may target any ordinal — earlier,
/// later (a forward edge), or `from` itself — so cycles are ordinary,
/// not special. An unknown `from` fails immediately; a forward `to` is
/// validated at `finish()`, which rejects dangling ordinals.
pub struct AtlasBuilder<T> { /* ... */ }
impl<T: Serialize> AtlasBuilder<T> {
    pub fn new() -> Self;
    pub fn add_node(&mut self, payload: T) -> Ordinal;
    pub fn add_edge(&mut self, from: Ordinal, label: impl Into<String>, to: Ordinal)
        -> Result<(), ContentError>;
    pub fn finish(self) -> Result<EncodedGraph<T>, ContentError>;
}

/// An encoded component: node blocks (index = ordinal) plus the atlas.
pub struct EncodedGraph<T> { pub nodes: Vec<AtlasNode<T>>, pub atlas: Atlas }
impl<T: Serialize> EncodedGraph<T> {
    pub fn root_id(&self) -> Result<ContentId, ContentError>; // atlas.content_id()
    pub fn resolve(&self, target: Ordinal) -> Option<&AtlasNode<T>>;
}

/// Narrow resolver seam for loading from any CAS. Intentionally minimal;
/// may be superseded by a crate-wide store trait (sibling issue in this
/// epic) — this module keeps the seam local until that lands.
pub trait BlockSource {
    fn fetch(&self, id: &ContentId) -> Result<Option<Vec<u8>>, ContentError>;
}
/// Fetches atlas + nodes from `src`, re-verifying every block against
/// its CID via the existing verify contract.
pub fn load_graph<T: DeserializeOwned>(root: &ContentId, src: &impl BlockSource)
    -> Result<EncodedGraph<T>, ContentError>;

/// MVP proof kind: edge (and non-edge) proofs. Verification is pure —
/// no store access; the proof carries the two blocks it commits to.
pub struct EdgeClaim { pub from: Ordinal, pub label: String, pub to: Ordinal }
pub struct EdgeProof { /* atlas bytes + source-node bytes + positions */ }
pub fn prove_edge(g: &EncodedGraph<impl Serialize>, claim: &EdgeClaim)
    -> Result<EdgeProof, ContentError>;
pub fn verify_edge_proof(root: &ContentId, claim: &EdgeClaim, proof: &EdgeProof)
    -> Result<bool, ContentError>; // mismatch => Ok(false), like verify()

Proof obligations

Law-minimal set — four laws, each with a real obligation; no TLA+ obligation in the MVP because the structure is purely functional (no temporal/concurrent behavior; a future mutation/rebind protocol would be TLA+-shaped and is a follow-up):

1. A1 — Wire acyclicity [Lean]: for any finite directed graph, including cyclic and self-looping, the encoder introduces exactly one layer of block-level CID references — atlas → node blocks — and no node→node or node→atlas references, with payload links treated as opaque external data (the builder never writes a component-internal CID into a payload). Structural induction over the encoder. Stated corollary, independent of payload discipline: block-level reference cycles are impossible, because a block's CID cannot occur inside bytes its own hash depends on.
2. A2 — Faithful round-trip [Lean]: decode(encode(G)) = G up to ordinal-preserving isomorphism under the committed CreationOrder policy — labels, edge order, multiplicities, and entry points all survive.
3. A3 — Determinism / CID convergence [Lean]: two builds presenting the same nodes and edges in the same creation order yield byte-equal blocks and an equal root CID (properties, not algorithms: the law names determinism; the CID's multihash self-describes the pinned profile).
4. A4 — Edge-proof soundness & non-edge completeness [Lean]: verify_edge_proof(root, claim, proof) = Ok(true) implies the claimed edge exists in the unique graph committed by root; and a node's committed exhaustive out_edges list suffices to refute any absent edge. Soundness assumes the pinned profile's collision-resistance — the law names the property, not the algorithm, per A3; the mechanized statement takes it as a hypothesis.

Honesty note (also goes in the module docs): making arbitrary isomorphic graphs converge to one CID requires canonical graph labeling, which is graph-isomorphism-hard in general. The MVP commits the cheap deterministic CreationOrder policy and records the policy in the hashed bytes, so differently-policied atlases can never silently collide; stronger canonical-labeling policies are follow-ups, not laws of this issue.

Python exposure

Deferred to the PyO3 parity work (sibling issue in this epic) — no bindings in this PR, consistent with the bytes being non-frozen. Target shape when it lands in content-addressable-py: AtlasBuilder / Atlas wrappers with dict-shaped payloads (via the existing pythonize path), root_id returning the same base32 presentation as Rust, and verify_edge_proof exposed for pure offline verification. Cross-language byte parity for atlas blocks arrives only with the atlas conformance vectors (see Non-goals), through the existing tag-driven cargo + pip pipeline (#14).

Acceptance criteria

• New cargo feature atlas, default-OFF: plain cargo build / cargo test compile no atlas code and leak no new symbols; CI and the pre-push hook exercise it via --all-features (same arrangement as merkle).
• src/atlas.rs (≤ 2,500 lines) with Ordinal, Edge, AtlasNode<T>, OrdinalPolicy, Atlas, AtlasBuilder, EncodedGraph, BlockSource, load_graph, prove_edge / verify_edge_proof, per the sketch above.
• Both block shapes implement ContentAddressable via canonical::to_canonical_dagcbor only — no bespoke canonicalization.
• Unit tests: a 2-cycle and a self-loop encode and round-trip; atlas bindings serialize as tag-42 links (mirroring merkle.rs's parents_encode_as_tag42_links test); node blocks with inline payloads contain zero tag-42 heads (wire-acyclicity smoke test for A1); edge order and duplicate edges change the node id (positional semantics — the explicit contrast with MerkleNode's set semantics); finish() rejects dangling edge targets; verify_edge_proof returns Ok(false) on mismatch, never Err (matching the frozen verify() contract shape).
• Property tests: random directed multigraphs (including cyclic) → encode → load_graph from an in-memory BlockSource → graph equality (A2/A3 as executable properties); fuzzed tampering of atlas or node bytes makes verify_edge_proof reject (A4 soundness); absent-edge claims are refuted (A4 completeness).
• Laws A1–A4 stated in the module docs with their Lean tags; mechanized proofs tracked as a follow-up (sibling issue in this epic) — not blocking this PR.
• Module docs carry the NON-FROZEN bytes disclaimer in the same form as src/merkle.rs (field key strings are load-bearing; bytes may change without a breaking change until atlas conformance vectors land) plus the novel/speculative disclaimer, and explicitly forbid adding atlas vectors to tests/vectors.json (the frozen cross-language parity gate excludes experimental surfaces).
• No frozen surface expands as a side effect: tests/vectors.json untouched, no changes to src/content_id.rs / src/canonical.rs / default features, MSRV unchanged.
• A rustdoc example (doubly-linked list or 2-cycle) that compiles and runs under --features atlas.
• Zero-warnings + full local checks pass; one issue, one PR.

Non-goals / follow-ups

• Sharded atlas as a Merkle vector for O(log n) proof and mutation cost — composes with the ordered-children structure work (sibling issue in this epic); the MVP atlas is a single block.
• Canonical-labeling policies beyond CreationOrder (isomorphism-invariant CIDs for restricted graph classes); the committed policy field is the extension seam.
• Cycle witnesses (a path of edge proofs returning to its start ordinal) — thin composition over EdgeProof, deliberately deferred.
• Mutation / rebind protocol (append nodes, re-emit atlas) and its TLA+ spec.
• A crate-wide CID-resolving store trait — BlockSource stays module-local until the shared seam lands (sibling issue in this epic).
• Atlas conformance vectors (the byte-freeze gate for this module, analogous to the promised Merkle conformance vectors under Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17).
• Python bindings — via the PyO3 parity sibling issue, after the byte shape settles.

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 (this lands under its merkle-layer track); feat: add feature-gated merkle module (MerkleNode DAG-node helper) #11 (MerkleNode, the causal-set sibling this design deliberately does not reuse); test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors / parity gate this module must stay out of until its own vectors land); ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline for eventual Python parity).
• IPLD data model (DAG-only by construction): https://ipld.io/docs/data-model/
• IPLD design docs: https://ipld.io/design/
• Goodrich, Tamassia, Triandopoulos, Cohen — Authenticated Data Structures for Graph and Geometric Searching (CT-RSA 2003) — closest published relative: authenticated connectivity/path queries over general graphs, via a different (accumulator-based) construction. Journal version: https://arxiv.org/abs/0908.4116
• Miller, Hicks, Katz, Shi — Authenticated Data Structures, Generically (POPL 2014): https://soc1024.ece.illinois.edu/gpads/ — generic ADS over inductive (hash-linked, acyclic) structures; instructive contrast: the atlas exists precisely because hash-linked inductive structures cannot express cycles.

---

Part of #30 (Merkle structure catalog epic).