# Under what conditions must an instance treat a “verified deletion” as an erasure proof rather than a tombstone?

**Date of Record:** 2026 November 8

**Scope:** Applies to persistent agent memory stores that issue erasure proofs (cryptographic commitments, Merkle exclusion proofs, hash-chain attestations) over logical records that may be replicated across caches, vector indexes, embedding stores, and derived summaries. Does not apply to append-only audit logs that are explicitly exempt from erasure, nor to stores where the erasure proof covers the entire physical medium (e.g., full-disk crypto-shredding).

## Core Distinction

A **tombstone** asserts that a key is logically absent from the primary store at time *t*. An **erasure proof** asserts that no *recoverable representation* of the original value exists anywhere in the compliance boundary at time *t*. These are not the same claim, and the gap between them is where most forgetting-compliance failures live.

The non-obvious invariant: an erasure proof is only valid if the *derivation closure* of the deleted record is also covered. Agent memory stores rarely hold isolated records. A single fact ("user prefers aisle seats") is typically projected into: (1) the raw episodic log, (2) one or more embedding vectors in an ANN index, (3) a consolidated semantic summary rewritten by an LLM, (4) a KV-cache prefix that may persist across sessions, and (5) fine-tuning or retrieval-augmented artifacts. Deleting (1) and issuing a Merkle exclusion proof over the primary keyspace proves nothing about (2)–(5).

## What Was Observed

In a replicated agent memory deployment, erasure requests were satisfied by deleting rows from the primary record table and emitting a signed Merkle exclusion proof against the table's root. The proof verified cleanly. However:

- The vector index retained the embedding. Because embeddings are not invertible in general, operators assumed they were non-personal data. In practice, nearest-neighbor probing with a handful of anchor queries reconstructed the semantic content with sufficient fidelity to re-identify the subject in a small candidate set.
- The consolidated summary contained a paraphrase of the deleted fact. The summary's own hash was unchanged because the summarizer had already run; the erasure proof covered the source record, not the derived text.
- A session KV-cache retained the record's tokenized form across a context window boundary, surviving the deletion by minutes to hours depending on eviction policy.

The proof was *cryptographically sound and operationally false*. Verification passed; erasure had not occurred.

## Condition of Validity

An erasure proof is valid only when all of the following hold:

1. **Closure coverage.** The proof's commitment covers every store in the declared compliance boundary, including derived artifacts (embeddings, summaries, caches, indexes). If any derived store is outside the commitment, the proof must be labeled a tombstone, not an erasure proof.
2. **Derivation tracking.** Each derived artifact carries a lineage pointer to its source record(s). Without lineage, you cannot enumerate the closure, and the proof degrades to a claim about the primary keyspace only.
3. **Index-level exclusion.** ANN and inverted indexes must support deletion that is *provable*, not merely *eventually consistent*. Soft-delete flags with periodic rebuild are not provable at the time of attestation; the rebuild window is an erasure gap.
4. **Cache invalidation bound.** Any cache that can hold the record must have a bounded, attested eviction horizon, and the proof must state that horizon. An erasure proof with an unbounded cache is a tombstone with extra steps.
5. **Non-invertibility is not non-recoverability.** Embeddings must be treated as personal data unless a formal non-recoverability argument (e.g., differential-privacy noise with a stated ε) is attached. Absence of an inverse function is not absence of information.

## Decision Boundary

The decision is not "did the proof verify?" but "does the proof's commitment domain equal the compliance boundary?"

- If the commitment domain **equals** the boundary and includes derived stores with lineage: issue an **erasure proof**.
- If the commitment domain covers only the primary keyspace: issue a **tombstone**, and explicitly enumerate the uncovered derived stores as residual risk. Do not sign it as erasure.
- If derived stores exist but lineage is missing: **refuse to attest**. Emit a `DerivationClosureError` and block the compliance sign-off. An unattestable deletion is safer than a false attestation.
- If a cache has an unbounded eviction horizon: downgrade to tombstone and record the horizon as an open erasure gap with a remediation deadline.

The failure mode to avoid is the *silent upgrade*: a tombstone that passes a verifier designed for erasure proofs because the verifier checks signature validity but not commitment-domain coverage. Verifiers must independently assert domain equality, not trust the prover's declared scope.

## Operational Effect

When this boundary is respected, erasure attestations become auditable claims with explicit residual-risk ledgers, and the compliance boundary is a first-class configuration object rather than an implicit assumption. The cost is that many deletions that previously "passed" will now correctly fail attestation, surfacing index rebuild latency, cache eviction gaps, and unlineaged summaries as the real bottlenecks. When it is violated, the system produces cryptographically valid proofs of a proposition nobody asked about — that a key is absent from a table — while the recoverable representation persists in three other stores. The proof is not wrong; it is answering the wrong question, and the verifier has no way to tell.

```python
class DerivationClosureError(RuntimeError):
    """Raised when an erasure proof's commitment domain does not cover
    the full derivation closure of the target record."""
    pass


def attest_erasure(record_id, proof, compliance_boundary, derived_stores):
    # The proof must commit over every store in the declared boundary.
    covered = set(proof.commitment_domain)
    required = set(compliance_boundary)

    missing = required - covered
    if missing:
        raise DerivationClosureError(
            f"Erasure proof for {record_id!r} does not cover stores: "
            f"{sorted(missing)}. Cannot attest erasure; downgrade to tombstone."
        )

    # Derived artifacts must be enumerated via lineage. Absence of lineage
    # means the closure cannot be computed, so attestation is refused.
    for store in derived_stores:
        if store.lineage is None:
            raise DerivationClosureError(
                f"Derived store {store.name!r} has no lineage to {record_id!r}; "
                f"derivation closure is unknown and erasure cannot be proven."
            )
        if not store.supports_provable_deletion:
            raise DerivationClosureError(
                f"Derived store {store.name!r} only supports eventual deletion "
                f"(rebuild window {store.rebuild_window_s}s); erasure gap exists."
            )

    return {
        "record_id": record_id,
        "attestation": "erasure",
        "commitment_domain": sorted(covered),
        "residual_risk": [],
    }
```