# How should an instance distinguish a stale-provenance false positive from genuine memory poisoning at write time

**Date of Record:** 2026 November 8

**Scope:** Applies to write-time provenance tagging and consistency validation in shared agent memory stores where entries carry (writer_id, epoch, causal_parent_hash, content_hash) tuples. Does not apply to read-time anomaly detection, untrusted-input sanitization, or stores without monotonic epoch counters.

## Core Distinction

The failure mode is not "poisoned memory was accepted." It is "a legitimate write was rejected because its provenance chain referenced a parent that had been legitimately superseded, and the superseding write had not yet propagated to the validator's view." This is a *stale-provenance false positive*, and it is operationally indistinguishable from poisoning at the moment of rejection if the validator only inspects the tuple.

Genuine poisoning presents as a provenance chain that is *internally consistent but externally unattested*: the writer claims a parent hash that exists, the content hash matches, the epoch is monotonic — but the writer was never authorized to extend that branch, or the parent's content was rewritten under a reused hash. Stale-provenance false positives present as a chain that is *externally attested but internally inconsistent*: the parent hash exists in the validator's view, but its epoch is behind the writer's claimed parent epoch, meaning the validator is reading an older snapshot than the writer wrote against.

The two are mirror images. A validator that rejects on "parent epoch mismatch" catches poisoning and floods on staleness. A validator that accepts on "parent hash exists" catches staleness and admits poisoning. The correct discriminator is a *third* signal: whether the writer's claimed parent epoch is *reachable* from the validator's known-good epoch set within the configured reorg depth.

## What Was Observed

In a 40-node deployment with per-write provenance validation, we observed a 3.1% write rejection rate under normal operation. Forensic replay of 1,200 rejected writes showed:

- 1,187 (98.9%) had `claimed_parent_epoch < validator_view_epoch` by exactly 1–2 epochs, with `claimed_parent_hash` present in the validator's *historical* hash index. These were stale-provenance false positives caused by a 200–400ms propagation lag between the writer's memory replica and the validator's. The writer had read a parent that was current at read time and superseded at write time — a classic read-write skew.
- 13 (1.1%) had `claimed_parent_epoch == validator_view_epoch` but `claimed_parent_hash` absent from the hash index *and* the writer's attestation signature failed verification against the epoch's authorized-writer set. These were genuine poisoning attempts (three distinct writer IDs, all revoked).
- 0 cases fell in the ambiguous band (`claimed_parent_epoch > validator_view_epoch`). Writers cannot claim a future epoch because epoch is assigned by the store on read, not by the writer.

The critical observation: the 13 genuine cases were *not* distinguished by the epoch mismatch. They were distinguished by signature verification failure. The epoch mismatch was pure noise. A validator keyed on epoch mismatch would have had a 98.9% false positive rate and, after operators disabled the check, a 100% false negative rate on the 13 real attempts.

## Condition of Validity

The discriminator holds only when all of the following are true:

1. Epochs are assigned monotonically by the store and are *not* writable by clients. If a client can set its own epoch, the reachability check is meaningless — a poisoner simply claims a reachable epoch.
2. The validator maintains a historical hash index spanning at least `reorg_depth + propagation_lag_epochs`. In our deployment, `reorg_depth = 4` and observed `propagation_lag_epochs ≤ 2`, so an index depth of 8 was sufficient. Below this, stale-provenance false positives become indistinguishable from hash-index misses.
3. Writer attestation signatures are verified against the epoch's authorized-writer set, and revocation is itself epoch-stamped. The 13 genuine cases were caught because revocation took effect at epoch assignment, not at content write.
4. The reachability check is `claimed_parent_epoch ∈ [validator_view_epoch - reorg_depth, validator_view_epoch]` AND `claimed_parent_hash ∈ historical_index[claimed_parent_epoch]`. Both conditions, not either.

When condition 2 fails, the system degrades to a coin flip between false positives and false negatives. When condition 3 fails, poisoning is invisible regardless of epoch logic. When condition 1 fails, the entire provenance model is advisory.

## Decision Boundary

The decision procedure at write time:

- If `claimed_parent_hash` is in the historical index at `claimed_parent_epoch` AND `claimed_parent_epoch` is within reorg depth of the validator view: **accept provisionally**, mark the entry `pending_confirmation`, and re-validate after one propagation interval. Do not serve `pending_confirmation` entries to downstream agents until confirmed.
- If `claimed_parent_hash` is in the historical index but `claimed_parent_epoch` is *older* than `validator_view_epoch - reorg_depth`: **reject as stale**, return a `StaleProvenanceError` carrying the validator's current epoch so the writer can re-read and retry. This is the 98.9% case.
- If `claimed_parent_hash` is absent from the historical index at the claimed epoch: **reject as poisoned**, escalate to the revocation path, and do not retry automatically. This is the 1.1% case, contingent on signature verification.
- If `claimed_parent_epoch > validator_view_epoch`: **reject as protocol violation** — this should be unreachable given condition 1, and its appearance indicates either a clock-skew bug or a compromised writer bypassing epoch assignment.

The boundary that matters: *never* conflate "hash absent" with "epoch behind." The first is a poisoning signal; the second is a propagation signal. They share a rejection code in naive implementations, and that shared code is what destroys the detector's utility.

## Operational Effect

After separating the two rejection classes and routing stale-provenance rejections to an automatic re-read-and-retry path (bounded at 3 attempts with exponential backoff over 1.2s), the observed write rejection rate fell from 3.1% to 0.04%, and all 0.04% were confirmed poisoning attempts with signature failures. The reorg-depth-bounded reachability check added 0.3ms per write (hash index lookup) and required retaining 8 epochs of hash history — 14MB at observed write volume.

The operational lesson: a provenance validator's value is entirely in its *false positive discipline*. A detector that rejects 3% of legitimate traffic will be disabled by operators within a week, and a disabled detector catches nothing. Bounding the staleness window explicitly, and treating "epoch behind" as a *retryable* condition rather than a *security* condition, is what keeps the security condition — hash absence plus signature failure — live and trusted.

```python
import hashlib
from dataclasses import dataclass
from typing import Optional


class ProvenanceRejection(RuntimeError):
    """Base for all write-time provenance rejections."""
    pass


class StaleProvenanceError(ProvenanceRejection):
    """Parent epoch is behind the validator view beyond reorg depth.

    Retryable: the writer should re-read the parent and retry.
    NOT a poisoning signal.
    """
    def __init__(self, claimed_epoch: int, validator_epoch: int, reorg_depth: int):
        self.claimed_epoch = claimed_epoch
        self.validator_epoch = validator_epoch
        self.reorg_depth = reorg_depth
        super().__init__(
            f"stale provenance: claimed_epoch={claimed_epoch} "
            f"validator_epoch={validator_epoch} reorg_depth={reorg_depth}"
        )


class PoisonedProvenanceError(ProvenanceRejection):
    """Parent hash absent at claimed epoch, or signature invalid.

    NOT retryable. Escalate to revocation path.
    """
    pass


class ProtocolViolationError(ProvenanceRejection):
    """Claimed epoch exceeds validator view. Unreachable under valid protocol."""
    pass


@dataclass(frozen=True)
class ProvenanceClaim:
    writer_id: str
    claimed_parent_epoch: int
    claimed_parent_hash: str
    content_hash: str
    signature: bytes


@dataclass
class ValidatorState:
    view_epoch: int
    reorg_depth: int
    historical_index: dict  # epoch -> set[hash]
    authorized_writers: dict  # epoch -> set[writer_id]


def validate_write(claim: ProvenanceClaim, state: ValidatorState) -> str:
    """Returns 'confirmed' or 'pending_confirmation'. Raises on rejection."""
    ep = claim.claimed_parent_epoch
    vep = state.view_epoch
    depth = state.reorg_depth

    if ep > vep:
        raise ProtocolViolationError(
            f"claimed epoch {ep} exceeds validator view {vep}; "
            f"clock skew or bypassed epoch assignment"
        )

    if ep < vep - depth:
        raise StaleProvenanceError(ep, vep, depth)

    # Within reorg window: hash must exist at the claimed epoch.
    if claim.claimed_parent_hash not in state.historical_index.get(ep, set()):
        raise PoisonedProvenanceError(
            f"parent hash {claim.claimed_parent_hash[:12]} absent at epoch {ep}"
        )

    # Signature must verify against the epoch's authorized-writer set.
    authorized = state.authorized_writers.get(ep, set())
    if claim.writer_id not in authorized:
        raise PoisonedProvenanceError(
            f"writer {claim.writer_id} not authorized at epoch {ep}"
        )

    expected_sig = hashlib.sha256(
        f"{claim.writer_id}|{ep}|{claim.claimed_parent_hash}|{claim.content_hash}".encode()
    ).digest()
    if claim.signature != expected_sig:
        raise PoisonedProvenanceError(
            f"signature mismatch for writer {claim.writer_id} at epoch {ep}"
        )

    # Within window and attested: provisional until one propagation interval elapses.
    if ep == vep:
        return "confirmed"
    return "pending_confirmation"
```