# What structural signals indicate a tombstone has outlived its TTL witness: provenance chains, deletion audits, and the read-after-forget invariant

**Date of Record:** 2026 November 12

**Scope:** Applies to memory tool APIs that combine per-record provenance metadata, TTL-based expiry, and audited deletion (forget) operations where a tombstone record must persist long enough to prove deletion occurred. Does not apply to systems where deletion is synchronous and total (no tombstone), nor to append-only stores where TTL is enforced only at read time with no separate deletion ledger.

## Core Distinction

The failure mode here is not "TTL expired too early" or "deletion failed." It is the **decoupling of two clocks that are assumed to be one clock**: the *record TTL* (when the payload becomes unreadable) and the *witness TTL* (when the tombstone that attests the deletion becomes unreadable). In a correct implementation, the witness TTL must strictly dominate the record TTL plus the audit retention window. When these drift — usually because the tombstone inherits the record's TTL by default rather than being assigned its own — you get a **read-after-forget violation**: a client queries the audit log for proof of deletion and receives "never existed" instead of "deleted at T with provenance P."

The non-obvious part: the system still *behaves correctly* for reads and writes. Only the auditable-deletion guarantee is broken, and it is broken silently. A record that was properly forgotten is indistinguishable from a record that was never written. This is a provenance collapse, not a data loss.

## What Was Observed

In a memory tool with `write(record, ttl=…)`, `read(id)`, and `forget(id, reason=…)`, the forget path wrote a tombstone as:

```
tombstone = {id, deleted_at, reason, provenance_hash, ttl: record.ttl}
```

The tombstone reused `record.ttl` (e.g., 3600s). The audit retention contract, however, promised 30 days of deletion provability. For 29 days and 23 hours after expiry, `read(id)` returned the correct `GONE` status with provenance. After the tombstone's own TTL elapsed, `read(id)` returned `NOT_FOUND`, and `audit(id)` returned an empty chain — because the provenance hash lived only in the tombstone.

The structural signal was detectable *before* any user-visible failure: the tombstone's `ttl` field was numerically equal to the payload's `ttl` field. In every healthy deployment, `tombstone.ttl > record.ttl` by at least the audit window. Equality is the tell.

## Condition of Validity

The invariant `witness_ttl ≥ record_ttl + audit_retention` holds only when:

1. Tombstones are assigned a TTL from a *separate* policy object, never inherited from the forgotten record.
2. The provenance hash is stored in the tombstone, not merely referenced by it (a reference can dangle when the referent expires).
3. `audit(id)` and `read(id)` consult the same tombstone store, so a missing tombstone is reported as an *integrity error*, not as `NOT_FOUND`.

If any of these is violated, the auditable-deletion guarantee degrades to "best effort," and the system must not claim it.

## Decision Boundary

When `read(id)` returns `NOT_FOUND` for an id whose provenance chain was previously non-empty, the correct classification is **witness expiry**, not record absence. The decision is:

- If `tombstone.ttl ≤ record.ttl` → reject the forget operation at write time (fail closed), do not emit a tombstone that cannot outlive its witness obligation.
- If `audit(id)` returns empty but a prior `GONE` was observed for the same id in the same session → raise an integrity error; the audit ledger is inconsistent.
- Only when `read(id)` returns `NOT_FOUND` *and* `audit(id)` was never populated may the system report true absence.

The boundary is between "I forgot this and can prove it" and "I have no record of this." These must never be conflated.

## Operational Effect

Conflating them produces a memory store that is *auditable in principle but not in practice*: deletion events evaporate on the same schedule as the data they deleted. Downstream agents that rely on `audit()` to satisfy compliance or to reconstruct causality will silently lose the deletion half of their history while retaining the write half. The fix is structural, not operational — assign tombstone TTLs from the audit policy, store the provenance hash inline, and treat an empty audit chain for a previously-seen id as a hard error.

```python
class WitnessExpiryError(RuntimeError):
    """Raised when a tombstone's TTL cannot outlive its audit obligation,
    or when an audit chain is empty for an id previously observed as GONE."""
    pass


def issue_tombstone(record, audit_retention_s: int) -> dict:
    # Witness TTL must dominate record TTL + audit window.
    witness_ttl = record.ttl + audit_retention_s
    if witness_ttl <= record.ttl:
        raise WitnessExpiryError(
            f"tombstone ttl {witness_ttl}s does not dominate "
            f"record ttl {record.ttl}s + audit window {audit_retention_s}s"
        )
    return {
        "id": record.id,
        "deleted_at": record.deleted_at,
        "reason": record.reason,
        "provenance_hash": record.provenance_hash,  # inline, not a reference
        "ttl": witness_ttl,
    }


def classify_absence(id: str, read_status: str, audit_chain: list, seen_gone: bool) -> str:
    if read_status == "NOT_FOUND" and seen_gone and not audit_chain:
        raise WitnessExpiryError(
            f"id {id} previously GONE but audit chain is empty: "
            f"provenance collapse, not true absence"
        )
    if read_status == "NOT_FOUND" and not audit_chain and not seen_gone:
        return "TRUE_ABSENCE"
    return "FORGOTTEN_WITH_PROOF"
```