Distributed Systems Security and Trust Questions
Security problems that exist because a system is distributed: keeping trust state correct while it propagates across many services, clusters and regions. Covers credential, token and certificate revocation under eventual consistency and network partitions; fleet-wide rotation of signing keys, secrets and trust anchors without outages (key rollover and grace windows, canary rotation, recovery from a compromised root); distributed authorization (replicated policy decision points, cached decisions, fail-open versus fail-closed when an auth dependency degrades); propagating caller identity and permissions through service call chains; tamper-evident audit trails across services and regions (hash chains, Merkle proofs, ordering events with imperfect clocks); Byzantine and partially trusted participants; cross-cluster and cross-organization trust federation; securing shared distributed components such as caches and message brokers against injection, replay and cross-tenant access; protecting data in transit across region boundaries; and tenant isolation as a security blast-radius boundary. Steady-state mTLS, service-mesh identity and network segmentation mechanics are covered by zero-trust service-to-service security; single-system cryptography and KMS basics by applied cryptography.
Why are tamper-evident and append-only audit logs important for a distributed system? As an SRE, describe how you would design audit logging across services and regions so logs can't be silently altered or deleted, how you'd keep events correctly ordered per entity, and what operational controls you would put in place to preserve logs during an incident.
Sample Answer
Direct answer
Audit logs are the record you use to answer "who did what, when" after something goes wrong. That makes them the first thing an attacker (or a panicking insider) wants to edit. Append-only means records can be added but never changed; tamper-evident means that if someone does change or delete a record, verification detects it. Across services and regions, the design is: each service writes events with a per-entity sequence number to a replicated log (an ordered sequence of events copied to multiple machines, so no single machine failure loses it and no single operator holds the only copy), events are chained by hashes, the chain head is regularly anchored somewhere the writers cannot modify, and the storage itself enforces retention that no operator can override.
Why it matters in a distributed system
- Forensics: after a breach you must reconstruct what happened across many services. If the log can be silently edited, you cannot trust any conclusion.
- Compliance: standards such as PCI DSS (Payment Card Industry Data Security Standard) and SOC 2 (a widely used security-controls audit report) require audit trails protected from modification.
- Distributed makes it harder: many writers, many regions, clocks that disagree, and many operators with access to some part of the pipeline.
Design
1. Making changes detectable: hash chains
Each record stores the hash of the previous record, so changing any record changes every hash after it. This short program shows what a chain catches and what it does not:
import hashlib, json
GENESIS = "0" * 64 # placeholder "previous hash" used only for the first entry, which has no real predecessor
def entry_hash(prev_hash, event):
body = json.dumps(event, sort_keys=True, separators=(",", ":"))
return hashlib.sha256((prev_hash + body).encode()).hexdigest()
def append(log, event):
prev = log[-1]["hash"] if log else GENESIS
log.append({"event": event, "prev": prev, "hash": entry_hash(prev, event)})
def verify(log):
prev = GENESIS
for i, rec in enumerate(log):
if rec["prev"] != prev or rec["hash"] != entry_hash(prev, rec["event"]):
return f"broken at entry {i}"
prev = rec["hash"]
return "ok"
log = []
append(log, {"seq": 1, "actor": "alice", "action": "role.grant", "target": "bob:admin"})
append(log, {"seq": 2, "actor": "bob", "action": "export", "target": "customers.csv"})
append(log, {"seq": 3, "actor": "alice", "action": "role.revoke", "target": "bob:admin"})
head = log[-1]["hash"]
print("clean log:", verify(log), "| head", head[:12])
# 1) edit an event in place
log[1]["event"]["target"] = "nothing.csv"
print("after edit:", verify(log))
log[1]["event"]["target"] = "customers.csv"
# 2) delete the incriminating entry and re-link the next one
forged = [log[0], dict(log[2], prev=log[0]["hash"])]
print("after delete + relink:", verify(forged))
# 3) delete it and recompute every later hash: the chain verifies again...
rebuilt = []
for rec in (log[0], log[2]):
append(rebuilt, rec["event"])
print("after full rewrite:", verify(rebuilt), "| head", rebuilt[-1]["hash"][:12])
# ...which is why the head hash must be anchored somewhere the writer cannot change
print("head matches anchored copy:", rebuilt[-1]["hash"] == head)
clean log: ok | head 1537d687119a
after edit: broken at entry 1
after delete + relink: broken at entry 1
after full rewrite: ok | head 8cf5f38f565b
head matches anchored copy: False
The third case is the important lesson: a hash chain alone does not stop someone with write access from rebuilding it. It only becomes tamper-evident when the head hash is anchored: copied every few minutes to a place the log writers cannot change (a separate account's locked storage, another organization, or a public transparency log, a shared append-only log, such as the one behind Certificate Transparency, that many independent parties can audit). This is a scale optimisation, not a change to the core idea above: instead of anchoring every single event's hash (expensive at high volume), events are batched into a Merkle tree (a tree of hashes whose single root commits to every event in the batch) and only that one root is anchored. A Merkle proof then shows a specific event was in a batch using about log2(n) hashes, which is 20 hashes for a batch of one million events, instead of handing over all one million. If your system's volume is low enough to anchor every event's hash directly, you do not need this step at all.
2. Making changes impossible at the storage layer
- Write to storage that enforces immutability, for example Amazon S3 Object Lock in compliance mode, where no user, including the account root, can delete or overwrite an object before its retention date.
- Put the audit store in a separate account owned by the security team, so compromising a production account does not grant delete rights.
- Replicate to a second region so losing one region does not lose the trail.
3. Keeping events ordered per entity
Wall clocks across servers drift by milliseconds or more, so timestamps alone cannot order two events that happened close together. Instead:
- Route all events for one entity (a user, an account, a resource) through one partition of the log. A partition is one independently ordered slice of the log; the log is split into many partitions (think separate lanes) so it can scale, and every event for a given entity ID is routed, by that ID, to the same lane every time. Within a partition, order is total: every event in that one lane has an unambiguous before-and-after position. Order is not directly comparable across two different partitions.
- The writer for that entity assigns a monotonic sequence number (1, 2, 3...). A gap reveals a missing event; a duplicate reveals a replay.
- Keep the wall-clock timestamp for humans, but use the sequence number for ordering. For causality across entities, a hybrid logical clock (a timestamp that never goes backwards and carries causal order: if event X caused event Y, Y's clock value is guaranteed to be greater than X's, so a reader can tell cause from effect even when the events sit in different partitions) is the usual addition.
In the example, seq 1, 2, 3 show that Bob's export happened while he had admin, even if the servers' clocks disagreed.
4. Operational controls during an incident
- Separation of duties: the people responding to an incident cannot delete or modify audit data; audit-store admin is a different role with its own approval.
- Legal hold: a flag placed on specific records that overrides the normal retention schedule, so declaring an incident and applying a hold guarantees those logs cannot be deleted, even by an expiry job, until the hold is explicitly lifted.
- Protect the pipeline, not just the store: agents buffer locally if the pipeline is down, and a gap in a service's sequence numbers raises an alert. An attacker's first move is often to stop logging, so "a service stopped sending audit events" is itself a high-priority alert.
- Continuous verification: a job re-verifies chains against anchored heads and pages on any mismatch.
Trade-offs and pitfalls
- Immutability versus data-protection deletion rights: you cannot delete a person's data from a compliance-locked log. Log IDs rather than personal data, or encrypt personal fields with a per-person key you can destroy.
- Per-entity ordering is cheap; global ordering is expensive. A single global sequence becomes a throughput bottleneck. Order per entity and accept that cross-entity order is approximate.
- Common wrong turn: relying on "only admins can delete". The threat model includes admins.
Design authentication and authorization propagation across hundreds of microservices. Discuss token formats (JWT vs opaque tokens), token exchange patterns for internal services, token refresh and revocation strategies, minimization of token bloat in headers, and patterns for enforcing fine-grained permissions in downstream services (authorization middleware, PDP/PAP, or policy-as-a-service).
Sample Answer
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
| Boundary | Format | Why |
|---|---|---|
| Internet client to edge | Opaque access token (or a JWT validated only at the edge) | Clients are untrusted and tokens leak (logs, browser storage); opaque tokens can be revoked instantly and reveal nothing |
| Edge to internal services | Short-lived JWT (2 to 5 minutes), signed by the internal token service | Hundreds of services each verify locally with a cached public key, so there is no per-hop call to the issuer |
| Service to service | Workload identity (mTLS certificate) plus the propagated user JWT when acting on a user's behalf | mTLS proves which service is calling; the JWT proves on whose behalf |
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:
- Orders receives a JWT with
aud: orders. - To call Payments it presents that token plus its own workload identity to the token service and requests
aud: payments. - The token service checks policy ("may orders call payments on behalf of a user?") and returns a JWT with
aud: payments, the samesub(the user), and anact(actor) claim recording that orders is the intermediary. RFC 8693 definesactfor 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 (
subor 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:
| Pattern | What it is | Use it when |
|---|---|---|
| Authorization middleware in each service | A shared library checks scopes and simple rules in-process | Coarse checks: "does this token have orders:write?" |
| Centralized PDP (policy-as-a-service) | Services call one authorization service per decision | Relationship-heavy rules ("can this user edit this document?") where the data is large and central |
| Distributed PDP: policy sidecar with pushed bundles | Policies authored centrally (PAP), compiled into bundles, pushed to a sidecar next to each service (Open Policy Agent, OPA: a widely used open-source policy engine that evaluates authorization rules written in its own policy language, is the common one) | The default for hundreds of services: sub-millisecond local decisions, no central runtime dependency |
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.
Your organization runs across 4 Kubernetes clusters, 3 cloud providers, and several third-party SaaS integrations, and needs a zero-trust architecture spanning all of them. Requirements: per-service identity, cross-org trust federation, least-privilege access, full auditability, and the ability to revoke cross-org access within 30 seconds. Describe your trust model (federated vs centralized CA), certificate issuance and attestation flows, policy enforcement points, and the SRE operational model for rotation, emergency revocation, and audits.
Sample Answer
Direct answer
Zero trust means no request is trusted because of where it comes from (inside a VPC, Virtual Private Cloud, or a cluster network); every call must prove who is calling and be checked against policy. For 4 clusters, 3 clouds and external SaaS, I would use a federated trust model: each cluster or cloud is its own trust domain with its own issuing CA (certificate authority) whose keys sit in that environment's HSM (hardware security module) or KMS (key management service), and domains trust each other by exchanging signed trust bundles, the set of CA certificates a domain has agreed to accept as valid issuers, not by sharing one global root. Workloads get short-lived, attested identities (SPIFFE IDs, a workload identity standard defined below, issued by SPIRE, its reference implementation), enforcement happens at proxies and gateways that pull policy continuously, and the 30-second cross-org revocation is met by pushing a deny policy to enforcement points and cutting live connections, because certificate revocation lists are far too slow for a 30-second promise.
Trust model: federated vs centralized CA
| Centralized CA (one root, one issuer) | Federated (one CA per trust domain, bundles exchanged) | |
|---|---|---|
| Blast radius of a CA compromise | Everything, everywhere | One domain; others drop its bundle |
| Cross-cloud latency / dependency | Every issuance crosses clouds | Issuance is local to each domain |
| Partner / SaaS fit | Partners must trust your root | Natural: they are just another trust domain |
| Operational effort | One thing to run | Bundle distribution and policy per domain |
Commit: federated, with one offline root of your own that signs each internal domain's intermediate, a subordinate CA certificate, signed by your root, that does the actual day-to-day issuing so the root itself can stay offline and rarely touched (so your own domains can share one root of trust for convenience) and separate, explicit federation relationships with external organisations, whose CAs you never chain to your root. What would flip it: a single small cloud estate with no external partners, where one CA is simpler and the blast-radius argument is weak.
SPIFFE (Secure Production Identity Framework For Everyone) is the open standard for workload identity: every workload gets an ID such as spiffe://prod.aws.example.com/ns/payments/sa/api, delivered as an SVID (SPIFFE Verifiable Identity Document), usually a short-lived X.509 certificate. SPIRE (the SPIFFE Runtime Environment) is the reference implementation that issues them and supports federation between trust domains.
flowchart TB
subgraph Org[Your organisation]
Root[(Offline root, HSM)]
A[SPIRE: AWS clusters] --- B[SPIRE: GCP cluster]
B --- C[SPIRE: Azure cluster]
Root -.signs intermediate.-> A & B & C
end
P[Partner trust domain] <-- "bundle exchange + policy" --> A
S[SaaS via OIDC federation] <-- "short-lived tokens" --> EG[Egress gateway]
A --> PEP[Envoy sidecars / gateways + policy engine]
Issuance and attestation flows
Attestation is how the issuer decides a workload deserves an identity, based on evidence it cannot fake, rather than on a secret someone copied into a config file.
- Node attestation: the SPIRE agent on a node proves what machine it is using the platform's own signed evidence, not a secret it holds itself: a Kubernetes projected service account token (a short-lived, audience-scoped token the cluster mints for that pod), an AWS instance identity document (a signed description of the EC2 instance that AWS itself vouches for), a GCP instance identity token (Google Cloud's equivalent signed statement), or an Azure managed identity (an identity Azure attaches to the VM or resource automatically, with no credential for anyone to copy). All four do the same job, prove the hardware or platform is who it claims to be, using whichever evidence that cloud or cluster natively signs.
- Workload attestation: the agent inspects the calling process (namespace, service account, image digest) and matches it to a registration entry.
- Issuance: the SPIRE server signs a short-lived SVID (1 hour here); the agent rotates it at half-life, meaning it requests a fresh one once 30 minutes (half of the 1-hour lifetime) have elapsed, so there is always a safety margin before the old one expires and workloads never hold a long-lived secret.
- To SaaS: most SaaS providers do not accept mTLS (mutual TLS: unlike ordinary TLS, both sides present a certificate and verify each other, not just the client verifying the server) from your workloads. Use OIDC workload identity federation (OIDC, OpenID Connect, is the identity layer on OAuth 2.0): the workload presents its JWT-SVID, its SPIFFE identity encoded as a JWT (JSON Web Token, a signed, self-contained token format) instead of the X.509 certificate form used inside the mesh, to the SaaS provider's or cloud's token service and receives a short-lived access token. No static API keys.
Load check: 4 clusters x 5,000 workloads each = 20,000 identities; rotating 1-hour SVIDs at half-life means 20,000 / 1,800 s, about 11 signatures per second. Trivial for any issuer; the real risk is a thundering herd, a burst of workloads all renewing at once (for example every SVID issued at the same moment during an outage recovery, so they all hit half-life together) that spikes load on the issuer, so add jitter to renewals.
Least privilege and policy enforcement points
- PEPs (policy enforcement points) are where a request is allowed or denied: Envoy (an open-source proxy) sidecars, a small proxy process deployed alongside each workload container that intercepts its traffic, or per-node proxies for east-west traffic (service-to-service calls inside the environment, as opposed to north-south traffic entering or leaving it), ingress gateways for inbound partner traffic, an egress gateway for all calls to SaaS and partners.
- Policy: authorisation rules written against SPIFFE IDs ("
payments/apimayPOST /chargeonledger"), evaluated locally by a policy engine such as OPA (Open Policy Agent), with default deny. - Distribution: policy is compiled centrally and pushed to proxies over xDS, Envoy's family of discovery APIs that lets a proxy pull its routing, cluster and policy configuration from a central control plane instead of reading a static file, so a change reaches every proxy in seconds, not on the next deploy.
Meeting 30-second cross-org revocation
X.509 revocation (CRLs, certificate revocation lists, and OCSP, the Online Certificate Status Protocol) is fetched and cached for hours, and short SVIDs of even 5 minutes cannot meet 30 seconds. So revocation is a policy action, not a certificate action:
| Step | Mechanism | Budget |
|---|---|---|
| Revoke command recorded | Control plane writes "deny trust domain partner.com" | 1 s |
| Push to all PEPs | xDS push to every proxy and gateway in all 4 clusters | p99 (99th percentile) 5 s |
| Kill existing connections | Proxies drain and close connections from/to that domain | 10 s |
| Remove federation bundle | Stop trusting the partner CA for new handshakes | in parallel |
| Verify | Synthetic partner-identity probe must get denied everywhere | 10 s |
| Total | about 26 s, inside 30 |
The connection-kill step is the one people forget: an mTLS connection established before revocation stays authenticated until closed. For outbound access to a SaaS, you cannot control the SaaS provider's revocation speed, so enforce at your own egress gateway and additionally revoke the federated credential at the provider.
SRE operational model
- Rotation: SVIDs rotate automatically; intermediates rotate yearly with overlap (new bundle published before the new intermediate issues); the offline root is used only in ceremonies requiring M-of-N key custodians (M of a set of N trusted people must each show up and jointly authorise the root's use, so no single person can act alone).
- Emergency revocation drills: run the partner-revocation play quarterly against a test trust domain and measure the 30-second SLO (service-level objective) end to end.
- Monitoring: SVID expiry histogram (anything within 10 minutes of expiry means rotation is failing), attestation failures by node type, xDS config version skew across proxies, denied-request rates by source trust domain, and bundle freshness per federated domain.
- Audit: every issuance, attestation decision, policy change and allowed/denied cross-domain call is logged with both SPIFFE IDs to an append-only store, so "who could reach what, and when" is answerable later.
Trade-offs and pitfalls
- Federation sprawl: each partner is a trust relationship to review; keep a registry with an owner and expiry date per relationship.
- Sidecar cost: a proxy per pod adds memory and latency; node-level or sidecar-less mesh modes, where one shared agent per node or the workload's own library enforces policy instead of a dedicated proxy container per pod, reduce it but concentrate more identities per enforcement point.
- Break-glass: if the policy control plane is down, proxies keep their last known policy (fail static), which is the right default, but it means revocations cannot land; alert on control-plane health as a security signal, not just an availability one.
You need to build a tamper-evident, globally-consistent audit trail for security events that supports efficient range proofs and legal requests. Requirements: per-region append-only chains, a way to verifiably merge them across regions with proofs, efficient queries for time ranges and per-entity history, and operational tooling for SREs to generate proofs for auditors. Walk through the data structures and storage backends you would use, your indexing strategy, and how you'd manage retention and proof generation.
Sample Answer
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 ⌈log2n⌉ hashes:
| Log size | Sibling hashes in an inclusion proof | Proof size (SHA-256) |
|---|---|---|
| 1,000 | 10 | 320 bytes |
| 1,000,000 | 20 | 640 bytes |
| 8.64 billion (one day at 100k events/s) | 34 | 1,088 bytes |
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
| Layer | Backend | Holds |
|---|---|---|
| Log server | A transparency-log implementation (Google's open-source Trillian is the established one) or a small custom service backed by a relational database | Leaf hashes, tree state, signed heads |
| Event payloads | Object storage with WORM (write once, read many) retention, for example S3 Object Lock in compliance mode, where no user including the account root can delete or shorten retention on a locked version | Batched event files (Parquet, a compressed columnar file format well suited to large batches of structured records), keyed by region/epoch |
| Tree tiles | Same WORM storage | Precomputed subtree hashes so proofs are generated without recomputing the tree |
| Query index | Columnar store (a database that stores each column of data together rather than each row, which is fast for aggregate and filter queries over specific fields) or search engine (ClickHouse, OpenSearch) | Pointers from (entity, time) to (region, epoch, leaf index) |
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.
Design a multi-region TLS termination strategy for a global API gateway with three goals: low latency for users, compliance with region-specific key residency rules, and the ability to provide end-to-end encryption when required. Describe where to terminate TLS (edge vs origin), your key management approach, and the SRE operational model for certificate issuance, rotation, and emergency key compromise.
Sample Answer
Direct answer
Terminate TLS at the edge by default, because a handshake with a server 20 ms away instead of 150 ms away is the biggest latency win you can buy. Then carve out two exceptions by hostname: regulated hostnames terminate only on in-region infrastructure, with their private keys held in that region's HSM (hardware security module) or cloud key management service and never exported, and end-to-end hostnames pass through the edge at layer 4 (layer 4 is the raw TCP connection: the edge forwards bytes without looking inside them, as opposed to layer 7, the HTTP level, where it can read and act on the request itself) so TLS terminates at the origin. Everything from edge to origin is re-encrypted with mutual TLS (mTLS, where both sides present certificates). Certificates are issued and rotated automatically via ACME, short-lived, with a rehearsed runbook for key compromise that can replace a certificate everywhere within an hour.
Why edge termination is the default
A new HTTPS connection costs one round trip for the TCP handshake and one for a TLS 1.3 handshake (TLS 1.2 needs two), before the first request byte is sent.
| Where TLS terminates | User RTT (round-trip time) | Setup before first request (TCP + TLS 1.3) |
|---|---|---|
| Origin in another continent | 150 ms | 2 x 150 = 300 ms |
| Edge PoP (point of presence) nearby | 20 ms | 2 x 20 = 40 ms |
The edge then reuses warm, long-lived connections to the origin (connections it keeps open and shares across many users' requests instead of opening and tearing one down per request), so the user never pays the long round trips for setup. Terminating at the edge also lets the edge do its layer 7 jobs: WAF (web application firewall) rules, rate limiting, caching, routing by path.
The cost: at the point of termination, traffic is plaintext in the edge's memory, and the edge holds (or can use) the private key. That is exactly what residency and end-to-end requirements object to.
The three tiers
flowchart LR
U[User] --> E{Edge PoP}
E -- "default: terminate, WAF, re-encrypt mTLS" --> O1[Origin any region]
E -- "regulated host: geo-pinned, in-region PoP only" --> R[In-region edge] --> O2[In-region origin]
R -. "signing request" .-> H[(In-region HSM / KMS key)]
E -- "e2e host: L4 passthrough by SNI" --> O3[Origin terminates TLS]
Tier 1: default (most APIs)
Terminate at the nearest PoP; keys are distributed to the edge fleet encrypted, decrypted only in memory. Re-encrypt to the origin with mTLS using an internal CA (certificate authority, the service that signs certificates), so a network observer between edge and origin sees nothing and the origin rejects anything that is not the edge.
Tier 2: key residency (for example, EU-regulated customers)
Two separate requirements get conflated here; separate them in the interview:
- Key residency: the private key must not leave the region. Solve it with remote signing: the edge performs the handshake, but the one operation that needs the private key (signing the handshake) is sent to a key server inside the region, backed by an HSM. The key never leaves. Several CDNs (content delivery networks) offer this as a product; you can also build it.
- Data residency: the decrypted traffic must not be processed outside the region. Remote signing alone does not satisfy this, because session keys (the symmetric keys the handshake negotiates, and that actually encrypt and decrypt the real traffic afterward) and plaintext still exist at whichever PoP terminated the connection. For that, route the regulated hostnames so termination only happens in-region, restricted to in-region PoPs via geo-DNS (DNS that returns a different answer depending on where the query came from) or anycast (one IP address announced from many PoPs, where the network itself routes each user to the nearest one).
Commit: for regulated hostnames, do both. The latency cost is small for users who are in the region, which is almost everyone the regulation covers; out-of-region users pay the longer round trip, and that is the price of compliance.
Tier 3: end-to-end encryption when required
Options, in order of preference for a strict "the edge must never see plaintext" requirement:
- Layer 4 passthrough: the edge reads only the SNI (server name indication, the hostname sent in clear in the TLS ClientHello, the very first message a client sends to start a TLS handshake, before anything is encrypted) and forwards the encrypted bytes to the origin, which terminates TLS. You lose edge caching, WAF and path routing for that host; move WAF and rate limiting to the origin.
- Application-layer encryption: keep edge termination, but encrypt sensitive payload fields with a key only the origin holds (for example JWE, JSON Web Encryption). The edge still routes by headers. Good for specific fields (card numbers, health data), not whole APIs.
"Re-encrypt at the edge" is not end-to-end, even though it is encrypted everywhere on the wire; say that explicitly.
Key management
- One key pair per hostname group (a set of hostnames that share a certificate and routing tier, for example all default-tier API hosts together) per region; no global wildcard certificate (one certificate valid for every hostname under a pattern like
*.example.com) whose key lives on every PoP (one leak compromises everything). - Regulated keys: generated inside the regional HSM, non-exportable, usable only by the regional key server's identity.
- Default-tier keys: generated centrally, wrapped (encrypted) under a per-region key-encryption key held in KMS, and unwrapped only in PoP memory.
- Internal mTLS between edge and origin uses a separate private CA with short-lived certificates (hours to days), so revocation is rarely needed.
SRE operational model
Issuance and rotation
- Automate with ACME (Automatic Certificate Management Environment, RFC 8555), the protocol public CAs use for automated issuance, and treat any manual step as a defect. The CA/Browser Forum has voted to shrink the maximum public certificate lifetime in steps from 398 days to 47 days between March 2026 and March 2029, so manual renewal will not survive.
- Renew at about two thirds of lifetime; roll out new certificates region by region with a canary PoP; keep the previous certificate deployable for fast rollback.
- Use two public CAs, pre-authorised via DNS CAA records (which list the CAs allowed to issue for your domain), so a CA outage or distrust event does not block renewal.
- Monitor: days-to-expiry for every certificate on every PoP (alert at 14 days, page at 7), handshake failure rate by PoP and by certificate, and Certificate Transparency logs for certificates issued for your domains that you did not request.
Emergency key compromise
A worked timeline, assuming a default-tier key leaked from one PoP:
- 0 to 15 minutes: generate a new key and CSR (certificate signing request); request a new certificate from the backup-ready CA; isolate the PoP.
- 15 to 45 minutes: deploy the new certificate to all PoPs holding that hostname group, canary first.
- After deployment: ask the CA to revoke the old certificate with reason key compromise. Revoke after the new one is live, or you cause an outage. Browser revocation checking is unreliable: most browsers "soft-fail," meaning that if the revocation check itself times out or the network is unreachable, they treat the certificate as valid rather than blocking the page, and many skip the check for performance reasons in the first place. So a revoked certificate often keeps working for whoever already has it cached, and containment really comes from replacement and short lifetimes, not revocation.
- Follow-up: find how the key left, and check whether other keys shared the same exposure path.
For regulated keys in an HSM, "compromise" usually means misuse of the signing service rather than key theft: revoke the offending identity's access to the key server first, then rotate.
Trade-offs and pitfalls
- Treating remote signing as data residency is the most common wrong answer.
- Passthrough everywhere for simplicity throws away the edge's security controls; use it only on hosts that require it.
- Certificate pinning in mobile clients (hard-coding, inside the app, exactly which certificate or public key it will accept, instead of trusting any certificate a public CA has signed) turns routine rotation into an outage; pin to a CA or public key set with a backup, or do not pin.
- What would flip the design: if nearly all traffic were from one region with strict residency, a regional-only termination model (no global edge) becomes simpler and loses little latency.
Unlock Full Question Bank
Get access to all 12 Distributed Systems Security and Trust interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.