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.

● MediumFREEBy ·Design problem·14 min read·Beginner → Intermediate
audit logtamper evidencehash chainMerkle treeWORM storagetransparency log

01Understand the problem and size it

✓What you will learn
  • 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
◎Interview radar

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

  1. Services send audit events; the log accepts them only from authenticated services.
  2. Entries can never be edited or deleted before retention ends, and any attempt is detectable.
  3. Anyone with access can verify that a given entry is present and that the log has only grown.
  4. Investigators query by actor, resource, action and time.

Non-functional requirements

  1. 2,000 events/s average across the company.
  2. Retention 7 years.
  3. Ingestion acknowledgement within 1 s; an acknowledged event is never lost.
  4. Verification keeps working even if the log operator is compromised.
Sizingtxt
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 year
▭On the whiteboard · Scope3 points
01
FR
authenticated append | no edit or delete, changes detectable | inclusion + consistency proofs | query
02
NFR
2k events/s | 7 years | ack < 1 s, never lost | verifiable if operator compromised
03
out
what each service chooses to log, SIEM detection on top

02High-level design

  1. 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.
  2. Sequencer: one writer per log assigns a monotonic sequence number and server timestamp, computes the leaf hash and appends it to the Merkle tree.
  3. 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.
  4. 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.
  5. 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

Hash chain: each entry commits to everything before itts
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.

▭On the whiteboard · Core3 points
01
ingest
mTLS, caller identity stamped, stream before ack
02
sequence
single writer, Merkle append, signed tree head each minute
03
keep
Object Lock compliance mode, witnesses in another trust domain

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:

ProofQuestion it answersSize
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
ConsistencyIs 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

WitnessProtects againstCost
Separate cloud account, different adminsA single compromised adminCheap; same company
RFC 3161 timestamping authorityBackdating, and proves when a head existedPer-request fee, external dependency
Publishing heads publicly or to a partnerThe whole company rewriting historyReveals log size and rate
!Hashes next to the data prove little

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

FailureBehaviourWhy
Sequencer crashStandby takes over from the last durable tree state; stream retains unsequenced eventsSingle writer keeps ordering simple; failover must never fork the tree
Witness unreachableKeep signing heads locally, queue them, alertA gap in checkpoints widens the undetectable window
Signing key compromiseKey in an HSM or KMS, rotate, publish key change as a logged eventA stolen key lets someone sign a fake history
Service sends personal dataSchema checks reject free-text fields marked sensitive; pseudonymise user IDsImmutable for 7 years makes deletion impossible
Clock skew between servicesStore both service time and sequencer time; order by sequenceTimestamps are claims, sequence numbers are facts
ChoiceGainCost
Merkle tree vs plain hash chainLogarithmic proofs, consistency checksMore code; still need checkpoints
Object Lock compliance vs governance modeNobody can delete, including rootMistakes are also undeletable until retention ends
Single sequencerTotal order, simple proofsThroughput ceiling; shard into several logs by tenant if needed
iImmutable plus personal data

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

▭On the whiteboard · Final design3 points
01
ingest
mTLS services, identity stamped, durable stream, ack < 1 s
02
integrity
single sequencer, Merkle tree, signed head every minute to witnesses in another trust domain
03
retain
WORM object storage 7 years, query index as a copy, proofs from the tree
“How to say it in the room

"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.

Test yourself

An admin deletes the final 200 entries of a hash-chained audit log and keeps the rest unchanged. What detects it?

Finished this one?
Tick it and it shows as done on the roadmap and the course.