“Verification failed” is not a useful answer
By Dylan Wolpe
The short version
- Most integrity checks return pass or fail. On a large archive, a bare fail means the problem is somewhere in the whole thing, which is close to useless operationally.
- A hash chain naturally locates the first divergence, because verification is sequential, the entry where recomputation stops matching is the earliest point of alteration.
- A tree structure narrows it faster, in logarithmic rather than linear time, which matters when the log has hundreds of millions of entries.
- The first divergence is where tampering started, not necessarily the only place it occurred, verification finds the boundary, and a human still has to establish the scope.
Your integrity check runs overnight across nine years of records and reports failure. That is genuinely important information, and by itself it is almost unusable: you now know something is wrong somewhere in several hundred million entries, with no indication of where, when, or how much.
Why most checks cannot localise
The common design hashes the artefact as one object. Take a hash of the whole archive, store it, recompute later, compare.
This detects any change, down to a single bit, and tells you nothing about which bit. A hash is a fingerprint of everything at once, so a mismatch is a statement about everything at once. The property that makes it a good detector is exactly what makes it a poor locator.
One hash over ten million records detects everything and locates nothing. That is not a limitation of hashing, it is a consequence of hashing them together.
How a chain localises for free
A hash chain commits each entry to its predecessor, which means verification is inherently sequential, and sequence gives you position:
entry 8211 recomputed == stored ok entry 8212 recomputed == stored ok entry 8213 recomputed != stored <-- first divergence entry 8214 recomputed != stored (consequence) entry 8215 recomputed != stored (consequence)
The first mismatch is the finding. Everything after it fails because the chain carries the error forward, not because those entries were touched. A verifier that reports “347,000 entries failed” is technically accurate and has buried the one number that matters.
What you get is a record and a timestamp. That turns a vague integrity incident into a specific question, what happened around that entry, who had access then, what else occurred at that moment, which is the difference between an alarm and an investigation.
When linear is too slow
Sequential verification is fine at millions of entries and painful at billions, because finding the divergence means walking to it.
A tree structure fixes this. Commit entries in blocks, commit blocks to a root, and verification becomes a descent: check the root, find which half disagrees, descend, repeat. Logarithmic rather than linear, so locating one altered entry among a billion is roughly thirty comparisons instead of a billion.
The trade is that trees are more complicated to get right, particularly domain separation between leaf and internal nodes, omit it and an attacker can present an internal node as a leaf, which is a real and well-documented class of bug rather than a theoretical one.
What to ask for
Two questions separate a real integrity feature from a checkbox:
- When verification fails, what exactly do I get? A boolean, or a record identifier and a timestamp?
- How long does verification take on my volume? A check that takes nine hours is a check that runs quarterly, and a check that runs quarterly gives an attacker a quarter.
Ours reports the specific entry where the chain first diverges, because the alternative is handing someone a failed check and a shrug at the exact moment they most need a starting point.
Questions people ask about this
Can you tell which record in a log was altered?
With a hash chain, yes. Verification recomputes each entry's hash from the previous one, so the first entry where the recomputed value stops matching is the earliest point of alteration. That gives you a specific record and timestamp rather than a failed check over the whole log.
Why do most integrity checks only return pass or fail?
Because they hash the artefact as a single blob. A single hash over ten million records detects any change and localises none of it. Locating requires the structure to be built from many smaller commitments rather than one large one.
Does finding the first altered entry tell you everything?
No. It tells you where tampering begins. Someone who altered entries 400 and 9,000 will be detected at 400 first, and the second change is only found once the first is resolved. Verification establishes the boundary; determining the full scope is investigative work.