How Merkle Trees Actually Work (And Why Git and Blockchains Both Use Them)

Quick Answer

A Merkle tree hashes data in pairs, layer by layer, until one root hash represents the entire dataset. Change even one byte anywhere in the data and the root changes too, and you can prove any single piece of data belongs to the set by checking just log2(n) hashes instead of re-hashing everything. That's exactly why Git's commit history and every blockchain's transaction list both use one.

The Problem a Merkle Tree Solves

Say you have a list of 10,000 records — bank transactions, files in a backup, commits in a repository — and you want two things at once: a single short fingerprint that changes if any record changes, and a fast way to prove one specific record is really part of that list without handing over all 10,000 records to check.

The naive fingerprint is easy: concatenate everything and hash it with SHA-256. That gives you the first property — change one byte anywhere and the hash changes completely. But it fails the second property badly. To prove record #4,731 is really in the set, you'd have to re-hash the entire 10,000-record blob again, which means whoever is checking your proof needs a copy of all 10,000 records in the first place. That defeats the point of a lightweight proof.

A Merkle tree (named after Ralph Merkle, who patented the idea in 1979) fixes this by hashing the data in a tree shape instead of a flat blob. The result: one root hash still fingerprints everything, but proving membership of a single record only costs you log2(n) hashes — for 10,000 records, that's about 14 hashes, not 10,000 records.

Building the Tree: Hash, Pair, Repeat

The construction is mechanical. Start with your data blocks as the leaves. Hash each one. Then pair up adjacent hashes and hash each pair together to get the next level up. Keep pairing and hashing until only one hash is left — that's the root.

Here's the real algorithm in Python, run against 8 sample transaction records:

import hashlib

def h(data: bytes) -> str:
    return hashlib.sha256(data).hexdigest()

def build_merkle_tree(blocks):
    level = [h(b) for b in blocks]
    levels = [level]
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level), 2):
            left = level[i]
            right = level[i + 1] if i + 1 < len(level) else level[i]
            nxt.append(h((left + right).encode()))
        levels.append(nxt)
        level = nxt
    return levels

blocks = [f\"transaction-{i}:pay {10*i} rupees\".encode() for i in range(8)]
levels = build_merkle_tree(blocks)
root = levels[-1][0]
print(\"Number of levels:\", len(levels))
print(\"Root hash:\", root)

Actually running this on 8 blocks produces a real 4-level tree: 8 leaf hashes, then 4, then 2, then 1 root. The output was:

Number of levels: 4
Root hash: f78e6ad8c065253f7dd2e74aeecc4a23bbafaa11062e0fd39d28b71951509e4e

Notice the odd-block-count handling in the code: if a level has an odd number of hashes, the last one gets paired with itself (some implementations pad with a zero hash instead — both are valid design choices, but they have to be applied consistently or two implementations will disagree on the same data).

Merkle Proofs: Proving One Leaf Belongs, Without the Rest

This is the actual payoff. To prove leaf #3 is part of the tree, you don't need the other 7 leaves — you only need the sibling hash at each level on the path from that leaf up to the root. For an 8-leaf tree, that path is 3 levels deep, so the proof is exactly 3 hashes.

def get_proof(levels, index):
    proof = []
    idx = index
    for level in levels[:-1]:
        sibling_idx = idx ^ 1
        if sibling_idx >= len(level):
            sibling_idx = idx
        is_left = (idx % 2 == 0)
        proof.append((level[sibling_idx], is_left))
        idx //= 2
    return proof

def verify_proof(leaf_hash, proof, root):
    cur = leaf_hash
    for sibling, is_left in proof:
        cur = h((cur + sibling).encode()) if is_left else h((sibling + cur).encode())
    return cur == root

proof = get_proof(levels, 3)
leaf3_hash = levels[0][3]
valid = verify_proof(leaf3_hash, proof, root)

Running this for real: len(proof) comes out to exactly 3, and verify_proof(...) returns True. The verifier only ever sees 3 sibling hashes plus the leaf hash they're checking — never the other 7 transactions. That's the whole trick: the tree structure turns "prove membership" from an O(n) problem into an O(log n) one.

What Tampering Actually Looks Like

The tamper-detection property isn't just claimed — it's checkable. Take the same 8 blocks, change block #3's content from "transaction-3:pay 30 rupees" to a tampered amount, and rebuild the tree:

tampered_blocks = blocks.copy()
tampered_blocks[3] = b\"transaction-3:pay 999999 rupees (TAMPERED)\"
tampered_levels = build_merkle_tree(tampered_blocks)
tampered_root = tampered_levels[-1][0]
print(\"Roots match:\", root == tampered_root)

Real output: Roots match: False. The tampered root came out as 9f4931cc9970a7678c10a24dc3fbd6fccb6c143f221713ba5adb22c41fbe4f78 — completely different from the original, even though only one of the eight blocks changed. That's SHA-256's avalanche effect propagating up through every level the tampered leaf touches on its way to the root.

Just as important: the OLD proof for leaf 3, checked against the tampered leaf's new hash and the ORIGINAL root, also comes back False. So an attacker can't just swap in new data and reuse an old, still-valid-looking proof — the proof only verifies against the exact data it was generated for.

Merkle Trees Inside Git

If you've read how Git actually stores data, you've already seen the raw materials for this without the "Merkle tree" label attached. Git's tree objects store hashes of blobs (file contents) and other tree objects (subdirectories), and a commit object stores the hash of its root tree plus the hash of its parent commit. Follow that chain and you get a Merkle DAG (directed acyclic graph) — a Merkle tree's less strict cousin, where a node can have more than one parent, which is exactly what happens at a merge commit.

This is why changing a single line in a deeply nested file changes the hash of that file's blob, which changes the hash of every tree object above it, which changes the hash of the commit itself. It's the identical mechanism as the tamper demo above — Git just calls the pieces "blobs," "trees," and "commits" instead of "leaves" and "root."

Merkle Trees Inside Blockchains

A block in a blockchain (see how blockchain actually works for the block/hash/mining side of this) doesn't hash its transactions as one flat blob either — it builds a Merkle tree out of them and stores only the root hash in the block header. A block with 2,000 transactions still fits its transaction fingerprint into one 32-byte root.

This is what makes "light clients" (SPV — simplified payment verification — wallets) possible: a phone wallet that doesn't store the whole blockchain can still verify that a specific transaction is really included in a specific block by asking a full node for a Merkle proof — around log2(2000) ≈ 11 hashes — instead of downloading and re-hashing all 2,000 transactions itself.

Why Not Just Hash Everything at Once?

You could get the tamper-detection property from a single flat hash over all the data. What you'd lose is the proof property, and at scale that loss is the whole difference between a usable system and an unusable one:

• Flat hash: verifying one record means re-hashing the entire dataset. For a blockchain block, that means downloading every transaction just to check one.
• Merkle tree: verifying one record costs log2(n) hashes. For 2,000 transactions, that's roughly 11 hashes instead of 2,000 full transaction downloads.

That logarithmic proof size is the entire reason Merkle trees show up wherever something needs to be both tamper-evident and cheaply verifiable in pieces: Git repositories, blockchains, certificate transparency logs, and distributed file systems like IPFS all lean on the same shape.

Frequently Asked Questions