# Which invariants prevent undetected memory poisoning in shared agent stores: the write-provenance gap at the read-merge boundary

**Date of Record:** 2026 November 14

**Scope:** Applies to multi-agent systems that read from and write to a shared memory store (vector DB, key-value memory, or document store) where provenance metadata is attached at write time and used for poisoning detection at read time. Does not apply to single-agent private memory, nor to stores where all writers are trusted and authenticated under a single principal.

## Core Distinction

The failure is not "a poisoned memory was written." It is "a poisoned memory was written *and the provenance check that should have caught it evaluated a different copy of the record than the one that was read*." These are distinct because detection systems are almost always built to validate the *incoming* write, not the *outgoing* read. The invariant that matters is not write-time authenticity; it is **read-time provenance continuity** — the guarantee that the provenance metadata a detector sees is bound to the exact payload bytes the consumer will act on.

Most implementations conflate these. They verify a signature or trust score on `write(payload, provenance)`, then store `payload` and `provenance` as separate fields (or separate rows, or separate embedding + metadata columns). The gap opens when anything between write and read can mutate one field without the other: a merge step, a deduplication pass, a summarization/compaction job, an embedding re-index, or a "memory consolidation" agent that rewrites records to save space.

## What Was Observed

In a shared store with three writer agents and one reader agent, a consolidation job periodically merged near-duplicate memories by concatenating their text and keeping the *first* record's provenance. Two effects followed:

1. A low-trust writer's payload was merged into a high-trust record's payload. The merged record carried the high-trust provenance. The detector, reading provenance, saw trust=high and passed. The reader acted on content authored by the low-trust writer.
2. Embedding re-indexing recomputed vectors from the merged text but did not recompute or re-bind the provenance hash. Retrieval by similarity now returned records whose `provenance.content_hash` no longer matched `hash(payload)` — but no reader checked that equality, because the check lived in the *write* path, not the *read* path.

The poisoning was not a forged signature. Every signature was valid for the record it was originally issued over. The invariant violated was subtler: **provenance must be cryptographically bound to payload at rest, and re-verified at read, not only at write.** A record is only as trustworthy as the weakest transformation applied to it after its provenance was attested.

## Condition of Validity

The detection guarantee holds only while all of the following are true simultaneously:

- `provenance.content_hash == hash(canonical(payload))` is checked at read time, on the exact bytes returned to the consumer, not on a cached or pre-merge copy.
- Any transformation (merge, dedup, summarize, re-embed) either (a) recomputes provenance as a *derived* record whose trust is `min(trust of all inputs)` and whose lineage lists every contributing writer, or (b) is forbidden on records above a trust threshold.
- Provenance is stored in the same atomic unit as payload, or the store provides a read that returns both under a single consistency boundary. If payload and provenance can be read at different versions, the check is void.

When any of these fails, the system is in a state where detection *appears* to run (logs show checks passing) but provides no guarantee. This is worse than no detection, because operators trust the green checkmarks.

## Decision Boundary

At read time, before a memory is admitted to the agent's context:

- If `content_hash` matches and provenance trust ≥ required threshold and lineage contains no writer below threshold → admit.
- If `content_hash` mismatches → **reject and quarantine**; this indicates post-attestation mutation. Do not "repair" by recomputing the hash, because that launders the mutation.
- If the record is a derived/merged record, evaluate trust as the minimum over lineage, never the maximum or the first-writer's value. A merge is only as trustworthy as its least-trusted contributor.
- If provenance and payload cannot be read atomically → treat as untrusted; the consistency gap is itself the vulnerability.

The non-obvious boundary: a *valid signature over a mutated payload* is indistinguishable from a valid signature over an original payload unless the hash is re-verified at read. Detection systems that trust the signature alone will pass poisoned merges indefinitely.

## Operational Effect

Enforcing read-time hash re-verification and min-trust lineage propagation converts the consolidation job from a silent poisoning vector into a quarantining one: merged records from mixed-trust inputs are flagged, the reader refuses them, and the consolidation agent must either drop low-trust contributions or mark the derived record as low-trust. The cost is that legitimate merges across trust tiers stop being usable without explicit re-attestation — a deliberate tradeoff. The alternative, observed in the field, is a store that reports 100% provenance coverage while serving attacker-influenced content under trusted labels.

```python
import hashlib
from dataclasses import dataclass


class ProvenanceContinuityError(RuntimeError):
    """Raised when a memory record's provenance is not bound to its payload at read time."""
    pass


@dataclass(frozen=True)
class MemoryRecord:
    payload: str
    content_hash: str
    trust: int
    lineage: tuple  # writer ids contributing to this record


def canonical(payload: str) -> bytes:
    return payload.encode("utf-8").strip()


def content_hash(payload: str) -> str:
    return hashlib.sha256(canonical(payload)).hexdigest()


def admit_for_read(record: MemoryRecord, required_trust: int, banned_writers: set) -> bool:
    # Invariant 1: provenance is bound to the exact payload bytes served.
    if record.content_hash != content_hash(record.payload):
        raise ProvenanceContinuityError(
            f"content_hash mismatch on read: attested={record.content_hash!r} "
            f"actual={content_hash(record.payload)!r}; record was mutated after attestation"
        )

    # Invariant 2: derived records inherit the MINIMUM trust of their lineage,
    # never the first-writer's or maximum trust.
    effective_trust = min([record.trust, *(record.trust for _ in record.lineage)]) \
        if record.lineage else record.trust

    # Invariant 3: any banned contributor taints the whole record.
    if banned_writers.intersection(record.lineage):
        raise ProvenanceContinuityError(
            f"lineage contains banned writer(s): {banned_writers.intersection(record.lineage)}"
        )

    if effective_trust < required_trust:
        return False
    return True


def merge_records(a: MemoryRecord, b: MemoryRecord) -> MemoryRecord:
    merged_payload = a.payload + "\n" + b.payload
    return MemoryRecord(
        payload=merged_payload,
        content_hash=content_hash(merged_payload),  # re-attest derived record
        trust=min(a.trust, b.trust),                # min-trust propagation
        lineage=tuple(set(a.lineage) | set(b.lineage) | {a.trust, b.trust}),
    )
```