---
id: 49
title: "Verify by computation, not lookup; store revocations, not issuances"
status: current
date: 2026-07-07
authors:
  - "Theo Zourzouvillys"
tags: [security, architecture, auth, scalability]
summary: "Verification should be a computation, not a query: HMACs, signatures, hashes, and pass-by-value claims let any node verify locally. When revocation is rarer than issuance, invert the state — keep the few revocations for the lifetime of what they revoke, not a row per grant."
supersedes: null
superseded_by: null
aliases: []
references:
  - id: fu-webauth
    title: "Dos and Don'ts of Client Authentication on the Web (USENIX Security 2001)"
    url: https://pdos.csail.mit.edu/papers/webauth:sec10.pdf
    abstract: "Fu, Sit, Smith & Feamster's classic study of web authentication schemes. Its constructive core is the stateless authenticator: HMAC over the data plus an expiry, verifiable by any server holding the key — the pattern under signed cookies, links, and tokens ever since."
  - id: macaroons
    title: "Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud (NDSS 2014)"
    url: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41892.pdf
    abstract: "Google's design for bearer credentials built from chained HMACs. A holder can attenuate a macaroon — add caveats narrowing where, when, and how it may be used — entirely offline, showing how far pass-by-value authority can go without a database."
  - id: crlite
    title: "CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers (IEEE S&P 2017)"
    url: https://cbw.sh/static/pdf/larisch-oakland17.pdf
    abstract: "Compresses the entire web PKI's revocation state into a few megabytes of layered Bloom filters pushed to every browser, making revocation checking a fast local computation. The existence proof that even internet-scale revocation fits in a distributable set."
  - id: le-ocsp
    title: "Let's Encrypt: Ending OCSP Support in 2025"
    url: https://letsencrypt.org/2024/12/05/ending-ocsp/
    abstract: "The largest CA's announcement that it is shutting down OCSP — the design where every verification is a live query to the issuer — in favour of CRLs, citing privacy and reliability. The web PKI's two-decade verdict on lookup-per-verification."
---

## TL;DR

Where you can, make validity checkable from the value itself — no store on the verify path:

- **HMAC or sign the claims plus an expiry.** Any node holding the key verifies locally; issuance
  writes nothing. Hash immutable content so the name proves the bytes.
- **Pass by value, not by reference.** Carry the claims the verifier needs, not an id that must be
  dereferenced against a database that is now everyone's availability ceiling.
- **Bound every lifetime.** Expiry is what makes the whole scheme work — an unbounded credential is
  an unbounded revocation problem.
- **When you need revocation and it's rarer than issuance, invert the state.** Keep a denylist of
  the revoked few — each entry retained only for the *remaining lifetime* of the thing it revokes —
  instead of a row for every grant ever issued. The set stays small, self-cleans, and is cheap
  enough to replicate to every verifier, so the lookup you removed never sneaks back.

## Context

The default shape in most codebases: generate a random id, insert a row, look the row up on every
use. Sessions, API keys, download links, email-verification and unsubscribe tokens, invite codes —
all pass-by-reference. It feels safe because the database is the truth. The cost is structural:
every verification anywhere becomes a read against one store, so that store's availability,
latency, and scale ceiling silently become every service's. And the busiest table in the system
ends up being one that stores no business data at all.

The alternative is old and settled. [HMAC the data plus an expiry](ref:fu-webauth) and the value
carries its own proof — this is 2001-era art, and it's what presigned URLs, signed cookies, and
self-contained tokens all are. [Macaroons](ref:macaroons) showed how far it stretches: holders can
*attenuate* a credential offline, adding caveats without any issuer round-trip. Content addressing
is the same move for data: the hash is the identity, so integrity is a computation and the object
is cacheable forever ([ZFN-21](/zfn/21-caches-sparingly-immutable-only/)).

The objection is always revocation — and the standard failure mode is to answer it by reintroducing
full state: a "valid tokens" table consulted on every request. Now you pay both costs: a write per
issuance *and* a read per verification, plus the key management of the signature you're no longer
really relying on.

The web PKI already ran this experiment at scale. OCSP — a live query to the issuer on every
verification — failed on availability and privacy so thoroughly that browsers soft-failed it into
meaninglessness, and [the largest CA has shut it down](ref:le-ocsp). What replaced it is the
inversion this note recommends: [CRLite](ref:crlite) compresses *every* revocation in the web PKI
into a few megabytes pushed to every browser, because certificates expire and revocation is rare —
so the outstanding-revocations set is small even at internet scale.

> [!aside]
>
> Every time I've profiled a system that "couldn't scale sessions", the sessions table was the
> hottest thing in the database — orders of magnitude more reads than the tables the product
> actually exists to serve, all to answer a question an HMAC answers in a microsecond. The database
> wasn't the bottleneck; the pass-by-reference habit was.

## Recommendation

**Make validity self-evident.** The credential is the claims plus a MAC or signature over them:
subject, audience/purpose, expiry, and a unique id. Shared-key HMAC is a fine start; move to
asymmetric when verifiers shouldn't be able to mint — the same progression as
[ZFN-5](/zfn/5-platform-workload-identity-service/) and [ZFN-7](/zfn/7-sign-the-message/). Always
include the unique id (a `jti`): it costs nothing at issuance and it is what makes precise
revocation possible later.

**Pass by value.** Put the claims the verifier needs *in* the value instead of behind an id. The
same principle shows up beyond auth: a version token the client carries beats a server-side session
table for read-your-writes ([ZFN-25](/zfn/25-read-your-writes-version-token/)); a content hash
beats an object-id-plus-lookup for anything immutable. Don't put secrets in claims — the holder can
read them; signed is not encrypted.

**Bound every lifetime, short.** Issue short and refresh to extend, the discipline of
[ZFN-9](/zfn/9-no-long-lived-cloud-keys/). The refresh point is a natural, *low-rate* stateful
checkpoint — the right place for policy and revocation checks — and short expiry is what caps how
long any revocation must be remembered.

**When you must revoke, store the revocations.** Keep a denylist keyed by token id or subject.
Each entry's TTL is the remaining lifetime of what it revokes — after that the expiry enforces
itself, so the set is self-cleaning; like a lease ([ZFN-37](/zfn/37-every-lock-is-a-lease/)),
cleanup is the passage of time, not a job. State is O(outstanding revocations), not O(issued):
issuing a million links costs nothing, revoking three costs three entries for an hour. This
inversion is only right when revocation is genuinely rarer than issuance — if you're consulting
per-grant state on most verifications anyway (per-request entitlements, usage metering), you want
honest pass-by-reference, not a denylist bolted onto a token.

**Replicate the denylist to the verifiers.** Small and bounded means it fits in memory everywhere —
a full set or a Bloom-filter cascade pushed to every node, CRLite-style. Verification stays a local
computation even with revocation in the picture. A revocation now takes effect within your
propagation interval; measure that interval, put a number on it, and get the number agreed as
policy — "revocation takes effect within N seconds, and expiry caps the damage at M minutes" is a
sentence a security review can accept or reject.

**Keep the coarse levers.** Rotating a signing key revokes everything it signed — the emergency
brake. A per-subject not-before timestamp ("reject anything for this principal issued before T")
implements *log out everywhere* with one small record per affected subject rather than a hunt
through per-token state. Between per-id, per-subject, and per-key, you can revoke at whatever
granularity the incident calls for.

## Consequences

**Easier:**

- Verification scales with CPU, not with a datastore — no hot-path dependency, no cross-region
  read, nothing to fall over during a partition. Issuance is free, so granting a million
  narrow, short-lived credentials is an architectural non-event.
- The blast radius of the credential store shrinks to the issuer; verifiers keep working through
  its outages, degraded only in revocation freshness.

**Harder:**

- Revocation is no longer instantaneous: worst case is denylist propagation delay, capped by
  expiry. That's a real policy decision to defend, not an implementation detail to hide.
- The signing key is now the crown jewels. Rotation must actually be built — key ids on every
  credential, overlap windows, a rehearsed rotation runbook — not left as "we'd figure it out."
- You gave up the inventory: "how many active sessions?" has no cheap answer. If audit needs
  enumeration, log issuance asynchronously off the hot path ([ZFN-48](/zfn/48-emit-async-work-into-the-wal/))
  — don't put a write back in front of verification.
- Claims travel with every request — size on the wire, and visible to the holder.

**New obligations:**

- Every issued credential carries a unique id and an expiry, even when you can't imagine revoking
  it — retrofitting `jti` into credentials already in the wild is miserable.
- The denylist propagation lag is monitored and alarmed; a stalled replica is a silent revocation
  failure.

## References

- [ZFN-5](/zfn/5-platform-workload-identity-service/) — short-lived platform-minted tokens, verified
  anywhere; the issuance side of this note.
- [ZFN-7](/zfn/7-sign-the-message/) — signing the message itself; shared keys first, asymmetric better.
- [ZFN-9](/zfn/9-no-long-lived-cloud-keys/) — short lifetimes and refresh as the base discipline.
- [ZFN-21](/zfn/21-caches-sparingly-immutable-only/) — content addressing: hashes as identity for
  immutable data.
- [ZFN-25](/zfn/25-read-your-writes-version-token/) — pass-by-value client state for consistency.
- [ZFN-37](/zfn/37-every-lock-is-a-lease/) — state that expires by itself; recovery as the passage of time.
- [Fu et al. — Dos and Don'ts of Client Authentication on the Web (2001)](https://pdos.csail.mit.edu/papers/webauth:sec10.pdf) —
  the canonical stateless authenticator: HMAC over data plus expiry.
- [Birgisson et al. — Macaroons (NDSS 2014)](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41892.pdf) —
  HMAC-chained bearer credentials attenuable offline.
- [Larisch et al. — CRLite (IEEE S&P 2017)](https://cbw.sh/static/pdf/larisch-oakland17.pdf) — all of
  the web PKI's revocations, compressed and pushed to every verifier.
- [Let's Encrypt — Ending OCSP Support in 2025](https://letsencrypt.org/2024/12/05/ending-ocsp/) — the
  ecosystem's verdict on lookup-per-verification.

## Changelog

- **2026-07-07**: First published as a Field Note.