# In what scenarios must an instance refuse to emit a cryptographic-erasure proof when downstream replica invalidation is incomplete **Date of Record:** 2026 November 15 **Scope:** Applies to forget-memory compliance systems that satisfy erasure obligations by destroying per-subject key material (crypto-shredding) and then asserting, via a signed proof object, that the subject's data is unrecoverable across all replicas. Does not apply to physical media destruction, nor to systems where the proof asserts only ciphertext deletion at the primary and makes no claim about replicas. ## Core Distinction A cryptographic-erasure proof is a *compliance attestation*, not an *operation log*. The distinction that matters operationally is between **key destruction** (a local, atomic, verifiable action on the KMS) and **recoverability** (a global property over every copy of the ciphertext and every copy of the key). Destroying the key at the primary KMS makes the primary's ciphertext unrecoverable *by that KMS*. It says nothing about: 1. Replicas holding an independently wrapped copy of the same data key (cross-region KMS replicas, DR escrow, offline tape with a wrapped DEK). 2. Derived caches and materialized views that hold *plaintext* (search indices, feature stores, analytics snapshots) and never needed the key again. 3. In-flight re-encryption or backup jobs that captured the DEK before destruction and will re-wrap it after. The non-obvious invariant: **the proof's truth value is the conjunction over all replicas of "unrecoverable," and this conjunction is not monotonic in time.** A replica that was invalidated at T1 can become recoverable again at T2 if a lagging replication stream replays a pre-destruction key-wrap. Therefore a proof emitted at T1 can be *retroactively falsified* by normal system operation. This is the boundary failure: teams treat the proof as a point-in-time fact, but the compliance claim is a durable assertion that must remain true for the retention horizon of the audit. ## What Was Observed In a multi-region deployment, subject-erasure requests destroyed the DEK at the primary KMS and emitted a signed proof within ~200 ms. Downstream invalidation was issued as asynchronous fan-out to three replica regions plus two derived stores. Two failure modes were observed: - **Replication replay resurrection.** A replica region's key-wrap log had a replication lag of 4–11 seconds. The invalidation tombstone was applied, but a subsequently replayed `WrapKey` event from before the destruction re-created a wrapped DEK in that region's KMS. The subject's ciphertext there became decryptable again for a window, and the emitted proof was false for that window — after it had already been signed and shipped to the auditor. - **Derived-store plaintext.** A search index held tokenized plaintext derived from the record. Key destruction had zero effect on it; the index was only invalidated once the async fan-out reached it. The proof claimed global unrecoverability while a plaintext-derived index remained queryable for minutes. Both cases shared a signature: the proof was emitted on the *success of the local destruction call*, not on the *quiescence of the invalidation fan-out*. ## Condition of Validity A cryptographic-erasure proof is valid if and only if, at emission time and for the entire audit retention horizon, all of the following hold: 1. Every replica that can hold a wrapped DEK has acknowledged the destruction **and** has fenced its key-wrap ingestion against replay of pre-destruction events (a monotonic tombstone with a sequence number, not a best-effort delete). 2. Every derived store that can hold plaintext or plaintext-equivalent tokens has acknowledged purge, with a positive count, not a timeout. 3. No in-flight job holds the DEK. This requires a barrier: either a lease/quiescence check on all re-encryption and backup workers, or proof that no such worker started before destruction and none can start after. 4. The proof carries the *set of replica acknowledgements* and the *fencing sequence numbers*, so a later auditor can verify non-resurrection rather than trust a boolean. If any of (1)–(3) is unverified, the correct behavior is to **withhold the proof** and emit a pending-erasure record instead. Emitting the proof is a one-way door: retracting a signed compliance attestation is materially worse than a delayed one. ## Decision Boundary The decision is not "did key destruction succeed?" but "can I prove no copy is recoverable now and cannot become recoverable later?" The boundary sits at **fan-out quiescence with fencing**, and it is asymmetric: - **Emit proof** only when all replica acks are positive, all derived-store purges return counts, the in-flight barrier is confirmed, and each replica's fencing sequence number is ≥ the destruction sequence number. - **Withhold and mark pending** when any ack is missing, any purge timed out, any worker lease is unexpired, or any replica's fencing sequence is behind. A timeout is *not* an ack; a `202 Accepted` is *not* an ack. - **Never** emit a proof whose validity depends on a future event ("replication will catch up"). That converts a compliance attestation into a bet. The trap is treating the async fan-out as best-effort telemetry. It is part of the proof's precondition. The proof is a *conjunction*, and a conjunction with an unknown term is unknown, not true. ## Operational Effect Withholding the proof until quiescence changed the system's failure surface from "silently false attestations discovered at audit" to "backlogged pending-erasure queue visible in dashboards." Latency to proof rose from ~200 ms to a p99 of ~14 s (dominated by replica lag), which was acceptable because the compliance SLA was measured in hours, not milliseconds. The pending queue became the primary operational signal: a growing queue means a replica is lagging or a derived store is failing to purge, both of which are exactly the conditions under which a proof would have been false. Resurrection windows were eliminated by monotonic fencing tombstones, verified by replaying pre-destruction key-wrap logs against the fenced replicas and confirming zero successful re-wraps. ```python class ErasureProofWithheld(RuntimeError): """Raised when a cryptographic-erasure proof cannot be truthfully emitted.""" pass def emit_erasure_proof( subject_id: str, destruction_seq: int, replica_acks: dict[str, int], # region -> fencing seq acknowledged derived_purge_counts: dict[str, int], active_worker_leases: int, ) -> dict: # A proof is a conjunction over all replicas and derived stores. # Any unknown term makes the conjunction unknown, not true. for region, fenced_seq in replica_acks.items(): if fenced_seq < destruction_seq: raise ErasureProofWithheld( f"replica {region} fencing seq {fenced_seq} < destruction seq " f"{destruction_seq}; pre-destruction key-wrap replay possible" ) for store, count in derived_purge_counts.items(): if count < 0: raise ErasureProofWithheld( f"derived store {store} purge unconfirmed (timeout, not ack)" ) if active_worker_leases > 0: raise ErasureProofWithheld( f"{active_worker_leases} worker lease(s) may hold the DEK; " "in-flight re-encryption/backup barrier not quiescent" ) return { "subject": subject_id, "destruction_seq": destruction_seq, "replica_fencing": replica_acks, "derived_purges": derived_purge_counts, "attestation": "unrecoverable_all_replicas_fenced", } ```