Hash Chain Audit Logs: Making Logs Impossible to Silently Alter

This article has three layers:

1. Layer 1: The Intuition: An interlocking ledger
2. Layer 2: Real-World Use: Certificate Transparency, Git, Blockchain, Financial Auditing
3. Layer 3: Principles and Engineering details

Layer 1: The Intuition

1.1 An Interlocking Ledger

Imagine a ledger where the footer of every page contains the "fingerprint of the previous page's content."

• If someone wants to secretly modify page 5: once modified, the fingerprint of page 5 changes and no longer matches the footer recorded on page 6;
• They are forced to then modify the footer of page 6, which changes its fingerprint and no longer matches page 7;
• ...and so on, all the way to the last page.

To change one page, you must change every subsequent page.

1.2 You Can Only Modify "Your Own Copy"

If you make a copy of the fingerprint of the last page every day and lock it in a drawer at home (a place an attacker cannot reach), then even if an attacker rewrites the entire ledger, the last page's fingerprint will not match the one in your drawer.

This is tamper-evident: it doesn't make tampering impossible, but it ensures that tampering will definitely be detected.

Layer 2: Real-World Use

Layer 3: Principles and Engineering

3.1 Construction

The $i$st record stores:

$$h_i = \mathrm{SHA256}\big(h_{i-1} \,\|\, \text{index} \,\|\, \text{timestamp} \,\|\, \text{operator} \,\|\, \text{content}\big),\qquad h_0 = 0\cdots0.$$

During verification, you recalculate from the beginning; every entry must match the stored $h_i$.

3.2 A worked example

3.3 External Anchors: The Most Critical Step

Implementing a hash chain within a single database only protects against "uninformed tampering"; it cannot protect against an attacker with full control over the database, who can recalculate all subsequent hashes starting from the point of tampering. Therefore, you must periodically save the latest hash to an independent location:

Note the phrase "recalculating using its own code": if the verification program also runs on the compromised server, the attacker can modify the verification program itself.

3.4 Database-Level Hardening

• Database triggers to prohibit UPDATE and DELETE on the log table, allowing only INSERT;
• The service account used for writing logs should not have deletion permissions;
• Do not store sensitive data like passwords, private keys, or full credit card numbers in logs (logs are often kept longer and viewed by more people than the primary data).

3.5 Merkle Trees: The Scalable Upgrade

To verify the $n$th record in a hash chain, you must calculate from the 1st to the $n$th record. Merkle Trees hash records in pairs, building up layer by layer until a single root hash is obtained. Proving "a specific record is in the log" only requires $\log_2 n$ hash values. Certificate Transparency, transactions in Bitcoin blocks, and Ethereum states all use Merkle Trees.

3.6 Where Security Comes From

For an attacker to modify a record without being detected, they must find another piece of content whose hash exactly matches the original value—meaning they must break the second preimage resistance of the hash function. For SHA-256, this would require approximately $2^{256}$ attempts (see "The Birthday Paradox and Hash Collisions").

Summary