Merkle Trees & Proofs

A block can hold hundreds or thousands of transactions, but the block header is tiny and fixed-size. So how does the header commit to all of them at once — such that changing a single transaction would visibly break the block? And how can a lightweight wallet, holding only headers, be convinced that one specific transaction is in a block without downloading the whole thing?

Both questions have the same answer: a Merkle tree. It folds a whole list of transaction ids (txids) into a single 32-byte Merkle root that the header stores, and it lets anyone prove membership with just a handful of hashes.

Where this fits in the bigger story

This is the hands-on companion to Merkle Trees & SPV Proofs. If the intuition for why a tree of hashes is tamper-evident is hazy, skim that chapter — here we build the real thing.

The idea before the code

Picture the txids as the leaves at the bottom of a tree. We hash them together in pairs to make the next level up, then pair those hashes, and so on, until a single hash remains at the top — the root.

        root
       /    \
     h01      h23
    /   \    /   \
  txid0 txid1 txid2 txid3

Because every level is built from the level below, the root is a fingerprint of every leaf. Flip one bit in any transaction and its txid changes, which changes its parent, which changes that parent — the change ripples all the way to the root. The header commits to the root, so the header effectively commits to every transaction. That’s the tamper-evidence we need.

The second gift is the proof. To convince someone that txid2 is in the tree, you don’t need the whole tree — you need just the siblings along the path from txid2 up to the root: txid3, then h01. The verifier re-hashes their way up and checks they land on the known root. For a tree of n leaves that’s only about log₂(n) hashes — the heart of SPV (Simplified Payment Verification), how light wallets verify inclusion cheaply.

Hashing a pair

Everything rests on one small helper that combines two child hashes into their parent:

fn hash_pair(left: &Hash, right: &Hash) -> Hash {
    let mut buf = Vec::with_capacity(64);
    buf.extend_from_slice(left);
    buf.extend_from_slice(right);
    sha256d(&buf)
}

A Hash is our 32-byte array. We make a Vec<u8> — a growable byte buffer — and pre-size it for 64 bytes with Vec::with_capacity(64) so it never has to reallocate. extend_from_slice copies the left hash’s bytes in, then the right hash’s, giving a 64-byte concatenation. Then sha256d (double SHA-256, the same construction Bitcoin uses) crunches it down to the 32-byte parent. Order matters: hashing left-then-right gives a different result than right-then-left, and we’ll rely on that when building and checking proofs.

Computing the root

/// Compute the Merkle root of a list of leaves (txids).
///
/// Like Bitcoin, when a level has an odd number of nodes we duplicate the last
/// one before pairing.
pub fn merkle_root(leaves: &[Hash]) -> Hash {
    if leaves.is_empty() {
        return ZERO_HASH;
    }
    let mut level: Vec<Hash> = leaves.to_vec();
    while level.len() > 1 {
        if level.len() % 2 == 1 {
            level.push(*level.last().unwrap());
        }
        let mut next = Vec::with_capacity(level.len() / 2);
        for pair in level.chunks(2) {
            next.push(hash_pair(&pair[0], &pair[1]));
        }
        level = next;
    }
    level[0]
}

The input is a slice — &[Hash] — a borrowed view of a list of leaves. We don’t own it, we just read from it, so the caller keeps their Vec.

First, the empty case: no transactions means there’s nothing to commit to, so we return ZERO_HASH (an all-zeros sentinel from our hashing module).

Otherwise we copy the leaves into an owned, mutable Vec called level — this is the current row of the tree, and we’ll repeatedly replace it with the row above. The while level.len() > 1 loop keeps collapsing rows until exactly one hash is left.

Inside each iteration:

• Handle odd counts. Pairs need an even number of nodes. If level.len() % 2 == 1, we duplicate the last hash: level.push(*level.last().unwrap()). (last() returns an Option; we unwrap() it safely because we already know the level is non-empty, and * copies the array out of the reference.) This “duplicate the last one” rule is exactly what Bitcoin does.
• Pair and hash. level.chunks(2) is a wonderfully tidy iterator: it hands us the slice two elements at a time — [txid0, txid1], then [txid2, txid3], and so on. For each pair we push hash_pair(&pair[0], &pair[1]) onto the next row.
• Move up. level = next makes the parent row the new current row, and the loop checks its length again.

When the loop ends, level holds a single element — level[0] — the root.

The duplicate-last subtlety

Duplicating the final node is simple but historically introduced a quirk (CVE-2012-2459) where two different transaction lists could produce the same root. Real systems guard against it; we keep the classic rule because it matches Bitcoin and keeps the loop readable. Worth knowing the sharp edge exists.

A single proof step

To prove inclusion we record, at each level, the sibling we paired with and which side it was on:

/// One step in a Merkle proof: a sibling hash and which side it sits on.
#[derive(Clone, Debug)]
pub struct ProofStep {
    pub sibling: Hash,
    /// True if the sibling is on the right (so we hash `current || sibling`).
    pub sibling_on_right: bool,
}

A ProofStep is a small struct: the sibling hash, plus a bool recording whether that sibling sat on the right. We need the side because hash_pair is order-sensitive — the verifier must combine the hashes in the same order they were originally combined, or the math won’t reproduce the root.

Building the proof

/// Build an authentication path proving `leaves[index]` is in the tree.
pub fn merkle_proof(leaves: &[Hash], index: usize) -> Vec<ProofStep> {
    let mut proof = Vec::new();
    if leaves.is_empty() || index >= leaves.len() {
        return proof;
    }
    let mut level: Vec<Hash> = leaves.to_vec();
    let mut idx = index;
    while level.len() > 1 {
        if level.len() % 2 == 1 {
            level.push(*level.last().unwrap());
        }
        let sibling_on_right = idx % 2 == 0;
        let sibling_index = if sibling_on_right { idx + 1 } else { idx - 1 };
        proof.push(ProofStep { sibling: level[sibling_index], sibling_on_right });

        let mut next = Vec::with_capacity(level.len() / 2);
        for pair in level.chunks(2) {
            next.push(hash_pair(&pair[0], &pair[1]));
        }
        level = next;
        idx /= 2;
    }
    proof
}

This mirrors merkle_root — same level-collapsing loop — but it also tracks where our leaf is and records its sibling at each level.

We start with idx = index, the position of the leaf we’re proving, and an empty proof vector. We guard against bad input up front: an empty list or an out-of-range index returns an empty proof.

At each level, before collapsing, we figure out our sibling:

• let sibling_on_right = idx % 2 == 0; — if our index is even, we’re the left child, so our sibling is to the right. If odd, we’re the right child and the sibling is on the left.
• let sibling_index = if sibling_on_right { idx + 1 } else { idx - 1 }; — if/else is an expression in Rust, so it produces a value we bind directly. The sibling is the neighbor on the computed side.
• We push a ProofStep capturing that sibling hash and its side.

Then we collapse the level just like before, and crucially update idx /= 2: integer division by two maps a child’s index to its parent’s index in the row above. Both index 2 and index 3 (a pair) map to parent index 1 — exactly right. The loop continues until we reach the root, and proof now holds one step per level, bottom to top.

Verifying the proof

/// Recompute the root from a leaf and its proof, to verify inclusion.
pub fn verify_proof(leaf: &Hash, proof: &[ProofStep], expected_root: &Hash) -> bool {
    let mut current = *leaf;
    for step in proof {
        current = if step.sibling_on_right {
            hash_pair(&current, &step.sibling)
        } else {
            hash_pair(&step.sibling, &current)
        };
    }
    &current == expected_root
}

This is the whole point, and it’s beautifully short. The verifier starts with current set to the leaf they care about and walks the proof from bottom to top. For each step:

• If the sibling was on the right, the original pairing was current || sibling, so we hash hash_pair(&current, &step.sibling).
• Otherwise the sibling was on the left, so we hash hash_pair(&step.sibling, &current).

Each iteration replaces current with the parent hash, climbing one level. After the loop, current is the root we recomputed. We compare it to the expected_root (the one from the trusted header) and return the bool: equal means the leaf really is in the tree; not equal means the proof is bogus.

Notice the verifier never saw the other transactions — only log₂(n) sibling hashes. That’s the SPV superpower: a phone-sized wallet can verify inclusion against a header it trusts, downloading almost nothing.

Try it

Here’s a self-contained test: build a root from fake leaves, generate a proof for one of them, and confirm it verifies (and that a wrong leaf doesn’t).

#[test]
fn proof_round_trips() {
    use blockchain_from_scratch::merkle::{merkle_proof, merkle_root, verify_proof};

    // Five fake leaves — note the odd count exercises the duplicate-last rule.
    let leaves = [[1u8; 32], [2u8; 32], [3u8; 32], [4u8; 32], [5u8; 32]];

    let root = merkle_root(&leaves);

    // Prove leaf 2 is included.
    let proof = merkle_proof(&leaves, 2);
    assert!(verify_proof(&leaves[2], &proof, &root));

    // A leaf that isn't there must NOT verify against the same proof.
    assert!(!verify_proof(&[99u8; 32], &proof, &root));
}

Run the project’s tests to see Merkle proofs (and everything else) pass:

cargo test

Check your understanding

1. The block header is small and fixed-size, yet it commits to every transaction in the block. By what mechanism does changing one transaction change the Merkle root?
2. Why does hash_pair care about the order of its two arguments, and how does verify_proof honor that order?
3. What does the idx /= 2 line do at the end of each loop in merkle_proof, and why is integer division the right operation?
4. A proof for a tree of 1,024 leaves contains roughly how many ProofSteps? Why is this the basis of SPV?
5. What does merkle_root do when a level has an odd number of nodes, and what subtle problem does that rule historically introduce?

Show answers

1. Changing one transaction changes its txid (a leaf), which changes its parent hash, which changes that parent — the change ripples all the way up to the root. Since the header commits to the root, the header effectively commits to every transaction, making any tampering visible.
2. hash_pair concatenates left-then-right before hashing, and hashing left || right differs from right || left, so order is part of the result. verify_proof honors it by checking each step’s sibling_on_right: if the sibling was on the right it hashes hash_pair(&current, &sibling), otherwise hash_pair(&sibling, &current) — reproducing the original order.
3. idx /= 2 (integer division) maps a child’s index in the current row to its parent’s index in the row above — both index 2 and index 3 (a pair) collapse to parent index 1. Integer division is right because pairs (2k, 2k+1) both belong to parent k, which is exactly what truncating division computes.
4. About 10 (log₂(1024) = 10). This is the basis of SPV: a light wallet holding only headers can verify a transaction’s inclusion with just ~log₂(n) sibling hashes, never downloading the whole block — cheap to check against a header it trusts.
5. It duplicates the last node so the level has an even count before pairing (exactly what Bitcoin does). This historically introduced a quirk (CVE-2012-2459) where two different transaction lists could produce the same root, which real systems must guard against.