Don't Delete the Row. Delete the Key.

For some industries, the law requires you to keep operational records for years. GDPR Article 17 requires you to delete records on request from EU data subjects. These two rules collide every day in B2B SaaS, and most of the systems I have seen handle the collision badly.

The pattern I settled on is small, not new in cryptography, but rare in product engineering: do not delete the row, delete the key. The chain stays intact. The data becomes unreadable. Both stakeholders are satisfied.

The two requirements

A handful of industries are required to retain operational records for years: finance, healthcare, regulated logistics, anything with a regulator who can demand evidence after the fact. Retention is not a feature. It is a legal obligation. Mutating those records, even to remove them, breaks the guarantee the regulator required.

GDPR Article 17 (and similar laws in other regions) gives the data subject the right to erasure. Article 17(3)(b) exempts erasure when retention is necessary for compliance with a legal obligation, so the regulator wins during the retention window. But the moment that window closes, the subject’s right takes effect. The technical question is: how do you delete a row from a structure that you committed not to mutate?

Most posts on this topic treat the two requirements as opposites. They are not. The solution sits one layer down, where most data engineers do not look.

Why the naive approaches fail

I tried each of these before settling on the current design.

Soft delete. Mark a row deleted_at = NOW() and exclude it from reads. The regulator is satisfied: the bytes are still there. The GDPR auditor is not: the data is still recoverable, still on disk, still subject to subpoena. Soft delete is a UX pattern, not a privacy one.

Hard delete. Run DELETE FROM records WHERE subject_id = $1. GDPR is satisfied. The regulator is not, because hard delete breaks any tamper-evident structure on top of the table: a hash chain, a Merkle tree, an external anchor. The next verification fails.

Just don’t have a tamper-evident structure. You give up the regulator side entirely. That makes the system unable to prove anything about its own history, which is a non-starter for regulated industries.

Per-subject partitioning, then drop the partition. Closer, but you have to know at row-insertion time which subject you will eventually have to delete, and your storage layout has to follow. And if you have any cross-subject structures (a global hash chain, for example), the partition drop still breaks them.

None of these work. They all force you to choose between immutability and erasure.

The pattern

Encrypt every record with a key that lives in a separate store. The tamper-evident structure commits to the ciphertext, not the plaintext. The key store is mutable; the ledger is not. To “erase” a subject’s data, delete the subject’s key.

The encrypted records stay in the ledger forever. The hash chain over the ciphertext still verifies. Reads of those records return random bytes. The data is unreadable, which under most legal opinions is equivalent to deletion. The structural integrity of the chain is untouched.

type Event struct {
    ID          uuid.UUID
    SubjectID   uuid.UUID
    EncPayload  []byte    // AES-256-GCM ciphertext
    Hash        []byte    // sha256(prev.Hash || subject_id || enc_payload)
    PreviousID  uuid.UUID
}

The Hash field is computed over the encrypted payload. Whether or not the key still exists, the chain hashes the same way. Destroying the key leaves every hash unchanged.

The architecture

Three components:

1. The ledger. Append-only table of encrypted events. Hash chain across rows. No row is ever modified. This is the “immutable” half.
2. The key store. A separate table (or service) that maps subject_id -> wrapped_subject_key. The subject key is itself encrypted under a master key kept outside the application database: in a vault, a KMS, an HSM, depending on your threat model. This is the “mutable” half.
3. The encryption boundary. A small library that fetches the subject key, unwraps it, decrypts the payload on read; encrypts and stores on write. Every read and write goes through this library. Nothing else touches plaintext.

Granularity is a design choice. I picked per-subject keys (one key per data subject, used to encrypt every event about them) because the erasure unit is a subject. You could go finer (per-record keys) for stronger separation, but the key store grows linearly with events instead of subjects, and most threat models do not require it.

How “erase” works

1. Receive the erasure request. Verify the subject’s legal retention window has expired in every relevant jurisdiction.
2. Mark the subject’s key as scheduled for shredding in the key store.
3. In a single transaction, delete the wrapped subject key.
4. Invalidate any cached unwrapped keys.
5. Backfill any backups of the key store that still contain the wrapped key. This is the hard one (see below).

After step 3, every future read of any event about that subject returns “key not found” from the encryption boundary, which the application surfaces as “this record has been redacted.” The row count does not change. The hash chain still verifies. The data is, in any operationally meaningful sense, gone.

What this forces you to do

• Key management is now load-bearing. Losing the key store is total data loss, the same way losing the database used to be. You back it up. You replicate it. You audit access to it.
• Backups need a strategy. A backup from before the shredding contains the ciphertext and (if the backup also covers the key store) the key. Restoring that backup un-erases the subject. Your backup retention policy has to be inside the legal retention window, or you need forward-secret backups that drop expired keys.
• Reads need to handle “key missing” gracefully. The application’s read path used to throw on missing rows; now it has to also handle “row present, key gone.” Surface this as a domain-level state (“redacted”) rather than an error.
• Key rotation introduces work. Rotating a subject key means re-encrypting all of that subject’s records. Doable, but heavy. Most systems do not rotate subject keys; they rotate the master key that wraps them.

What doesn’t work

• Backups remain the hardest problem. If your backup retention exceeds the subject’s legal retention window, you have to handle expired keys inside backups. There are a few patterns (forward-secret backups, key-rotation-on-backup, shorter retention for the key store), and none of them are free.
• Some auditors do not accept crypto-shredding. A small number of regulatory regimes want the bytes physically gone, not unreadable. Get a legal opinion in writing before you build this; for most EU and US scenarios the opinion is favorable, but “most” is not “all.”
• Master key loss is total system loss. Every subject key is wrapped under the master key. Lose the master key and every subject’s data is unreadable forever. Plan accordingly: quorum-based recovery, split-knowledge, the usual KMS practices.
• Performance: every read decrypts, every write encrypts. AES-256-GCM is fast (well under a microsecond for typical record sizes on hardware with AES-NI) but the cost is nonzero. Hot subjects need a cached unwrapped key, and the cache invalidation has to be tied to the erasure path so a shredded key does not stay live in memory.
• Ciphertext indistinguishability matters. If your encryption is not IND-CCA2 (use AES-GCM, not raw block ciphers), an attacker with old ciphertexts may still infer structure. This is a “use the right primitive” requirement, not a deep change.

The reframe

Append-only and right-to-erasure are not opposites. They are two different constraints on two different layers: one on storage, one on cryptography. When you put the secret in a layer that is allowed to mutate, you can satisfy both.

Most of the time, the conflict exists because both stakeholders are looking at the same row. Crypto-shredding gives them different rows to look at: the regulator looks at the ledger and its chain, the subject looks at the key store and its absence. The two views never collide.

I spent a week trying to design a soft-delete pattern that would satisfy GDPR. It cannot. The append-only people and the erasure people are both reasoning about the data and not about the secret. The reconciliation is one layer down: separate the bytes from the meaning, and let only the meaning be erased.