The Merkle Proof Bug That Silently Returns the Wrong Root

A Merkle proof check that comes back false doesn't always mean the file was tampered with. Half the time it means the hash-combination step is wrong: hex decoded as text instead of bytes, a sibling hash combined on the wrong side, or a hash function swapped out without anyone noticing. None of these throw an error. They just produce a root that doesn't match, and you're left assuming the worst about a file that's actually fine.

I ran into every one of these while writing the Merkle verification logic for verify-proof, a small Python package that checks a file's SHA-256 hash against a blockchain-anchored proof offline. It implements the same proof-checking logic that validates a ProofLedger timestamp proof, minus the anchoring service itself. Just the math, run locally, no API call required. The algorithm is short. The bugs it hides are not obvious until you've hit them once.

Two Ways to Combine a Hash, One Correct Answer

A Merkle proof is a list of sibling hashes plus a position ("left" or "right") for each step. Starting from your leaf hash, you combine it with each sibling in order, hash the result, and repeat until you land on a value. If that value matches the published root, the leaf was part of the tree.

The combining step looks trivial: concatenate two hex strings and hash them. Here's the version that looks right and isn't:

import hashlib

leaf_hash = "a3f5c8e1b2d4f6a8c0e2b4d6f8a0c2e4b6d8f0a2c4e6b8d0f2a4c6e8b0d2f4a6"
sibling_hash = "1f2e3d4c5b6a798877665544332211001f2e3d4c5b6a798877665544332211"

combined = leaf_hash + sibling_hash
result = hashlib.sha256(combined.encode()).hexdigest()

That .encode() call is the bug. combined is a hex string, forty bytes of ASCII characters like "a", "3", "f". Encoding it treats those characters as text, so you end up hashing the string "a3f5c8e1..." instead of the sixteen raw bytes it represents. The hash function runs fine. It just runs on the wrong input.

The fix is to decode the hex into bytes before concatenating:

combined = bytes.fromhex(leaf_hash) + bytes.fromhex(sibling_hash)
result = hashlib.sha256(combined).hexdigest()

Two different byte sequences, two different roots. Nothing in the code tells you which one the original tree was built with. You find out by testing against a known-good proof, or you don't find out at all.

Left and Right Aren't Symmetric

Even with correct byte handling, order matters. hash(A + B) and hash(B + A) are different values, so each proof step needs to know which side the sibling belongs on:

def combine(current, sibling, position):
    current_bytes = bytes.fromhex(current)
    sibling_bytes = bytes.fromhex(sibling)
    if position == "left":
        combined = sibling_bytes + current_bytes
    else:
        combined = current_bytes + sibling_bytes
    return hashlib.sha256(combined).hexdigest()

Get "left" and "right" backwards and every proof with an odd number of steps fails, while proofs with an even number sometimes pass by coincidence, because reversing the order twice cancels out. That's the part that cost me an afternoon. A test suite with only even-depth trees will tell you the code works when it's actually broken half the time.

What This Means If You're Verifying, Not Just Building

If you're on the receiving end of a Merkle proof rather than the one generating it, none of this is visible to you. You get a leaf hash, a list of siblings, a root, and a "valid: true/false" result. When it comes back false, the honest first question isn't "was this file altered?" It's "did the verifier implement the combining step correctly?"

That's worth checking before you tell a claims adjuster or an opposing counsel that a document failed verification. A bad .encode() call and actual tampering produce the exact same output.