I Shipped a Broken Consistency Proof Verifier. Here's How I Found Out.

ATL Protocol needs append-only integrity. Every entry that was ever written to a transparency log must remain exactly where it is, exactly as it was. If an operator, a compromised server, or a software defect silently drops or mutates a past record, the entire trust model is gone. Not degraded -- gone.

Consistency proofs enforce this. A consistency proof takes two snapshots of the same log -- say, one at size 4 and another at size 8 -- and proves that the first four entries in the larger log are byte-for-byte identical to the entries in the smaller log. No deletions. No substitutions. No reordering. The proof is a short sequence of hashes that lets any verifier independently confirm the relationship between the two tree roots.

RFC 9162 (Certificate Transparency v2) specifies the exact algorithm for generating and verifying these proofs. I implemented it from scratch in Rust for ATL Protocol. Not a wrapper around an existing C library. Not a condensed version. The complete SUBPROOF algorithm from Section 2.1.4.

Or at least, that was the plan.

The Shortcut That Bit Me

When I first read Section 2.1.4 of RFC 9162, the verification algorithm looked overengineered. Bit shifting, a boolean flag, nested loops, an alignment phase. I thought I understood the essence of what it was doing and could distill it to something simpler.

So I wrote a simplified verifier. It did four things:

1. Check that the proof path is not empty.
2. If from_size is a power of two, check that path[0] matches old_root.
3. Check that path.len() does not exceed 2 * log2(to_size).
4. Return true.

That last line is the problem. My simplified implementation never reconstructed the tree roots. It checked surface properties -- non-empty path, plausible length, matching first element in the power-of-two case -- and called it good. The tests I had at the time all passed, because valid proofs do have these properties. I moved on to other parts of the codebase.

I do not remember exactly when the doubt crept in. Probably while re-reading the RFC for an unrelated reason. The verification algorithm does two parallel root reconstructions from the same proof path, and my version did zero. That is not a minor difference. That is the entire security property missing.

The Attack

I sat down and tried to break my own code. It took about five minutes.

The old root is public -- anyone monitoring the log already has it. An attacker constructs a proof starting with old_root (passing the "first hash matches" check), followed by arbitrary garbage. The proof length of 3 is within any reasonable bound for an 8-leaf tree. My simplified verifier checks these surface properties, never reconstructs either root, and returns true. The attacker has just "proved" that the log grew from 4 to 8 entries with content they control.

The concrete attack:

#[test]
fn test_regression_simplified_impl_vulnerability() {
    let leaves: Vec<Hash> = (0..8).map(|i| [i as u8; 32]).collect();
    let old_root = compute_root(&leaves[..4]);
    let new_root = compute_root(&leaves);

    let attack_proof = ConsistencyProof {
        from_size: 4,
        to_size: 8,
        path: vec![
            old_root,   // Passes simplified check
            [0x00; 32], // Garbage
            [0x00; 32], // Garbage
        ],
    };

    assert!(
        !verify_consistency(&attack_proof, &old_root, &new_root).unwrap(),
        "CRITICAL: Simplified implementation vulnerability not fixed!"
    );
}

This proof passes every check the simplified verifier performs. The path is non-empty. from_size is 4 (a power of two), and path[0] is indeed old_root. The path length of 3 is well within 2 * log2(8) = 6. My old code would have returned true and accepted a completely forged log extension.

The test name is test_regression_simplified_impl_vulnerability. The word "regression" is deliberate -- it means this is not a hypothetical attack I imagined for educational purposes. I wrote the broken code first. I found the hole. I rewrote the verifier. The test exists so that no future refactor can quietly reintroduce the same vulnerability. My mistake, immortalized in the test suite.

How Consistency Proofs Actually Work

A Merkle tree is a binary hash tree where leaves and internal nodes are domain-separated:

leaf_hash = SHA256(0x00 || data)
node_hash = SHA256(0x01 || left_hash || right_hash)

In an append-only log, new entries are added to the right side of the tree. The left subtrees are immutable once formed. A consistency proof leverages this structure: it provides the minimum set of intermediate hashes that a verifier needs to reconstruct both the old root (from the smaller tree) and the new root (from the larger tree) using a single walk over the proof path.

The critical property -- the one my simplified version missed entirely -- is that the verifier does not simply check whether old_root appears somewhere in the new tree. It must reconstruct both roots from the same proof path. If any hash in the path is incorrect -- even by a single bit -- both reconstructions produce wrong results, and the proof fails.

The RFC 9162 algorithm works by decomposing the tree at the largest power-of-two boundary, then recursively collecting the sibling hashes that the verifier will need. The bit-level operations in the verification algorithm encode the tree structure implicitly: each bit of the size counters tells the verifier whether a proof hash belongs on the left or right at each level.

Five Structural Invariants

After the rewrite, before the verification algorithm processes a single hash, my implementation enforces five structural invariants. Each invariant eliminates a category of malformed or malicious proofs with zero cryptographic work:

Invariant 1: Valid bounds. from_size must not exceed to_size. A proof that claims the tree shrank is structurally impossible in an append-only log. Rejecting it immediately avoids nonsensical bit arithmetic downstream.

if proof.from_size > proof.to_size {
    return Err(AtlError::InvalidConsistencyBounds {
        from_size: proof.from_size,
        to_size: proof.to_size,
    });
}

Invariant 2: Same-size proofs require an empty path. When from_size == to_size, the only valid consistency proof is an empty one -- verification reduces to old_root == new_root. If someone submits a non-empty path for equal sizes, they are attempting to inject hashes into the verification pipeline. Reject it without processing.

Invariant 3: Zero old size requires an empty path. Every tree is consistent with the empty tree by definition. A non-empty proof from size zero is an attempt to force the verifier to process attacker-controlled data for a case that requires no proof at all.

Invariant 4: Non-trivial proofs need at least one hash. When from_size is not a power of two and from_size != to_size, the proof must contain at least one hash. The RFC 9162 algorithm prepends old_root to the proof path only when from_size is a power of two. For non-power-of-two sizes, an empty path means the proof is incomplete -- the verifier has nothing to work with.

Invariant 5: Path length bounded by O(log n). A Merkle tree of depth d requires at most O(d) hashes in a consistency proof. I compute the bound as 2 * ceil(log2(to_size)):

let max_proof_len = ((64 - proof.to_size.leading_zeros()) as usize)
    .saturating_mul(2);
if proof.path.len() > max_proof_len {
    return Err(AtlError::InvalidProofStructure { ... });
}

A 100-hash proof for an 8-leaf tree is rejected before any hashing occurs. Without this bound, an attacker could force the verifier into an arbitrarily expensive hash chain.

These five checks are structural preconditions, not defense-in-depth extras. Every class of malformed proof that can be rejected without hashing should be rejected without hashing. My simplified version skipped this discipline entirely.

The Full Verification Algorithm

The replacement verifier is a faithful implementation of RFC 9162. A single pass over the proof path, maintaining two running hashes and two bit-shifted size counters:

// Step 1: If from_size is a power of 2, prepend old_root to path
let path_vec = if is_power_of_two(from_size) {
    let mut v = vec![*old_root];
    v.extend_from_slice(path);
    v
} else {
    path.to_vec()
};

// Step 2: Initialize bit counters with checked arithmetic
let mut fn_ = from_size.checked_sub(1)
    .ok_or(AtlError::ArithmeticOverflow {
        operation: "consistency verification: from_size - 1",
    })?;
let mut sn = to_size - 1;

// Step 3: Align -- shift right while LSB(fn) is set
while fn_ & 1 == 1 {
    fn_ >>= 1;
    sn >>= 1;
}

// Step 4: Initialize running hashes from the first proof element
let mut fr = path_vec[0];
let mut sr = path_vec[0];

// Step 5: Process each subsequent proof element
for c in path_vec.iter().skip(1) {
    if sn == 0 { return Ok(false) }

    if fn_ & 1 == 1 || fn_ == sn {
        // Proof hash is a left sibling
        fr = hash_children(c, &fr);
        sr = hash_children(c, &sr);
        while fn_ & 1 == 0 && fn_ != 0 {
            fn_ >>= 1;
            sn >>= 1;
        }
    } else {
        // Proof hash is a right sibling (only affects new root)
        sr = hash_children(&sr, c);
    }
    fn_ >>= 1;
    sn >>= 1;
}

// Step 6: Final check
Ok(use_constant_time_eq(&fr, old_root)
    && use_constant_time_eq(&sr, new_root)
    && sn == 0)

The bit operations encode the tree structure. fn_ tracks the position within the old tree boundary, sn tracks the position within the new tree. When a proof hash is a left sibling (fn_ & 1 == 1 or fn_ == sn), it contributes to both root reconstructions. When it is a right sibling, it only contributes to the new root -- the old tree did not extend that far.

The fn_ == sn condition handles the transition point where both trees share a common subtree root and then diverge. The alignment loop at the start skips tree levels where the old tree's boundary falls at an odd index, synchronizing the bit counters with the proof path.

This is the part I tried to skip. Every bit operation matters. Getting any of it wrong means either accepting invalid proofs or rejecting valid ones.

Constant-Time Hash Comparison

The final verification step compares reconstructed hashes against expected roots. A standard == comparison on byte arrays short-circuits on the first differing byte, leaking timing information proportional to the position of the first mismatch.

I use the subtle crate for constant-time comparison:

fn use_constant_time_eq(a: &Hash, b: &Hash) -> bool {
    use subtle::ConstantTimeEq;
    a.ct_eq(b).into()
}

Root hashes are public in a transparency log, so timing side-channels here are less exploitable than in password verification. I use constant-time comparison anyway -- the cost is zero for 32 bytes, and if the function is ever reused in a context where the hash is not public, there is no latent vulnerability waiting to be discovered.

The sn == 0 check in the final expression is part of the RFC specification: after processing all proof elements, the bit-shifted to_size - 1 counter must have reached zero. If it has not, the proof path was the wrong length for the claimed tree sizes. This catches a specific class of attack where the proof contains valid hashes but claims incorrect sizes.

Checked Arithmetic

If from_size is 0 and the code computes from_size - 1 without checking, the result wraps to u64::MAX on release builds. Every subsequent bit operation produces garbage.

Every arithmetic operation uses Rust's checked arithmetic:

let mut fn_ = from_size.checked_sub(1)
    .ok_or(AtlError::ArithmeticOverflow {
        operation: "consistency verification: from_size - 1",
    })?;

No wrapping_sub. No unchecked_add. No silent truncation. If an operation would overflow, it returns an explicit error naming the specific operation. The structural invariants already prevent from_size == 0 from reaching this code path. The checked arithmetic is a second layer: if someone refactors the invariant checks, the arithmetic still will not silently produce wrong results.

Adversarial Test Suite

After the simplified-implementation incident, I was not going to rely on happy-path tests alone. The adversarial test suite in adversarial_tests.rs (344 lines) exists specifically to verify that incorrect, malicious, and boundary-case inputs produce correct rejections. Every test includes both a positive case (valid proof accepted) and a negative case (tampered proof rejected):

Replay attacks across trees. Generate a valid consistency proof for one tree, then attempt to verify it against a different tree with the same sizes but different leaf data:

#[test]
fn test_adversarial_replay_different_tree() {
    let proof_a = generate_consistency_proof(4, 8, get_node_a).unwrap();

    let old_root_b = compute_root(&leaves_b[..4]);
    let new_root_b = compute_root(&leaves_b);

    // Proof from tree A must not verify against tree B
    assert!(!verify_consistency(&proof_a, &old_root_b, &new_root_b).unwrap());
}

The proof is cryptographically bound to specific leaf content. Same structure, different data, different hashes, verification fails.

Replay attacks across sizes. Take a valid proof for (4 -> 8) and relabel it as (3 -> 7). The bit operations in the verification algorithm are size-dependent -- each bit of the size counter determines left-vs-right sibling ordering. A proof path that is valid for one pair of sizes is invalid for another, even if the underlying data is the same.

Boundary size testing. Sizes at or near powers of two trigger different code paths in the bit manipulation logic. I test pairs around every boundary: 63/64, 64/65, 127/128, 128/129, 255/256. Off-by-one errors here are the most common failure mode in Merkle tree implementations because is_power_of_two gates whether old_root is prepended to the proof path.

All-ones binary sizes. Values like 7 (0b111), 15 (0b1111), and 31 (0b11111) have every bit set, maximizing the iterations in the alignment loop and exercising every branch condition. These are the sizes most likely to expose off-by-one errors in the bit-shifting logic.

Proof length attacks. A proof with 100 elements for an 8-leaf tree is rejected by Invariant 5 before any hashing occurs. Without the O(log n) bound, an attacker could force the verifier into an extended hash computation.

Duplicate hash attacks. A proof where every element is old_root is rejected because the hash reconstruction deterministically produces wrong intermediate values. The algorithm's correctness does not depend on hash diversity.

Each test is accompanied by single-bit-flip verification: flipping one byte in any proof hash causes the proof to fail. This confirms that the verification is sensitive to every byte of every hash in the proof path.

The 415 lines of consistency.rs and 344 lines of adversarial tests do not prove the implementation is correct in a formal sense -- that would require a proof assistant. But they do prove that every attack vector I could identify is covered, and they document those vectors permanently in the test names and assertions. Including the vector I accidentally created myself.

---

The full implementation is open source: github.com/evidentum-io/atl-core

Files discussed in this post:

• src/core/merkle/consistency.rs -- proof generation and verification (415 lines)
• src/core/merkle/tests/adversarial_tests.rs -- adversarial test suite (344 lines)
• src/core/merkle/crypto.rs -- RFC 6962 hash functions
• src/core/merkle/helpers.rs -- tree navigation utilities