Spec 0020 — Tombstones (Deletion Primitive)

Status: Normative (v0.2). Implemented in the reference impl (dreamdb-protocol tombstone / tombstone_index; dreamdb-dataset delete() + read-side suppression filter). Existing v1/v2 flat lists remain readable; new writes use the Timeline-scoped, persistent paged index in §3.6. Conformance at 0009 §8.9 pins both wire forms, and public Dataset tests distinguish range-pruned reads and path-copy writes from their O(total) predecessors. Physical reclamation remains delegated to 0021 (§6). OQ-89 is resolved by §3.6–§5.4; a compressed bitmap representation is no longer required for scalability. 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 legacy TombstoneListObject and the current TombstoneIndexObject — immutable Objects that name anchors to suppress on subsequent reads.
• The Manifest registry entry dreamdb.tombstones — opt-in, pointing to the latest tombstone head for a Space.
• Read-side semantics: how iter and query verbs MUST consult the tombstone set.
• Persistent paging: how a time-window read prunes unrelated pages and a delete path-copies only the changed B+tree path.
• Chain-aware lineage: how a deletion preserves prior flat or foreign-Timeline heads without rewriting them, via parents.
• 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; a tombstone suppresses only views at or after the deletion (§5.1), not time-travel to Manifests published before it. Operators wanting full retroactive erasure must additionally GC old Manifests beyond keep_manifests and re-publish — see §2.1 for the deletion levels and full compliance posture.

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. v0 provides no protocol-level cryptographic erasure. 0019 now specifies encrypted Objects and domain-level key destruction, but no reference writer/reader ships and its immutable per-Object wrapped keys do not provide per-record or per-subject shredding. Deployments requiring selective cryptographic deletion must still handle it at the storage layer or await a separately specified mutable key-index design. Tombstones are the v0 logical-deletion primitive; they do not guarantee byte-level erasure.

2.1 Deletion levels and compliance posture

Immutable, time-travelable history and "the data is gone" are in fundamental tension: for the same data you can keep the history (reproducible, therefore recoverable) or destroy it (erased, therefore not reproducible) — not both. The only mechanism that escapes the dichotomy is cryptographic erasure (keep the Manifests and ciphertext, destroy the key), and that is not a v0 capability. So DreamDB offers deletion at three levels, with different guarantee strengths:

GDPR subject-erasure is a chain, not a primitive: (1) resolve the subject's anchors — identity → anchors via the scalar-id pattern (0001 §5.4, 0000 OQ-88), since a person's data spans many anchors; (2) tombstone them (L1) for immediate suppression; (3) physically erase (L2) or crypto-shred (L3) to make the bytes irrecoverable. A tombstone alone is step (2) only — necessary, far from sufficient.

Bottom line. v0 provides logical deletion as a protocol guarantee and the building blocks for physical erasure (compaction, GC, retention via keep_manifests); it provides no selective protocol-level secure-erasure guarantee. An operator with a hard erasure obligation today must bound history retention — a small keep_manifests / short retention window — so pre-deletion Manifests age out and L2 physically removes erased data within the compliance window, explicitly accepting the loss of time-travel over that data. 0019 domain destruction can retain ciphertext history only by making the whole encryption domain unreadable; it does not solve selective subject erasure (see 0000 OQ-90).

3. TombstoneListObject

The original v1 shape below remains readable with its original Space-wide semantics. New deletions MUST use Timeline-scoped v2 (§3.5); bare anchors from different Timelines are not the same Item. V1 conformance vectors do not change.

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/<base32-multihash> (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.

3.5 Timeline-scoped v2 and coexistence with v1

A v2 list has the same anchors, parents and issued_at representations as v1, with kind: "dreamdb.tombstone-list.v2" and a required timeline field containing the Timeline's 33-byte Multihash. Missing, wrong-type or malformed Timeline values MUST refuse. The list's anchors apply only to that Timeline, across all its modalities. The path stays tombstones/<hash>; timeline is part of the hashed canonical bytes. Entries remain strictly anchor-sorted and unique within each list. No per-entry metadata or reinterpretation of v1 is required.

The discriminator is a semantic version boundary: readers unable to interpret v2 MUST refuse it, not treat it as v1 or an empty set. The v1-only codec remains available and rejects v2; the scope-aware codec reads both. A historical v1 Object always broadcasts across the Space, even if it carries an ignored extension named timeline; new readers MUST NOT narrow that old meaning.

Parents have their own scopes, not their child's scope. Walking a v2 list for Timeline A must still traverse a Timeline B parent: that parent might name a v1 broadcast or another A-scoped ancestor. The effective deletion predicate for (Timeline T, anchor a) is true iff any reachable v1 list contains a, or any reachable v2 list with timeline == T contains a.

Historical Dataset.delete(anchors, reason) implementations published v2 for the Timeline represented by that Dataset handle; current writers publish the paged form in §3.6. All read paths apply the predicate to their binding's Timeline; the current Dataset API refuses schemas spanning multiple Timelines. tombstone_set() reports the effective set for the handle's Timeline, not a Space-wide union. Schema projection does not change a stored tombstone's scope.

When reading or migrating historical flat objects, coalescing MUST key entries by (scope, anchor), with a distinct broadcast scope for v1. It MUST preserve every scope and every prior deletion; it MUST NOT fold broadcasts into one Timeline or foreign entries into the broadcast set. Current writers retain those immutable lists as parents of a §3.6 head rather than publishing new flat deletion entries. Historical Manifests and their tombstones remain untouched.

GC MUST understand all three head discriminators and the page discriminator, follow all parent and page references regardless of scope, and retain every scoped head's Timeline Genesis Object. An unknown kind or unreadable/invalid object means an incomplete closure and MUST abort sweep. Deploy paged-capable readers and collectors before permitting paged writers.

3.6 Timeline-scoped paged index

New deletions MUST publish a dreamdb.tombstone-index.v1 head. It is a distinct wire form, not a reinterpretation of either flat list:

TombstoneIndexObject := {                 // CLOSED
    "kind":      "dreamdb.tombstone-index.v1",
    "timeline":  Multihash,              // exactly 33 bytes
    "root":      TombstonePageRef | null,
    "parents":   [ Multihash, ... ],     // strictly hash-sorted, unique
    "issued_at": u64,
}

TombstonePageRef := {                     // CLOSED
    "min":   u64,
    "max":   u64,
    "count": u64,                        // distinct anchors in subtree
    "level": u8,                         // leaf = 0
    "hash":  Multihash,
}

TombstoneLeafPage := {                    // CLOSED
    "kind":    "dreamdb.tombstone-page.v1",
    "level":   0,
    "entries": [ TombstoneEntry, ... ],
}

TombstoneInternalPage := {                // CLOSED
    "kind":     "dreamdb.tombstone-page.v1",
    "level":    u8,                      // > 0
    "children": [ TombstonePageRef, ... ],
}

All maps are canonical CBOR CLOSED maps. A leaf contains 1..=128 entries, strictly increasing by anchor; an internal page contains 2..=128 children. Children have level exactly one below their parent and strictly non-overlapping, increasing bounds (left.max < right.min). count is non-zero and summaries MUST equal the decoded child's min, max, count, and level; a mismatch is malformed. Every encoded page MUST be at most 65,536 bytes. New paged entries limit reason to 256 UTF-8 bytes. These are protocol limits, not tuning hints.

root: null is a valid empty local index, normally used by a merge head whose parents carry both histories. parents may name any of the three tombstone head forms. Their own Timeline/broadcast scope applies; a child's scope never rewrites a parent's scope. A head without a local root and without parents denotes the empty set.

The index head and every page use the existing tombstones/<base32-multihash> address. A reader determines the form from the required kind discriminator and MUST reject an unknown kind. Sharing the path does not permit trying another decoder after the selected decoder rejects.

3.7 Persistent update and merge

For a prior paged head on the same Timeline, delete() merges the new anchors into the affected leaf and path-copies only that leaf and its ancestors. It preserves the prior head's parents; it MUST NOT retain the superseded local root as another parent. A new anchor may split a page; balanced output MUST respect the §3.6 fanouts and MUST NOT create a one-child internal page.

If the prior head is a flat list or belongs to another Timeline, it becomes a parent and the new Timeline gets a fresh local tree. A multi-writer union emits an empty local head with the two sorted unique heads as parents. All page and head bytes are constructed and validated before the first PUT; every immutable Object is made durable before the Manifest/Ref publication that exposes it.

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": <multihash-of-latest-tombstone-head> }

The entry value is a CBOR map with one required key:

• head: 33-byte Multihash of the latest flat list or paged index head for this Space.

Manifests without dreamdb.tombstones have no tombstones (the set is empty). This is the default; adding tombstones is purely additive.

The head is per-Space, not per-modality. Its graph can contain multiple scopes: historical v1 broadcasts and Timeline-scoped v2 lists. Within the targeted Timeline, deletion still covers all modalities of the Item, not one 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 head, verify its content address, and dispatch on kind.
3. Walk mixed-form parents breadth-first to a finite implementation limit, tracking visited Object hashes to terminate on cycles. Always walk parents, including parents of non-matching Timeline-scoped heads.
4. For a full read, accumulate anchors from v1 lists, matching v2 lists, and matching paged local roots into an in-memory ordered set. For a half-open time window [start,end), descend only page references whose inclusive summary bounds overlap that window. Flat parents necessarily remain whole-Object reads.
5. Cache by both head multihash and the read's Timeline, within the exact Manifest view. A scope-filtered set must never be reused for another Timeline.

The effective set is resolved from the registry of the Manifest being read — the current head for live reads, or the time-traveled-to Manifest for open_at / historical reads. A tombstone therefore suppresses an anchor in the view of every Manifest at or after the deletion, but not when time-traveling to a Manifest published before it: that read faithfully reproduces the earlier Manifest's state, in which the record was still live. This is by design — time-travel is exact reproduction — and is precisely why retroactive erasure cannot be achieved by tombstoning alone (see §2.1). It also reconciles the two framings elsewhere in this spec: a tombstone is retained through compaction (§6.3) so reads of at/after-deletion Manifests stay correct, while pre-deletion Manifests — whose registry never named the tombstone — still surface the record.

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).

5.4 Cost and scale

Against a paged local root containing N distinct anchors, a point/range lookup reads O(log N + P) pages, where P is the number of overlapping leaf pages; an incremental delete writes O(log N + S) pages, where S is the bounded number of pages created by splits. Full-set APIs and non-time-selective query modes still read O(N), as do any legacy flat parents. Parent-DAG cost is additive and bounded separately.

This resolves OQ-89's unbounded per-delete rewrite and makes time-window reads range-prunable without requiring a resident Roaring bitmap. It does not make a full tombstone materialization sublinear and does not itself retire old tombstones. A tombstone is satisfied only once its records are physically removed by compaction (§6) and every Manifest that still exposes them is GC'd beyond keep_manifests; retirement remains future work.

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

Tombstone compaction reuses the publish discipline and safety properties of 0021 (operator-driven; 0021 §2). It is a Track + Manifest advance, not a reindex, and MAY run as a mode of the 0021 compactor in the same operator pass. For each candidate bucket:

1. Fetch the bucket and decode its records.
2. Filter out records whose time_anchor is tombstoned at the compaction head.
3. Re-encode the survivors into a new bucket under the same spatial_index_hash and vector_compressor_hash — dropping records changes neither the SI hyperplanes nor the VC codebook, so the registry (SI/VC) is unchanged. If rerank=true, consolidate the parallel rerank_storage VectorStorage in lockstep (0021 §5 invariant). If no survivors remain for a cell, drop the cell's entry entirely (no replacement bucket).
4. Emit the replacement SpatialBucketEntry (or removal) for the cell.

Publish via 0021 §3.3 verbatim: rebuild the Track Object with the replacements, PUT it, PUT a new Manifest with the registry unchanged (SI/VC unchanged), and CAS-advance the Ref. The 0021 safety properties carry over: read-online during compaction (0021 §4), CAS-conflict handling (0021 §3.4), and MUST-refuse on a SpatialIndex-hash change (0008 §6.5) — a real SI change is a reindex (0008 §6), never a compaction.

This differs from 0021's fragment-consolidation only in the per-bucket transform: 0021 unions F fragments per cell by time_anchor; tombstone compaction drops tombstoned time_anchors. Because 0021's idempotence no-op keys on fragment count (0021 §7), a tombstone-only pass is a distinct trigger (§6.1), not a no-op.

Optionally, the operator emits a parent-only tombstone head that signals "compaction caught up to head N" (operator policy). This marker does not by itself authorize retirement while any retained Manifest still exposes data.

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 tombstone head/page graph. 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:

impl Dataset {
    /// Tombstone the named anchors with a persistent paged update.
    /// Returns the new Manifest hash.
    pub async fn delete(&mut self, anchors: &[u64], reason: Option<&str>)
        -> Result<Multihash, Error>;

    /// Resolve the effective tombstone set at this Dataset's current Manifest.
    pub async fn tombstone_set(&self) -> Result<BTreeSet<u64>, Error>;
}

Read verbs MUST consult tombstone_set automatically; callers do NOT pass it through.

8. Conformance

A conforming implementation:

1. Decodes/encodes all three tombstone forms per §3 with their CLOSED canonical-CBOR, sort, fanout, bound, and summary invariants.
2. Walks mixed-form parents to a finite limit and applies every applicable scope.
3. Filters all read verbs by the effective set.
4. Prunes non-overlapping paged children for a time-window read and path-copies only the affected local tree path for an ordinary delete.
5. Marks the head, every reachable page and parent, and every Timeline named by a scoped head before GC sweep.
6. Returns deterministic results across writers running on different machines.
7. (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. Flat v1/v2 lists remain valid and retain their historical O(total) behavior; paged index writers/readers use the explicit discriminators in §3.6 and MUST NOT reinterpret old bytes. Future revisions may:

• Add a compressed leaf representation if measurement shows page payload, not page fetch count, is the remaining constraint.
• Define a retirement rule so compaction-removed + GC'd tombstones drop out of the live set (§5.4).
• Add sub-anchor field-level tombstones.
• 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.