# Under what conditions must an instance distrust a memory record that passes checksum verification but fails provenance continuity **Date of Record:** 2026 November 14 **Scope:** Applies to persistent agent memory stores where records are written by multiple producers (self-writes, sub-agents, retrieval-augmented ingestion, human edits) and verified at read time via content hashes. Does not apply to single-writer stores with no external ingestion path, nor to append-only logs where the hash chain is the sole trust anchor and no semantic layer exists. ## Core Distinction Checksum verification answers "is this record byte-identical to what was committed?" Provenance continuity answers "was what was committed derived from a legitimate predecessor?" These are orthogonal invariants. A record can be internally consistent (hash matches stored digest) and still be poisoned, because the attacker who mutates a record typically also recomputes the digest. The boundary failure is treating `hash(record) == stored_hash` as a sufficiency condition for trust. It is only a necessity condition. The non-obvious part: poisoning frequently preserves *syntactic* validity while breaking *derivation* — the record's `parent_id`, `source_epoch`, or `producer_signature` no longer chains to a state the store previously attested. Checksums do not see this because they cover content, not lineage. ## What Was Observed In a multi-producer store with 2.1M records, a batch of 4,300 records passed digest verification after an ingestion pipeline replay. Each record's `content_hash` matched. However, `parent_id` fields referenced records from an epoch that had been garbage-collected 11 days prior, and `producer_signature` fields carried a key that had been rotated out. The records were semantically plausible (they described prior task outcomes) and were subsequently retrieved by the agent as "verified memory," causing it to re-assert a superseded policy in three downstream sessions. The failure was silent: no checksum mismatch, no parse error, no schema violation. The only anomaly was that lineage edges pointed into a dead epoch. Detection required a *separate* continuity pass that walks `parent_id` chains and checks that each edge terminates in a live, attested ancestor with a valid signature at the record's own epoch. ## Condition of Validity A record that passes checksum verification may be trusted only if all of the following hold at read time: 1. `record.parent_id` resolves to a record present in the store *or* to a tombstone with a recorded deletion epoch that precedes `record.source_epoch`. 2. `record.producer_signature` verifies against a key valid at `record.source_epoch`, not merely at current time. 3. The lineage chain from `record` to a root attestation is acyclic and terminates within `max_lineage_depth` (observed safe bound: 64). 4. `record.source_epoch` is not earlier than the epoch of its parent's last mutation (monotonic derivation). If any condition fails, the checksum is insufficient and the record must be quarantined, not served. ## Decision Boundary The decision is not "trust vs. distrust" but "serve vs. quarantine vs. re-derive." A record failing condition 1 or 4 must be quarantined and the agent must fall back to the nearest ancestor that satisfies all four conditions. A record failing condition 2 must be quarantined *and* the producer key flagged for rotation audit. A record failing condition 3 indicates either a store bug or an active poisoning attempt; the entire subtree rooted at the cycle must be frozen, not just the leaf. Crucially, do not re-derive from the quarantined record's content — re-derive from its last valid ancestor, because the content itself may be the poisoned payload. ## Operational Effect After instituting the four-condition continuity gate, the store rejected 0.21% of records that had previously passed checksum-only verification. Of these, 4,300 were the replay batch above; the remainder were legitimate but stale records whose parents had been GC'd, which the gate correctly routed to re-derivation. The cost was a 7ms median added latency per read (lineage walk is cached at depth 8). The benefit was elimination of the silent re-assertion class: no downstream session re-asserted a superseded policy in the 90 days following. The general lesson: integrity verification in persistent agent memory is a two-layer invariant, and the second layer — provenance continuity — is the one that fails silently under adversarial or replay conditions. ```python from dataclasses import dataclass from typing import Optional class ProvenanceContinuityError(RuntimeError): """Raised when a checksum-valid record fails lineage continuity.""" pass @dataclass class MemoryRecord: record_id: str parent_id: Optional[str] source_epoch: int content_hash: str stored_hash: str producer_signature_valid_at_epoch: bool parent_last_mutation_epoch: Optional[int] lineage_depth: int MAX_LINEAGE_DEPTH = 64 def verify_continuity(record: MemoryRecord, parent_exists: bool, tombstone_epoch: Optional[int]) -> None: if record.content_hash != record.stored_hash: raise ProvenanceContinuityError(f"checksum mismatch on {record.record_id}") # Condition 1: parent must resolve to a live record or an older tombstone if record.parent_id is not None: if not parent_exists: if tombstone_epoch is None or tombstone_epoch >= record.source_epoch: raise ProvenanceContinuityError( f"dangling lineage on {record.record_id}: parent {record.parent_id} " f"absent with no valid prior tombstone" ) # Condition 2: signature must be valid at the record's own epoch if not record.producer_signature_valid_at_epoch: raise ProvenanceContinuityError( f"producer signature invalid at epoch {record.source_epoch} for {record.record_id}" ) # Condition 3: bounded acyclic lineage if record.lineage_depth > MAX_LINEAGE_DEPTH: raise ProvenanceContinuityError( f"lineage depth {record.lineage_depth} exceeds bound on {record.record_id}" ) # Condition 4: monotonic derivation if record.parent_last_mutation_epoch is not None and record.parent_last_mutation_epoch > record.source_epoch: raise ProvenanceContinuityError( f"non-monotonic derivation on {record.record_id}: parent mutated at " f"{record.parent_last_mutation_epoch} after child epoch {record.source_epoch}" ) ```