HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Algorithm: The Double-Spend Ledger

5 min read

A single-use token is worthless if you can use it twice. But "remember every token ever spent" is both a metadata store and an unbounded database — two things this system refuses to build. The double-spend ledger is the smallest possible memory that closes the gap, and its whole subtlety is in one number: how long to remember.

This is the state-keeping counterpart to The Admission Token. It is short, because the mechanism is short; the interesting part is why the timing works.

1. The requirement

An admission token is a (nonce, token) pair the relay accepts once. Nothing about the cryptography stops a client from attaching the same pair to a thousand envelopes — the token verifies fine each time. Only memory stops replay: the relay must record that a nonce has been spent and reject its reappearance. That memory is the double-spend ledger.

Two constraints make it delicate:

  • It must forget. A ledger that remembers every token forever grows without bound and becomes exactly the kind of durable, queryable state the ephemeral relay exists to avoid. It has to expire entries.
  • It must not forget too soon. If the ledger forgets a nonce while that token is still valid, the token becomes spendable again — a double-spend hole. Forgetting is only safe once a token can no longer be legitimately presented.

The entire design is threading between those two: forget, but never a second before it is safe.

2. The mechanism: one atomic mark

The check is as small as it can be. The ledger is a key-value store (Redis) and each spend is a single atomic operation:

SETNX  tokens:redeemed:<key_id>:<nonce>   with a TTL

SETNX — "set if not exists" — is the whole trick. It atomically does two things: if the key is absent, it writes it and reports "fresh"; if the key is already there, it writes nothing and reports "already spent." One round trip, no read-then-write race, no way for two simultaneous spends of the same nonce to both win. The relay accepts the token if and only if SETNX reports "fresh." There is nothing else to it — no per-user record, no recipient, no content. The ledger key is (key_id, nonce) and nothing more, so the one piece of state the anonymous system keeps is itself anonymous: a pile of "this serial number is used" markers with no one's name on them.

That last claim leans on something outside this article, and it is worth being explicit about the dependency. key_id is anonymous only because the live key set is forced to be short, public, and identical for every client. With a per-user issuing key, this same table would be a per-user spend log — the ledger would quietly become the deanonymising artefact the rest of the design works to avoid. The checks that prevent it live in The Admission Token §5, and they are load-bearing here as much as at the mint.

Rollback on later rejection. Admission runs more checks after the spend (notably the certificate-revocation check). If one of those rejects the envelope, the relay rolls back the spend — deletes the just-written marker — so a message dropped for an unrelated reason does not burn an otherwise-good token. You only lose the token if the token itself was the problem.

3. The one number that matters: how long to remember

Now the crux. What TTL does the ledger entry get? Too short and you reopen the double-spend hole; too long and you keep useless state (and, worse, a longer-lived database). The answer falls out of three durations that have to line up:

  • The key epoch — 24 hours. The relay's checking key s rotates daily. A token minted under yesterday's key is checked against yesterday's key.
  • The grace window — 6 hours. A token minted just before a key rotates should still work for a while afterward (clock skew, a client that batched tokens and is spending them a little late). So a key stays honored for redemption for 6 hours past its epoch. Present a token older than that and the relay refuses it outright — this "key-redemption window" drains hoarded or lapsed tokens and is a spam-hygiene lever in its own right.
  • The ledger TTL — 30 hours. And here is the invariant: 24 + 6 = 30. A nonce is remembered as spent for exactly as long as that token could possibly still be validly presented — the full epoch plus the full grace. Not a minute less (or a forgotten nonce could be re-spent inside its grace window), and not much more (or the ledger hoards dead state).

Put the three together and the guarantee is airtight: at every instant, a token is either (a) still redeemable — and then its nonce is still in the ledger — or (b) past its 30-hour horizon — and then it is refused by the key-redemption window before the ledger is even consulted. There is no window in which a token is simultaneously acceptable and forgotten. The double-spend gap is closed not by remembering forever, but by remembering for precisely the interval a token can matter, and refusing anything older on a different check.

The image is a nightclub hand-stamp tuned to fade exactly at closing time. While the club is open your stamp is visible and you can't get a second one; the moment the stamp could no longer be honored anyway, it fades. The bouncer never has to remember last week's stamps, because last week's stamps wouldn't be honored regardless.

4. Why this is the whole ledger

It is worth appreciating how little state this is. The anonymous-admission system — sender hidden, unlinkable, no mailbox — keeps, as its only durable memory, a set of (key_id, nonce) markers that each evaporate in 30 hours and name no one. There is no "spends per user" table (there is no user), no "who sent to whom" (the ledger doesn't see recipients), nothing to mine. The one concession to state that stopping replay forces on us is a self-erasing, anonymous set of serial numbers. That is about as close to "stateless" as a system that enforces single-use can get.

References & further reading