Distributed Systems Security and Trust Questions

Direct answer

A JWT (JSON Web Token) is fast because any service can validate it locally with a public key, without calling the issuer. Revocation re-introduces shared state, so the design goal is to keep that state tiny, local and pushed, not queried. My design: short-lived access tokens (5 minutes) so the revocation list only has to remember tokens for 5 minutes, a denylist of revoked token IDs plus per-user "revoked before" timestamps that the auth service pushes to an in-memory copy in every gateway, and a propagation SLO (service-level objective) of a couple of seconds, with a fail-closed rule for sensitive routes when a gateway's copy goes stale. Long-lived sessions live in refresh tokens, which are always checked against the auth server's database, so revoking a session is authoritative there.

Why this is hard

• Stateless validation: the gateway checks the signature and the exp (expiry) claim. Nothing in that check can learn that the token was stolen an hour ago.
• "Immediately" needs a number. In a distributed system it means "within a bounded, monitored delay". I would commit to p99 (99th percentile) revoke-to-enforced under 2 seconds and alert above 5.
• Performance budget: the reason for JWTs is avoiding a network call per request. A design that calls a central revocation service on every request has quietly turned the JWT into an opaque token with extra steps.

The design

1. Bound the problem with token lifetime

Access tokens live 5 minutes; a refresh token (revocable, stored server-side) mints new ones. Now a revoked entry only needs to be remembered until the revoked token's own exp passes, after which the ordinary expiry check rejects it. The denylist's size is "revocations per 5 minutes", not "revocations ever".

2. Two kinds of revocation entry

A gateway rejects a token if its jti is denylisted or its iat (issued-at) is earlier than the subject's cutoff. The cutoff entry kills every outstanding token for a user with one record, which is what incident response usually needs.

3. Push, don't pull

sequenceDiagram
  participant Admin as Security tool
  participant Auth as Auth service
  participant Bus as Revocation stream
  participant GW as Gateway (in-memory set)
  Admin->>Auth: revoke jti or subject
  Auth->>Auth: write to durable store, assign sequence number
  Auth->>Bus: publish entry with sequence
  Bus->>GW: deliver within ~1 s
  GW->>GW: add to local set, record last sequence
  Note over GW: every request: signature + exp + local set lookup

Every gateway holds the full active set in memory and subscribes to a stream (Kafka, NATS, a lightweight open-source messaging system, or Redis Streams; any of the three does this job). Entries carry a monotonically increasing sequence number, so a gateway knows if it missed one and re-syncs from a snapshot. The per-request cost is a hash-set lookup, which keeps JWT performance intact.

4. Optional: a Bloom filter when the set is big

If revocations get large (for example a mass logout of a million users), ship a Bloom filter: a compact bit array that answers "definitely not revoked" or "possibly revoked". It has false positives but no false negatives. On "possibly", the gateway asks the authoritative store. Sizing, with $n$ entries and false-positive rate $p$:

where $m$ is the number of bits in the filter and $\ln$ is the natural logarithm (log base $e$). For $n = 10^6$ and $p = 10^{-4}$: $\ln(10^{-4}) \approx -9.21$, so $m \approx (10^6 \times 9.21) / 0.4805 \approx 19.2$ million bits, roughly 2.4 MB. The number of hash functions that minimises false positives for a given $m$ and $n$ is $k = (m/n)\ln 2$: here $m/n \approx 19.2$, so $k \approx 19.2 \times 0.693 \approx 13$ hash functions. At that false-positive rate, only 1 in 10,000 valid requests pays a remote lookup.

5. Convergence without a central coordinator: a CRDT revocation set

A senior candidate should be able to raise this option, though it is not required to answer the question well; the push-based denylist in steps 1 to 3 is the core design. A CRDT (conflict-free replicated data type) is a data structure whose replicas can be updated independently and merged in any order, always converging to the same value. A revocation set is a natural fit because revocation is monotonic: you add, you essentially never "un-revoke" within a token's lifetime. So each region's auth node keeps a grow-only set of jti -> exp, and replicas exchange updates by gossip: periodically, each node picks a peer and exchanges what it has, rather than relying on one central broadcaster, so the set still converges even if some nodes cannot reach each other directly. Merge is set union (keeping the later exp). Each node also keeps per-node logical counters (a version vector, one counter per node recording how many updates from that node you have applied). The sketch below merges full state on every exchange, which is simple and correct but sends more data than necessary; in a real deployment, the version vector is exactly what lets two nodes compare "how many updates have I seen from node X" and request only the entries the other is missing, instead of resending everything each round. Expiry uses the token's own exp claim, set by the issuer, so garbage collection does not depend on trusting each node's local clock beyond a small skew allowance.

Runnable sketch (Python 3, no dependencies):

class RevocationSet:
    """Grow-only set of revoked token IDs (jti), each kept until the token's own exp."""
    def __init__(self, node):
        self.node = node
        self.entries = {}          # jti -> exp (unix seconds, from the token itself)
        self.clock = {}            # node -> highest counter seen (version vector)

    def revoke(self, jti, exp):
        self.entries[jti] = max(exp, self.entries.get(jti, 0))
        self.clock[self.node] = self.clock.get(self.node, 0) + 1

    def merge(self, other):        # union + pointwise max: commutative, associative, idempotent
        for jti, exp in other.entries.items():
            self.entries[jti] = max(exp, self.entries.get(jti, 0))
        for n, c in other.clock.items():
            self.clock[n] = max(c, self.clock.get(n, 0))

    def is_revoked(self, jti):
        return jti in self.entries

    def gc(self, now, skew=60):    # safe: an expired token is rejected by the exp check anyway
        self.entries = {j: e for j, e in self.entries.items() if e + skew >= now}

us, eu, ap = RevocationSet("us"), RevocationSet("eu"), RevocationSet("ap")
us.revoke("jti-A", exp=1_000_300)
eu.revoke("jti-B", exp=1_000_600)
# Partition: ap has seen nothing yet
print("ap before merge:", ap.is_revoked("jti-A"), ap.is_revoked("jti-B"))
# Gossip in different orders still converges
ap.merge(eu); ap.merge(us)
us.merge(eu); eu.merge(us)
print("converged:", us.entries == eu.entries == ap.entries, sorted(ap.entries))
print("version vector at ap:", dict(sorted(ap.clock.items())))
ap.merge(us)  # re-delivery is harmless
print("after duplicate merge:", sorted(ap.entries))
ap.gc(now=1_000_400)
print("after gc at t=1_000_400:", sorted(ap.entries))

Output:

ap before merge: False False
converged: True ['jti-A', 'jti-B']
version vector at ap: {'eu': 1, 'us': 1}
after duplicate merge: ['jti-A', 'jti-B']
after gc at t=1_000_400: ['jti-B']

Why not a full add/remove CRDT? Supporting "remove" (un-revoke) needs an observed-remove set with tombstones: instead of a value simply vanishing, "remove" is recorded as its own entry (a tombstone) that has to be seen and outrank every earlier "add" for that key, which is the standard way CRDTs make delete-then-re-add behave correctly under out-of-order merges. It opens a dangerous race: a stale remove can resurrect a stolen token. If un-revocation is ever needed, issue the user a new token instead. I would use the CRDT for cross-region replication of the authoritative set (it survives partitions and needs no leader), and still push the merged result to gateways as in step 3.

Worked example

A platform with 50 million active users, 5-minute access tokens, and a bad day of 2,000 individual revocations per minute. The active jti set holds at most about 2,000 x 5 = 10,000 entries plus a skew allowance; at under 100 bytes per entry that is about 1 MB per gateway. Subject cutoffs for a mass incident (say every user in one tenant, 200,000 users) add 200,000 small records, still a few MB. No Bloom filter needed; it becomes worthwhile only when the set reaches millions.

How SREs operate, monitor and scale it

• Key metrics: revoke-to-enforced latency measured by a canary, a synthetic, fake-but-realistic probe run continuously in production so you get a steady measurement instead of waiting for a real revocation (revoke a synthetic token every 10 seconds, probe every gateway, time until 401); per-gateway last_applied_sequence lag behind the stream head; set size; snapshot age; share of requests hitting the authoritative store.
• Staleness policy: if a gateway's sequence lags by more than a threshold (say 10 seconds), it fails closed on high-risk scopes (payments, admin) by calling the auth service directly, and keeps serving low-risk reads. Decide this per route in advance, not during an incident.
• Cold start: a new gateway loads a snapshot plus the stream from the snapshot's sequence before it takes traffic; readiness probes (the orchestrator's check for "is this instance actually ready to serve," used to hold new instances out of the load balancer until they pass it) enforce this.
• Scale: the stream's fan-out, how many downstream subscribers one stream has to deliver every message to, is the only thing that grows with gateway count. Thousands of subscribers on one topic is routine for the streaming systems named above; if not, add a regional relay tier.
• Runbook for a real compromise: revoke by subject cutoff (covers tokens you don't know about), rotate the signing key if the key itself leaked (every token becomes invalid; publish the new public key through the JWKS endpoint, the JSON Web Key Set URL gateways fetch keys from), and verify with the canary.

Trade-offs and pitfalls

• Shorter token lifetimes vs refresh load. 5-minute tokens with 10 million concurrent sessions means about 33,000 refreshes per second (10,000,000 / 300). Check the auth service can take that before shortening further.
• Revoking only by jti misses tokens you have not seen; the subject cutoff is the incident-response tool.
• Fail-open everywhere makes the revocation system decorative during exactly the outages attackers exploit; fail-closed everywhere turns a stream hiccup into a platform outage. Split by route risk.
• What would flip the design: if you need revocation guarantees in milliseconds with strict consistency on every request, stop using self-contained tokens on that path and introspect instead.

Direct answer

Model each region's audit trail as a Merkle-tree transparency log, the structure Certificate Transparency (the public, append-only logging system browsers use to catch mis-issued TLS certificates) uses (RFC 6962): events are appended as leaves (the tree's bottom-level entries, one per event), and every so often the region publishes a signed tree head, a signature over the tree's root hash (a single hash that commits to the contents of every leaf beneath it) and size. Anyone holding a signed head can check two things with a handful of hashes: that a given event is in the log (an inclusion proof) and that today's log is an append-only extension of yesterday's (a consistency proof). To merge regions verifiably, a global log takes each region's signed head at fixed epochs (say every minute) as its own leaves, producing one global root per epoch that commits to all regions at once. Event data lives in write-once object storage, a separate index serves time-range and per-entity queries, and proof generation is a tool SREs run on demand for auditors.

The data structures

Hash chain vs Merkle tree. A hash chain (each record includes the hash of the previous one) is tamper-evident, but proving that event #5,000,000 is in the log means handing over everything after it. A Merkle tree hashes events in pairs, then pairs of pairs, up to one root. Proving one event is included takes one sibling hash per level, about $\lceil \log_2 n \rceil$ hashes:

Per-region append-only log. Each region runs its own log (append-only by construction: the log server only appends leaves, and consistency proofs let anyone detect a rewrite). Leaf = canonical serialisation of the event (encoding it into bytes in one fixed, unambiguous order, so hashing the same event twice always produces the same hash; here: event ID, entity ID, actor, action, timestamp, payload hash).

Verifiable cross-region merge. Regions do not share one total order in real time; forcing one would make every write wait on a cross-region round trip. Instead, at each epoch boundary, each region's signed head becomes a leaf in the global epoch tree, in a fixed region order. The global root for epoch 1042 therefore commits to exactly which events every region had at that moment. A proof for any event is a pair: inclusion in its regional tree, plus inclusion of that regional head in the global tree.

flowchart TB
  subgraph US[us region log]
    U1[events] --> UR[signed head us]
  end
  subgraph EU[eu region log]
    E1[events] --> ER[signed head eu]
  end
  subgraph AP[ap region log]
    A1[events] --> AR[signed head ap]
  end
  UR & ER & AR --> G[Global epoch tree, root per minute]
  G --> W[(WORM archive + external witnesses)]

Runnable demonstration (Python 3, standard library)

This follows RFC 6962's hashing: leaves are hashed with a 0x00 prefix and interior nodes with 0x01, so a leaf can never be passed off as an interior node.

import hashlib

def H(b): return hashlib.sha256(b).digest()
def leaf(d): return H(b"\x00" + d)          # RFC 6962 leaf hash
def node(l, r): return H(b"\x01" + l + r)    # RFC 6962 interior hash

def split(n):                                # largest power of 2 < n
    k = 1
    while k * 2 < n: k *= 2
    return k

def root(items):
    if len(items) == 1: return leaf(items[0])
    k = split(len(items))
    return node(root(items[:k]), root(items[k:]))

def prove(items, i):                         # audit path for item i
    if len(items) == 1: return []
    k = split(len(items))
    if i < k: return prove(items[:k], i) + [("R", root(items[k:]))]
    return prove(items[k:], i - k) + [("L", root(items[:k]))]

def verify(item, path, expected_root):
    h = leaf(item)
    for side, sib in path:
        h = node(h, sib) if side == "R" else node(sib, h)
    return h == expected_root

# Regional logs for one epoch (a minute of events per region)
regions = {
    "us": [f"us|{i}|user:42|login".encode() for i in range(5)],
    "eu": [f"eu|{i}|user:7|export".encode() for i in range(3)],
    "ap": [f"ap|{i}|svc:billing|keyread".encode() for i in range(6)],
}
region_roots = {r: root(ev) for r, ev in regions.items()}

# Global epoch tree: leaves are (epoch, region, regional root), fixed region order
epoch = 1042
g_leaves = [f"{epoch}|{r}|".encode() + region_roots[r] for r in sorted(regions)]
global_root = root(g_leaves)

# Proof that eu event #2 is in the globally committed epoch
ev = regions["eu"][2]
p1 = prove(regions["eu"], 2)
gi = sorted(regions).index("eu")
p2 = prove(g_leaves, gi)
ok1 = verify(ev, p1, region_roots["eu"])
ok2 = verify(g_leaves[gi], p2, global_root)
print("regional inclusion:", ok1, "| proof hashes:", len(p1))
print("global inclusion:  ", ok2, "| proof hashes:", len(p2))

# Tamper: someone edits the stored event after the root was signed
tampered = b"eu|2|user:7|view"
print("tampered event verifies:", verify(tampered, p1, region_roots["eu"]))

# Proof size grows with log2(n), not n
import math
for n in (1_000, 1_000_000, 8_640_000_000):
    print(f"n={n:>13,} -> about {math.ceil(math.log2(n))} sibling hashes, {math.ceil(math.log2(n))*32} bytes")

Output:

regional inclusion: True | proof hashes: 1
global inclusion:   True | proof hashes: 2
tampered event verifies: False
n=        1,000 -> about 10 sibling hashes, 320 bytes
n=    1,000,000 -> about 20 sibling hashes, 640 bytes
n=8,640,000,000 -> about 34 sibling hashes, 1088 bytes

The demo omits signatures to stay short; production signs every published root with a key in an HSM or KMS (below). It does not omit consistency proofs.

Walking through the proof, by hand

split(n) finds the largest power of two strictly less than n. That is how RFC 6962 shapes an unbalanced tree for any size: the left side is always a perfect subtree of size k, and the right side (n - k items) is built the same way, recursively. For the eu region above, 3 events, split(3) = 2, so the tree is node( node(L0, L1), L2 ): leaves 0 and 1 pair up first, and leaf 2 hangs directly off the root.

That is why prove(regions["eu"], 2) (the proof for event index 2) returns exactly one sibling instead of the ceil(log2(3)) = 2 you might expect from a balanced tree: at the top level, index 2 is not less than k = 2, so the function takes the ("L", root(items[:2])) branch and recurses into prove(items[2:], 0), a single-item list, which returns []. The whole proof is that one ("L", ...) entry: the combined hash of leaves 0 and 1, labelled L because it sits to the left of leaf 2 when they are joined.

verify() starts from leaf(item) and folds in each sibling in the order the proof lists them: "R" means the sibling is combined on the right (node(h, sib), used when the proved leaf was in the left half at that level), "L" means it is combined on the left (node(sib, h), used here). One fold with the leaves-0-1 hash on the left reproduces the root, so verify returns True.

Consistency proof and range proof, worked small

Both are missing from the demo above; here they are, small enough to read in full and to run on their own (repeating the leaf/node/split/root helpers from the first demo).

import hashlib

def H(b): return hashlib.sha256(b).digest()
def leaf(d): return H(b"\x00" + d)
def node(l, r): return H(b"\x01" + l + r)

def split(n):
    k = 1
    while k * 2 < n: k *= 2
    return k

def root(items):
    if len(items) == 1: return leaf(items[0])
    k = split(len(items))
    return node(root(items[:k]), root(items[k:]))

def consistency_proof(items, m):             # proves size-m tree is a prefix of size-n tree
    n = len(items)
    return _subproof(items, m, n, True)

def _subproof(items, m, n, b):
    if m == n:
        return [] if b else [root(items)]
    k = split(n)
    if m <= k:
        return _subproof(items[:k], m, k, b) + [root(items[k:])]
    return _subproof(items[k:], m - k, n - k, False) + [root(items[:k])]

def verify_consistency(m, n, proof, old_root, new_root):
    proof = list(proof)
    def rec(m, n, b, claimed_old):
        if m == n:
            if b:
                return claimed_old, claimed_old
            h = proof.pop()
            return h, h
        k = split(n)
        if m <= k:
            right = proof.pop()
            oh, nh_left = rec(m, k, b, claimed_old)
            return oh, node(nh_left, right)
        left = proof.pop()
        oh, nh_right = rec(m - k, n - k, False, claimed_old)
        return node(left, oh), node(left, nh_right)
    oh, nh = rec(m, n, True, old_root)
    return oh == old_root and nh == new_root

def range_proof(items, start, end):           # boundary hashes for the contiguous range [start, end]
    n = len(items)
    needed = []
    def walk(lo, hi):
        if hi <= start or lo > end:
            needed.append(root(items[lo:hi]))
        elif lo >= start and hi - 1 <= end:
            return
        else:
            k = split(hi - lo)
            walk(lo, lo + k); walk(lo + k, hi)
    walk(0, n)
    return needed

def verify_range(range_items, start, end, n, needed, expected_root):
    needed = list(needed)
    def rebuild(lo, hi):
        if hi <= start or lo > end:
            return needed.pop(0)
        if lo >= start and hi - 1 <= end:
            return _root_sub(range_items[lo - start:hi - start])
        k = split(hi - lo)
        return node(rebuild(lo, lo + k), rebuild(lo + k, hi))
    def _root_sub(sub):
        if len(sub) == 1: return leaf(sub[0])
        k = split(len(sub))
        return node(_root_sub(sub[:k]), _root_sub(sub[k:]))
    return rebuild(0, n) == expected_root

# 1. Consistency proof: the eu region's log grows from 2 events to 3.
eu_old = [f"eu|{i}|user:7|export".encode() for i in range(2)]
eu_new = [f"eu|{i}|user:7|export".encode() for i in range(3)]
old_root, new_root = root(eu_old), root(eu_new)
cproof = consistency_proof(eu_new, 2)
print("consistency proof, 2 events -> 3 events: hashes needed =", len(cproof))
print("verifies (append-only holds):", verify_consistency(2, 3, cproof, old_root, new_root))
rewritten = [b"eu|0|user:7|EDITED-LATER", eu_new[1], eu_new[2]]  # attacker edits event 0, still grows to 3
fake_new_root = root(rewritten)
print("same proof against a silently rewritten history:", verify_consistency(2, 3, cproof, old_root, fake_new_root))

# 2. Range proof: prove events 1..3 of a 5-event log, nothing omitted from the middle.
five = [f"us|{i}|svc:billing|keyread".encode() for i in range(5)]
five_root = root(five)
rproof = range_proof(five, 1, 3)
print()
print("range proof for events[1..3] of 5: boundary hashes needed =", len(rproof))
print("verifies with the real 3 events:", verify_range(five[1:4], 1, 3, 5, rproof, five_root))
tampered_middle = [five[1], b"us|2|svc:billing|EDITED", five[3]]
print("verifies if the middle event is edited:", verify_range(tampered_middle, 1, 3, 5, rproof, five_root))
dropped_middle = [five[1], five[3]]  # attacker returns only 2 of the 3 claimed events
try:
    ok = verify_range(dropped_middle, 1, 3, 5, rproof, five_root)
except IndexError:
    ok = False
print("verifies if the middle event is silently dropped:", ok)

Output:

consistency proof, 2 events -> 3 events: hashes needed = 1
verifies (append-only holds): True
same proof against a silently rewritten history: False

range proof for events[1..3] of 5: boundary hashes needed = 2
verifies with the real 3 events: True
verifies if the middle event is edited: False
verifies if the middle event is silently dropped: False

For 3 leaves, proving events 0 and 1 haven't been disturbed while a third is appended needs only 1 hash: the new leaf hangs directly off the old root (the same unbalanced shape explained above), so that old root itself is the one sibling the consistency proof supplies. For the range proof, the 5-event log splits as node(node(node(L0,L1),node(L2,L3)),L4); proving events 1 to 3 needs the hash of L0 (the left edge of the first proved leaf) and the hash of L4 (everything to the right of the range), 2 boundary hashes. Handing over 2 hashes instead of leaf 2's own separate inclusion proof is what proves the auditor's own copy of events 1, 2 and 3 is complete: drop or edit any one of the three and the reconstructed root stops matching, exactly as the last two lines show.

Storage backends

Indexing strategy

The index is for finding events; the log is for proving them. The index never needs to be trusted, because every result can be proved against a signed head.

• Time ranges: leaves are appended in time order within a region, so a range maps to a contiguous leaf-index range per region. Store epoch -> (first_leaf, last_leaf) per region; a time-range query is a lookup plus a scan of that slice.
• Per-entity history: a secondary index (entity_id, timestamp) -> (region, leaf_index). For each hit, generate an inclusion proof. Across regions, order by timestamp and then region, and state that cross-region order within one epoch is by timestamp, not causality.
• Range proofs: for "all events in [t1, t2]", deliver the contiguous run of leaves plus the sibling hashes along the left edge of the first leaf and the right edge of the last leaf (worked small, with real code and output, in "Consistency proof and range proof, worked small" above); the auditor hashes the delivered events together with those boundary siblings and must reproduce the signed root exactly. That proves nothing was omitted from the middle of the range, which a list of separate inclusion proofs cannot.

Retention, legal hold and compliance

• Defensible retention policy: each event class has a documented retention period (for example seven years for security events), applied as a default retention on the WORM bucket. Deletion happens only by automated expiry after the lock lapses, and each expiry batch is itself an audit event.
• Legal holds: a legal hold on a locked object keeps it immutable beyond its retention date until explicitly removed. Legal-hold search runs on the index ("all events for entity X or matter Y"), then places holds on the matching object versions, and records the hold list as a signed manifest so you can later prove what was held and when.
• Deletion vs immutability: privacy law may require erasing a person's data from a log you promised never to change. Resolve it with crypto-shredding: encrypt each entity's payloads with its own data key and put only the ciphertext hash in the tree. Destroy the key and the content is unreadable, while every proof still verifies.
• Integrity proof via key management: signed heads are signed by a key in a KMS or HSM (key management service or hardware security module) the log operators cannot export; the KMS's own access log shows every signing call. For an external audit you hand over the public key, the signed heads, and the KMS log showing the key was used only by the log service. That is what turns "our logs are intact" into evidence.
• Witnessing: publish each global root to independent witnesses (another team's account, a partner, or a public timestamping service). A log operator who rewrites history would need to fork every witnessed head, which consistency checks expose.

Operational tooling for SREs

• audit-proof event <event_id>: returns the event, its regional inclusion proof, the regional signed head, the global inclusion proof and the global signed head, packaged with a standalone verifier script the auditor runs themselves.
• audit-proof range --entity X --from t1 --to t2: the events plus range proof.
• A continuous monitor that fetches every new signed head, checks consistency with the previous one, and pages if any check fails or a region stops publishing heads (a stalled log can hide events as effectively as a rewritten one).
• Quarterly drill: hand a colleague playing auditor a proof package and have them verify it with nothing but the public key.

Trade-offs and pitfalls

• One global log is simpler to prove but puts a cross-region round trip on every append; per-region logs with an epoch merge keep writes local and delay only the global commitment by one epoch.
• Trusting the index is the common mistake; every answer to an auditor must be backed by a proof, not a query result.
• Signing key loss breaks nothing retroactively but stops new heads; keep a documented key rotation that signs the transition with both keys, and retain old public keys for the full retention period.

Direct answer

An opaque token is a random string that means nothing by itself; a service must ask the authorisation server "is this valid, and for whom?" (token introspection, standardised in RFC 7662). A JWT (JSON Web Token) carries its claims (the payload's key-value assertions about the token, such as who it identifies and when it expires) and a signature, so any service can validate it locally. Under network partitions the difference becomes a choice between consistency and availability of the auth decision: opaque tokens give you accurate, immediately revocable decisions but fail (or go stale) when the introspection endpoint is unreachable; JWTs keep working through a partition but keep honouring a revoked token until it expires or a denylist reaches that node. My recommendation for a global microservices estate: opaque tokens at the external trust boundary, introspected at the regional gateway, exchanged for short-lived JWTs inside, with the partition behaviour chosen per route from its SLO (service-level objective) and risk.

Side-by-side on the five named axes

Proposed architecture for each approach

Opaque-token architecture

• A token service with a replicated token store in every region (not one central region), so introspection is an in-region call. Tokens are created with a region-independent ID and the store is replicated asynchronously; revocations replicate the same way, with priority.
• Introspection happens once at the edge gateway (the proxy at the boundary between the open internet and your internal services, which terminates and inspects every incoming request), not in every microservice; results are cached for a short TTL (for example 10 seconds).
• Revocation is a delete in the store plus a purge message to gateway caches.

JWT architecture

• Access tokens with a 5-minute lifetime, signed by keys published through a JWKS endpoint; refresh tokens (long-lived credentials a client exchanges for a fresh access token, so it does not have to make the user log in again) held server-side.
• A revocation stream pushing token IDs and per-user "revoked before" timestamps to every service's in-memory denylist.
• Services validate locally; no runtime dependency on the auth server except key refresh and the stream.

The hybrid I would ship (the "phantom token" pattern)

sequenceDiagram
  participant C as External client
  participant GW as Regional gateway
  participant AS as Regional token service
  participant S as Internal service
  C->>GW: request + opaque token
  GW->>AS: introspect (cache miss only)
  AS-->>GW: active, subject, scopes
  GW->>GW: mint 60 s internal JWT
  GW->>S: request + internal JWT
  S->>S: verify signature locally

The outside world holds an opaque token: nothing leaks if it is logged, and it is revocable at once. The gateway's introspection call above gets back whether the token is active, its subject (whose token it is) and its scopes (the specific permissions it grants), and mints a JWT carrying only those. Inside, services get a JWT that lives 60 seconds, so revocation reaches internal calls within one minute without any denylist, and internal hops never block on the auth server.

Worked example: what a partition does

A request path spans three internal hops, and the EU region loses connectivity to the US for 20 minutes. The token service is replicated in both regions.

• All-JWT (5-minute access tokens): EU keeps serving. A token revoked in the US at minute 2 of the partition is honoured in EU until its exp passes, at most 5 minutes after it was issued, because the revocation stream cannot cross the partition. Worst-case exposure: 5 minutes.
• All-opaque with central introspection in the US: every EU cache miss fails. With a 10-second cache, EU effectively goes down for authenticated traffic within about 10 seconds of the partition starting, unless you fail open.
• Hybrid with regional token stores: EU introspects locally, so it stays up. A US-side revocation does not reach the EU store until the link heals, so exposure is the partition duration for that token on EU gateways. Mitigation: EU gateways notice replication lag (heartbeat sequence stops advancing: each region's token store publishes a steadily incrementing counter to the others on a fixed interval, and a store that has fallen out of contact stops advancing its counter) and, for high-risk scopes, reduce cache TTL to zero and require step-up (re-authentication) for new sessions, while low-risk reads continue.

The point to make out loud: no design gives both perfect revocation and full availability during a partition. You choose where to sit per route, and you choose it before the incident.

Guidelines for SREs: when to prefer which

Two terms recur in this table: fail closed means denying a request when the system cannot get a fresh answer (safer, less available), and fail open means allowing it anyway and accepting some risk (more available, less safe).

Monitoring that proves the choice is working: introspection p99 and error rate per region, cache hit rate, revocation propagation lag per region (with a synthetic revoked-token canary), and the count of requests served under fail-open.

Trade-offs and pitfalls

• Introspecting at every microservice multiplies latency and load by the number of hops; do it once at the edge.
• Long cache TTLs on introspection quietly turn opaque tokens into JWTs with worse performance; keep TTLs short and deliberate.
• Putting sensitive claims in JWTs (email, roles, internal IDs) exposes them to anyone holding the token, since JWT payloads are only encoded, not encrypted.
• Forgetting key rotation for JWTs: services must refresh the JWKS and accept both old and new keys during rotation, or a rotation becomes an outage.

Direct answer

A compromised root is not something you can "revoke" in the usual sense: a root CA (certificate authority) is a trust anchor, a key every workload trusts because it is in their configured trust bundle, and the only way to stop trusting it is to remove it from every bundle. So the plan is: stop the bleeding (freeze the compromised key, hunt for attacker-minted certificates, shrink what the old root can vouch for), stand up a new root in a clean ceremony, run a short dual-trust window in which workloads trust both roots while every certificate is re-issued from the new one, then remove the old root everywhere and verify that nothing still presents or accepts it. Downtime is avoided by ordering: trust the new root first, re-issue second, distrust the old root last. The hard constraint is that during the dual-trust window the attacker's certificates are still trusted, so that window must be short and watched.

Phase 0: first hour, containment and scoping

1. Declare the incident, name an incident commander, open a war room, start a timeline. Legal and communications join now, not later.
2. Freeze the key: disable the compromised key in the HSM (hardware security module), revoke every credential and role that could invoke it, and stop all automated issuance that chains to it. Preserve logs and host images for forensics.
3. Scope the compromise: was the key exfiltrated (copied out, so the attacker can sign anything, forever) or was the signing service abused (the key never left; the attacker could only request signatures during a known window)? The second case is much smaller: every certificate the attacker got is in your issuance logs.
4. Hunt attacker certificates: compare every certificate seen in the wild (mesh proxy handshake logs: the connection logs a service mesh, the network of small proxies, one per workload, that carries and secures service-to-service traffic, writes each time its proxies complete a TLS handshake, the negotiation in which client and server exchange and verify certificates before encrypted traffic starts; plus load balancer logs) against your issuance log. Any certificate that chains to the root but is not in your log is attacker-minted and tells you what they are impersonating.
5. Short-term guardrails while you prepare the replacement: tighten authorisation so that high-value services (payments, identity, secrets) accept only an allowlist of SPIFFE IDs (workload identity names under the SPIFFE standard, Secure Production Identity Framework For Everyone) or certificate serials (the unique serial number stamped on each certificate you issue, so you can allowlist exactly the ones your own issuance log shows as legitimate) you issued; raise alerting on new identities appearing.

Phase 1: build the new trust anchor

• Ceremony: generate the new root offline in an HSM with M-of-N custody (for example 3 of 5 custodians must be present), witnessed and recorded. Do not reuse any host, HSM partition, pipeline or credential from the old chain until forensics clears it.
• Design it to fail smaller next time: a certificate chain has three tiers: the root (the offline trust anchor itself), intermediates (subordinate CAs the root signs once, which do the day-to-day signing so the root never has to come online), and leaf certificates (the end-entity certificates a workload actually presents on a connection, signed by an intermediate). Keep the root offline and issue per-region or per-environment intermediates, each with a path length constraint of 0 (it can sign leaf certificates but not further CAs) and, where your clients enforce them, name constraints (limit which names or URI SANs, the subject alternative names that carry SPIFFE IDs, an intermediate may certify). A future intermediate compromise then affects one region, and the root never touches the network.
• Do not cross-sign the new root with the old one. Cross-signing means having one root issue a certificate over the other root's public key, so anyone who already trusts root A automatically trusts anything root B signs too; that is how you migrate trust between two healthy roots, but here it would let the untrusted old root vouch for the new one, handing the attacker a path back in.

Phase 2: dual trust, then rotate millions of workloads

flowchart LR
  A[Bundle: old root only] --> B[Bundle: old + new root]
  B --> C[Re-issue all leaf certs from new chain]
  C --> D[Bundle: new root only]
  D --> E[Verify: no old-chain handshakes]
  C -. "rollback target" .-> B

Step A to B, push the new bundle. Every workload must trust the new root before anything presents a new-chain certificate, or handshakes fail. Distribute through the normal channel (the mesh's trust bundle distribution, SPIRE, the SPIFFE Runtime Environment, or the service mesh control plane) and gate the next step on telemetry: 100% of proxies reporting the new bundle version.

Step B to C, re-issue at scale. Workloads fetch new leaf certificates from the new intermediates. This plan commits to a 6-hour re-issuance window as the target (a business-hours window with slack for retries and backoff); 2 hours is shown only as the aggressive case worth checking your infrastructure against, not a promise the plan makes. Capacity arithmetic for 2 million instances:

Split across regional intermediates both rates are modest, but verify each against your issuer's measured signing rate and your HSM's, and add jitter so 2 million agents do not stampede in the first minute. Roll out by ring (deploy in expanding waves, each one gated on the previous wave's health before the next starts): internal tooling, then one low-risk region, then the rest, with automatic pause on handshake-error spikes. Workloads keep serving while they rotate; existing connections complete, and new connections use the new certificate.

Step C to D, distrust the old root. Once telemetry shows no workload presenting an old-chain certificate, push bundles containing only the new root. This is the moment the attacker's certificates stop working.

Window length: this whole A-to-D sequence should be hours, not weeks. If automation allows, target same day. The window is your exposure.

External partners

• Notify partners who trust your root (federation, mTLS (mutual TLS) integrations where both sides present certificates, customer devices) with: what happened at a level legal approves, the new root's fingerprint (a short cryptographic hash of the root certificate, unique enough that comparing it byte for byte confirms a partner has the genuine new root and not a substitute), and a firm deadline for removing the old one.
• Deliver the fingerprint out of band (a signed advisory on a separate channel plus a phone confirmation between named contacts), never only in an email that could come from the attacker.
• Offer a validation endpoint partners can test against before the cutover; track each partner's status on a board. Partners who miss the deadline lose connectivity rather than keeping a compromised trust path open, and that decision is made in advance by an executive, not improvised.

Cryptographic constraints to plan around

• No CRL (certificate revocation list) or OCSP (Online Certificate Status Protocol) for roots. Revocation lists are signed by the issuer; a root's "revocation" would be signed by the compromised key itself. Bundle removal is the only mechanism.
• Every certificate issued under the old root is untrustworthy, including legitimate ones, because the attacker can mint identical-looking ones. Everything gets re-issued.
• Pinned and embedded roots (firmware, mobile apps, appliances, partner configs) cannot be updated by your control plane. Inventory them first; they set your real deadline.
• Clock skew: issue new certificates with a small backdated notBefore so slightly slow clocks do not reject them.
• Algorithm choice: take the opportunity to use the current recommended key type (for example ECDSA, the elliptic curve digital signature algorithm, on P-256 or P-384) and plan how you would do this again; the rotation you are rehearsing now is also your future crypto-agility.

Rollback strategy

Rollback never means going back to trusting only the old root. The safe rollback target is the dual-trust state (B): if re-issued certificates break something, revert those workloads to their old-chain certificate, which still works in state B, fix, and retry. Keep bundle versions immutable and numbered so "roll back to bundle v41" is one command. Once you reach state D, rolling back re-opens the attacker's access, so it requires incident-commander sign-off.

Monitoring to verify success

• Bundle version per proxy (target 100% on each step before moving on).
• Handshakes by issuing chain: old-chain presentations should fall to zero before step D, and old-chain acceptances must be zero after it.
• Handshake failure rate per service and region during each ring (the canary signal for pausing).
• Certificates observed that are absent from the issuance log (should be zero on the new chain; any hit is a new incident).
• Partner cutover status and synthetic probes from partner-like clients.

Trade-offs and pitfalls

• Speed vs safety: a same-day rotation risks breakage; a slow one leaves the attacker trusted. Pre-built automation and quarterly root-rotation drills are what let you have both.
• Minimising downtime by skipping step A (pushing new certificates before new trust) is the classic self-inflicted outage.
• Forgetting non-mesh consumers (batch jobs, databases with client-certificate authentication, VPN concentrators) leaves pockets that break at step D or, worse, keep trusting the old root silently.

Direct answer

A JWT (JSON Web Token) has three base64url-encoded parts (base64: a scheme for representing arbitrary bytes as printable text; the URL-safe variant avoids characters like + and /), header.payload.signature. Verification is: decode the header, refuse any algorithm other than the one you expect (RS256), pick the public key by the header's kid (key ID), verify the RSA signature over the exact bytes header.payload, and only then trust and check the claims (the payload's key-value assertions about the token, decoded from its middle segment), specifically exp (expiry) and nbf (not before). Key rotation is supported because the key set (JWKS, JSON Web Key Set) can hold the old and the new key at the same time, each with its own kid. In production, a missing kid should be rejected for tokens you issue yourself; a kid you do not recognise should trigger one rate-limited refresh of the key set, not a scan of every key.

Approach

1. Parse strictly. Exactly three segments; each segment valid base64url; header and payload must decode to JSON objects.
2. Pin the algorithm. RS256 means an RSA signature using the PKCS#1 v1.5 padding scheme (from the Public-Key Cryptography Standards) over a SHA-256 hash. Rejecting everything else closes two well-known attacks: alg: none (an unsigned token) and algorithm confusion (a token that says HS256 so a naive library uses the RSA public key as an HMAC (hash-based message authentication code) secret, which the attacker also knows).
3. Select keys. With a kid, use only that key. Without one, try the keys in the set, but cap how many (trying keys is a CPU cost an attacker can exploit, and it hides misconfiguration).
4. Verify the signature over the original encoded bytes, never over re-serialised JSON.
5. Validate time claims after the signature, with a small leeway for clock skew between issuer and verifier. Unverified claims mean nothing.
6. Return the claims, or raise one error type the caller maps to HTTP 401.

This uses the cryptography package for the RSA primitive only; all JWT logic is in the function.

Code

import base64, json, time
from typing import Dict, List, Optional

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import padding, rsa


class JWTError(Exception):
    pass


def _b64url_decode(part: str) -> bytes:
    if not part or any(c not in "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_" for c in part):
        raise JWTError("malformed base64url segment")
    return base64.urlsafe_b64decode(part + "=" * (-len(part) % 4))


def _load_keys(jwks: List[Dict]) -> Dict[Optional[str], list]:
    keys: Dict[Optional[str], list] = {}
    for entry in jwks:
        try:
            pub = serialization.load_pem_public_key(entry["pem"].encode())
        except (KeyError, ValueError):
            continue  # skip unusable entries instead of failing every token
        if not isinstance(pub, rsa.RSAPublicKey) or pub.key_size < 2048:
            continue  # RS256 needs an RSA key of at least 2048 bits
        keys.setdefault(entry.get("kid"), []).append(pub)
    return keys


def verify_jwt(token: str, jwks: List[Dict], now: Optional[float] = None,
               leeway: int = 30, max_keys_without_kid: int = 3) -> Dict:
    if not isinstance(token, str) or token.count(".") != 2:
        raise JWTError("token must have exactly three segments")
    h64, p64, s64 = token.split(".")
    try:
        header = json.loads(_b64url_decode(h64))
        claims = json.loads(_b64url_decode(p64))
    except ValueError as e:
        raise JWTError(f"undecodable header or payload: {e}")
    if not isinstance(header, dict) or not isinstance(claims, dict):
        raise JWTError("header and payload must be JSON objects")

    # Pin the algorithm: never let the token choose it ("none", HS256 key confusion).
    if header.get("alg") != "RS256":
        raise JWTError(f"unsupported alg {header.get('alg')!r}")

    keys = _load_keys(jwks)
    kid = header.get("kid")
    if kid is not None:
        candidates = keys.get(kid, [])
        if not candidates:
            raise JWTError(f"unknown kid {kid!r}")  # caller may refresh JWKS once and retry
    else:
        candidates = [k for ks in keys.values() for k in ks]
        if len(candidates) > max_keys_without_kid:
            raise JWTError("no kid and too many keys to try")

    signing_input = f"{h64}.{p64}".encode()
    signature = _b64url_decode(s64)
    for pub in candidates:
        try:
            pub.verify(signature, signing_input, padding.PKCS1v15(), hashes.SHA256())
            break
        except InvalidSignature:
            continue
    else:
        raise JWTError("signature verification failed")

    # Only now, with an authentic payload, do the time checks mean anything.
    now = time.time() if now is None else now
    for name in ("exp", "nbf"):
        if name in claims and (isinstance(claims[name], bool) or not isinstance(claims[name], (int, float))):
            raise JWTError(f"{name} must be a number")
    if "exp" not in claims:
        raise JWTError("missing exp")
    if now >= claims["exp"] + leeway:
        raise JWTError("token expired")
    if "nbf" in claims and now < claims["nbf"] - leeway:
        raise JWTError("token not yet valid")
    return claims


# ---------------- driver: build keys and tokens, then exercise every path ----------------
def b64url(b: bytes) -> str:
    return base64.urlsafe_b64encode(b).rstrip(b"=").decode()


def sign(priv, header: Dict, claims: Dict) -> str:
    h = b64url(json.dumps(header, separators=(",", ":")).encode())
    p = b64url(json.dumps(claims, separators=(",", ":")).encode())
    sig = priv.sign(f"{h}.{p}".encode(), padding.PKCS1v15(), hashes.SHA256())
    return f"{h}.{p}.{b64url(sig)}"


def pem(priv) -> str:
    return priv.public_key().public_bytes(
        serialization.Encoding.PEM, serialization.PublicFormat.SubjectPublicKeyInfo).decode()


old_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
new_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
attacker = rsa.generate_private_key(public_exponent=65537, key_size=2048)

NOW = 1_700_000_000
good = {"sub": "user-42", "iat": NOW - 60, "nbf": NOW - 60, "exp": NOW + 600}
jwks_both = [{"kid": "2024-old", "pem": pem(old_key)}, {"kid": "2025-new", "pem": pem(new_key)}]
jwks_new_only = [{"kid": "2025-new", "pem": pem(new_key)}]

forged_payload = sign(new_key, {"alg": "RS256", "kid": "2025-new"}, good).split(".")
forged_payload[1] = b64url(json.dumps({**good, "sub": "admin"}).encode())

cases = [
    ("old-key token, both keys published", sign(old_key, {"alg": "RS256", "kid": "2024-old"}, good), jwks_both),
    ("new-key token, both keys published", sign(new_key, {"alg": "RS256", "kid": "2025-new"}, good), jwks_both),
    ("old-key token after old key retired", sign(old_key, {"alg": "RS256", "kid": "2024-old"}, good), jwks_new_only),
    ("no kid, found by trying keys", sign(new_key, {"alg": "RS256"}, good), jwks_both),
    ("attacker key claiming a real kid", sign(attacker, {"alg": "RS256", "kid": "2025-new"}, good), jwks_both),
    ("payload edited after signing", ".".join(forged_payload), jwks_both),
    ("alg none", b64url(b'{"alg":"none"}') + "." + b64url(json.dumps(good).encode()) + ".", jwks_both),
    ("expired 10 minutes ago", sign(new_key, {"alg": "RS256", "kid": "2025-new"}, {**good, "exp": NOW - 600}), jwks_both),
    ("expired 10 s ago (inside 30 s leeway)", sign(new_key, {"alg": "RS256", "kid": "2025-new"}, {**good, "exp": NOW - 10}), jwks_both),
    ("nbf 5 minutes in the future", sign(new_key, {"alg": "RS256", "kid": "2025-new"}, {**good, "nbf": NOW + 300}), jwks_both),
    ("exp given as a string", sign(new_key, {"alg": "RS256", "kid": "2025-new"}, {**good, "exp": str(NOW + 600)}), jwks_both),
]
for label, tok, keyset in cases:
    try:
        c = verify_jwt(tok, keyset, now=NOW)
        print(f"ACCEPT  {label}: sub={c['sub']}")
    except JWTError as e:
        print(f"REJECT  {label}: {e}")

Output:

ACCEPT  old-key token, both keys published: sub=user-42
ACCEPT  new-key token, both keys published: sub=user-42
REJECT  old-key token after old key retired: unknown kid '2024-old'
ACCEPT  no kid, found by trying keys: sub=user-42
REJECT  attacker key claiming a real kid: signature verification failed
REJECT  payload edited after signing: signature verification failed
REJECT  alg none: unsupported alg 'none'
REJECT  expired 10 minutes ago: token expired
ACCEPT  expired 10 s ago (inside 30 s leeway): sub=user-42
REJECT  nbf 5 minutes in the future: token not yet valid
REJECT  exp given as a string: exp must be a number

The keys are generated fresh on each run, but the output does not depend on them: every line is an accept or reject decision fixed by how each token was constructed, and now is pinned to 1,700,000,000.

Key points

• Rotation in action. The first two cases show the overlap period: tokens signed by the old key and the new key both verify while the JWKS lists both. Case 3 shows what happens after the old key is retired: an old-key token fails with "unknown kid". That is correct only once every old-key token has expired, which is why rotation needs a waiting period between "stop signing with old" and "remove old".
• A matching kid is not trust. Case 5 is an attacker's key claiming a real kid; the signature check, not the kid lookup, is what rejects it.
• The payload is covered by the signature. Case 6 edits sub to "admin" after signing and fails.
• Leeway is explicit and small. 30 seconds absorbs normal clock skew (case 9 is 10 seconds past expiry and still accepted); case 8 at 10 minutes past is rejected.
• Type-check numeric claims. exp sent as a string is rejected rather than compared as a string or silently skipped. exp is also required here: a token that never expires cannot be contained after a leak, so this verifier treats a missing exp as an error (a policy choice; the JWT standard itself leaves exp optional).
• Bad key-set entries are skipped, not fatal, so one malformed entry published during a rotation does not take authentication down. Keys under 2048 bits are ignored.

Complexity

Parsing and claim checks are O(n) in token length. The dominant cost is RSA verification, one modular exponentiation per key tried: O(1) verifications with a kid, and up to max_keys_without_kid (3 here) without one. Loading PEM keys on every call is wasteful; a production version parses the JWKS once per refresh and caches the key objects, making each call a dictionary lookup plus one verification.

Edge cases

• Wrong number of segments, empty segments, characters outside the base64url alphabet: rejected before any crypto runs.
• Header or payload that is valid JSON but not an object (for example []): rejected.
• alg missing, none, HS256, or any other value: rejected.
• Duplicate kids in the JWKS (possible during a botched rotation): all keys with that kid are tried.
• exp or nbf given as a boolean (Python treats True as an integer): rejected explicitly.
• Empty JWKS: every token fails with "unknown kid" or a signature error, never an exception from inside the crypto library.

Handling a missing kid during rotation in production

• For tokens you issue, require kid and reject tokens without one. An issuer that omits kid makes every verifier guess, and the guessing loop grows with every key you keep for overlap.
• For third-party issuers that omit kid, allow trying keys only while the set is small (the cap above), and alert if that path is used, since it usually signals a misconfigured issuer.
• Unknown kid is the more important rotation case: it usually means the issuer started signing with a new key before this verifier's cached JWKS picked it up. The right response is one refetch of the JWKS, rate limited per instance (for example at most once every 30 seconds), then retry verification once. Without the rate limit, a stream of tokens with random kids becomes a flood of JWKS requests.
• Real validators also check iss (issuer) and aud (audience), so a token minted by your auth service for service A cannot be replayed against service B. The question's interface does not include them, but a production verifier must; for real services, use a maintained library (such as PyJWT) configured with a pinned algorithm list, rather than hand-rolled code.