GDPR right-to-erasure on an immutable hash chain: the tombstone pattern

TL;DR
An immutable hash chain and GDPR Article 17 appear to conflict: you must delete personal data on request, yet changing any receipt would invalidate every subsequent hash. The tombstone pattern resolves this by replacing only the payload with a minimal marker while keeping the receipt_hash and prev_hash values intact, so the chain’s cryptographic integrity is preserved and auditors can still verify the entire log.

Article 17 of the GDPR gives data subjects the “right to erasure,” also called the right to be forgotten. When a valid request is received, the controller must delete the individual’s personal data without undue delay and confirm the action. The obligation applies to any system that stores data in a way that allows identification, including audit logs that record who performed which action on which tenant record.

Why a naive DELETE breaks verification¶

A typical receipt contains:

receipt_hash = SHA-256(prev_hash || payload || timestamp)
prev_hash pointing to the prior receipt

Running DELETE FROM receipts WHERE subject = '[email protected]' removes the row. The next receipt’s prev_hash now points to a non-existent hash, so any verification routine that walks the chain fails at that point. The entire suffix of the log becomes unverifiable even though nothing else was altered.

The tombstone design¶

Instead of deleting the row, Marturia replaces the payload with a fixed tombstone object and records the time of erasure:

{
  "deleted": true,
  "deleted_at": "2026-05-20T14:31:00Z",
  "original_hash": "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
}

The receipt_hash and prev_hash fields are left exactly as they were. Because the hash that subsequent receipts reference never changes, the chain math continues to hold. The tombstone itself is still signed by the same Ed25519 key that signed the original receipt, proving the erasure was performed by the operator rather than an attacker.

Worked example¶

Consider a four-receipt chain. Receipt #2 contains personal data for [email protected].

After the erasure request is verified, only the payload of R2 is rewritten:

Any verifier that recomputes hashes from R0 onward will find every receipt_hash still matches, including R3’s reference to the (now-tombstoned) R2.

Operational commitment¶

Marturia executes verified erasure requests within 30 calendar days. The request is logged as a new receipt (itself subject to the same rules), and the affected receipt is tombstoned in the same transaction. Both the erasure receipt and the tombstone carry the operator’s signature, giving regulators an auditable trail of the action.

Edge cases¶

Recent receipt: the tombstone is written immediately; the next receipt simply links to the new payload hash (which is unchanged).
Receipt buried 100 000 entries deep: the process is identical. Only one row is updated; verification cost remains O(n) regardless of depth because no hashes are recomputed or re-linked.

Auditor-friendly properties¶

A tombstone is explicit evidence that data was removed at a known time. An auditor can:

Confirm the receipt_hash chain is continuous.
Observe the deleted: true marker and its timestamp.
Verify the operator’s signature on both the tombstone and the erasure-request receipt.

No other receipt was altered, satisfying both the “data deleted” requirement and the “no tampering” requirement.

Industry context¶

Public blockchains such as Bitcoin or Ethereum have no erasure mechanism; once written, data is permanent. Traditional append-only logs that support deletion usually re-hash the suffix, breaking historical signatures. The tombstone pattern is one of the few designs that satisfies both cryptographic immutability and data-protection law without forcing a trade-off.

Related Marturia resources
- /legal/privacy.html
- /learn/lesson_07_threat_models.html

GDPR Article 17 in plain English¶