Hash chains & transparency logs

Understand append-only hash-chained logs and why they are tamper-evident, how transparency systems like Certificate Transparency (RFC 6962 / 9162) make a log publicly auditable, and how to apply the same construction to agent audit trails.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Hash functions · Merkle trees · Digital signatures

An ordinary log can be edited after the fact — rows deleted, timestamps changed, entries inserted — and nothing about the file reveals it. A hash chain makes tampering evident. Each entry includes the hash of the previous entry, so entries are linked like a chain: altering any past entry changes its hash, which changes every hash after it, which breaks the link to the latest value everyone has seen. You cannot quietly rewrite history; you can only break the chain, which is detectable. This turns a log into tamper-evident evidence, the foundation of trustworthy audit trails.

There are two related constructions, often combined.

Hash chain (linked log)

Each entry stores head_i = H(head_{i-1} || entry_i). The latest head commits to the entire ordered history; one tampered entry invalidates every subsequent head.

Merkle / transparency log

Entries are leaves of a Merkle tree whose signed root (a Signed Tree Head) is published. This adds inclusion proofs (an entry is in the log) and consistency proofs (a newer root is an append-only extension of an older one — nothing was removed or rewritten).

Equivocation / split view

A dishonest log showing different histories to different observers. Transparency defends against it through gossip: observers compare the signed heads they saw, so a split view is eventually caught.

The key upgrade from a bare chain to a transparency log is the consistency proof: it lets a verifier confirm that version N+k of the log strictly extends version N (same prefix, only appends) in logarithmic work — so even the operator cannot retroactively edit accepted history without detection.

The chain itself is a one-line recurrence; transparency wraps it with a signed Merkle root and append-only consistency checks.

hash chain + signed tree head (schematic)
# Append-only hash chain
head_0 = H("genesis")
head_i = H( head_{i-1} || canonical(entry_i) )     # link each entry to the last

# Tamper check: a verifier who recorded head_j earlier can replay entries
# j+1..k and confirm they still reproduce the current head_k. Any edit to an
# entry <= k changes head_k and fails the check.

# Transparency layer (RFC 6962 style):
root_n = merkle_root(entries[0..n])
STH    = Sign(log_sk, { size:n, root:root_n, time:t })   # Signed Tree Head
#   inclusion proof : entry e is a leaf under root_n            (~log n hashes)
#   consistency proof: root_m is a prefix-extension of root_n   (~log n hashes)

Signing the tree head matters: without a signature, an attacker who controls the log can present a fresh self-consistent chain. The signature binds each published head to the log’s identity, and consistency proofs bind each new head to the old one, so the only way to cheat is to equivocate — which gossip between independent observers is designed to expose.

1. 1Canonicalize each entry and append it, computing head_i = H(head_{i-1} || entry_i).
2. 2Periodically build a Merkle tree over the entries and publish a Signed Tree Head (size, root, time), signed by the log.
3. 3Give writers an inclusion proof so they can confirm their entry was actually incorporated under a published root.
4. 4Have verifiers request a consistency proof between any two heads to confirm the newer one only appended — nothing was rewritten or removed.
5. 5Have independent observers (auditors, monitors) gossip the STHs they see and compare them, so an operator showing split views is detected.
6. 6Anchor or distribute heads widely (sign them, publish them, or cross-log them) so a trusted reference point exists outside the operator.

Certificate Transparency (CT), specified in RFC 6962 and updated by RFC 9162, is the canonical deployed transparency system. CAs submit every certificate they issue to public append-only Merkle logs, which return a signed promise of inclusion. Browsers and independent monitors watch these logs, so a certificate mis-issued for a domain cannot stay hidden — the domain owner can see it in the public log. CT does not prevent mis-issuance; it makes mis-issuance publicly detectable, which changed CA behavior across the web.

synthetic — the CT pattern applied generally
submit(cert) -> log returns SCT (signed inclusion promise)
monitor:   scans every new entry for certificates touching domains it watches
auditor:   checks inclusion proofs (my cert is really logged)
           and consistency proofs (the log only ever appended)
# Mis-issuance can't hide: it must be logged to be trusted, and logging is public.

Agent systems generate exactly the kind of history that needs to be trustworthy after the fact: who authorized what, which policy was in force, which tool call ran, what a model decided. Writing those events into an append-only hash chain makes the audit trail tamper-evident — no component, not even an operator, can quietly rewrite "who approved this action" once it is chained and its head is published. Wrapping the chain in a transparency log adds inclusion proofs (prove a specific authorization was recorded) and consistency proofs (prove the trail was only appended to), and independent monitors can watch it the way CT monitors watch certificates. Combined with signed entries (each event signed by its author) and Merkle roots (commitments to batched decisions), this gives an audit trail that supports the question at the heart of agent governance: "who authorized this, and when — and can anyone have altered the record since?"

• ▸Tamper-evident, not tamper-proof: the chain detects edits only for someone who retained an earlier head. If no one kept a prior head, an attacker can rebuild a fresh consistent chain.
• ▸Without a signed tree head, a log operator can present a self-consistent but fabricated history; sign heads and distribute them.
• ▸A hash chain alone does not stop equivocation (showing different histories to different parties); detecting that needs gossip/monitoring among independent observers.
• ▸Append-only is a liability for privacy and right-to-erasure: you cannot delete a chained entry without breaking the chain, so keep sensitive data out of entries (store hashes/commitments, not plaintext).
• ▸Availability and monitoring are part of the trust model: a transparency log that nobody audits provides little assurance, and unresponsive logs or missing monitors silently weaken it.
• ▸The log proves an event was recorded in order; it does not prove the event itself was correct, authorized or truthful. Evidence of history is not validation of content.

Expected direction: The auditor requests a consistency proof between the old head (size N) and the new head (size N+500). Verifying it establishes that the size-N+500 log is an append-only extension of the size-N log — the first N entries are unchanged and only new entries were added — in ~log(n) work. It does NOT establish that any entry’s content is correct, authorized, or truthful; it only proves the history was not rewritten. (To also trust specific entries, check their signatures and inclusion proofs.)

What exactly makes a hash-chained log tamper-evident?

Each entry’s stored head hashes the previous head with the new entry, so altering any past entry changes its head and every head after it, breaking the link to the latest head that observers already recorded.

What does a consistency proof add beyond a plain hash chain?

It lets a verifier confirm in logarithmic work that a newer signed tree head is an append-only extension of an older one — same prefix, only appends — so even the operator cannot rewrite accepted history undetected.

What does Certificate Transparency prevent, and what does it only make possible?

It does not prevent certificate mis-issuance; it makes mis-issuance publicly detectable by requiring certificates to be recorded in public append-only Merkle logs that monitors and domain owners can watch.