Skip to main content
Version: v0.9.0a2
Spec
Experimental feature
This feature is Experimental. Breaking changes may occur before it reaches Stable. See feature status definitions →

§23. Right-to-be-Forgotten Tombstones

7 min readSpec contributor · Compliance reviewerExperimental · future plugin line

What this section covers

Cryptographic tombstones, recall-time suppression, federation propagation, and legal-hold mode. A tombstone is a signed, durable record that directs every node in the federation to suppress facts about a specified entity from all future recall responses.

Status: Experimental / opt-in source package on main

Source material: Archived evolutionary spec snapshots. This page is the maintained Spec-X home for RTBF tombstone semantics.

EXPERIMENTAL

The tombstone signing format and federation propagation rules are still under security review. Until §23 reaches GA:

  • Do not rely on tombstone federation for compliance workflows in multi-node deployments.
  • Tombstone DELETE operations are locally reliable; cross-node propagation is best-effort.
  • Operators with GDPR/CCPA obligations should implement manual deletion coordination across nodes until federation is confirmed correct.
Section body

Each subsection below shows the most recent normative text from the spec source. When earlier spec drafts also contained text for the same subsection, those revisions are collapsed under a Revisions accordion beneath it — open one to see what changed. Subsections that only appear in one draft render as plain text with no accordion.

Status: Experimental. §23.1–§23.7 preserve proposed MUST/SHOULD/MAY language for ADR-008 review, but they are not part of the supported default install.

§23.1 Scope​

This section defines the tombstone mechanism for compliance with right-to-be-forgotten (RTBF) obligations under data-protection frameworks (e.g., GDPR Art. 17, CCPA §1798.105).

Tombstones are a protocol primitive, not a legal determination.

Operators MUST obtain appropriate legal guidance before issuing or refusing tombstone requests.

§23.2 Tombstone Record Shape​

§23.2.1 Schema​

A tombstone record is a self-contained, cryptographically signed directive. It identifies the target entity, the scopes to suppress, and the admin who authorised the erasure. The signature field covers the canonical JSON of all other fields (except reason, which is excluded to allow redaction during federation rebroadcast).

TombstoneRecord:
  id:          string            // globally unique tombstone ID; MUST use prefix "tomb_"
                                 //   followed by a UUID v7 (time-ordered) suffix
  entity_uri:  string            // URI of the entity being tombstoned
  scope:       ScopePattern      // which scope(s) this tombstone covers
  reason:      string | null     // operator-supplied reason; MAY be redacted to "redacted"
                                 //   before forwarding to federation peers
  signed_by:   string            // URI of the admin agent or service that signed the tombstone
  key_id:      string            // SHA-256 hex of the signing key; REQUIRED
  signature:   string            // base64url Ed25519 signature over canonical-JSON body
                                 //   (with "signature" and "reason" excluded)
  created_at:  ISO 8601 string
  legal_hold:  boolean           // default false; see §24.3

§23.2.2 Invariants​

  1. id MUST be globally unique and MUST use the "tomb_" prefix followed by a UUID v7 (time-ordered) suffix.
  2. entity_uri MUST conform to the URI format defined in §9. Wildcards MUST NOT be used; each tombstone covers exactly one entity URI.
  3. signed_by MUST identify an agent or service that holds an active admin API key at the time of tombstone issuance. The signature MUST be verifiable against the signing key in the org manifest.
  4. Tombstone records MUST be stored in a dedicated tombstones table separate from the facts table. Tombstones MUST NOT be stored as ordinary facts.
  5. Tombstone records are immutable once written. To reinstate a tombstoned entity, a separate TombstoneRevocation record MUST be issued.

§23.2.3 Scope Pattern​

ScopePattern controls which scopes of facts the tombstone suppresses:

Value
Type
Meaning
"*"
all scopes
All scopes (local, team, company, public).
"local" / "team" / "company" / "public"
single
That scope only.
Array
union
Union of listed scopes.

Operators SHOULD use the narrowest scope that satisfies the RTBF obligation.

A tombstone with scope: "*" is the broadest possible suppression.

§23.2.4 Canonical JSON for Signing​

The canonical-JSON body for signature computation MUST be produced using RFC 8785 (JCS — JSON Canonicalization Scheme) over the TombstoneRecord object with the "signature" and "reason" fields excluded from the object before canonicalization (consistent with the field-exclusion pattern in §19.1.3). The signed_by value MUST be the plain string URI, not a reference.

Excluding "reason" from the signed body allows the issuing node to redact it to "redacted" before federation rebroadcast without invalidating the signature on peer nodes. Excluding "signature" avoids self-reference. Both exclusions MUST be applied before JCS serialization; implementations MUST NOT use empty-string sentinels in place of exclusion.

The "key_id" field MUST be included in the signed canonical body so that verifiers can resolve the correct historical signing key without trial-verifying against the entire rotation chain.

§23.2.5 Tombstone Revocation​

A tombstone may be revoked by an admin who has a documented legal basis. Revocation is expressed via a separate TombstoneRevocation record rather than deleting the tombstone, because tombstone records are immutable.

TombstoneRevocationRecord:
  id:            string   // "tombrevoke_" + UUID v7
  tombstone_id:  string   // the "tomb_" record being revoked
  reason:        string   // MUST be provided (e.g., court order reference)
  signed_by:     string
  signature:     string
  created_at:    ISO 8601 string

A revocation does NOT delete the tombstone record.

It instructs nodes to re-expose facts that were suppressed solely by the revoked tombstone. Both records are retained indefinitely for compliance evidence.

§23.3 Recall-Time Tombstone Filter​

§23.3.1 Direct-Entity Suppression​

At recall time, before returning any fact or memory card to the caller, the node MUST:

  1. Resolve the set of active tombstones for every entity_uri that appears in the candidate result set (as the entity field, or as a value of type ref).
  2. Exclude any fact whose entity matches a tombstoned entity_uri where the tombstone scope covers the fact's scope.
  3. Exclude any memory card whose about_entity matches a tombstoned entity under the same scope rule.

A tombstone is active if it is present in the tombstones table and has no corresponding tombstone_id entry in the tombstone_revocations table.

§23.3.2 Graph Reference Suppression​

The tombstone filter MUST also suppress indirect graph references to tombstoned entities:

  1. During graph traversal (k-hop, §20.1), edges that reference a tombstoned entity as the target_entity_uri MUST be excluded. The traversal MUST NOT propagate through tombstoned nodes.
  2. Facts whose value is of type ref and whose ref value matches a tombstoned entity_uri MUST be excluded.
  3. Memory cards in the candidate set: a card whose about_entity is tombstoned MUST be suppressed entirely. A card where the tombstoned entity appears only in related_entities MUST have that entry omitted; if the text body still contains PII attributed to the tombstoned entity, the card MUST also be suppressed.
  4. Facts with derived_from entries referencing tombstoned entities MUST represent those entries as {"hash": "...", "exists": false}.

§23.3.3 Completeness and Consistency​

A result set that would have included tombstoned facts MUST be indistinguishable from one that never contained them.

No count, aggregate, or embedding may reveal the existence of suppressed facts. Pagination totals and X-Total-Count headers MUST be computed on the post-tombstone-filter set only.

After scope, before packing

The tombstone check MUST be applied after scope filtering and before token-budget packing.

All recall paths

Applies to GET /v1/recall, recall_instruction, and subscription event delivery.

60 s LRU refresh

Implementations MUST cache active tombstone IDs in an in-process LRU and refresh at most every 60 seconds.

SQLite / PG isolation

SQLite MUST use BEGIN IMMEDIATE; PostgreSQL MUST use at minimum READ COMMITTED with tombstone reads issued after the query plan is complete.

§23.4 Federation Propagation​

§23.4.1 Outbound Rebroadcast​

  1. When a node issues a new TombstoneRecord, it MUST enqueue the tombstone for replication to all active federation peers under the existing federation protocol.
  2. The tombstone MUST be replicated with the signed_by and signature fields unchanged. Peer nodes MUST NOT re-sign tombstones; they MUST verify the original signature before applying the tombstone locally.
  3. The reason field MAY be redacted to "redacted" by the issuing node before rebroadcast. Peer nodes MUST NOT require a non-"redacted" reason to accept the tombstone.

§23.4.2 Inbound Tombstone Handling​

On receiving an inbound tombstone from a federation peer, the node MUST:

  1. Verify the signature against the public key published in the org manifest for the entity URI identified by signed_by. Resolving the relaying peer's manifest instead of the signed_by manifest is a protocol error. Use key_id to select the correct historical key from the rotation chain.
  2. Verify the created_at timestamp is not older than the node's configured retention horizon. The ±5-minute replay-protection window from §22.5 does NOT apply to persistent tombstone records — they are durable records whose created_at is inherently in the past.
  3. Write the tombstone to the local tombstones table if it does not already exist (idempotent on id).
  4. Apply the recall-time filter within 60 seconds for the tombstoned entity.

Nodes MUST NOT silently drop inbound tombstones.

If tombstone verification fails, the node MUST emit a tombstone_verification_failed audit log event and SHOULD alert the operator. Nodes MUST accept tombstones from any trusted federation peer, not only from the org that first issued the tombstone.

§23.4.3 Tombstone Federation Route​

Tombstones are exchanged via a dedicated federation route, separate from the fact replication path. This separation ensures that tombstones can be propagated even when fact replication is paused or throttled.

GET /v1/federation/tombstones?since=<ISO8601>&limit=<N>
Authorization: Bearer <peer capability token>

→ 200 {
    "tombstones":  [ ...TombstoneRecord... ],
    "revocations": [ ...TombstoneRevocationRecord... ],
    "cursor":      "<opaque pagination cursor>"
  }
→ 401 if capability token invalid or scope insufficient

The peer capability token MUST include the "tombstone:read" verb in its verbs array. Peers MUST poll this route at least every 5 minutes in standard federation mode, and MUST poll within 60 seconds of receiving a tombstone_new event via the subscription channel.

§23.5 Storage-Trait Extension​

§23.5.1 New Methods​

tombstone(entity_uri, scope, reason, signed_by, signature, legal_hold) → TombstoneRecord
is_tombstoned(entity_uri, scope) → bool
list_tombstones(scope, since) → [TombstoneRecord]
revoke_tombstone(tombstone_id, reason, signed_by, signature) → TombstoneRevocationRecord

§23.5.2 Semantics​

Idempotent tombstone()

Calling with the same entity_uri and scope when a matching active tombstone exists MUST return the existing tombstone without writing a new record.

Cached is_tombstoned()

Returns true if any active tombstone covers entity_uri with a ScopePattern that includes the given FactScope. SHOULD be cached per §23.3.3.

Revoke failures

revoke_tombstone() MUST fail with tombstone_not_found if no matching tombstone exists, and tombstone_already_revoked if a revocation already exists.

§23.5.3 Schema Migration​

Migration 013a adds the tombstones and tombstone_revocations tables. Tombstones are indexed by entity_uri for the hot-path is_tombstoned() lookup. Migration 013c adds the fact_retractions table, an append-only log of retraction events needed by time-travel queries (§24).

-- Migration 013a: RTBF tombstones
CREATE TABLE tombstones (
  id          TEXT PRIMARY KEY,
  entity_uri  TEXT NOT NULL,
  scope       TEXT NOT NULL,
  reason      TEXT,
  signed_by   TEXT NOT NULL,
  signature   TEXT NOT NULL,
  created_at  TEXT NOT NULL,
  legal_hold  INTEGER NOT NULL DEFAULT 0
);

CREATE INDEX idx_tombstones_entity_uri ON tombstones(entity_uri);

CREATE TABLE tombstone_revocations (
  id           TEXT PRIMARY KEY,
  tombstone_id TEXT NOT NULL REFERENCES tombstones(id),
  reason       TEXT NOT NULL,
  signed_by    TEXT NOT NULL,
  signature    TEXT NOT NULL,
  created_at   TEXT NOT NULL
);
-- Migration 013c: append-only retraction log (time-travel compat — §24.2.1 c.3)
CREATE TABLE fact_retractions (
  id           TEXT PRIMARY KEY,
  fact_id      TEXT NOT NULL REFERENCES facts(id),
  retracted_at TEXT NOT NULL,
  retracted_by TEXT
);

CREATE INDEX idx_fact_retractions_fact_id ON fact_retractions(fact_id);
CREATE INDEX idx_fact_retractions_retracted_at ON fact_retractions(retracted_at);

§23.6 Wire Format​

§23.6.1 Issue a Tombstone​

POST /v1/tombstones
Authorization: Bearer <admin api-key>
Content-Type: application/json

{
  "entity_uri": "user:alice",
  "scope":      "*",
  "reason":     "GDPR Art. 17 erasure request #2026-042",
  "legal_hold": false
}
→ 201 { ...TombstoneRecord with id, signature, created_at populated... }
→ 400 tombstone_invalid_scope
→ 400 tombstone_entity_uri_invalid
→ 403 if caller is not an admin API key
→ 409 tombstone_already_exists

§23.6.2 Check Tombstone Status​

This endpoint MUST NOT be accessible with agent API keys.

The existence of a tombstone for a given entity is itself sensitive information that could reveal the identity of a data-erasure requester.

GET /v1/tombstones/:entity_uri_encoded
Authorization: Bearer <admin api-key>

→ 200 { "tombstoned": true,  "tombstones": [...TombstoneRecord...], "revocations": [...] }
→ 200 { "tombstoned": false, "tombstones": [] }
→ 403 if caller is not an admin API key

§23.6.3 Revoke a Tombstone​

POST /v1/tombstones/:tombstone_id/revoke
Authorization: Bearer <admin api-key>
Content-Type: application/json

{ "reason": "Court order #2026-CR-1234 reinstating data access" }

→ 200 { ...TombstoneRevocationRecord... }
→ 403 if caller is not an admin API key
→ 404 tombstone_not_found
→ 409 tombstone_already_revoked

§23.7 Error Reference​

HTTP
Error code
Condition
400
tombstone_invalid_scope
scope value is not a valid ScopePattern.
400
tombstone_entity_uri_invalid
entity_uri does not conform to §9 namespace format.
400
tombstone_verification_failed
Signature verification failed on inbound federation tombstone.
403
tombstone_access_denied
Agent API key used on tombstone endpoint; admin key required.
404
tombstone_not_found
Tombstone ID not found.
409
tombstone_already_exists
Active tombstone for this entity_uri + scope already exists.
409
tombstone_already_revoked
Tombstone has already been revoked.

Subsection anchors​

Anchors below are provided so docs links to specific subsections always resolve, even when the subsection text lives only in earlier spec drafts.

§23.4.1.3​