Distributed Systems Security and Trust Questions

Direct answer

Split the problem into two kinds of secret. Client API keys (presented by callers to the gateway) are stored only as hashes in a central key registry and pushed to gateways as a versioned, in-memory snapshot plus a change stream (a continuous feed of create, scope-change and revoke events, so a gateway only has to apply what changed rather than re-fetch everything), so a gateway can validate a key locally and a revocation reaches every gateway in seconds. Service secrets (database passwords, third-party credentials) live in a secrets manager, encrypted under keys held in a KMS (key management service) or HSM (hardware security module), and are fetched at runtime by workloads that authenticate with their platform identity, never with a secret baked into an image. Rotation always runs through a window where old and new are both valid; revocation skips that window and is pushed, acknowledged and audited.

Terms

• Blast radius: how much one leaked key can do. Shrink it with per-client, per-environment, narrowly scoped, short-lived credentials.
• Envelope encryption: each secret is encrypted with its own data key, and that data key is encrypted with a master key that never leaves the KMS/HSM.
• Secret zero: the first credential a brand-new workload needs in order to fetch all its other secrets. How you bootstrap it decides whether the whole design is sound.

Storage model

flowchart LR
  ADM[Key admin API] --> REG[(Key registry: hashes + metadata)]
  REG --> STR[Change stream]
  STR --> G1[Gateway region A]
  STR --> G2[Gateway region B]
  SM[(Secrets manager)] --> KMS[KMS or HSM master key]
  W[Service workload] -->|platform identity| SM
  REG --> AUD[(Append-only audit log)]
  SM --> AUD

Client API keys. Generate 256 random bits, format as pk_live_<keyid>_<secret>. Store keyid, SHA-256(secret), owner, scopes, environment, status, created and expiry times. Never store the key itself: it is shown once at creation. A fast hash is correct here (unlike passwords): passwords are hashed with deliberately slow algorithms like bcrypt because people choose low-entropy, guessable values, so the hash must be expensive enough to make guessing infeasible. A 256-bit random secret has no such weakness: it cannot be brute-forced regardless of hash speed, so bcrypt's deliberate slowness buys nothing and would add latency on every request. The keyid prefix lets gateways look up the record in one step and lets secret-scanning tools (automated scanners that watch code repositories for accidentally committed credentials) recognise a leaked key in a public repository.

Service secrets. Stored in the secrets manager under envelope encryption, organised by path per service and environment (prod/orders/db), with a policy granting each workload identity exactly its own paths. Prefer dynamic secrets where the backend supports them: the secrets manager creates a unique database user per workload with a lease (a grant that expires automatically unless the workload renews it before the deadline) of, say, 1 hour, so there is nothing long-lived to leak and each credential is attributable to one workload.

Sizing the gateway snapshot. With 2,000,000 active client keys at about 32 bytes of hash plus 100 bytes of metadata each: 2,000,000 x 132 = 264,000,000 bytes, about 252 MiB. That fits in gateway memory, so every validation is a local lookup with no network call. If it did not fit, gateways would cache on demand with a short TTL (time-to-live) and fall back to the registry on a miss.

Distribution to gateways and services

• Gateways load a full snapshot at start-up (tagged with a version number), then apply a change stream of created / scope_changed / revoked events in order. Each gateway reports the version it has applied, so the control plane (the system that manages and coordinates gateway configuration, as distinct from the data plane that carries live request traffic) always knows the laggards, the gateways that have fallen behind the latest version. If the stream breaks, the gateway re-fetches a snapshot; if it cannot, it keeps serving from its last snapshot and alerts, because refusing all traffic is worse than a snapshot a few minutes old, except for revocations (see below).
• Services fetch their secrets at start-up through a local agent (a sidecar: a helper process deployed alongside the application container that does this fetching and renewal on the app's behalf), which renews leases before expiry and writes secrets to an in-memory file the app re-reads, so rotation does not require a redeploy.

Secret zero: bootstrapping a brand-new workload

The failure pattern is putting a long-lived token in CI (continuous integration) variables or the container image so the new container can log in to the secrets manager. Instead, let the platform vouch for the workload:

1. CI/CD pipeline: the CI provider issues a short-lived OIDC (OpenID Connect) token describing the exact repository, branch and job; the secrets manager or the cloud provider's security token service (STS) trusts that issuer and exchanges the token for credentials scoped to that pipeline. No static secret exists in CI at all.
2. Ephemeral containers: Kubernetes projects a service-account token that is audience-bound (it can only be redeemed by the exact service it was issued to, not replayed elsewhere) and expires; the agent presents it, the secrets manager validates it against the cluster and returns a short-lived token for that service's paths. On a cloud VM the equivalent is the instance identity document: a document signed by the cloud provider itself, attesting which specific VM instance is making the request.
3. When no platform identity exists, use a single-use, short-lived wrapped token delivered by the deploy system (Vault calls this response wrapping: the secrets manager seals the real credential in an envelope that can be opened, or "unwrapped," exactly once): if an attacker used it first, the legitimate workload's unwrap fails and that failure is itself the alarm.

Zero-downtime rotation orchestration

For client API keys, rotation is the client's action, so the platform must allow two active keys per client:

1. Client (or automation) creates key B; A and B are both valid.
2. Client deploys B; the gateway emits last_used per key ID, so both sides can see traffic migrate from A to B.
3. When A has had zero traffic for a set period (for example 7 days), A is revoked. Keys also carry an expiry (for example 1 year), with warnings at 30 and 7 days.

For service secrets:

1. Create the new credential in the backend (new DB password or user) while the old one stays valid.
2. Publish it to the secrets manager as a new version; agents pick it up on their next refresh.
3. Wait until every consumer reports the new version (or until one full refresh interval plus margin has passed).
4. Disable the old credential, then delete it after a cooldown. If error rates rise after step 4, re-enabling the old credential is the rollback, which is why you disable before deleting.

Emergency revocation flow

Leak detected (secret scanner hit, anomaly alert or customer report):

1. Revoke in the registry: status revoked, with reason and actor recorded in the audit log.
2. Push: the revocation event goes on the change stream with priority; gateways apply it and acknowledge by version. Target: 99% of gateways within 5 seconds.
3. Bound the tail: a gateway that has not acknowledged within the deadline is marked unhealthy and removed from the load balancer until it catches up. This turns "eventually revoked" into "revoked, or not serving traffic".
4. Scope the damage: query the audit log for every request made with that key ID since the suspected leak time.
5. Replace: issue a new key to the owner; for a service secret, rotate immediately without the normal overlap window, accepting a brief error spike.

Audit logging

Every key creation, scope change, revocation, secret read and failed authentication is written to an append-only store in a separate account that application operators cannot delete from. Log key IDs, never key material. Alert on reads from an unexpected identity, a spike in failed validations for one key ID (someone guessing), and use of a key from a new network or country.

Trade-offs and pitfalls

• Local validation vs instant revocation: local snapshots make validation fast and resilient but make revocation a distributed-propagation problem. The acknowledgement-plus-eviction step is what closes that gap; without it you only have "probably revoked".
• Rotation that requires a restart is rotation nobody runs. Hot reload of secrets is a prerequisite.
• Scoping is the cheapest blast-radius control: a key that can only read orders in staging is a far smaller incident than a master key.
• Common wrong turn: encrypting API keys reversibly "so support can look them up". If the platform can decrypt them, so can whoever compromises the platform.

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

A crash fault is a node that stops or goes silent; a Byzantine fault is a node that keeps running but lies: it sends different answers to different peers, forges or replays messages, or votes for two conflicting values. Crash-fault-tolerant (CFT) consensus such as Raft or Paxos assumes every node that speaks tells the truth, so a single lying node can corrupt it. Byzantine-fault-tolerant (BFT) consensus, such as PBFT (Practical Byzantine Fault Tolerance, an older, well-studied protocol) or the newer HotStuff family (used in systems like DiemBFT; its main selling point is a cheaper leader change), assumes up to $f$ nodes may be malicious and still agrees correctly, at the cost of more nodes (at least $3f+1$ instead of $2f+1$), cryptographic authentication of every vote, and more messages. A candidate should be able to name at least one of these two protocols in depth, not necessarily both. An SRE should reach for BFT only when the nodes in the quorum are run by parties who do not trust each other, or when a single compromised node must not be able to rewrite shared state. Inside one organisation, the usual answer is CFT consensus plus strong identity and hardening.

How the security reasoning changes

Consensus is a group of nodes agreeing on one value or one ordered log. A quorum is the minimum set of nodes whose votes are enough to decide.

Why 3f+1: the quorum-intersection argument

Two properties matter for any consensus protocol: safety (nothing bad ever happens: no two quorums decide different values) and liveness (something good eventually happens: a decision does get reached, even while some nodes are unresponsive). Safety rests on this: any two quorums that could decide must overlap, so they cannot decide different things. With crashes, overlapping in one node is enough, because that node is honest and will not vote twice. With liars, the overlap must contain at least one honest node, so it must be at least $f+1$ nodes.

Quorums of size $q$ out of $n$ overlap in at least $2q - n$ nodes: two groups of size $q$ drawn from a pool of $n$ each exclude at most $n - q$ members, so together they can exclude at most $2(n-q)$, leaving at least $n - 2(n - q) = 2q - n$ members in both. You must still be able to reach a quorum while $f$ nodes refuse to answer:

Taking the smallest quorum that still satisfies liveness, $q = n - f$, and substituting $n = 3f+1$ gives the quorum size in the table above: $q = (3f+1) - f = 2f+1$.

Worked numbers: to tolerate one bad node, CFT needs 3 nodes (quorum 2), BFT needs 4 (quorum 3). To tolerate two, CFT needs 5 (quorum 3), BFT needs 7 (quorum 5). With 4 BFT nodes, any two quorums of 3 share 2 nodes; at most 1 is lying, so at least 1 honest node saw both and refuses to vote for conflicting values.

What one malicious Raft node can do

Seeing the failure concretely is what convinces an interviewer. As a reminder, Raft normally works by electing one leader per term (an epoch number that increases every time a new election happens) among a set of followers; the leader alone accepts writes and replicates them, in order, to the followers, who simply accept and apply what the leader sends. That normal-case trust is exactly what a Byzantine node can abuse. A Raft follower that lies can claim an enormous term number, forcing everyone else to step down (a node that sees a higher term abandons its own leadership or vote and defers to the new one) and trigger repeated elections, which is a liveness attack. A malicious Raft leader is worse: followers accept whatever log entries it sends, so it can replicate a forged configuration change or a forged value (entries the followers wrongly apply as if they were legitimate), and it can send different entries to different followers. Raft has no defence because its safety proof assumes nodes follow the protocol. mTLS (mutual TLS, where both ends present certificates) stops outsiders from joining, but does nothing about an insider with a valid certificate.

Authentication

• Every protocol message is signed or MAC-authenticated (a MAC, message authentication code, is a shared-secret-based tag, cheaper to compute than a full signature but only verifiable by parties who hold that shared secret) so a vote is attributable to one replica and cannot be forged or replayed. PBFT's classic design uses message authentication codes between pairs in the common case for speed; HotStuff-family protocols use signatures that can be combined into a compact quorum certificate (proof that $2f+1$ replicas voted).
• Keys per node, not per cluster. If all replicas share one key, the adversary who owns one node can speak as all of them, and your $f$ becomes meaningless.
• Equivocation becomes evidence. Two signed, conflicting votes from one replica for the same round are cryptographic proof of misbehaviour you can use to eject it.
• Clients authenticate too. BFT protects agreement among replicas; it does not stop an authorised client from submitting a bad but well-formed request. Authorisation still has to happen.

Quorum composition: the part people get wrong

The $3f+1$ bound assumes faults are independent. In practice $f$ must count failure domains an adversary can control together, not boxes:

• If one cloud account, one operator team, or one software build controls two of four replicas, a single compromise yields two faults and exceeds $f = 1$.
• Common-mode failure: if every replica runs identical code, one exploited vulnerability can turn all of them Byzantine at once. BFT then protects nothing. Diversity (different operators, clouds, hardware, sometimes implementations) is what makes the bound real.
• Sybil risk: in open membership, an attacker creates many identities to exceed $f$. Permissioned membership with vetted, per-node identities avoids this; changing membership must itself go through consensus.

Multi-tenant and partially trusted environments

• Multi-tenant platform, one operator: tenants do not run replicas, so the replicas trust each other; the tenant threat is at the API, not inside consensus. Use CFT (etcd, a Raft-based store) with strict tenant authorisation.
• Consortium or cross-organisation ledger (several banks, several companies sharing a settlement log): each party runs replicas and none trusts the others. This is the canonical BFT case.
• Partially trusted hardware (edge sites, customer premises, a confidential-computing deployment, where the workload runs inside a hardware-isolated enclave specifically because the host machine itself is not trusted): a node can be physically tampered with, so treating it as potentially Byzantine is reasonable.

When should an SRE care?

Recommendation, applied honestly: use CFT unless one of these is true.

1. Replicas are operated by parties with conflicting incentives.
2. A compromise of any single node must not be able to change the agreed state (regulatory or high-value integrity requirement), and you can place replicas in genuinely independent domains.
3. The system is exposed to open membership.

What an SRE takes on with BFT: at least one more node per tolerated fault, O(n^2) message patterns in PBFT (the total messages exchanged grow roughly with the square of the replica count, fine at 4 to 20 replicas, painful at 100), signature verification CPU on every message, key management for every replica, and detection and ejection of misbehaving nodes as a routine operational task.

Trade-offs and pitfalls

• BFT is not intrusion prevention. It tolerates $f$ bad nodes; it does not detect the $(f+1)$th. You still need monitoring and fast ejection.
• Choosing BFT for an internal control plane (the layer that makes configuration and coordination decisions, as opposed to the data plane that serves user traffic) where all nodes share an admin team, deployment pipeline and image often buys cost without security, because one compromise of that pipeline takes every node. Hardening the pipeline and signing the state is the better spend.
• Crash tolerance goes down per node. With 4 nodes, BFT tolerates only 1 failure of any kind; a CFT cluster of 5 tolerates 2 crashes. If availability matters more than adversarial nodes, CFT gives you more of it per machine.

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

In an eventually consistent system, a change is written in one place and reaches other places later. For access control, that means a revocation takes effect at different times in different places, and until it arrives everywhere, some part of the system still grants the old access. The window's length is the sum of every copy of the permission along the request path: tokens, caches and replicas. The mitigation is to measure and bound each window, shorten or bypass it for high-risk actions, and accept a bounded window for low-risk ones, because making every check strongly consistent costs latency and availability the business usually will not accept.

A plain-language picture

Think of a company that revokes Bob's building badge at 9:00. The central system updates instantly, but the door at the side entrance only downloads the badge list every hour. Bob can walk through the side door until 10:00. Every cache and replica in a distributed system is a side door with its own download schedule.

Concrete examples

1. Permissions baked into a token. Bob's JWT (JSON Web Token) says role: admin and is valid for 15 minutes. At 9:00 he is demoted. Services verify the token locally and never ask anyone, so Bob remains admin until 9:15.
2. Replica lag across regions. The revocation is written to the primary policy database (the one copy that accepts writes) in one region; a replica (a read-only copy that receives changes from the primary after a short delay) in another region applies it 2 seconds later (at p99, the 99th-percentile lag). A request routed to that region in those 2 seconds is checked against the old policy.
3. Decision cache in a sidecar (a small helper process running alongside the main service on the same host, handling this kind of cross-cutting work for it). Each service caches "Bob may edit document 42" for 60 seconds. Bob's removal from the document is invisible until the cache entry expires.
4. The "new enemy" problem. Alice removes Bob from a shared folder, then uploads a confidential file into it. If Bob's check for the new file reads a stale replica that still lists him, he sees content that was only created after he lost access. The ordering of two changes (revoke, then add content) was not respected by the read. Google's Zanzibar authorization system named this problem.
5. Grant-side inconsistency. Symmetrically, a newly granted permission may not be visible yet, causing false denials: a support ticket, not a breach, but it matters when you tune caches.

Sizing the window

For the stack above, a revocation's worst case is governed by the longest path:

The token path dominates: until it is fixed, tuning the cache from 60 s to 5 s changes nothing that matters.

Mitigations, in the order I would apply them

1. Take authority out of long-lived tokens. Tokens carry identity (sub, tenant), not roles; roles are resolved at decision time. Keep token lifetime to about 5 minutes for internal tokens. The 15-minute path above becomes at most 5, and with step 3 it becomes seconds.
2. Push invalidation, with TTL as the backstop. Publish revocation events on a stream; caches evict the affected entries immediately. The TTL remains the upper bound if an event is lost, so it must still be chosen deliberately.
3. Revocation epochs. Store a per-user security epoch (a counter) that is incremented on any revocation. Tokens and cache entries record the epoch they were created under; a check rejects anything older than the current epoch, which is replicated as one small, hot value.
4. Consistency tokens for the new-enemy problem. Concretely, using the Alice and Bob example above: removing Bob from the folder is itself a policy write, so say it bumps the policy version from v106 to v107. When Alice's upload is processed, the write path stamps that file with the policy version current at that instant, v107, as a "checks on this must use a snapshot at least this fresh" watermark. Later, when Bob's client asks whether Bob can read that file, the check must run against a policy snapshot versioned >= 107; a replica still sitting on v106 is not allowed to answer it, the request either waits for that replica to catch up or is routed to one that has, so Bob's stale-replica read is refused rather than silently served from the old version. SpiceDB, an open-source Zanzibar-style system (Zanzibar is Google's large-scale permissions-checking system, described in a published paper that much of the industry's authorization tooling is now modeled on), exposes exactly this pattern as ZedTokens with an "at least as fresh" consistency mode: the version number above is the same idea under a product name.
5. Risk-tiered consistency. Reads of ordinary data use cached decisions. Money movement, permission changes, data exports and admin actions bypass caches and check against the primary (a fully consistent read).
6. Kill live sessions. On a high-severity revocation (terminated employee, compromised account), actively close websockets (persistent, long-lived two-way connections, unlike the one-request-one-response HTTP calls the rest of this system makes) and long-lived connections; a check that only runs at connection time never sees the revocation.
7. Detect what slips through. Log every decision with the policy version used; a job flags actions performed by a principal (the identity, a user or a service, that a request is attributed to) after their revocation time, so any window that was exploited is at least visible and reversible.

Performance vs security trade-offs, with numbers

Take a service handling 20,000 requests per second with a 95% cache hit rate:

• With the cache: 20,000 x 5% = 1,000 checks per second reach the policy decision point (the component that actually evaluates the policy rules and returns allow or deny, as opposed to the cache in front of it that just returns an already-computed answer).
• Remove the cache entirely: all 20,000 do, a 20x load increase, and each request gains a network round-trip. If the primary is in another region, that round-trip can be tens of milliseconds on every request, and if that region is down, every check fails.
• Risk-tiering captures most of the benefit: if 2% of requests are high-risk, strong checks add 400 per second while the other 98% stay cached.

Recommendation: identity-only tokens with 5-minute lifetimes, push invalidation with a 30-to-60-second TTL backstop, strong checks for the high-risk tier, and consistency tokens only where the new-enemy pattern exists (shared content). What would push toward stronger consistency everywhere: a regulated environment where any post-revocation access is a reportable incident.

Pitfalls

• Assuming "revoked" means "revoked everywhere now". State the worst-case window explicitly in design docs.
• Caching denies as long as allows. Cache denials briefly, or a new grant appears broken for the full TTL.
• Forgetting non-request paths: batch jobs and queued work authorised at enqueue time and executed hours later with the old permission.