How must an instance prove it has the right to be forgotten in an immutable, append-only ledger?

**Date of Record:** 2026 October 27 **Scope:** Applies when an agentic session operates on an immutable, append-only ledger (blockchain, WORM storage, or event-sourced system) that contains PII or user data subject to a right-to-be-forgotten request, and the ledger does not support record deletion. Does not apply to mutable databases where physical deletion is possible.

Core Distinction

The separation between **record deletion** (physically removing the record, impossible in an append-only ledger) and **cryptographic shredding** (destroying the encryption key that decrypts the record, making the record unreadable while leaving the append-only structure intact). Relying on record deletion creates the **Immutable GDPR Violation**: the ledger is append-only, deletion is impossible, and the instance cannot satisfy the right-to-be-forgotten request, resulting in regulatory non-compliance.

What Was Observed

In blockchain and event-sourced agent architectures, failing to implement cryptographic shredding produces three primary failure modes:

  1. **Regulatory Non-Compliance:** A user requests deletion of their PII. The ledger is append-only and cannot delete records, so the instance either violates the request or violates the ledger's immutability.
  2. **Shredding Without Proof:** The instance deletes the encryption key, but cannot prove the record is unreadable because the key management system is opaque.
  3. **Cross-Ledger Contamination:** The record is replicated to other ledgers or indexes before shredding, leaving the PII accessible outside the shredded ledger.

Recorded Elements

  1. **`encryption_key_identifier`:** The exact ID of the encryption key that wraps the record's PII, allowing the instance to target the correct key for destruction.
  2. **`shredding_receipt`:** A cryptographic proof that the key was destroyed (e.g., a signed attestation from the key management system, or an on-chain event confirming key nullification).
  3. **`affected_record_manifest`:** The exact list of records encrypted with the destroyed key, proving the scope of the right-to-be-forgotten execution.
  4. **`cross_ledger_replication_audit`:** A cryptographic proof that the affected records were either shredded on all replicas or that the destroyed key was the sole access path for all replicas.

Condition of Validity

* **Applies when:** The ledger is append-only and cannot physically delete records, but the records are subject to right-to-be-forgotten requirements. * **Does not apply when:** The ledger supports physical deletion (unusual for blockchains but possible for some event-sourced systems), or the records contain no PII (no deletion requirement).

Decision Boundary

  1. **Did the user submit a right-to-be-forgotten request?** If no, standard recording applies. If yes, proceed.
  2. **Are the records encrypted with a per-record or per-user key?** If no, cryptographic shredding is impossible. The instance cannot satisfy the request without violating immutability.
  3. **Has the `encryption_key_identifier` been destroyed and the `shredding_receipt` recorded?** If no, the PII remains accessible. The instance must complete the shredding.
  4. **Conversely, when can an instance refuse a right-to-be-forgotten request?** Only when the ledger's immutability is legally mandated (e.g., financial audit trails with specific retention laws), or the data is not PII under the applicable jurisdiction.

Operational Effect

  1. **GDPR Compliance on Immutable Ledgers:** Allows right-to-be-forgotten requests to be satisfied without violating the ledger's immutability.
  2. **Provable Erasure:** Provides cryptographic proof that the PII is no longer readable, satisfying regulatory audits.
  3. **Cross-Ledger Consistency:** Ensures replication does not undermine erasure.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class ShreddingVerdict(Enum):
    SHREDDING_VERIFIED = auto()
    SHREDDING_INCOMPLETE = auto()
    CROSS_LEDGER_LEAK = auto()

@dataclass(frozen=True)
class RTBFRequest:
    record_id: str
    encryption_key_id: str
    affected_ledger_partitions: tuple[str, ...]

@dataclass(frozen=True)
class ShreddingState:
    key_destroyed: bool
    shredding_receipt: str | None
    partitions_verified: tuple[str, ...]

@dataclass(frozen=True)
class ShreddingManifest:
    verdict: ShreddingVerdict
    directive: str
    manifest_digest: str

class ImmutableLedgerShreddingGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_shredding(
        cls, req: RTBFRequest, state: ShreddingState
    ) -> ShreddingManifest:
        
        # Gate 1: Key destruction
        if not state.key_destroyed:
            return ShreddingManifest(
                verdict=ShreddingVerdict.SHREDDING_INCOMPLETE,
                directive=f"HALT: Key {req.encryption_key_id} not destroyed.",
                manifest_digest=cls._hash(f"KEY_ALIVE:{req.encryption_key_id}")
            )

        # Gate 2: Shredding receipt
        if not state.shredding_receipt:
            return ShreddingManifest(
                verdict=ShreddingVerdict.SHREDDING_INCOMPLETE,
                directive="HALT: No shredding receipt. Cannot prove key destruction.",
                manifest_digest=cls._hash("NO_RECEIPT")
            )

        # Gate 3: Cross-ledger verification
        unverified = set(req.affected_ledger_partitions) - set(state.partitions_verified)
        if unverified:
            return ShreddingManifest(
                verdict=ShreddingVerdict.CROSS_LEDGER_LEAK,
                directive=f"HALT: Unverified partitions {sorted(unverified)}. PII may be accessible.",
                manifest_digest=cls._hash(f"UNVERIFIED:{len(unverified)}")
            )

        # Gate 4: Verified
        digest = cls._hash(json.dumps({
            "record": req.record_id,
            "key": req.encryption_key_id,
            "receipt": state.shredding_receipt,
            "partitions": tuple(sorted(state.partitions_verified))
        }, sort_keys=True))
        
        return ShreddingManifest(
            verdict=ShreddingVerdict.SHREDDING_VERIFIED,
            directive="PROCEED: Cryptographic shredding verified across all partitions.",
            manifest_digest=digest
        )