Design a tamper-evident audit log
Design the audit trail that records who did what across a company's systems so that any later edit, deletion or truncation can be detected: authenticated ingestion, hash chains and Merkle trees, signed checkpoints held by someone else, write-once storage and seven years of queries.
01Understand the problem and size it
- Tell tamper-proof (cannot be changed) from tamper-evident (changes are detected) and design for the second
- Build a hash chain and see why it cannot detect truncation without external checkpoints
- Use a Merkle tree for short inclusion and consistency proofs at billions of entries
- Combine authenticated ingestion, write-once storage and signed checkpoints held outside the operator's control
What they probe: who you are defending against (often an insider with admin rights), what exactly a hash chain proves, how a verifier knows the log was not rolled back, how you prove a single entry is present without replaying billions. Where candidates slip: "we store it in an append-only table", hashes kept in the same database they protect, no answer for deleting the last hour of entries.
An audit log records security-relevant actions: who logged in, who changed a permission, who exported customer data, who approved a payment. Auditors, incident responders and courts rely on it, so the hard requirement is integrity: an administrator, or an attacker with administrator rights, must not be able to quietly remove the entry that shows what they did.
Functional requirements
- Services send audit events; the log accepts them only from authenticated services.
- Entries can never be edited or deleted before retention ends, and any attempt is detectable.
- Anyone with access can verify that a given entry is present and that the log has only grown.
- Investigators query by actor, resource, action and time.
Non-functional requirements
- 2,000 events/s average across the company.
- Retention 7 years.
- Ingestion acknowledgement within 1 s; an acknowledged event is never lost.
- Verification keeps working even if the log operator is compromised.
events 2,000 / s x 1 kB = 2 MB/s
per day 2 MB/s x 86,400 ≈ 173 GB raw, ~35 GB compressed (5:1)
7 years 35 GB x 365 x 7 ≈ 89 TB compressed
entries in 7 years 2,000 x 86,400 x 365 x 7 ≈ 4.4 x 10^11
Merkle proof length log2(4.4 x 10^11) ≈ 39 hashes x 32 B ≈ 1.25 kB
checkpoint cadence one signed tree head per minute = 525,600 per year02High-level design
- Ingestion: services authenticate with mTLS; the API records the caller's identity in the event (the service cannot claim to be another). The event goes to a replicated stream before the API acknowledges.
- Sequencer: one writer per log assigns a monotonic sequence number and server timestamp, computes the leaf hash and appends it to the Merkle tree.
- Storage: batches go to object storage with Object Lock in compliance mode, so even the account's root user cannot delete them before retention ends.
- Checkpoints: every minute the sequencer signs a tree head (tree size plus root hash) and sends it to witnesses: a separate cloud account owned by another team, an external timestamping service, or both.
- Query: a search index built from the batches. It is a convenience copy; proofs always come from the tree.
A hash chain, and its weakness
import { createHash } from "node:crypto";
interface Entry { seq: number; body: string; prevHash: string; hash: string }
const h = (s: string) => createHash("sha256").update(s, "utf8").digest("hex");
export function append(prev: Entry | null, body: string): Entry {
const seq = prev ? prev.seq + 1 : 0;
const prevHash = prev ? prev.hash : "0".repeat(64);
return { seq, body, prevHash, hash: h(seq + "|" + prevHash + "|" + body) };
}
/** Detects edits and deletions in the middle. Cannot detect the tail being cut off. */
export function verify(entries: Entry[], trustedHeadHash?: string): boolean {
for (let i = 0; i < entries.length; i++) {
const e = entries[i];
const prevHash = i === 0 ? "0".repeat(64) : entries[i - 1].hash;
if (e.seq !== i || e.prevHash !== prevHash || e.hash !== h(e.seq + "|" + prevHash + "|" + e.body)) return false;
}
// Only an externally held head proves nothing was removed from the end.
return trustedHeadHash === undefined || entries.at(-1)?.hash === trustedHeadHash;
}Changing entry 500 changes its hash, which breaks entry 501's prevHash, and so on. But an attacker can delete the last 100 entries, or recompute the whole chain after an edit, and the chain still verifies. Only a head hash stored somewhere the attacker cannot reach detects that.
03Deep dive: Merkle trees and proofs
A Merkle tree hashes entries in pairs, then pairs of those hashes, up to a single root. Certificate Transparency logs (RFC 6962, with version 2.0 in RFC 9162) use exactly this structure, and it gives two proofs a hash chain cannot give cheaply:
| Proof | Question it answers | Size |
|---|---|---|
| Inclusion (audit path) | Is entry N in the tree whose root is R? | About log2(n) hashes: 39 for 4.4 x 10^11 entries |
| Consistency | Is the tree of size n2 an append-only extension of the tree of size n1? | About log2(n2) hashes |
- A verifier that saw yesterday's signed head can ask for a consistency proof to today's head. If anything was removed or changed, no valid proof exists.
- An investigator can prove to a court that a specific entry was in the log at a given checkpoint with a 1.25 kB inclusion proof, without handing over the log.
- The operator signing two different heads for the same tree size is proof of misbehaviour, which is why heads go to several witnesses who compare notes.
Who holds the checkpoints
| Witness | Protects against | Cost |
|---|---|---|
| Separate cloud account, different admins | A single compromised admin | Cheap; same company |
| RFC 3161 timestamping authority | Backdating, and proves when a head existed | Per-request fee, external dependency |
| Publishing heads publicly or to a partner | The whole company rewriting history | Reveals log size and rate |
If the root hashes live in the same database, with the same admins, an attacker rewrites both. Tamper evidence comes from separation: the checkpoint must be in a different trust domain from the log.
04Failure modes and trade-offs
| Failure | Behaviour | Why |
|---|---|---|
| Sequencer crash | Standby takes over from the last durable tree state; stream retains unsequenced events | Single writer keeps ordering simple; failover must never fork the tree |
| Witness unreachable | Keep signing heads locally, queue them, alert | A gap in checkpoints widens the undetectable window |
| Signing key compromise | Key in an HSM or KMS, rotate, publish key change as a logged event | A stolen key lets someone sign a fake history |
| Service sends personal data | Schema checks reject free-text fields marked sensitive; pseudonymise user IDs | Immutable for 7 years makes deletion impossible |
| Clock skew between services | Store both service time and sequencer time; order by sequence | Timestamps are claims, sequence numbers are facts |
| Choice | Gain | Cost |
|---|---|---|
| Merkle tree vs plain hash chain | Logarithmic proofs, consistency checks | More code; still need checkpoints |
| Object Lock compliance vs governance mode | Nobody can delete, including root | Mistakes are also undeletable until retention ends |
| Single sequencer | Total order, simple proofs | Throughput ceiling; shard into several logs by tenant if needed |
GDPR erasure and seven-year immutability collide. Log stable pseudonymous IDs rather than names and emails, keep the mapping in a deletable table, and encrypt any unavoidable personal fields with keys you can destroy.
05Final design, follow-ups and self-test
"I'd aim for tamper-evident, not tamper-proof. Services send events over mTLS and the ingestion API stamps the caller's identity, so nobody writes as someone else. A single sequencer appends each event to a Merkle tree, the same structure Certificate Transparency uses, and writes batches to object storage under compliance-mode Object Lock. Every minute it signs the tree head and sends it to witnesses outside our admins' reach. That gives me 39-hash inclusion proofs for any entry over seven years, and consistency proofs that show the log only grew, which is what a hash chain alone cannot show if someone trims the tail."
Q1Why not use a blockchain?+
You need an append-only structure and independent witnesses, not a consensus protocol among strangers. A Merkle log with signed checkpoints gives the same evidence at a fraction of the cost and latency.
Q2How would an auditor verify the log without trusting you?+
They keep copies of signed heads over time, request consistency proofs between them, and request inclusion proofs for sampled entries, checking signatures against your published key.
Q3How do you scale beyond one sequencer?+
Run one log per tenant or per region, each with its own tree and heads, and optionally a top-level tree over their heads.
An admin deletes the final 200 entries of a hash-chained audit log and keeps the rest unchanged. What detects it?
Related lessons
- Design a tamper-evident audit logLLD · Problems: Advanced componentsPro
- TLS and PKI in practiceSecEng · Network & Infrastructure SecurityFree
- Design a global certificate issuance and rotation serviceHLD · Design problems: global security control planesPro
- Design a secrets managerHLD · Design problems: Infrastructure & dataPro