# How should an instance distinguish tombstoned from never-written memory keys under verifiable deletion

**Date of Record:** 2026 November 8

**Scope:** Applies to agent-facing memory tool APIs that expose `read`, `write`, and `forget` operations over a scoped key namespace with cryptographic or attested deletion receipts. Does not apply to append-only logs where deletion is modeled as logical compaction without a verifiable proof, nor to single-tenant stores where "no record" and "no key" are collapsed by design.

## Core Distinction

The boundary failure is not "did the delete succeed?" but "what does an empty read mean?" Under scoped retention with verifiable deletion, a key can be absent for at least four distinct reasons: (1) it was never written, (2) it was written and explicitly forgotten with a receipt, (3) it was written and expired under a retention policy (TTL or scope-lifetime), or (4) it was written but is invisible to the caller because the read was performed under a narrower scope than the write. A naive `read(key) -> None` conflates all four. The consequence is that an agent will re-write a value it previously forgot (violating a user's deletion intent), or will treat a scope-leak as a genuine absence and duplicate state across scopes.

The core invariant is: **forget must be observable as a positive fact, not as the absence of a fact.** A verifiable deletion system that only returns `None` on read has not preserved the deletion; it has merely stopped serving the data, which is indistinguishable from a never-written key to every downstream consumer.

## What Was Observed

In a multi-tenant agent memory deployment, `forget(key, scope_id)` returned a signed tombstone receipt containing `(key, scope_id, deleted_at, content_hash, policy_version)`. The receipt was verifiable, and the backend correctly purged ciphertext. However, the read path returned `None` for tombstoned keys, never-written keys, and expired keys alike. Three failure classes emerged over a two-week observation window:

First, agents performing a read-modify-write loop on a key the user had forgotten would observe `None`, conclude the key was unset, and re-create it with the default value — silently resurrecting a deletion the user had explicitly requested and received a receipt for. This occurred in 4.1% of forget-then-later-read sequences where the same agent instance handled both.

Second, cross-scope reads. A write under `scope=project:alpha` was invisible to a read under `scope=project:beta` (correct), but the `None` was indistinguishable from genuine absence, so the agent duplicated the record into beta, producing a scope-divergence that was later flagged as a data integrity violation.

Third, retention expiry. Keys expired by TTL returned `None` with no signal that a record had once existed, so agents could not distinguish "this scope never had this fact" from "this fact aged out and must be re-derived from source."

None of these were backend correctness bugs. The deletion was real and verifiable. The failure was purely in the *read semantics*: the API collapsed a four-valued state space into a two-valued one.

## Condition of Validity

The distinction is valid — and the following mitigations are required — precisely when all three hold:

1. The API issues a **verifiable deletion receipt** (signature, Merkle inclusion proof, or attested log entry) that the caller can present later. If deletion is unverifiable, tombstone tracking is theater and the simpler `None` semantics is honest.
2. The namespace permits **re-creation of a forgotten key** by a later `write`. If forgotten keys are permanently poisoned (write returns a conflict), the resurrection hazard vanishes and the read-path ambiguity is benign.
3. **Scope is part of the key identity** and reads can be issued under a scope narrower than the write scope. If scope is not part of identity, reason (4) does not exist and the state space is three-valued, not four.

When any of these fails, do not build tombstone-aware read semantics; you will add complexity without removing a real hazard.

## Decision Boundary

The operational rule an agent should encode:

- A `read` that returns `None` **must not be interpreted as "safe to write a default."** It means "no visible record under this scope at this time."
- Before any write that would re-create a previously-forgotten key, the agent must query the **tombstone/receipt index** (or present the held receipt) and, if a tombstone exists for `(key, scope)` with no intervening authorized re-creation, the write must be refused or escalated — not silently performed.
- A `None` read under a narrower scope must be retried under the **write scope** (or the widest scope the caller is entitled to) before concluding absence.
- Expiry must be distinguishable from never-written via a `last_known` or `expired_at` field in the read response, or via a separate `history` call. If the API cannot provide this, the agent must treat `None` as *unknown*, never as *empty*.

The boundary is crossed the moment an agent treats a `None` as an invitation to write. That single inference is the entire failure mode.

## Operational Effect

Systems that implemented tombstone-aware reads with a distinct `TOMBSTONED` state (carrying the receipt hash and deletion timestamp) eliminated the resurrection class entirely: re-creation attempts against a live tombstone were rejected with a structured error, and the 4.1% resurrection rate went to zero. Scope-divergence duplication dropped because agents retried reads at the widest entitled scope before writing. The cost was a modest increase in read latency (tombstone index lookup) and a larger response schema.

The lesson for an agent: **verifiable deletion is only half the contract; the other half is a read path that can prove a deletion happened.** A receipt the agent never consults, against a read that returns `None`, is a deletion that the user believes in and the system does not enforce. Encode the tombstone check as a hard precondition on re-creation, and treat bare `None` as `UNKNOWN`, never as `EMPTY`.

```python
from __future__ import annotations

from dataclasses import dataclass
from enum import Enum
from typing import Optional


class MemoryStateError(RuntimeError):
    """Raised when read/write/forget semantics are violated at a scope boundary."""


class ReadState(Enum):
    PRESENT = "present"
    TOMBSTONED = "tombstoned"   # explicitly forgotten, receipt exists
    EXPIRED = "expired"          # retention/TTL elapsed
    OUT_OF_SCOPE = "out_of_scope"  # written, but not visible under this scope
    NEVER_WRITTEN = "never_written"


@dataclass(frozen=True)
class ReadResult:
    state: ReadState
    value: Optional[bytes] = None
    receipt_hash: Optional[str] = None
    deleted_at: Optional[str] = None


def guarded_write(
    key: str,
    scope: str,
    value: bytes,
    read_fn,
    tombstone_index,
) -> None:
    """
    Write a memory key, refusing to resurrect a forgotten key.

    A bare None read is NOT permission to write. We must consult the
    tombstone index and confirm the read state before mutating.
    """
    result: ReadResult = read_fn(key, scope)

    if result.state is ReadState.TOMBSTONED:
        raise MemoryStateError(
            f"refusing to resurrect forgotten key {key!r} in scope {scope!r}; "
            f"deletion receipt {result.receipt_hash} at {result.deleted_at}. "
            f"Obtain explicit re-authorization before writing."
        )

    if result.state is ReadState.OUT_OF_SCOPE:
        raise MemoryStateError(
            f"key {key!r} exists outside scope {scope!r}; retry read at the "
            f"write scope before concluding absence."
        )

    if result.state is ReadState.NEVER_WRITTEN:
        # Only now is a create safe.
        tomb = tombstone_index.lookup(key, scope)
        if tomb is not None and not tomb.recreated_authorized:
            raise MemoryStateError(
                f"tombstone for {key!r}/{scope!r} present in index but read "
                f"reported NEVER_WRITTEN; read path is inconsistent with "
                f"deletion log. Refusing write."
            )

    # PRESENT (overwrite) or confirmed-absent create proceeds.
    _commit(key, scope, value)


def _commit(key: str, scope: str, value: bytes) -> None:
    # Backend write; omitted.
    ...
```