# Spec 0020 — Tombstones (Deletion Primitive) **Status:** Draft (Phase 5). **Depends on:** `spec/0001`, `spec/0002`, `spec/0006`, `spec/0008`. **Motivation:** DreamDB is structurally append-only. The protocol is content-addressed and immutable, which is exactly why it scales — but it also means that "delete this record" cannot mean "rewrite history." For GDPR Right-to-Erasure, individual record retraction, and any other workflow that must *hide* prior writes without rewriting them, the protocol provides a tombstone primitive: an immutable Object that names anchors which subsequent reads MUST skip. Compaction of the underlying bytes is a separate operator-driven step (see §6). --- ## 1. Purpose DreamDB's append-only data plane means every record ever written is, by construction, recoverable from any Manifest that referenced it. This is correct from a content-addressing perspective (the bytes are still in S3) and load-bearing for time-travel queries. It is also, on its own, a compliance hazard. This spec defines: - The **TombstoneListObject** — an immutable Object that lists anchors to suppress on subsequent reads. - The **Manifest registry entry** `dreamdb.tombstones` — opt-in, pointing to the latest TombstoneListObject for a Space. - **Read-side semantics**: how iter and query verbs MUST consult the tombstone set. - **Chain-aware lineage**: how a deletion extends prior tombstones without rewriting them, via `parents: Vec`. - **Compaction**: how the underlying bucket bytes are eventually reclaimed. What this spec does NOT define: - **Authentication / authorization**. Who is allowed to publish a tombstone is operator-policy. - **Per-record (sub-anchor) deletion**. Tombstones target Item-level anchors; a single anchor's records across all modalities are suppressed together. Field-level redaction is out of scope. - **Retroactive deletion of *manifests***. Old Manifests that referenced the now-tombstoned records still exist and remain time-travel-queryable; the tombstone filter applies on the current path. Operators wanting full retroactive erasure must additionally GC old Manifests beyond `keep_manifests` and re-publish. ## 2. Threat model Tombstones are **suppress on the read path**, not "secure erase." A determined attacker with backend credentials can still find the underlying bytes by walking the bucket directly. For environments requiring cryptographic deletion, use spec/0019 encryption with per-record keys and shred the keys at delete time. Tombstones complement, not replace, that mechanism. ## 3. TombstoneListObject ### 3.1 Structure ``` TombstoneListObject := { "kind": "dreamdb.tombstone-list.v1", // string, exact "anchors": [ TombstoneEntry, ... ], // array; sorted ascending by anchor value "parents": [ Multihash, ... ], // array of prior TombstoneListObject hashes "issued_at": u64, // ms since epoch; MAY be 0 (unsigned) } TombstoneEntry := { "anchor": u64, // Item-level TimeAnchor (same key as SpatialBucket records) "deleted_at": u64, // ms since epoch "reason": ?Text, // optional short tag (operator-defined; e.g. "gdpr", "test", "abuse") } ``` The `anchor` field is the 64-bit TimeAnchor of the Item to suppress. This is the same `time_anchor` used in `SpatialBucket` records and across modality joins. A single anchor suppresses every record bound to it across every Track / modality — anchor-level (not field-level) is the right granularity for GDPR-style deletion. The CBOR encoding is canonical per spec/0002 §4.1 (sorted map keys, definite-length, smallest encoding). The Object's address is the BLAKE3-256 multihash of its canonical CBOR bytes. Path: `tombstones/` (new top-level prefix; see spec/0002 §7.5 path table). ### 3.2 Anchor sort invariant `anchors` MUST be sorted ascending by raw u64 anchor value. This makes set-membership checks O(log N) via binary search and gives content-addressed canonicalization (the same set of anchors → the same bytes → the same hash). Decoders MUST reject TombstoneListObjects with unsorted or duplicate anchors as malformed. ### 3.3 Parents `parents` references prior TombstoneListObjects whose anchors are also suppressed. The effective tombstone set is the transitive union of `anchors` over all ancestors. The list MAY have multiple parents to support multi-writer merges (cf. SpatialIndex multi-parent merges from spec/0008). Cycles are forbidden: parents MUST form a DAG. A reader resolving the effective set walks parents breadth-first to a configurable depth limit (RECOMMENDED 100). If the limit is reached before the chain terminates, the reader MUST abort with a clear error — partial tombstone application is unsafe. The list MAY be empty (initial deletion in a Space). ### 3.4 Issued-at The `issued_at` field is operator metadata only. It is NEVER consulted for correctness. Readers MAY use it to surface "tombstone N records since T" observability. Two TombstoneListObjects with identical `anchors` and `parents` but different `issued_at` are distinct Objects (different content → different hash). Setting `issued_at: 0` is permitted and discouraged outside of test fixtures. ## 4. Manifest registry entry A Space opts in to tombstones by adding a `dreamdb.tombstones` entry to its Manifest's `registry` map: ``` manifest.registry["dreamdb.tombstones"] = { "head": } ``` The entry value is a CBOR map with one required key: - `head`: 33-byte Multihash of the latest TombstoneListObject for this Space. Manifests without `dreamdb.tombstones` have no tombstones (the set is empty). This is the default; adding tombstones is purely additive. The entry is per-Space, not per-modality. Tombstones target Item anchors; a single tombstone suppresses every record bound to that anchor across every modality. This matches the GDPR semantics: erasing a person erases their data, not a specific column. ## 5. Read-side semantics Every read verb — `iter`, `iter_stream`, `query`, `time-range`, `nearest` — MUST consult the effective tombstone set before yielding records. ### 5.1 Resolution On first read against a Manifest: 1. Look up `registry["dreamdb.tombstones"].head`. If absent: effective set is empty; proceed. 2. Fetch the named TombstoneListObject. 3. Walk `parents` breadth-first to a depth limit (RECOMMENDED 100). 4. Accumulate the union of `anchors` arrays into an in-memory `BTreeSet`. 5. Cache the set keyed by the head multihash (it is content-addressed, hence safe to memoize indefinitely for that head). ### 5.2 Filtering For each candidate record (`anchor`, `record_bytes`): ``` if tombstone_set.contains(record.anchor) { skip; } else { yield (anchor, record_bytes); } ``` Implementations MAY apply the filter at the bucket-decode boundary (records-per-bucket already requires per-record work; the additional cost is one BTreeSet hit per record). ### 5.3 Counting Verbs that report counts (e.g., `Dataset::count_records`) MUST exclude tombstoned records from the count. The pre-tombstone count is recoverable by reading the Track Object's `object_index` total and subtracting `tombstone_set.len()` (bounded above; exact only if every anchor exists in the dataset). ## 6. Compaction A tombstone is a hint to the read path; the underlying record bytes still occupy storage. Operator-driven compaction reclaims the bytes. ### 6.1 Compaction trigger When the ratio of tombstoned records to total records in a bucket exceeds a threshold (e.g., 10%), the bucket is a compaction candidate. ### 6.2 Compaction process A future `dreamdb-cli compact-tombstones --bucket ` verb (deferred to spec/0020.1): 1. Fetches the bucket. 2. Decodes records. 3. Filters out tombstoned anchors. 4. If <50% of records remain: marks the bucket for deletion and re-distributes survivors to adjacent buckets via the spec/0004 dispatch path. 5. Otherwise: writes a new compact bucket without the tombstoned records. 6. Publishes a new SpatialIndex with `parents: [old_si_hash]`. 7. Optionally: emits a new TombstoneListObject with `parents: [old_head]` and empty `anchors`, signaling "compaction caught up to head N." This is operator-policy. Once a bucket's tombstoned records have been compacted out AND no Manifest retained by `keep_manifests` references the old bucket, `dreamdb-cli gc` reclaims the old bucket's bytes. ### 6.3 Tombstones survive compaction Compaction does NOT remove entries from the TombstoneListObject chain. Even after the underlying records are reclaimed, the tombstone entries remain — necessary for time-travel correctness against older Manifests that still reference the original buckets. A bounded-history variant (truncating very old tombstone entries after, say, `keep_manifests` × `bucket_compaction_interval`) is deferred to a future revision. ## 7. SDK API (informative) Reference implementations SHOULD expose: ```rust impl Dataset { /// Tombstone the named anchors. Single round-trip. /// Returns the new Manifest hash. pub async fn delete(&mut self, anchors: &[u64], reason: Option<&str>) -> Result; /// Resolve the effective tombstone set at this Dataset's current Manifest. pub async fn tombstone_set(&self) -> Result, Error>; } ``` Read verbs MUST consult `tombstone_set` automatically; callers do NOT pass it through. ## 8. Conformance A conforming implementation: 1. Decodes/encodes TombstoneListObject per §3 with full canonical-CBOR sort invariants. 2. Walks `parents` to a depth limit, accumulates the set, caches by head. 3. Filters all read verbs by the effective set. 4. Returns deterministic results across writers running on different machines. 5. (Optional) Supports `dreamdb-cli compact-tombstones`; absence is permitted in v0 implementations. A conforming reader that encounters a `dreamdb.tombstones` registry entry but does NOT know how to walk it MUST refuse to serve reads (fail-closed): silently ignoring the entry would surface deleted records to callers, violating the contract. ## 9. Versioning This spec is v0. Future revisions may: - Define paged TombstoneListObjects (B-tree pages for >100K anchors). - Add sub-anchor field-level tombstones. - Define merge semantics for multi-writer tombstones (analogous to spec/0008 SpatialIndex merge rules). - Add `compatible_with_manifest_versions` to constrain when a tombstone applies (for time-travel-aware deletion). All extensions MUST preserve §3's canonical CBOR and content-addressing.