Re-Minted by Refresh: An Eventual-Consistency Race in Delete-Based Revocation, and the Tombstone Fix

Revocation is usually implemented as deletion: remove the record that grants access, and access ends. This paper exhibits a live failure of that implementation in an eventually consistent key-value store, and a verified fix. In the system studied — a deployed web service in which per-device owner bindings are stored in Cloudflare KV — a binding carries a write-on-read refresh path: owner service updates the record's `lastSeen` field. During a revocation drill, a test device's binding was deleted and the delete verified, yet the device continued to read as owner for over five minutes and continued to answer from the owner's record. The mechanism was not a cache, an attacker, or a failed delete. On lagging edges the store continued to serve the not-yet-propagated binding; owner service there ran the refresh, and the refresh wrote the binding back — re-minting, from a stale copy, the very record revocation had removed. The burn was, in the build report's phrase, chasing its own tail, self-extending for as long as the device kept asking. The fix is tombstone-first revocation: before deleting anything, write a refusal record — a tombstone — for the identity; make every identity-resolution choke point refuse a tombstoned identity even if a copy of its binding is still visible; and clear the tombstone only on the legitimate re-binding path. Under this design revocation converges monotonically: once an edge has seen either the tombstone or the delete, it can never serve or re-mint the binding again. A focused live re-proof passed 18/18 checks, including a ten-poll resurrection drill with no flap-back, and a deterministic harness reproduction passes as part of a 30/30 test section. The propagation bound is stated at the same size as the fix: roughly 1–2 seconds typical, approximately 23 seconds observed worst in the re-proof, approximately 60 seconds quoted as the outer bound — eventual, not guaranteed. Tombstones are a known instrument; the contribution claimed here is narrow and exactly what the record shows: the exhibited failure mode of refresh-re-minting in a live revocation drill, and the verified fix in situ. Keywords: revocation; eventual consistency; tombstones; key-value stores; race conditions