HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Rate-Limiting a Stranger: Anonymous Admission

7 min read

We spent five articles making the sender invisible to the relay. Now the bill comes due: if the relay cannot see who is sending, how can it stop one person from flooding the whole network? You cannot throttle a user you refuse to identify — unless you change what "throttle" means.

This is the paradox at the center of the relay, and its resolution is one of the prettiest ideas in the system.

1. The paradox

Rate limiting is normally identity-based: count requests per user, per IP, per account, and cut off whoever exceeds a threshold. Every one of those hooks is something we deliberately removed. The relay does not know the account (sealed sender), cannot link a sender's messages across conversations (unlinkability), and keeps no durable record to tally against (ephemeral delivery). An anonymous message system with no admission control is a spam cannon — free, untraceable bulk messaging is the abuser's dream. So we need to limit sending without the one thing rate limiting normally needs: knowing who is sending.

The resolution is to separate the two things "rate limiting" secretly bundles together: metering (deciding how much a user is allowed to send) and enforcement (checking, at send time, that this particular message is within the allowance). We do the metering where the user is identified, and the enforcement where they are not — and connect the two with a token that carries the permission but not the identity.

2. Pay upstream, spend downstream

The design is exactly a transit token system. To ride the subway you buy a roll of tokens at the booth with your card — fully identified, and the booth enforces "you may buy N per hour." Then you drop an anonymous token in the turnstile, which counts tokens and lets you through without any idea who you are. The token is a bearer object: it carries the right to one ride, unlinkable to the purchase that created it.

Mapped onto the relay:

  • Issuance (the booth): credential-svc. A logged-in, in-good-standing user asks for a batch of admission tokens over an authenticated session. The service enforces the rate policy here, where identity exists: a per-user, per-class, hourly budget. This is the only sender-visible rate lever in the whole system, and it is enough, because it caps how many tokens a user can ever obtain.
  • Enforcement (the turnstile): the relay. Every envelope must carry one single-use token, which the relay redeems at ingress. The relay learns exactly one bit of economic truth — "a valid token of this class was spent" — and nothing about who spent it.

The metering happens where identity is known; the enforcement happens where it isn't; and a banned or abusive account is cut off at the booth — it simply stops being able to mint fresh tokens — rather than being recognized-and-blocked at the turnstile. Revocation moves upstream with the metering.

3. The token that carries permission but not identity

For this to actually protect privacy, the token must be unlinkable to its issuance: the relay, even colluding with credential-svc, must not be able to match "token spent at the turnstile" back to "token #N minted for Alice at the booth." Otherwise the whole exercise just launders the identity through a coupon.

The tokens are built on the lattice OPRF — the same post-quantum oblivious PRF the discovery series builds from scratch. The issuance is a blind evaluation: credential-svc computes the token's value without ever seeing the final token, because the client hides its input on the way in and unwraps the result on the way out. (Classical anonymous-token systems like Privacy Pass have the same shape; ours is the post-quantum, lattice version. The full issue/redeem mechanics are The Admission Token.)

How strong is that hiding? This is worth being exact about, because two similar-sounding guarantees differ here, and the difference is a genuinely useful thing to have straight.

What leaves the device is a lattice encryption of the client's nonce. Recovering the nonce from it means solving Ring-LWE, a problem believed hard for classical and quantum computers. So the unlinkability is computational: it rests on a hardness assumption. An adversary with unbounded computing power who kept the issuance transcript could, in principle, break the encryption and match a redeemed token to its mint.

Compare a classical blinded signature, where the client multiplies its value by a random blinding factor. There the blinding is a genuine one-time pad: the issuer's transcript is statistically independent of the redeemed token — no amount of computation recovers the link, because the information simply is not there. That property is sometimes called everlasting anonymity, and it is strictly stronger than what we have.

We gave it up on purpose, and the trade runs both ways. The classical scheme's unlinkability was unconditional, but its unforgeability rested on a discrete logarithm — which a quantum computer breaks. The lattice scheme reverses that: unforgeability now rests on a lattice problem no known quantum algorithm solves, and unlinkability became computational. The project chose to leave no discrete log anywhere in the stack, so it took the lattice side of that trade.

The honest position, then: a quantum computer cannot link a token to its issuance; an adversary with unlimited computation could, if it kept the transcript. Those are different threats, and the system is built against the first.

One more deliberate placement: credential-svc never sees a redemption. The relay does hold a copy of the checking key — it has to, since verifying a token means recomputing F_s(nonce) itself — so the separation here is not that the two parties hold different secrets. It is that they see different halves of the token's life: the booth knows who got tokens and never watches them spent; the turnstile watches them spent and never learns who was issued what. They are joined only by an object neither can link back to its issuance. Neither alone — and, short of breaking Ring-LWE, not even both together — can rebuild "who sent what."

The token does carry one field the relay reads in the clear: a key_id naming which live issuing key minted it. Under honest operation that is about two bits, but the issuer picks it, so it is exactly the sort of field that could be turned into a per-user tag. It is not left to good intentions — The Admission Token §5 is entirely about the three checks that keep it meaningless.

4. Two classes, so receipts can't ring your phone

Not all sends are equal, and a single token type creates an abuse channel. A delivery/read receipt is tiny and constant; a message can wake a phone. If both cost the same token, an abuser could mint cheap "receipt" allowance and use it to smuggle real, phone-waking messages — draining victims' wake budgets.

So there are two cryptographically distinct token classes, bound to what they may carry:

  • a send token — the tighter budget, required for anything that can wake or deliver real content,
  • an ack token — cheap and plentiful, but cryptographically restricted to small, non-waking receipt envelopes. Present an ack token with a message-class envelope and the relay rejects it before it spends.

The classes are bound into the token itself, not just checked by policy, so the restriction is enforced by mathematics rather than by a rule someone could forget. Receipts stay cheap; they just cannot masquerade as messages.

5. Spending it exactly once

A bearer token is only as good as the guarantee that it is spent once. Nothing stops a client from replaying the same token on a thousand envelopes unless the relay remembers what it has seen. It does, with a minimal double-spend ledger — one atomic "mark this token spent, fail if already marked" per redemption — and a carefully chosen retention window that closes the reuse gap without keeping anything a moment longer than necessary. Because that ledger is the one place the anonymous system keeps state, its design is delicate enough to be its own article: The Double-Spend Ledger.

6. The honest residual

Anonymous admission stops floods while keeping the sender invisible. What each party still sees:

  • credential-svc knows your mint volume — how many tokens you asked for — because it enforces the budget. It does not see recipients, content, or redemptions; its ledger keys on a hashed handle, and the budget is the deliberately-visible lever.
  • The relay sees spends per class — an anonymous count of "a send token was used," "an ack token was used" — with no spender attached and no link to issuance.

So the residual is an aggregate: the system knows roughly how much a hashed handle is allowed to send (at the booth) and how many anonymous tokens of each class are being spent (at the turnstile), and the blind issuance keeps those two views from being joined. That is the price of stopping abuse in a system that refuses to know its users — and it is a genuinely small price for resolving what looked like a contradiction.

References & further reading

  • The Lattice OPRF — the post-quantum oblivious PRF the token is built on, from scratch.
  • Privacy Pass, RFC 9576 and the original design — the classical anonymous-token system this mirrors.
  • "Everlasting anonymity" tokens, ePrint 2025/1030 — the other side of the trade above: keeps unconditional unlinkability and accepts classically-secure unforgeability. Worth reading to see the choice laid out explicitly.
  • The Admission Token and The Double-Spend Ledger — the two deep dives.