Hash-Chained Audit Log

A hash-chained audit log is an append-only log in which each entry stores a cryptographic hash of the entry before it, so that every entry commits to the whole history preceding it. If someone later edits or deletes an entry in the middle, the stored hashes no longer match and a verifier can detect it. The log makes tampering evident; it does not make tampering impossible.

Mechanism

Let \(e_i\) be the content of entry \(i\) and \(H\) a cryptographic hash function such as SHA-256. Each entry stores the previous entry's hash \(h_{i-1}\) and its own hash:

\[ h_i = H(i,\; h_{i-1},\; e_i), \qquad h_{-1} = \text{a fixed starting value}. \]

Changing any field of \(e_j\) changes \(h_j\). Entry \(j+1\) stored the old \(h_j\), so its link no longer matches, and so on down the chain. The attacker must therefore recompute every hash from the edited entry to the end. Deleting an entry has the same effect: the next entry's stored previous hash refers to something that is gone.

Verification walks the log from the start, recomputing each hash and comparing each stored previous hash with the hash of the entry before it:

import hashlib, json, copy
GENESIS = "0" * 64
def h(core):
    data = json.dumps(core, sort_keys=True, separators=(",", ":")).encode("utf-8")
    return hashlib.sha256(data).hexdigest()

def append(log, **ev):
    prev = log[-1]["hash"] if log else GENESIS
    e = {"seq": len(log), "prev": prev, **ev}
    e["hash"] = h({k: v for k, v in e.items() if k != "hash"}); log.append(e)

def verify(log, anchor=None):
    prev = GENESIS
    for i, e in enumerate(log):
        core = {k: v for k, v in e.items() if k != "hash"}
        if e["prev"] != prev or h(core) != e["hash"]: return f"BROKEN at seq {i}"
        prev = e["hash"]
    if anchor is not None and (not log or log[-1]["hash"] != anchor): return "HEAD != anchor"
    return "ok"

log = []
for event in ("requested", "approved", "executed", "closed"):
    append(log, event=event, order_id="ord_8", cents=3000)
anchor = log[-1]["hash"]

edited = copy.deepcopy(log); edited[1]["cents"] = 5000
one_rehashed = copy.deepcopy(edited)
one_rehashed[1]["hash"] = h({k: v for k, v in one_rehashed[1].items() if k != "hash"})
rebuilt = []
for entry in edited:
    append(rebuilt, **{k: v for k, v in entry.items() if k not in {"seq", "prev", "hash"}})
cases = [("none", log), ("edit entry 1", edited),
         ("delete entry 1", copy.deepcopy(log[:1] + log[2:])),
         ("rehash only entry 1", one_rehashed),
         ("rewrite all hashes", rebuilt), ("truncate last two", log[:-2])]
for label, candidate in cases:
    print(label + ":", verify(candidate))
print("anchored rewrite:", verify(rebuilt, anchor))
print("anchored truncation:", verify(log[:-2], anchor))

The program builds a hypothetical four-entry log (requested, approved, executed, closed), applies six changes, and produces these results:

Tampering	Result
none	ok
edit field in entry 1	broken at entry 1
delete entry 1	broken at entry 1
edit entry 1 and recompute only its hash	broken at entry 2
rewrite every hash consistently after editing	ok
truncate the last two entries	ok

The last two rows are the limits. A chain proves that entries are consistent with each other; it cannot prove they are the entries originally written, because anyone who can write the whole log can also rebuild a consistent chain. Dropping entries from the end leaves a shorter, valid chain.

Anchoring

The remedy is to publish the latest hash (the head) somewhere the attacker cannot rewrite: a separate system with its own access controls, a write-once store, a signed record held by another party, or a periodic checkpoint sent to an external service. A verifier then checks that the log's head matches the anchor. In the same run, with the anchor stored outside the log, both the full rewrite and the truncation were reported as HEAD != anchor. An anchor helps only if whoever can rewrite the log cannot also change the anchor, its retention, or the verifier's trust in it; an anchor kept where the attacker can edit it adds nothing. Anchoring is usually periodic, so entries written after the last anchor remain unprotected until the next one, and the more often heads are anchored, the less recent history an attacker can drop unnoticed.

Keyed hashes (an HMAC under a secret key) or signatures raise the bar further, since an attacker who reads the log cannot compute a valid hash without the key. They only help while the key stays out of the attacker's reach; Schneier and Kelsey's scheme evolves the key forward so that a later compromise cannot forge entries written earlier. Their paper also shows why the chain alone is not enough: such schemes protect entries written before a compromise but do not stop deletion of the most recent entries.

Use for agent approval and action logs

For human approval of agent actions, the log records proposals, decisions, refusals, executions and handoffs. A hash chain lets an auditor confirm that the sequence of "requested, approved by a second person, executed" was not edited after the fact. Combine it with these properties: the log writer is a separate service the agent cannot call to write arbitrary entries, entries are timestamped by that service, and the head is anchored regularly.

Neighbors

A Merkle tree arranges hashes as a tree rather than a line and supports efficient proofs that one entry is in the log; certificate-transparency-style logs use it. A blockchain is a hash chain with a consensus protocol for who may append. A plain audit log records events; the hash chain is an integrity layer on top of one.

References

• Schneier and Kelsey, Secure Audit Logs to Support Computer Forensics, ACM TISSEC 2(2), 1999