Cryptographic Hashing and Digital Signatures Questions

Direct answer

A length-extension attack exploits the fact that a Merkle-Damgard hash's final digest IS its complete internal state at the moment hashing stopped. Anyone holding that digest can resume hashing from that exact state and process more data, computing a valid hash for a longer message whose prefix they never actually saw. Against a naive MAC (Message Authentication Code) built as MAC = H(key || message), this means an attacker who knows only the digest and the plaintext message, never the key, can still produce a valid tag for (message plus padding plus an attacker-chosen suffix).

Structured elaboration

Merkle-Damgard recap. A message is split into fixed-size blocks after standardized padding: a delimiter bit, zero padding, and an encoded bit-length field. A fixed starting value is compressed together with each block in turn, and the digest is simply whatever the running state equals after the last block. MD5, SHA-1, and SHA-256 (part of the SHA, Secure Hash Algorithm, family) are all built this way.

Why internal state enables forgery. The compression function only needs the CURRENT state plus the next block; it has no memory of how that state was reached. Resuming from a leaked digest is therefore mechanically identical to resuming from any legitimate intermediate state partway through hashing; the hash function itself cannot tell the difference.

Step-by-step forgery against MAC = H(key || message):

1. The attacker observes tag = H(key || message) and the plaintext message. They don't know key, but guess or brute-force its LENGTH, often a narrow search since key sizes are frequently fixed, such as a standard API-key length.
2. They compute glue, the exact padding bytes H would have appended after (key || message) at that guessed total length. This depends only on the length, never on the key's actual content.
3. They set the hash's internal state to tag, the resume step, and continue compressing an attacker-chosen suffix, applying the standard padding rules again but now accounting for the new, longer total length.
4. The result is a valid H(key || message || glue || suffix), computed with zero knowledge of key.
5. The attacker sends (message || glue || suffix) along with the forged tag. A server that naively recomputes H(key || received_bytes) accepts it, because the values genuinely match.

Tooling. Publicly available tools such as hashpump automate steps 1 through 4 against MD5, SHA-1, and SHA-256, searching candidate key lengths and computing the extension automatically, without the attacker writing any hash-internals code themselves.

Worked example

Real MD5 or SHA-256 implementations don't expose a "resume from this state" API directly, so here is a small, from-scratch hash built specifically to demonstrate the exact structural mechanism, the same padding rules and the same digest-equals-final-state property that MD5, SHA-1, and SHA-256 all share in production, without needing to reimplement a full production hash function.

MASK64 = (1 << 64) - 1
IV = 0xCBF29CE484222325
BLOCK = 16
ODD_CONST = 0xBF58476D1CE4E5B9

def rotl64(x, r):
    return ((x << r) | (x >> (64 - r))) & MASK64

def compress(state, block):
    w0 = int.from_bytes(block[:8], 'big')
    w1 = int.from_bytes(block[8:], 'big')
    x = state ^ w0
    x = rotl64(x, 17)
    x = (x + w1) & MASK64
    x ^= rotl64(x, 31)
    x = (x * ODD_CONST) & MASK64
    x ^= (state >> 7)
    return x & MASK64

def md_pad(local_len, total_len_bytes):
    pad = b'\x80'
    while (local_len + len(pad)) % BLOCK != BLOCK - 8:
        pad += b'\x00'
    pad += (total_len_bytes * 8).to_bytes(8, 'big')
    return pad

def H(message):
    padded = message + md_pad(len(message), len(message))
    state = IV
    for i in range(0, len(padded), BLOCK):
        state = compress(state, padded[i:i+BLOCK])
    return state.to_bytes(8, 'big')

def H_resume(state_bytes, processed_len, tail):
    state = int.from_bytes(state_bytes, 'big')
    total_len = processed_len + len(tail)
    padded_tail = tail + md_pad(len(tail), total_len)
    for i in range(0, len(padded_tail), BLOCK):
        state = compress(state, padded_tail[i:i+BLOCK])
    return state.to_bytes(8, 'big')

secret = b'k3y-unknown-to-attacker'
message = b'user=alice&amount=10'
suffix = b'&admin=true'

real_mac = H(secret + message)
guessed_secret_len = len(secret)
original_total_len = guessed_secret_len + len(message)
glue = md_pad(original_total_len, original_total_len)
forged_digest = H_resume(real_mac, original_total_len + len(glue), suffix)
forged_message = message + glue + suffix

server_side = H(secret + forged_message)

print('MAC(secret||message)    =', real_mac.hex())
print('forged digest           =', forged_digest.hex())
print('server-recomputed digest=', server_side.hex())
print('forgery accepted?       =', forged_digest == server_side)

Output:

MAC(secret||message)    = 30d840639d174d72
forged digest            = f3e85087bb9b1a3c
server-recomputed digest = f3e85087bb9b1a3c
forgery accepted?        = True

The forged digest, computed with no knowledge of secret at all, matches exactly what the server independently recomputes with the real secret. This is the same mechanism a real attack against MD5, SHA-1, or SHA-256 would use.

Trade-offs and pitfalls

• This answer is deliberately about the ATTACK MECHANICS only. It does not by itself tell you how to fix a naive MAC, since that requires understanding what's structurally different about a properly nested construction, not just concluding "switch to something else."
• Guessing the key length is usually easy in practice, given fixed key sizes or a small brute-forceable range, so "the attacker doesn't know the key" is a much weaker protection than it sounds.
• SHA-3, built on a sponge construction rather than Merkle-Damgard, does not expose its full internal state through its digest the same way, so this specific attack doesn't apply to it. That's a property of the construction, not a blanket guarantee that every SHA-3-based scheme is automatically safe against every other kind of attack.

Direct answer

I'd build a JWS (JSON Web Signature) verifier around three rules: never let the token's own header choose the verification algorithm, always check the signature against the exact bytes that were transmitted rather than a re-parsed version, and always check freshness separately from validity, since a signature only proves who signed something and that it wasn't altered, not that it's still supposed to be accepted right now. Production JWS bugs cluster around exactly the places where the verifier trusts something the ATTACKER controls: the algorithm name in the header, a stale but validly-signed token being replayed, or ambiguity about which bytes were actually hashed and signed.

Structured elaboration

Glossary. JWS (JSON Web Signature) is a standard for representing a signed JSON payload as a compact, base64url-encoded string in the form header.payload.signature. JWT (JSON Web Token) is the common special case where the payload holds a set of identity or authorization claims.

Algorithm confusion. The JWS header includes an "alg" field that the TOKEN ITSELF supplies. If a verifier is configured to accept multiple algorithms and blindly uses whichever one the token names, an attacker can often exploit the gap between an asymmetric and a symmetric algorithm specifically. For example, a server that verifies RS256 tokens (RSA signatures, asymmetric) using a public key, but is ALSO configured to accept HS256 (HMAC, Hash-based Message Authentication Code, a symmetric construction) using that SAME key value as the verification argument, lets an attacker who merely knows the public key, which is intentionally public, forge an HS256-"signed" token: HMAC only needs some shared secret bytes, and the public key's own PEM string works fine as one. The fix is to pin exactly one expected algorithm per verification context and never let the token select it.

Replay of an old but validly-signed request. A signature proves who signed something and that it wasn't altered; it says nothing about WHEN it's still valid to accept. The mitigation is to embed and check an expiry claim and an issued-at claim with a small allowed clock-skew window, plus a unique nonce or token identifier tracked server-side in a short-lived store, so a given token can't be replayed a second time within its own validity window.

Exactly what bytes get hashed and signed. JWS signs the base64url-encoded header and payload CONCATENATED WITH A LITERAL PERIOD CHARACTER, not the raw, re-parsed JSON object. If a verifier re-serializes the JSON, for instance re-encoding fields in a different key order or with different whitespace, before checking the signature, instead of checking it against the exact bytes that were transmitted, it can accept a token whose claims were subtly altered after signing, provided the alteration happens to normalize back to something matching after re-serialization.

Worked example

Here is the algorithm-confusion attack end to end, using a real RSA keypair and a real JWS library, showing a vulnerable verifier accept a forged token and a correctly pinned verifier reject it.

import json, hmac, hashlib, base64
import jwt
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding

def b64u(data: bytes) -> str:
    return base64.urlsafe_b64encode(data).rstrip(b'=').decode()

def b64u_decode(s: str) -> bytes:
    return base64.urlsafe_b64decode(s + '=' * (-len(s) % 4))

# server: RSA keypair, signs with RS256, publishes the PUBLIC key (e.g. via a JWKS endpoint)
key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
priv_pem = key.private_bytes(serialization.Encoding.PEM, serialization.PrivateFormat.PKCS8, serialization.NoEncryption())
pub_pem = key.public_key().public_bytes(serialization.Encoding.PEM, serialization.PublicFormat.SubjectPublicKeyInfo)

legit_token = jwt.encode({"sub": "alice", "role": "user"}, priv_pem, algorithm="RS256")

# VULNERABLE verifier: trusts the token's own "alg" header, reuses the SAME key bytes either way
def vulnerable_verify(token: str, verification_key: bytes):
    header_b64, payload_b64, sig_b64 = token.split('.')
    header = json.loads(b64u_decode(header_b64))
    signing_input = f"{header_b64}.{payload_b64}".encode()
    sig = b64u_decode(sig_b64)
    if header["alg"] == "HS256":
        expected = hmac.new(verification_key, signing_input, hashlib.sha256).digest()
        if not hmac.compare_digest(expected, sig):
            raise ValueError("bad HS256 signature")
    elif header["alg"] == "RS256":
        pub = serialization.load_pem_public_key(verification_key)
        pub.verify(sig, signing_input, padding.PKCS1v15(), hashes.SHA256())
    else:
        raise ValueError("unsupported alg")
    return json.loads(b64u_decode(payload_b64))

print("legit RS256 token verifies:", vulnerable_verify(legit_token, pub_pem)["role"] == "user")

# attacker: no private key, but the public key IS public by design; forge an HS256 token
# using the public-key PEM bytes as the HMAC secret
header = {"alg": "HS256", "typ": "JWT"}
payload = {"sub": "alice", "role": "admin"}
signing_input = f"{b64u(json.dumps(header, separators=(',', ':')).encode())}.{b64u(json.dumps(payload, separators=(',', ':')).encode())}"
forged_sig = hmac.new(pub_pem, signing_input.encode(), hashlib.sha256).digest()
forged_token = f"{signing_input}.{b64u(forged_sig)}"

try:
    result = vulnerable_verify(forged_token, pub_pem)
    print("FORGED token accepted by vulnerable verifier! role =", result["role"])
except Exception as e:
    print("forged token rejected:", e)

# FIXED verifier: pins ONE expected algorithm; PyJWT also independently refuses to use a
# PEM-shaped key for HS256, a defense added specifically against this bug class
def fixed_verify(token):
    return jwt.decode(token, pub_pem, algorithms=["RS256"])

try:
    fixed_verify(forged_token)
    print("FIXED verifier: forgery accepted (BUG)")
except jwt.InvalidTokenError as e:
    print("FIXED verifier correctly rejects the forged token:", type(e).__name__)

Output:

legit RS256 token verifies: True
FORGED token accepted by vulnerable verifier! role = admin
FIXED verifier correctly rejects the forged token: InvalidAlgorithmError

The vulnerable verifier escalates the attacker from "user" to "admin" using only the public key, which was never secret in the first place. Pinning the algorithm closes the hole entirely. Worth noting: PyJWT itself independently refuses to use a PEM-shaped key as an HMAC secret, a guard added specifically because this exact bug class was common enough in real deployments to justify hardening the library itself.

Trade-offs and pitfalls

• "Accept multiple algorithms for flexibility" is almost always the wrong trade. Pin one algorithm per key or context; if you genuinely need to rotate algorithms, select a specific known key-and-algorithm pair via a key identifier looked up from a server-side allowlist, never from attacker-supplied header content alone.
• A replay window sized to be "generous for clock skew" is a real, live trade-off: too tight and legitimate clients with slightly-off clocks get rejected, too loose and a captured token stays exploitable for longer. There's no universally correct number; size it to your actually observed clock drift plus a safety margin, and prefer short-lived tokens over a large skew window.
• Signing the raw transmitted bytes exactly, rather than a re-serialized or re-parsed version, avoids a whole class of canonicalization-mismatch bugs, but requires the client, server, and any intermediary to agree on byte-for-byte fidelity in transit; don't let a proxy "prettify" JSON along the way.

Direct answer

I'd push back on reusing the same fast hash for both cache keys and passwords: speed is exactly the property you want for a cache key generator and exactly the property you must NOT want for password hashing, because speed is what lets an attacker try billions of password guesses per second against a stolen database. The real boundary isn't "cryptographic hashes are better," it's whether an adversary controls or benefits from the input or the output. A general-purpose hash like MurmurHash is optimized assuming no adversary is present; a cryptographic hash like SHA-256 (part of the SHA, Secure Hash Algorithm, family) is built assuming a motivated one is.

Structured elaboration

Definitions. MurmurHash is a family of non-cryptographic hash functions designed for speed and a good, even distribution of outputs, originally built for hash tables and checksums. A cryptographic hash function additionally has to survive an adversary who is actively trying to break it: preimage resistance (given a digest, you can't find an input that produces it), second-preimage resistance (given one input, you can't find a different input with the same digest), and collision resistance (you can't find any two distinct inputs, of your own choosing, that produce the same digest). MurmurHash provides none of these against a motivated attacker; SHA-256 is designed and studied specifically to provide all three.

Three situations where a non-cryptographic hash is perfectly fine (no adversary, or a collision only costs a little accuracy, not security):

1. In-process hash tables or maps keyed by data the caller controls internally, not data supplied over a network by an untrusted party.
2. Probabilistic data structures such as Bloom filters or HyperLogLog, used for approximate counting, where an occasional collision only slightly degrades accuracy rather than breaking a security property.
3. Sharding or partitioning keys for a cache or a distributed system, where the goal is even distribution across nodes, not resistance to a deliberate adversary (with the caveat below about attacker-supplied keys).

Three situations where using one would be a serious mistake:

1. Password storage. A fast hash lets an attacker who steals the password database try enormous numbers of candidate passwords per second offline; a password hash needs to be deliberately slow and memory-hard instead, using a KDF (key derivation function) such as bcrypt, scrypt, Argon2, or PBKDF2.
2. Message authentication or integrity checks against an adversary, such as verifying a downloaded file or a signed API request. Collision and preimage resistance are exactly what stop forgery here, and MurmurHash offers neither.
3. Any hash table exposed to attacker-controlled keys over a network, such as a web server hashing request parameters into an internal table. A known non-cryptographic hash lets an attacker craft many inputs that collide on purpose, degrading the table toward a linked list and causing an algorithmic-complexity denial-of-service, sometimes called hash flooding.

Worked example

The clearest way to see the password-hashing mistake in concrete numbers is to look at what a KDF's iteration count actually buys you, since that number multiplies attacker cost directly and doesn't depend on wall-clock benchmarking. Suppose a team configures PBKDF2, one of the KDFs named above, with, as one illustrative configuration, N = 100,000 iterations, versus hashing the password once with a fast hash like SHA-256:

• Fast hash (1 iteration): testing a 10,000,000-entry common-password wordlist against a stolen digest costs 10,000,000 hash evaluations.
• KDF at N = 100,000 iterations: the SAME wordlist costs 10,000,000 times 100,000 = 1,000,000,000,000 (one trillion) hash evaluations, because every single guess now has to pay the full iteration count, not just one hash call.

That multiplier applies uniformly whether the attacker has one laptop or a warehouse of GPUs; it's a property of the KDF's design, not of any particular attacker's hardware. A fast hash like MurmurHash has no equivalent knob at all: it was never designed to be slow, so there is no "iteration count" to raise.

Trade-offs and pitfalls

• "Non-cryptographic" doesn't mean "insecure everywhere," it means "not designed for an adversarial threat model." Using SHA-256 for a purely internal hash table works correctly but burns CPU cycles for no security benefit, which is a legitimate but different critique from the password-hashing mistake above.
• Watch for the middle ground: a hash-flood-resistant non-cryptographic hash, such as SipHash, exists specifically because "just use a full cryptographic hash for indexing" is often overkill. SipHash is fast AND keyed, which is the real fix for hash-flooding, not full collision resistance.
• Document the boundary explicitly in code and API naming, rather than relying on tribal knowledge. Naming functions distinctly, for example hash_for_indexing() versus hash_for_password_storage(), prevents exactly this kind of accidental reuse from recurring later.

Direct answer

H(secret || message) is insecure as a MAC (Message Authentication Code) when H is a Merkle-Damgard hash, because a Merkle-Damgard digest literally IS the hash's complete internal state at the moment processing stopped. Anyone who sees that digest can resume hashing from that exact state and feed in more data, computing a valid hash for a longer message whose secret prefix they never saw. This is the length-extension attack. HMAC (Hash-based Message Authentication Code) fixes it by nesting two keyed hash computations, so the value an attacker could mechanically "extend" is never the value the verifier actually recomputes.

Structured elaboration

Merkle-Damgard construction. MD5, SHA-1, and SHA-256 (part of the SHA, Secure Hash Algorithm, family) all build a hash over arbitrary-length input the same way: split the padded message into fixed-size blocks, run each block through a compression function that mixes it into a running state, and output whatever that state equals after the last block. Padding is standardized (a delimiter bit, zero bytes, and an encoded bit-length field) so the final block is unambiguous.

The attack idea. Suppose MAC = H(secret || message). An attacker who knows message and the tag also effectively knows the hash's internal state right after processing (secret || message), because that state IS the tag. They can:

1. Guess or brute-force the length of secret (often narrow, since key sizes are frequently fixed).
2. Compute glue, the exact padding H would have appended after (secret || message) at that guessed length. This only depends on the length, never on the secret's actual bytes.
3. Resume hashing from the leaked state (the tag) and continue compressing an attacker-chosen suffix, applying the standard padding rules again for the new, longer total length.
4. The result is a valid H(secret || message || glue || suffix), computed without ever knowing secret.
5. The attacker sends (message || glue || suffix) with the forged tag; a server that naively recomputes H(secret || received_bytes) accepts it, because the values genuinely match.

Why HMAC resists it.

The tag the attacker sees is the output of the OUTER hash call. It's true that the attacker can mechanically continue that outer computation, since the length of its input (a block-size padded key plus one inner digest) is fixed and publicly known, so the padding is computable without secret knowledge. But doing so computes H((K xor opad) || inner || glue || suffix), a hash of a specific, longer byte string. That is simply not the string the verifier ever hashes. Verification always recomputes HMAC(K, candidate_message) from scratch: a brand-new inner hash over (K xor ipad || candidate_message), then a brand-new outer hash over (K xor opad || that fresh inner digest). Those two computations diverge from the attacker's extension as soon as the candidate message differs at all, so the extended value never equals what verification checks, regardless of whether the attacker can mechanically compute it.

Properties HMAC relies on. The proof needs the compression function to behave unpredictably once keyed, formally requiring H (when used the way HMAC uses it) to act like a PRF (pseudorandom function), plus the structural fact that the inner hash's output is a short, fixed-length value with no byte-for-byte relationship to any message an attacker would need to forge.

Worked example

A real MD5/SHA-256 implementation doesn't expose a "resume from this state" API, so here is a small, from-scratch Merkle-Damgard hash built specifically to demonstrate the exact structural mechanism (padding, state-as-digest, resumability) that also applies to MD5, SHA-1, and SHA-256 in production.

MASK64 = (1 << 64) - 1
IV = 0xCBF29CE484222325
BLOCK = 16
ODD_CONST = 0xBF58476D1CE4E5B9

def rotl64(x, r):
    return ((x << r) | (x >> (64 - r))) & MASK64

def compress(state, block):
    w0 = int.from_bytes(block[:8], 'big')
    w1 = int.from_bytes(block[8:], 'big')
    x = state ^ w0
    x = rotl64(x, 17)
    x = (x + w1) & MASK64
    x ^= rotl64(x, 31)
    x = (x * ODD_CONST) & MASK64
    x ^= (state >> 7)
    return x & MASK64

def md_pad(local_len, total_len_bytes):
    pad = b'\x80'
    while (local_len + len(pad)) % BLOCK != BLOCK - 8:
        pad += b'\x00'
    pad += (total_len_bytes * 8).to_bytes(8, 'big')
    return pad

def H(message):
    padded = message + md_pad(len(message), len(message))
    state = IV
    for i in range(0, len(padded), BLOCK):
        state = compress(state, padded[i:i+BLOCK])
    return state.to_bytes(8, 'big')

def H_resume(state_bytes, processed_len, tail):
    state = int.from_bytes(state_bytes, 'big')
    total_len = processed_len + len(tail)
    padded_tail = tail + md_pad(len(tail), total_len)
    for i in range(0, len(padded_tail), BLOCK):
        state = compress(state, padded_tail[i:i+BLOCK])
    return state.to_bytes(8, 'big')

def hmac_toy(key, message):
    if len(key) > BLOCK:
        key = H(key)
    key = key.ljust(BLOCK, b'\x00')
    ipad = bytes(b ^ 0x36 for b in key)
    opad = bytes(b ^ 0x5c for b in key)
    inner = H(ipad + message)
    return H(opad + inner)

secret = b'k3y-unknown-to-attacker'
message = b'user=alice&amount=10'
suffix = b'&admin=true'

# 1. naive MAC = H(secret || message): forgeable
naive_mac = H(secret + message)
guessed_len = len(secret) + len(message)
glue = md_pad(guessed_len, guessed_len)
forged = H_resume(naive_mac, guessed_len + len(glue), suffix)
server_side_naive = H(secret + message + glue + suffix)
print('naive MAC                        =', naive_mac.hex())
print('forged (length-extended) MAC     =', forged.hex())
print('server recomputes to             =', server_side_naive.hex())
print('naive MAC forgery accepted?      =', forged == server_side_naive)

# 2. same trick against HMAC-style construction: fails
tag = hmac_toy(secret, message)
outer_input_len = BLOCK + 8  # fixed: padded key + one digest, regardless of message length
naive_ext_of_tag = H_resume(tag, outer_input_len, suffix)
real_hmac_of_extended_message = hmac_toy(secret, message + suffix)
print('HMAC(K, message)                 =', tag.hex())
print('naive extension of the HMAC tag  =', naive_ext_of_tag.hex())
print('real HMAC(K, message+suffix)     =', real_hmac_of_extended_message.hex())
print('HMAC forgery accepted?           =', naive_ext_of_tag == real_hmac_of_extended_message)

Output:

naive MAC                        = 30d840639d174d72
forged (length-extended) MAC     = f3e85087bb9b1a3c
server recomputes to             = f3e85087bb9b1a3c
naive MAC forgery accepted?      = True
HMAC(K, message)                 = 6c71eb8f8d2ae6ea
naive extension of the HMAC tag  = 1ca1d95df1f503e9
real HMAC(K, message+suffix)     = 860b4a1b8ed8024b
HMAC forgery accepted?           = False

The naive construction accepts the forgery outright. The HMAC-style construction lets the attacker mechanically compute an extension of the tag, but that value simply doesn't match what real verification checks, exactly as the reasoning above predicts.

Trade-offs and pitfalls

• SHA-3, built on a sponge construction rather than Merkle-Damgard, does not expose its full internal state through its digest, so plain H(secret || message) with SHA-3 is not vulnerable to this specific attack. That is not a reason to skip a dedicated MAC construction: use HMAC, or a sponge-native keyed mode, since ad hoc MAC constructions have a long history of other subtle breaks even when length-extension isn't one of them.
• A common near-miss: H(message || secret), with the secret at the end instead of the start, is not vulnerable to this specific length-extension attack, but it inherits other weaknesses (for instance, if H has any known collision between message1 and message2, then H(message1 || secret) equals H(message2 || secret) for any secret). "Not vulnerable to length-extension" is not the same claim as "secure"; use HMAC either way.
• Don't try to patch this by hiding the secret's length. Attackers can often infer or brute-force it from context, such as a fixed-size API key, so security must never depend on length secrecy.

Direct answer

A Merkle tree is a binary tree in which every leaf is the hash of one data record and every internal node is the hash of its two children, so a single hash at the top, the root, commits to the entire dataset at once. A Merkle proof lets you prove that one specific leaf belongs under a given root by revealing only the sibling hashes along the path from that leaf up to the root, a number that grows logarithmically with the dataset size, letting a verifier recompute the same root without ever seeing the rest of the data.

Structured elaboration

Building the tree. Each leaf is leaf_i = H(data_i). Each parent is H(left_child || right_child). This repeats level by level until a single root remains. Real systems tag which KIND of thing is being hashed, for instance leaf = H(0x00 || data) and internal node = H(0x01 || left || right), so an attacker can't pass an internal node's hash off as if it were itself a valid leaf. Skipping this domain separation opens a real, if narrow, forgery.

Producing and checking a proof. To prove leaf_i is included, the prover supplies leaf_i's data plus exactly one sibling hash per level on the path up to the root, never the whole tree. The verifier recomputes the hash bottom-up using the supplied siblings and checks that the final result equals the trusted root.

Why the proof is logarithmic in size. A tree with n leaves has depth roughly log base 2 of n, and the proof needs exactly one sibling hash per level, so both proof size and verification cost grow with the LOG of the dataset size, not linearly with it.

Odd leaf counts. An unbalanced level, for example five leaves at the bottom, needs an explicit, specified rule, commonly duplicating the last node upward. This isn't a cosmetic detail: the exact rule must be fixed and applied consistently, since an ambiguous or inconsistently-implemented rule is itself a source of proof-forgery bugs.

Worked example

import hashlib

def H(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()

def leaf_hash(data: bytes) -> bytes:
    return H(b'\x00' + data)

def node_hash(left: bytes, right: bytes) -> bytes:
    return H(b'\x01' + left + right)

def build_tree(leaves_data):
    level = [leaf_hash(d) for d in leaves_data]
    levels = [level]
    while len(level) > 1:
        if len(level) % 2 == 1:
            level = level + [level[-1]]
        level = [node_hash(level[i], level[i+1]) for i in range(0, len(level), 2)]
        levels.append(level)
    return levels

def proof_for(levels, index):
    proof = []
    for level in levels[:-1]:
        if index % 2 == 1:
            proof.append(('L', level[index - 1]))
        else:
            sib = index + 1 if index + 1 < len(level) else index
            proof.append(('R', level[sib]))
        index //= 2
    return proof

def verify_proof(leaf_data, proof, root):
    h = leaf_hash(leaf_data)
    for side, sib in proof:
        h = node_hash(sib, h) if side == 'L' else node_hash(h, sib)
    return h == root

records = [b'txn-A: alice pays bob 10', b'txn-B: bob pays carol 5',
           b'txn-C: carol pays dave 2', b'txn-D: dave pays alice 7',
           b'txn-E: alice pays carol 1']  # odd count, exercises the duplicate-last-leaf rule

levels = build_tree(records)
root = levels[-1][0]
print('root =', root.hex())

target = 2
proof = proof_for(levels, target)
print('proof for leaf', target, 'has', len(proof), 'sibling hashes')
print('proof verifies?', verify_proof(records[target], proof, root))
print('tamper check (wrong content) verifies?', verify_proof(b'txn-C: carol pays dave 999', proof, root))

Output:

root = 0cf284c5f722737591a9b62df8a344ce1e6cc04630455eea27e54fe193ae7010
proof for leaf 2 has 3 sibling hashes
proof verifies? True
tamper check (wrong content) verifies? False

Five records need ceil(log2 5) = 3 sibling hashes per proof, matching what the code returns, and a proof over tampered content correctly fails.

Real-world systems and what they'd lose without this structure. Git's object model is content-addressed, and commits chain through hashes of trees, which are themselves Merkle-like structures over the repository's file layout. Without it, git would have no cheap way to know exactly which subtrees changed between two commits or to verify history's integrity without re-hashing the entire repository on every check. Certificate Transparency logs, the public append-only logs of every issued TLS certificate, use Merkle trees so any monitor can get a compact proof that a specific certificate is definitely in the public log, and a compact proof that the log grew consistently without being silently rewritten, without downloading the entire log. Without Merkle structure, auditing the whole Certificate Transparency ecosystem would require trusting each log operator outright or downloading everything ever logged for every single check.

Trade-offs and pitfalls

• Leaf and internal-node domain separation, the tagging shown above, is not decoration. Without it, an attacker can sometimes pass a two-child internal node's hash off as if it were itself a valid leaf, a second-preimage-style forgery against a naive, untagged tree.
• Sparse Merkle trees and Merkle Patricia tries trade away this simple structure for efficient non-membership proofs and key-value semantics, at real added implementation complexity. Reach for them only when you actually need to prove something is absent, not merely present.
• Proof size depends on a leaf's depth, so a pathologically unbalanced tree can make some proofs much larger than the ceil(log2 n) siblings a balanced tree would need; tree construction should keep the tree reasonably balanced.