feat(merkle): Merkle Time-Series Ring — retention-proof circular log

[hartsock]

Status: NOVEL / SPECULATIVE (invented-tier). This structure is not, to our knowledge, published anywhere in this exact shape. It composes well-understood pieces (time-bucketed Merkle commitments, a Merkle Mountain Range, CIDv1 content addressing) into a new commitment: circular-overwrite semantics as part of the Merkle structure itself. Treat the design as a hypothesis to be validated by tests and proof obligations, not as settled art.

Summary

A fixed-capacity ring of B time-bucketed commitments plus a retirement MMR that accumulates the root CID of every bucket ever evicted. One root CID commits to: the live retention window, the head position, and the complete append-only history of evictions. Two proof kinds fall out:

1. In-window inclusion — "sample at time t is present": committed head/epoch arithmetic selects the bucket; the MVP proof reveals the sealed bucket, so it is O(samples_per_bucket). Upgrading to O(log samples_per_bucket) via an in-bucket Merkle tree is an explicit follow-up (see Non-goals).
2. Eviction (retention-then-deletion) — "the bucket covering time t was retained for its full window and then evicted on schedule": epoch arithmetic shows t's epoch e is at or before head_epoch − B (the live window is exactly head_epoch − B < e ≤ head_epoch), plus a retirement-MMR inclusion path for that epoch's bucket root, O(log total_epochs). Evictions happen in strict epoch order, so the MMR leaf index for epoch e is e — the verifier derives the leaf position from t alone.

Provably gone, commitment survives: evicted buckets' blocks become GC-able from the CAS while their commitments remain verifiable forever.

MVP lands as src/time_series_ring.rs behind a new default-off cargo feature, bytes explicitly NON-FROZEN, under epic #17.

Why (the telescope)

The user need is bounded retention you can prove — not hashing machinery:

• Flight recorders / audit logs. An agent or system flight recorder must show a verifier what happened recently (tamper-evident inclusion) without growing forever. Today, truncating a Merkle log breaks its commitment; keeping everything breaks the disk. This structure makes truncation part of the commitment.
• GDPR-style retention schedules. "We keep telemetry 90 days, then delete it" is currently an unverifiable policy statement. Here it becomes a CID-graph fact: an auditor can verify that data older than the window is gone from the live structure and that it existed and was evicted exactly on schedule — without the operator retaining the data itself.
• Verifiable sync of bounded state. Two replicas comparing one root CID learn both what is live and whether their eviction histories are consistent (transparency-log-style, per RFC 6962 lineage).

Existing published structures commit to append-only logs (RFC 6962, MMRs) or to snapshots; none we know of commit to fixed-capacity overwrite semantics. That gap is what this issue fills, and why it is labeled speculative.

Structure & CID linkage

Every node in the structure is content-addressed through the frozen ContentId (src/content_id.rs — CIDv1, dag-cbor 0x71, BLAKE3 multihash 0x1e, 32-byte digest) by implementing ContentAddressable (src/trait_def.rs) with canonical_form deferring to to_canonical_dagcbor (src/canonical.rs) — exactly the derivation MerkleNode uses. No bespoke hashing anywhere.

MerkleNode's causal-set parents do NOT fit here, by design. MerkleNode<T> (src/merkle.rs) carries parents: BTreeSet<ContentId> — deduplicated, deterministically ordered causal-set semantics; its docs explicitly reject Vec<ContentId> parents because causal parents must not hash differently by insertion order. The ring is exactly the kind of structure that seam does not serve: it needs positional, order-significant links (buckets[i] means "the bucket at ring position i"; MMR children are left/right). Sorting or deduplicating those links would destroy the structure's meaning. So this issue introduces sibling node shapes with Vec<ContentId> / named links, sharing only the ContentAddressable derivation:

• RingRoot — named links + one positional array: { capacity: B, bucket_span, head_index, epoch, buckets: [CID; B], retired_mmr: CID, retention_policy: CID }. The single commitment; its own CID is the ring identity at a given state. During the initial fill phase, not-yet-used slots hold a designated placeholder CID (pinned in module docs), so buckets has length B from genesis.
• TimeBucket — { epoch, samples } with samples { t, payload: CID | inline, source }, ordered by t (positional Vec, duplicates of payload CIDs legal). Flat in the MVP; see Non-goals for the in-bucket tree upgrade.
• MmrNode — retirement-MMR interior node with positional left/right child links; leaves are { evicted_epoch, bucket_root: CID }. RingRoot.retired_mmr commits the MMR's bagged peaks (a small node listing the current peak CIDs positionally), so one CID covers the whole accumulator.

Traversal from the root CID (via a CID-resolving block source — a local trait in this MVP, see the API sketch; a shared store trait is a follow-up, to be filed): resolve RingRoot → index into buckets by committed head/epoch arithmetic → resolve TimeBucket → find the sample; or RingRoot.retired_mmr → peaks → MMR path → evicted bucket-root commitment. Everything live is reachable from the ring root CID; everything ever evicted is reachable as a commitment (bucket root CID + eviction epoch) via retired_mmr. Presence and absence are both CID-graph facts. Sample payload CIDs may point at any content-addressed value — including MerkleNode event DAGs when the merkle feature is also enabled — which is how this composes with, rather than replaces, the causal-set layer.

Rotation is one atomic root transition. When the bucket for epoch e_new is sealed: (1) the ring slot it takes — the oldest — currently holds the bucket for epoch e_new − B (once past the fill phase); that displaced bucket's root CID and epoch are appended to the retirement MMR; (2) the sealed bucket's CID is written into the slot; (3) head_index/epoch advance and the new RingRoot is minted. The just-sealed bucket stays live in the ring for B epochs before it is retired — the MMR holds evicted buckets only, which is precisely what makes MMR membership a proof of retirement rather than mere existence. In the fill phase (epoch < B) the displaced slot holds the placeholder and nothing is appended. The transition proof is (old_root_cid, new_root_cid, sealed_bucket_root, evicted_bucket_root, mmr_append_path) — O(log total_epochs).

API sketch (Rust)

src/time_series_ring.rs, gated behind a new default-off feature (composes with, but does not require, merkle):

[features]
merkle = []
time-series-ring = []   # default-OFF; bytes NON-FROZEN until conformance vectors land

//! ⚠️ BYTES ARE NON-FROZEN (experimental, default-off feature).
//! Deliberately EXCLUDED from tests/vectors.json until this structure's
//! conformance vectors land. Changing these bytes is NOT a breaking change yet.

use serde::{Deserialize, Serialize};

use crate::{canonical, content_id::ContentId, error::ContentError, trait_def::ContentAddressable};

/// Sibling node shape to MerkleNode: positional + named links, NOT a causal set.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct RingRoot {
    pub capacity: u32,             // B
    pub bucket_span: u64,          // duration of one bucket (units pinned by profile)
    pub head_index: u32,
    pub epoch: u64,
    pub buckets: Vec<ContentId>,   // len == capacity; POSITIONAL — order is meaning
    pub retired_mmr: ContentId,    // commits the MMR's bagged peaks
    pub retention_policy: ContentId,
}

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

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct TimeBucket { pub epoch: u64, pub samples: Vec<Sample> }  // ordered by t

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Sample { pub t: u64, pub payload: SampleLink, pub source: String }

#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum SampleLink { Link(ContentId), Inline(Vec<u8>) }

/// Minimal local resolution seam for the MVP; migrates to a shared
/// CID-resolving store trait when one lands (follow-up, to be filed).
pub trait BlockSource {
    fn get(&self, id: &ContentId) -> Option<Vec<u8>>;
}

/// Proof structs carry the ring-root witness bytes (which must hash to the
/// given root id) so verification needs only (root_id, proof).
pub struct RotationProof  { /* old_root, new_root, sealed_bucket_root, evicted_bucket_root, mmr_append_path */ }
pub struct InclusionProof { /* ring-root witness + epoch arithmetic witness + bucket bytes */ }
pub struct EvictionProof  { /* ring-root witness + epoch arithmetic witness + retirement-MMR inclusion path */ }

/// Pure state transition: write the sealed bucket over the oldest slot,
/// retiring the displaced bucket into the MMR (no-op retire during the fill
/// phase), then advance head/epoch.
pub fn rotate(root: &RingRoot, sealed: &TimeBucket, src: &impl BlockSource)
    -> Result<(RingRoot, RotationProof), ContentError>;

pub fn prove_inclusion(root: &RingRoot, t: u64, src: &impl BlockSource)
    -> Result<InclusionProof, ContentError>;
pub fn prove_eviction(root: &RingRoot, t: u64, src: &impl BlockSource)
    -> Result<EvictionProof, ContentError>;

/// Frozen verify contract (#8) mirrored: well-formed-but-unproven => Ok(false);
/// malformed input => Err.
pub fn verify_inclusion(root_id: &ContentId, proof: &InclusionProof) -> Result<bool, ContentError>;
pub fn verify_eviction(root_id: &ContentId, proof: &EvictionProof) -> Result<bool, ContentError>;

Notes: operations are pure (old state in → new state + proof out); persistence stays behind the seam. All node ids come from the provided content_id() on ContentAddressable — no new hashing paths, and the CID remains self-describing (codec + multihash), so laws below name properties, never algorithms.

Proof obligations

Law minimalism: only what this structure needs to mean what it claims.

1. [Lean] Root binding. RingRoot's CID is injective over its canonical form: two ring states with equal root CIDs have equal (capacity, bucket_span, head_index, epoch, buckets, retired_mmr, retention_policy) — up to collision-resistance of the multihash digest (stated as a property assumption, not a claim about BLAKE3 specifically). Equational; per-structure.
2. [TLA+] Rotation soundness. The rotate transition, modeled as a state machine over (head_index, epoch, buckets, retired_mmr): the sealed bucket lands at exactly one slot; the displaced bucket — the oldest, epoch new_epoch − B, when the ring is past its fill phase — and only it is appended to the retirement MMR; the MMR grows append-only (the old leaf sequence is a prefix of the new); no other slot changes. Safety invariant + action property.
3. [TLA+] Window totality. Invariant on all reachable states: every sealed epoch e ≤ head_epoch is either live in the ring (head_epoch − B < e) or committed in retired_mmr (at leaf index e) — never both, never neither. This is the law that makes "provably gone" and "provably present" jointly exhaustive.
4. [Lean] Proof soundness. verify_inclusion(root_id, p) = Ok(true) implies the witnessed sample is committed under root_id (and dually for verify_eviction and the retired bucket root), again reduced to the digest collision-resistance property.

Machine-checked artifacts may land with later formal work; this issue must at minimum state each law in the module docs with its tag so the formal work has a fixed target.

Python exposure

Follow-up, not MVP: expose RingRoot / proofs through content-addressable-py (PyO3 + pythonize) once bytes freeze, shipping via the existing maturin + tag-driven Trusted Publishing pipeline (#14). Cross-language byte parity joins the conformance-vector gate at that point (pattern of #12), never tests/vectors.json before freeze. (Follow-up issue, to be filed once bytes freeze.)

Acceptance criteria

• New feature flag (e.g. time-series-ring) is default-OFF; plain cargo build / cargo test compile zero new symbols; CI + pre-push exercise it via --all-features (same pattern as merkle).
• Module docs carry the ⚠️ BYTES ARE NON-FROZEN banner matching the src/merkle.rs pattern, including "not a breaking change until conformance vectors land" and the explicit prohibition on adding vectors to tests/vectors.json.
• RingRoot, TimeBucket, MmrNode implement ContentAddressable via to_canonical_dagcbor only; module docs state why MerkleNode's causal-set parents were rejected (positional semantics) — the design seam documented, not just implemented.
• Unit tests: rotation is atomic and deterministic (same inputs ⇒ same new root CID); steady-state rotation appends exactly the displaced (oldest) bucket to the MMR while fill-phase rotation appends nothing; buckets order changes the root CID (positional links are order-significant, inverse of MerkleNode's insertion-order-independence test); duplicate payload links do NOT collapse.
• Proof round-trip tests: prove_inclusion → verify_inclusion = Ok(true) in-window; prove_eviction → verify_eviction = Ok(true) past-window; tampered bucket/sample/MMR path ⇒ Ok(false) (never Err) per the frozen verify contract (decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8).
• Property tests over random sample streams and rotation schedules: window-totality (law 3) holds at every observed state; retirement MMR is append-only across arbitrary rotation sequences; the MMR leaf index of every retired bucket equals its epoch.
• The four proof obligations are named in module docs with [Lean]/[TLA+] tags.
• New file(s) stay under the soft 2,500-line cap; split the MMR into its own module if needed.
• README / crate docs mention the feature with its speculative + non-frozen status.

Non-goals / follow-ups

• O(log) in-bucket inclusion proofs — the MVP TimeBucket is a flat sample vector, so in-window inclusion reveals the bucket (O(samples_per_bucket)). An in-bucket Merkle tree (another positional sibling node shape, same ContentAddressable derivation) upgrades this to O(log samples_per_bucket). (Follow-up, to be filed.)
• Downsample-on-evict — linking an aggregate summary CID beside each retired bucket root (the "keep the shape, drop the samples" story). (Follow-up, to be filed.)
• CAS garbage collection of evicted buckets' blocks — this crate only guarantees the commitments survive; actual GC belongs to stores built on the seam.
• Consistency proofs between arbitrary ring states (full RFC 6962-style consistency across many rotations, not just one transition). Follow-up once the MVP transition proof exists.
• Byte freeze + conformance vectors — explicitly deferred, per the freeze-minimally rule; tracked toward 0.1.0-rc1 under Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17 alongside the promised Merkle conformance vectors.
• Python bindings — see Python exposure above.
• A shared CID-resolving store trait — MVP uses the local BlockSource seam; migration happens if/when a shared seam lands. (Follow-up, to be filed.)

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 issue lands under it); feat: add feature-gated merkle module (MerkleNode DAG-node helper) #11 (MerkleNode), test: golden conformance vectors + Rust↔Python byte-parity gate #12 (golden vectors + Rust↔Python parity), decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (frozen verify contract), ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline).
• RFC 6962 — Certificate Transparency (Merkle consistency/inclusion proof lineage): https://datatracker.ietf.org/doc/html/rfc6962
• Merkle Mountain Ranges (Peter Todd, OpenTimestamps): https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md
• S. Crosby & D. Wallach — "Efficient Data Structures for Tamper-Evident Logging" (USENIX Security 2009); background on tamper-evident log commitments and proof kinds.

---

Part of #30 (Merkle structure catalog epic).