Hash chaining

The whole technique is one line. The digest of record n is taken over the digest of record n minus one, a separator, and a canonical serialisation of record n’s content, with the record’s own digest field excluded and a fixed genesis value standing in for the digest of record zero. Everything else about a hash-chained log is a consequence of that line. Two details in it do most of the work: canonical serialisation — sorted keys, no whitespace, one encoding per record — so that two parties independently compute the same value, and the exclusion of the record’s own digest from its own input, without which a verifier recomputing from a stored row would cover a field the original write never covered and every check would fail. The same reasoning applies to any column added later: if it is not inside the digest input, it is not protected, and that should be written down rather than assumed.

Detection is located, not merely raised. Alter record 12 and the discrepancy appears twice — record 12’s recomputed digest no longer matches the value stored beside it, and record 13’s stored link no longer matches record 12’s actual digest — so a walk from genesis can name the first sequence at which the chain breaks and say which of the two it found. Removal shows up as a broken link at the following record, or as a gap if sequence numbers are drawn from a counter that deletion does not lower. This is the practical advantage over a periodic digest of a whole table: a table digest tells you something changed, and a chain tells you where.

The property being relied on is not that digests are hard to compute. They are cheap and public, and anyone holding the rows can compute them. It is that a change requires recomputing every record after it, and therefore write access to all of them. Against an outside reader, a bug that rewrote a column, a partial restore, or an injection that reaches one row, that is a real barrier. Against the party who administers the database it is none: they rewrite the entry, walk forward, re-hash the remainder, and the chain verifies clean afterwards. Any statement about what a hash chain proves is incomplete without naming which of those two attackers it is being claimed against.

Keying closes the second case, at a cost worth understanding. Replace the plain digest with a message authentication code — HMAC-SHA256 under a key held outside the store — and rewriting history needs the key as well as database access. Three qualifications travel with that: the key must be injected from a secret manager the database administrator cannot read, or it buys nothing; records written before the key existed cannot be re-tagged under it, because re-tagging is the act being prevented, so they are covered instead by a keyed checkpoint over the head they add up to, and altering any of them moves that head; and unkeyed digests must be tolerated only as an unbroken prefix, because once a record verifies under the key, an unkeyed successor is a forgery rather than a legacy row. One trap is worth naming separately: do not key a digest that anything looks records up by. Systems commonly store the SHA-256 of a credential as its identifier, and keying that digest would make every credential already issued unresolvable. An integrity tag can be keyed; an identifier cannot.

What chaining structurally lacks is a partial proof. Verification is linear in the length of the log — it gets slower every day, and it is normally the reason implementations end up streaming the walk in bounded chunks — and there is no way to demonstrate that one record belongs to the chain without disclosing the records around it. That is what a Merkle tree with signed tree heads provides, at the cost of more machinery than most on-premises deployments want to carry. Choosing the chain is a reasonable decision; choosing it without knowing that a regulator cannot be handed a verifiable extract is not.