Distributed Systems Security and Trust Questions

Direct answer

I would run a HotStuff-family protocol (the lineage behind DiemBFT, the consensus protocol originally built for Meta's Diem payments project, which uses a rotating leader and linear-cost leader changes) on 10 replicas, 2 per region, each operated in a separately administered failure domain. Ten replicas tolerate $f = 3$ Byzantine faults with quorums of 7, which covers a whole region going dark (2 crashed replicas) plus one malicious replica at the same time. Every vote is signed with a per-replica key held in an HSM (hardware security module), votes are aggregated into quorum certificates, a quorum certificate being a single compact proof that at least $2f+1$ replicas voted for the same thing, so nobody has to carry all their individual signatures around separately, transport is mTLS (mutual TLS), and equivocation (signing two conflicting votes) is automatically turned into evidence that ejects the replica. The price is roughly half a second of commit latency; that is per commit, not per second of throughput, because commits pipeline (explained below), so a control plane that changes configuration tens of times per second can still keep up.

Why BFT here, and why HotStuff over PBFT

The question stipulates malicious nodes, so crash-fault consensus (Raft, Paxos) is out: a single lying Raft leader can replicate forged entries. Both PBFT and HotStuff organise time into views: a view is one leader's term, during which that replica proposes and the others vote. A view change is the handoff from one leader to the next, whether that is routine (HotStuff) or triggered by a timeout on a suspected-bad leader (PBFT). Among BFT protocols:

Justification for this use case: a malicious leader is the main performance attack in BFT. It stays within the rules while being slow or dropping selected requests, so no one can prove misbehaviour. PBFT keeps a leader until replicas time out on it and then pays an expensive view change; HotStuff rotates leaders every view and makes the change cheap, so a bad leader costs one view, not an outage. At 10 replicas the message count is not the deciding factor; the cheap, routine leader change is. What would flip it: a latency-critical path (sub-100 ms commits) with a stable, trusted-hardware leader, where PBFT's fewer round trips win.

Quorum sizes

For $n$ replicas tolerating $f$ Byzantine faults you need $n \ge 3f+1$, and quorums of $2f+1$ guarantee any two quorums share at least $f+1$ replicas, so at least one honest replica is in both and blocks conflicting decisions:

Why not one replica per region (n = 5)? Then $f = 1$ and the quorum is 4 of 5: losing one region uses the entire fault budget, and a single malicious node during a regional outage breaks liveness, meaning the system stops making progress (no decision can ever reach quorum), as opposed to a safety failure where it makes a wrong decision. Why not 7 (f = 2)? With 2 replicas in some regions, one regional outage again consumes the whole budget. Ten, 2 per region, is the smallest layout that survives "one region down plus one attacker".

Performance implications (illustrative numbers)

Assume illustrative round-trip times from the current leader: about 1 ms to its regional peer, then 70, 90, 140 and 200 ms to the other four regions. The leader needs 7 votes: 2 from its own region, 2 at 70 ms, 2 at 90 ms, and the 7th from the 140 ms region. So one quorum round trip, the time for the leader to broadcast and hear back from enough replicas to reach quorum, is about 140 ms.

Where the phase multipliers come from: the message-count row above already showed each protocol's phase structure. Basic HotStuff runs three sequential voting phases (prepare, pre-commit, commit), each of which is a full quorum round trip because the leader must broadcast and then wait for $2f+1$ signed votes back before moving on, plus a final decide phase where the leader just broadcasts the completed quorum certificate and does not wait for any reply, so that phase costs about half a round trip (message travels out; no return trip is needed): $3 \times 1 + 1 \times 0.5 = 3.5$ quorum round trips. PBFT's pre-prepare is the leader's own proposal and is not itself a voted round; it only starts the clock. The prepare phase is one full quorum round trip. The commit phase, however, can complete for the client as soon as $2f+1$ commit votes are in, and because commit votes start arriving while the tail of the prepare round trip is still in flight, in the common case the two phases overlap into roughly one and a half round trips rather than two:

Both multipliers are illustrative, consistent with the phase counts above, not a formal proof; the qualitative point, that HotStuff pays roughly twice the round trips of PBFT per commit, is what drives the design trade-off below.

Throughput is decoupled from per-commit latency by pipelining: chained HotStuff starts the next proposal while the previous one is still collecting votes, so the 490 ms figure is the time for one commit to complete, not a cap on how many commits per second the system can sustain. This is an optimisation layered on top of the core protocol, not something the correctness argument depends on. Batching many control-plane writes into one proposal further raises effective throughput. Signature verification is the CPU cost; aggregating votes into one threshold signature (a single signature that only a quorum, not any individual replica, can produce, so it proves "$2f+1$ replicas signed this" without listing every signature separately) or aggregate signature (BLS, Boneh-Lynn-Shacham, signatures allow this) keeps quorum certificates compact. Put the leader-rotation schedule in region order so leaders rotate toward users rather than always paying the worst-case geometry.

Authentication and cryptographic protections

• Per-replica identity: each replica has its own signing key, generated in and never exported from an HSM or TPM (trusted platform module), and a certificate from a CA (certificate authority) dedicated to the control plane. No shared keys: a shared key lets one compromised node speak for all of them.
• Signed votes and proposals: every proposal and vote carries the view number, a block hash (a fingerprint of the exact proposed state, so a vote is provably for one specific proposal and not some other one with the same view number) and the signer's ID, so they cannot be replayed into a different view.
• Transport: mTLS between replicas prevents outsiders from injecting traffic; it does not replace vote signatures, because an insider has a valid TLS certificate.
• Client requests signed by the submitting operator or service, and authorised by policy that is itself part of the replicated state, so a malicious replica cannot invent requests.
• Membership changes go through consensus, and require the same 7-of-10 quorum, so an attacker cannot add Sybil replicas (fake identities) to grow past $f$.
• Independent domains: different operators, cloud accounts and ideally deployment pipelines per region pair. If one CI/CD (continuous integration and delivery) pipeline can push code to all 10, $f = 3$ is fiction.

Monitoring: detecting malicious nodes

Treat attributable evidence (equivocation, invalid signatures) differently from suspicion (slowness). Evidence justifies automatic ejection; suspicion only lowers a replica's leader priority and pages a human, because an attacker could otherwise induce slowness in honest nodes to get them ejected.

Recovery procedures

1. Eject: a membership-change proposal removes the replica and its key; it needs a 7-of-10 quorum. Now $n = 9$ and $f$ drops to 2, so restore the count quickly.
2. Forensics before reuse: snapshot the ejected host; assume its key is compromised, revoke its certificate and never re-admit that key.
3. Rebuild: provision a fresh replica from a clean image in the same failure domain, generate a new HSM key, and have it state-sync from a checkpoint signed by 2f+1 replicas, so it cannot be fed a forged snapshot by one bad peer.
4. Re-admit via another membership change, back to $n = 10$.
5. If more than f replicas were compromised, BFT's guarantees are gone: freeze writes, pick the last checkpoint certificate you trust, rotate every replica key, and rebuild from that checkpoint. Rehearse this, because it is the scenario the protocol cannot handle for you.

Trade-offs and pitfalls

• Common-mode compromise (one bug, one image, one admin team) defeats any replica count; diversity is a design requirement, not polish.
• Latency budget: half a second per commit is fine for configuration and policy; do not put per-request data-plane decisions through this path. The data plane reads committed state locally.
• Cost of f = 3: 10 replicas plus HSMs across five regions; if the real threat is one compromised node, not region-plus-attacker, 7 replicas is a defensible cheaper choice, and saying so shows judgement.

Direct answer

Give every workload a cryptographic identity issued by its own region's certificate authority after the platform attests what the workload is, and make every credential short-lived so rotation is continuous rather than an event. Authentication happens with mutual TLS (both sides present certificates) using those identities; authorization is a default-deny policy keyed on the caller's identity, evaluated locally. The design principle that answers "what if the identity provider is down" is: verification never needs the issuer online, and issuance is regional with enough credential lifetime left to ride out an outage.

Terms

• Workload identity: a name for a running service, for example the SPIFFE ID spiffe://prod.eu.example/ns/payments/sa/api (SPIFFE, the Secure Production Identity Framework for Everyone, is an open standard for naming workloads and issuing them certificates, called SVIDs, short for SPIFFE Verifiable Identity Document: the actual certificate or token a workload presents).
• Attestation: proving what a workload is from facts the platform controls (its Kubernetes service account, node, image) rather than from something the workload says.
• Certificate chain: a certificate is signed by the authority above it (its issuer); that issuer's own certificate is signed by the authority above it, and so on up to a root. A workload's certificate, at the bottom of that chain, is called a leaf certificate. To trust a leaf, a verifier walks the chain up to a root it already has in its trust bundle; if it has never been told about one of the intermediates in between, it cannot validate anything that intermediate signed, no matter how correctly the leaf itself was issued. That is what "chained to a CA" means, and it is why the rotation order below matters.
• Trust domain / trust boundary: the set of workloads that share a root of trust; crossing a boundary requires explicit federation: the two sides must each deliberately configure trust for specific identities in the other domain, rather than automatically trusting everything the other domain issues.
• Trust bundle: the set of CA (certificate authority) certificates a verifier accepts.

Architecture

flowchart TB
  ROOT[Offline root CA] --> ICA1[Intermediate CA: region EU]
  ROOT --> ICA2[Intermediate CA: region US]
  ICA1 --> AG1[Node agents EU clusters]
  ICA2 --> AG2[Node agents US clusters]
  AG1 --> W1[Workload certs, 24h]
  AG2 --> W2[Workload certs, 24h]
  PAP[Policy repo] --> PE1[Local policy check EU]
  PAP --> PE2[Local policy check US]

Token and credential issuance

1. A node agent (a small process the platform runs on every host, distinct from the application itself) attests the workload using facts it can verify locally: its Kubernetes service account, its namespace (a Kubernetes grouping boundary that scopes and isolates related workloads), and its image digest (a cryptographic hash identifying the exact container image build, so a tampered or swapped image gets a different identity). It then requests a certificate from the regional intermediate CA.
2. The workload receives an X.509 certificate (X.509 is the standard format essentially every TLS certificate uses) valid for 24 hours, with its SPIFFE ID in the subject alternative name, a field in the certificate that states which identity or identities it is valid for.
3. For calls that also need application-level claims (user on whose behalf, audience), a regional token service issues JWTs (JSON Web Tokens: compact, signed tokens that carry a set of claims, such as who the caller is and who the token is for) valid for 5 minutes with an audience claim, signed with a key whose public half is distributed alongside the trust bundle.

Short-lived credentials and outage tolerance, with numbers

Agents renew a certificate when 50% of its lifetime remains. The worst case for an issuer outage is that it starts at the moment renewal was due, so the tolerance is the remaining lifetime at the renewal point:

Commit to 24 hours for certificates. Twelve hours of outage tolerance is long enough to fix a broken CA across a night, and a day is a tolerable exposure window when combined with the other controls. Load is trivial: 50,000 workloads renewing every 12 hours is 50,000 / 43,200 s, about 1.2 issuances per second. The JWT layer stays at 5 minutes because it carries user context, where faster expiry matters more.

Certificate and key rotation

• Leaf certificates rotate continuously by construction.
• Intermediate CAs rotate every few months by overlap: add the new intermediate to trust bundles first, wait until every verifier has the updated bundle, then start issuing from it, and remove the old one only after the last certificate it signed has expired (24 hours plus margin). Reversing that order causes an outage because verifiers reject certificates chained to a CA they have not been told about.
• The root is kept offline in an HSM (hardware security module) and used only to sign intermediates. Root rotation is the same add-then-switch-then-remove sequence stretched over weeks.
• JWT signing keys rotate the same way, publishing the new public key before signing with it.

Trust boundaries

• One trust domain per region (or per environment), not one global domain. A compromised EU intermediate lets an attacker mint EU identities only.
• Cross-region calls use federation: US verifiers are explicitly configured to accept the EU bundle, for specific identities. The US payments service accepts spiffe://prod.eu.example/ns/checkout/sa/api and nothing else from EU.
• Staging and production never share a root. This is the most common real-world boundary failure.

Least-privilege authorization

Policies are written against identities, not network addresses: "payments accepts calls from checkout on POST /charges; everything else is denied". Policies live in version control, are compiled and pushed to a local enforcement point in every workload (a sidecar, a helper process deployed alongside the application container, or a library linked into the application itself), and are evaluated without a network call. New services start with zero inbound permissions and receive them through review. Every allow and deny is logged with caller identity and policy version.

Fallback when the identity provider is down

Walk through what depends on the issuer:

What we deliberately do not do: fall back to a long-lived static shared secret, or disable mTLS. Both turn an availability incident into a security incident. If the outage outlasts the 12-hour tolerance, the controlled response is an emergency extension: issue longer-lived certificates from a standby intermediate held for this purpose, logged and time-boxed.

Operational practices for key management

• Private keys for leaf certs are generated on the host and never leave it; only CSRs (certificate signing requests) travel.
• CA keys live in HSMs or a cloud KMS (key management service); root operations require two people (dual control) and are recorded.
• Monitor: certificate time-to-expiry across the fleet (alert when any workload is under 25% of lifetime), issuance error rates, and bundle version per verifier.
• Rehearse a compromised intermediate: revoke it by removing it from bundles, re-issue the region's workloads from a fresh intermediate, and measure how long that takes. That measured time is your real recovery objective.

Trade-offs and pitfalls

• Short lifetimes replace revocation lists. Certificate revocation lists and OCSP (Online Certificate Status Protocol) checks are rarely reliable at mesh scale (the scale of a service mesh, the network of many services all calling each other over these short-lived certificates); expiry is. The cost is issuer availability, which the table above quantifies.
• Regional isolation costs federation configuration. It is worth it: it bounds a CA compromise to one region.
• Clock skew breaks short-lived credentials. Allow a small skew tolerance (a minute or two) and monitor time sync.
• Common wrong turn: authorizing by IP or namespace label. Those change with every reschedule; identities do not.

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.

Direct answer

A safe rotation tool is a small state machine with a durable journal. The tool moves through four recorded states: rotating while it is still pushing the new secret out, complete once every service has confirmed it, or, if something fails, rolling_back while it undoes a partial rotation, and rolled_back once every changed service is back on its old secret. In practice: mint the new secret once and record it, snapshot every service's current secret and version, roll out to a small canary group and validate, then roll out in batches with validation after each, and on any failure roll every changed service back. Idempotence (running the same rotation twice has the same effect as running it once) comes from the journal: a retry with the same rotation ID reuses the same secret, skips services already done, and never re-runs a finished rotation. Concurrency safety comes from a lease (a time-limited right to be the only actor allowed to run a rotation, that automatically expires if its holder crashes without releasing it) so only one rotation runs at a time, plus a compare-before-write that detects anyone else changing a secret mid-rotation. Rollback writes the old secret under a new, higher version so caches treat it as the newest value.

Assumptions the interface leaves open

• get_secret(service) returns a (secret, version) tuple with an integer version.
• put_secret is not conditional (no compare-and-set), so the tool re-reads before each write and relies on a lease to be the only rotator. If the real store supports a conditional put, use it instead; it closes the small window between read and write.
• Because this is a shared symmetric secret (the same key used by multiple services, for example to sign internal requests with HMAC, a hash-based message authentication code), services will be on different secrets during the rollout. That is only safe if each service accepts both the current and the previous secret while rotating. That dual-accept behaviour belongs in the services, and the canary is what proves it works.
• rotation_id, store and journal are added as keyword arguments; the positional signature is as specified.

Design

Code

import math, secrets, threading
from typing import Callable, Dict, List, Optional


class SecretStore:  # the interface given in the question
    def get_secret(self, service_name): pass
    def put_secret(self, service_name, secret, version): pass
    def validate_service(self, service_name, secret) -> bool: pass


class RotationInProgress(Exception): pass
class ConflictError(Exception): pass
class RotationFailed(Exception): pass


class Journal:
    """Durable rotation state. In production: a DB row per rotation, updated with
    conditional writes. Here: a dict guarded by a lock, plus a single rotation lease."""
    def __init__(self):
        self.records: Dict[str, dict] = {}
        self.lease_holder: Optional[str] = None
        self.mu = threading.Lock()

    def acquire(self, rotation_id: str):
        with self.mu:
            if self.lease_holder not in (None, rotation_id):
                raise RotationInProgress(f"rotation {self.lease_holder} holds the lease")
            self.lease_holder = rotation_id

    def release(self, rotation_id: str):
        with self.mu:
            if self.lease_holder == rotation_id:
                self.lease_holder = None


def _put_if_unchanged(store, svc, expected_version, secret, version):
    """Compare-then-put. The given interface has no compare-and-set, so the lease makes
    us the only rotator and this re-read catches writers that bypass the tool."""
    current = store.get_secret(svc)
    if current == (secret, version):
        return  # already done by an earlier attempt: retry-safe no-op
    if current[1] != expected_version:
        raise ConflictError(f"{svc}: expected v{expected_version}, found v{current[1]}")
    store.put_secret(svc, secret, version)


def rotate_secret(services: List[str], new_secret_generator: Callable[[], str],
                  canary_fraction: float = 0.05, *, store: SecretStore,
                  journal: Journal, rotation_id: str, batch_size: int = 10) -> dict:
    journal.acquire(rotation_id)
    try:
        rec = journal.records.get(rotation_id)
        if rec is None:  # first attempt: snapshot the old state and mint the secret ONCE
            prev = {s: store.get_secret(s) for s in services}
            rec = {"secret": new_secret_generator(), "prev": prev,
                   "target": {s: prev[s][1] + 1 for s in services},
                   "done": [], "state": "rotating"}
            journal.records[rotation_id] = rec
        if rec["state"] in ("complete", "rolled_back"):
            return rec  # a retry of a finished rotation changes nothing
        if rec["state"] == "rolling_back":  # died mid-rollback: finish it, never resume forward
            _rollback(store, rec)
            rec["state"] = "rolled_back"
            return rec

        ordered = sorted(services)  # deterministic order so retries resume, not reshuffle
        n_canary = max(1, math.ceil(canary_fraction * len(ordered)))
        waves = [ordered[:n_canary]] + [ordered[i:i + batch_size]
                                        for i in range(n_canary, len(ordered), batch_size)]
        try:
            for wave in waves:
                for svc in wave:
                    if svc in rec["done"]:
                        continue
                    _put_if_unchanged(store, svc, rec["prev"][svc][1], rec["secret"], rec["target"][svc])
                    rec["done"].append(svc)  # journal AFTER the put succeeds
                bad = [s for s in wave if not store.validate_service(s, rec["secret"])]
                if bad:
                    raise RotationFailed(f"validation failed on {bad}")
        except (RotationFailed, ConflictError) as e:
            rec["state"], rec["error"] = "rolling_back", str(e)  # journal the decision first
            _rollback(store, rec)
            rec["state"] = "rolled_back"
            return rec
        rec["state"] = "complete"
        return rec
    finally:
        journal.release(rotation_id)


def _rollback(store, rec):
    for svc in reversed(rec["done"]):
        old_secret, old_version = rec["prev"][svc]
        # Restore the OLD value under a NEW, higher version so every cache treats it as newest.
        store.put_secret(svc, old_secret, rec["target"][svc] + 1)


# ---------------- driver: an in-memory store with injectable faults ----------------
class FakeStore(SecretStore):
    def __init__(self, services):
        self.data = {s: ("initial-secret", 1) for s in services}
        self.puts = 0
        self.reject = set()        # services whose validation fails
        self.crash_on = set()      # services whose next put "crashes the process"
        self.on_validate = None    # hook to interleave another actor
    def get_secret(self, s): return self.data[s]
    def put_secret(self, s, secret, version):
        if s in self.crash_on:
            self.crash_on.discard(s)
            raise ConnectionError(f"process died while writing {s}")
        self.puts += 1
        self.data[s] = (secret, version)
    def validate_service(self, s, secret):
        if self.on_validate: self.on_validate(s)
        return s not in self.reject and self.data[s][0] == secret


SERVICES = [f"svc-{i:02d}" for i in range(40)]
calls = {"n": 0}
def gen():
    calls["n"] += 1
    return f"secret-{calls['n']}-" + secrets.token_hex(4)

def summary(store):  # count services per (secret, version); random suffix hidden
    counts = {}
    for sec, v in store.data.values():
        key = (sec.rsplit("-", 1)[0] if sec.startswith("secret-") else sec, v)
        counts[key] = counts.get(key, 0) + 1
    return dict(sorted(counts.items()))

print("1. happy path")
st, j = FakeStore(SERVICES), Journal()
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-A")
print("  state:", r["state"], "| puts:", st.puts, "| generator calls:", calls["n"], "|", summary(st))

print("2. retry of the same rotation id")
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-A")
print("  state:", r["state"], "| puts:", st.puts, "| generator calls:", calls["n"])

print("3. canary fails validation")
calls["n"] = 0
st, j = FakeStore(SERVICES), Journal()
st.reject = {"svc-01"}
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-B")
print("  state:", r["state"], "|", r["error"], "| puts:", st.puts, "|", summary(st))

print("4. crash mid-rollout, then retry")
calls["n"] = 0
st, j = FakeStore(SERVICES), Journal()
st.crash_on = {"svc-20"}
try:
    rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-C")
except ConnectionError as e:
    print("  first attempt died:", e, "| rotated so far:", len(j.records["rot-C"]["done"]))
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-C")
print("  retry state:", r["state"], "| puts:", st.puts, "| generator calls:", calls["n"], "|", summary(st))

print("5. second rotation starts while the first is running")
calls["n"] = 0
st, j = FakeStore(SERVICES), Journal()
started, finish = threading.Event(), threading.Event()
def hold_once(svc):
    if svc == "svc-00" and not started.is_set():
        started.set(); finish.wait()
st.on_validate = hold_once
t = threading.Thread(target=rotate_secret, args=(SERVICES, gen, 0.05),
                     kwargs=dict(store=st, journal=j, rotation_id="rot-D"))
t.start(); started.wait()
try:
    rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-E")
except RotationInProgress as e:
    print("  rot-E refused:", e)
finish.set(); t.join()
print("  rot-D state:", j.records["rot-D"]["state"], "| generator calls:", calls["n"], "|", summary(st))

print("6. someone else writes a secret mid-rotation")
calls["n"] = 0
st, j = FakeStore(SERVICES), Journal()
def rogue(svc):
    if svc == "svc-05":
        st.data["svc-30"] = ("hand-edited", 7)
st.on_validate = rogue
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-F")
print("  state:", r["state"], "|", r["error"], "|", summary(st))

print("7. crash during rollback, then retry")
calls["n"] = 0
st, j = FakeStore(SERVICES), Journal()
st.reject = {"svc-15"}
def crash_rollback(svc):
    if svc == "svc-15":
        st.crash_on = {"svc-07"}
st.on_validate = crash_rollback
try:
    rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-G")
except ConnectionError as e:
    print("  first attempt died:", e, "| journal state:", j.records["rot-G"]["state"])
r = rotate_secret(SERVICES, gen, 0.05, store=st, journal=j, rotation_id="rot-G")
print("  retry state:", r["state"], "|", summary(st))

Output:

1. happy path
  state: complete | puts: 40 | generator calls: 1 | {('secret-1', 2): 40}
2. retry of the same rotation id
  state: complete | puts: 40 | generator calls: 1
3. canary fails validation
  state: rolled_back | validation failed on ['svc-01'] | puts: 4 | {('initial-secret', 1): 38, ('initial-secret', 3): 2}
4. crash mid-rollout, then retry
  first attempt died: process died while writing svc-20 | rotated so far: 20
  retry state: complete | puts: 40 | generator calls: 1 | {('secret-1', 2): 40}
5. second rotation starts while the first is running
  rot-E refused: rotation rot-D holds the lease
  rot-D state: complete | generator calls: 1 | {('secret-1', 2): 40}
6. someone else writes a secret mid-rotation
  state: rolled_back | svc-30: expected v1, found v7 | {('hand-edited', 7): 1, ('initial-secret', 1): 9, ('initial-secret', 3): 30}
7. crash during rollback, then retry
  first attempt died: process died while writing svc-07 | journal state: rolling_back
  retry state: rolled_back | {('initial-secret', 1): 18, ('initial-secret', 3): 22}

The new secret contains random bytes, so summary hides the random suffix and prints how many services hold each (secret, version) pair; everything printed is deterministic.

Reading the results

1. Happy path: 40 services, ceil(0.05 x 40) = 2 canaries, then batches of 10. 40 puts, generator called once, every service on version 2.
2. Retry of a completed rotation: no additional puts and no new secret. This is the idempotence property that makes it safe for an operator or a scheduler to re-run the command.
3. Canary failure: svc-01 fails validation, so only the 2 canaries were changed. 4 puts total (2 forward, 2 rollback); those two now hold the original secret at version 3, the other 38 were never touched.
4. Crash mid-rollout: the process dies writing svc-20 after 20 services succeeded. The retry uses the journalled secret (generator still called once) and finishes with exactly 40 successful puts, because the 20 already-done services are skipped.
5. Concurrent rotations: the driver starts rot-D in a background thread and, via a threading.Event, pauses it mid-validation on the very first service, so rot-E genuinely overlaps rot-D in wall-clock time instead of just running after it. While rot-D is running, rot-E is refused by the lease instead of generating a second secret and interleaving writes.
6. Out-of-band write: someone hand-edits svc-30 during the rollout. The compare-before-write sees version 7 where it expected 1, raises a conflict, and rolls back the 30 services already rotated (svc-00 to svc-29, now at version 3). svc-30 keeps its hand-edited value because the tool never overwrites something it did not expect.
7. Crash during rollback: svc-15 fails validation after 22 services were rotated; the rollback dies partway. The journal says rolling_back, so the retry finishes the rollback (22 services at version 3, 18 untouched at version 1) rather than resuming the forward rollout.

Key points

• Journal before acting on a decision. The state is set to rolling_back before the first rollback write, and a service is added to done only after its put succeeds. Getting either order wrong makes a crash resume in the wrong direction.
• Rollback moves the version forward. Writing the old secret back at its old version 1 would look older than version 2 to any cache or consumer that keeps the highest version it has seen, and they would keep the new secret.
• Validation happens per wave, so a problem that only appears at scale (a service type the canaries did not include) is still caught before the whole fleet changes.

Complexity

O(n) store operations for n services: one snapshot read and one read-plus-write per service, plus one validation each; a rollback adds at most one write per changed service. Memory is O(n) for the journal. Runtime is dominated by validation calls, which are sequential here; running each wave's validations in parallel shortens wall time without changing the logic.

Edge cases

• canary_fraction of 0 or a single service still gets at least one canary.
• Duplicate service names in the input: deduplicate before calling, otherwise a service is counted twice in the canary math.
• A service added to the list on retry is not in the snapshot; the tool would fail with a missing key. A retry must use the same service list, or start a new rotation ID.
• The lease here dies with the process only because the demo releases it in finally. A real crash does not run finally, so a production lease needs an expiry (for example 5 minutes, renewed while working) and a fencing token (a number that increases with each new lease, which the store rejects if it is older than the last one seen), so a paused old rotator that wakes up cannot write after its lease has passed to someone else.
• Validation that is flaky (a transient timeout) causes a needless rollback; retry validation a small fixed number of times before declaring failure.

Trade-offs and pitfalls

• Rotating everything at once is simpler, but turns one bad secret format or one service without dual-accept into a fleet-wide outage.
• Generating the secret inside the per-service loop (a common bug) gives every service a different secret, which silently breaks a shared symmetric key.
• Retiring the previous secret is a separate, later step: only after every service is on the new version and has been for longer than any in-flight request or cached token can live.
• Store the journal somewhere durable and access-controlled: it contains the new secret in this demo; a production journal stores a reference to the secret in the secret store, not the value.

Direct answer

Use opaque tokens at the edge and short-lived, audience-scoped JWTs inside the mesh (the network of proxies that carries and secures service-to-service traffic across the estate), minted by a central token service through token exchange at each trust hop. The edge gateway turns the user's external token into an internal token that carries only who the user is and which service it is meant for, not every permission they hold. Downstream services authenticate the calling service with its workload identity (for example mTLS, mutual TLS where both sides present certificates), validate the internal token locally, and ask a policy decision point for fine-grained decisions, with a local sidecar cache (a small helper process deployed alongside each service instance, sharing its network so it can intercept and answer calls without a remote hop) to keep that off the latency critical path. Revocation is handled by keeping internal tokens to a few minutes and pushing revocation events for the rare cases that cannot wait.

Vocabulary first

• JWT (JSON Web Token): a signed, self-contained token. Any service holding the issuer's public key can verify it without a network call. Downside: once issued it is valid until it expires.
• Opaque token: a random string meaningful only to the issuer. Verifying it means calling the issuer (introspection, RFC 7662). Revocation is instant, but every check is a network call.
• Token exchange (RFC 8693): an OAuth 2.0 grant where a service presents a token it holds and receives a new token for a different audience, typically with narrower scope.
• PEP / PDP / PAP / PIP: the policy enforcement point (code that blocks or allows the request), policy decision point (evaluates the policy), policy administration point (where policies are authored and versioned) and policy information point (the source of attributes such as team membership).

Architecture

flowchart LR
  U[Client] -->|opaque token| GW[Edge gateway]
  GW -->|exchange| TS[Token service]
  TS -->|internal JWT aud=orders| GW
  GW -->|JWT + mTLS| O[Orders service]
  O -->|exchange for aud=payments| TS
  O -->|new JWT + mTLS| P[Payments service]
  O -.->|check| SC1[Policy sidecar]
  P -.->|check| SC2[Policy sidecar]
  PAP[Policy admin and store] -->|bundles| SC1
  PAP -->|bundles| SC2

1. Token formats: commit per boundary

Introspecting an opaque token on every internal hop does not scale: 20,000 requests per second fanning out through an average of 6 internal hops is 120,000 introspection calls per second against one service, which becomes the platform's single point of failure.

2. Token exchange for internal calls

Forwarding the user's original token unchanged through the call chain is the common anti-pattern: every downstream service receives a token that is valid at every other service (a replayable bearer credential: whoever holds the bytes can use it, with no extra proof that they are the party it was issued to), and a compromised low-value service can replay it against a high-value one.

Instead, each hop exchanges:

1. Orders receives a JWT with aud: orders.
2. To call Payments it presents that token plus its own workload identity to the token service and requests aud: payments.
3. The token service checks policy ("may orders call payments on behalf of a user?") and returns a JWT with aud: payments, the same sub (the user), and an act (actor) claim recording that orders is the intermediary. RFC 8693 defines act for exactly this delegation chain.

Payments rejects any token whose aud is not payments, so a token stolen from Orders is useless against Payments. Cost: one extra call per cross-service hop, which you cache: the exchanged token is reusable for its lifetime for the same user and audience.

3. Refresh and revocation

• Internal tokens are not refreshed; they are re-minted. They live 2 to 5 minutes, so the worst-case window in which a revoked user keeps access internally is that lifetime.
• Refresh tokens exist only between the client and the authorization server, are rotated on every use (a reused refresh token signals theft and revokes the whole family), and never enter the mesh.
• Urgent revocation (account takeover, fired employee): the auth server publishes a revocation event (sub or session ID plus a timestamp) on a stream; sidecars and gateways keep a small in-memory deny set and reject any token for that subject issued before the revocation time. The set stays small because entries can be dropped once every token issued before them has expired.

4. Minimizing token bloat

Putting a user's permissions in the token is the fastest way to break the platform. Measured by encoding real JWTs (ES256: an elliptic-curve signing algorithm producing a compact, fixed 64-byte signature, versus RS256, an RSA signature that runs 256 bytes for a 2048-bit key; compact JSON): jwt_len builds the same three parts a real token has (a header naming the algorithm and key, a claim set, and a fixed-length signature), base64url-encodes each, and adds them up, once with a bare claim set and once with a growing list of permission strings appended to it, to measure how token size scales with how many permissions ride inside it.

import base64, json

def b64url(b):
    return base64.urlsafe_b64encode(b).rstrip(b"=")

def jwt_len(claims):
    header = {"alg": "ES256", "kid": "2026-09-a", "typ": "JWT"}
    h = b64url(json.dumps(header, separators=(",", ":")).encode())
    p = b64url(json.dumps(claims, separators=(",", ":")).encode())
    sig = b64url(bytes(64))  # an ES256 signature is always 64 bytes (r || s)
    return len(h) + 1 + len(p) + 1 + len(sig)

base = {"iss": "https://auth.internal", "sub": "user:48213", "aud": "orders-api",
        "exp": 1790000000, "iat": 1789999100, "jti": "8f14e45fceea167a"}
print("minimal claims:", jwt_len(base), "bytes")
for n in (50, 200, 500):
    fat = dict(base, perms=[f"tenant-{i:04d}:orders:read" for i in range(n)])
    print(f"{n} permission strings:", jwt_len(fat), "bytes")

minimal claims: 319 bytes
50 permission strings: 2066 bytes
200 permission strings: 7266 bytes
500 permission strings: 17666 bytes

Each permission string like tenant-0004:orders:read is 23 raw characters; as one element of a JSON array that is 26 bytes (23 plus 2 quote bytes plus a comma), and base64url encoding then expands every 3 raw bytes into 4 encoded characters, a 4/3 blow-up, so each permission costs about 26 x 4/3 ~= 34.7 bytes in the final token. That matches the numbers above exactly: 200 permissions minus 50 is 7266 - 2066 = 5200 bytes over 150 permissions, 5200 / 150 ~= 34.7 bytes each. nginx's default buffer for one large request header line is 8 KB, so a user with a few hundred permissions starts getting unexplained 4xx errors at the proxy, and a 7 KB header repeated across 6 hops is 42 KB of overhead per request. The fix is structural, not compression: keep identity claims (sub, aud, exp, iat, jti, tenant, maybe a coarse role) in the token and resolve permissions at decision time from the PIP. Using ES256 rather than RS256 also helps: its signature is 64 bytes versus 256 bytes for a 2048-bit RSA key.

5. Fine-grained authorization downstream

Three options, and where each fits:

Recommendation: middleware for coarse scope checks, a sidecar PDP for most fine-grained rules, and a central relationship service only for resource-level sharing graphs. Every decision is logged with the policy version that produced it so an auditor can reconstruct why access was granted.

Trade-offs and pitfalls

• JWTs trade revocation for scale. The honest statement of the design is "internal access can outlive revocation by at most the internal token lifetime", and that lifetime is the knob.
• Token exchange adds a dependency. If the token service is down, cross-service calls fail. Run it per region, cache exchanged tokens, and treat it with the same SLO (service-level objective) as the edge.
• Do not let services mint their own internal tokens. Only the token service holds signing keys; services only verify.
• Policy drift: sidecars running stale bundles make inconsistent decisions. Export the bundle version each sidecar is running and alert when any lags the published version beyond a threshold.
• Common wrong turn: using the same token for user identity and service identity. Keep them separate: the certificate says which service, the token says which user.