Merkle Trees Explained: How Git, DynamoDB, and Bitcoin Verify Data Without Reading All of It

Copying a 500GB database to check if two replicas actually match is a bad plan. Reading a whole file to prove one paragraph in it is genuine is worse. A Merkle tree solves both problems the same way: it turns a large dataset into a small hash that changes if anything inside it changes, and a structure you can walk to find exactly what changed without touching the rest. Git uses this idea for every commit. DynamoDB uses it to keep replicas in sync without comparing every row. Bitcoin uses it so a phone can verify a transaction without downloading the blockchain.

The structure, built from the bottom up

Start with your data split into chunks, files, rows, blocks, whatever unit makes sense. Hash each chunk. Those hashes are the leaves of the tree.

Now pair the leaves up and hash each pair together, concatenating the two hashes and hashing the result. That gives you the next level up, half as many nodes. Keep pairing and hashing until exactly one hash remains: the root.

import hashlib

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

def build_merkle_tree(chunks: list[bytes]) -> list[list[str]]:
    """Returns every level of the tree, leaves first, root last."""
    level = [h(chunk) for chunk in chunks]
    tree = [level]
    while len(level) > 1:
        if len(level) % 2 == 1:
            level = level + [level[-1]]  # duplicate the odd one out
        next_level = [
            h((level[i] + level[i + 1]).encode())
            for i in range(0, len(level), 2)
        ]
        tree.append(next_level)
        level = next_level
    return tree

data = [b"block-1", b"block-2", b"block-3", b"block-4"]
tree = build_merkle_tree(data)
print("Root:", tree[-1][0])

That root hash is the entire dataset’s fingerprint. Change one byte in block-3, and every hash on the path from that leaf to the root changes, but every hash off that path stays exactly the same. That last part is the whole point.

Why the structure, not just a single hash

A single SHA-256 of the whole dataset already tells you whether two copies match. What it can’t do is tell you where they differ, or let someone prove a small piece is genuine without handing over everything.

Finding the difference. Two systems holding a Merkle tree over the same data structure can compare root hashes first. If they match, done, no further work. If they don’t, each side compares the hashes one level down. Whichever branch differs, recurse into it; whichever branch matches, skip it entirely. You end up walking only the path to the actual change, in O(log n) comparisons instead of comparing every leaf.

Proving membership. A Merkle proof for one leaf is the sibling hash at every level on the way to the root, not the whole tree. Recompute the pairwise hashes up that specific path using the proof, and if you land on the known root hash, that leaf is provably part of the dataset. Nobody needed to send you the other leaves.

Task	Without a Merkle tree	With a Merkle tree
Confirm two copies match	Transfer and compare everything	Compare one root hash
Find what changed	Compare every chunk	Walk only the diverged branch, O(log n)
Prove one item belongs to the set	Send the entire dataset	Send O(log n) sibling hashes

Where this actually shows up

Git. Every blob, tree, and commit object is content-addressed: its hash is derived from its contents, and a tree object’s hash depends on the hashes of everything inside it. That’s a Merkle DAG rather than a strict binary tree, files aren’t paired up two at a time, but the principle is identical. It’s why git fetch can figure out exactly which objects a remote is missing by comparing commit and tree hashes, instead of re-transferring the whole repository, and why two clones sharing a commit hash are guaranteed to be byte-identical all the way down.

Database anti-entropy. DynamoDB, Cassandra, and Riak use Merkle trees to keep replicas in sync after a partition heals or a node comes back online. Instead of comparing every row across replicas, which is exactly the “copy 500GB to check it” problem from the top of this post, each replica builds a Merkle tree over its data and the nodes exchange root hashes first, then walk down only the branches that diverge. This is also the same conceptual foundation behind distributed locks and coordination primitives in that it trades a full comparison for a structured, incremental one.

Content-addressed storage and CDNs. IPFS and similar systems name every piece of content by its hash, and larger files get split into chunks organized in a Merkle structure so a client can verify each chunk as it arrives, rather than downloading the whole file before trusting any of it. BitTorrent does something similar with its piece hashes.

Certificate Transparency and blockchains. CT logs commit to a Merkle tree of every certificate they’ve seen, so anyone can request a proof that a specific certificate is logged without downloading the whole log. Bitcoin blocks commit to a Merkle root of their transactions, which is what lets a lightweight (SPV) wallet verify a transaction is in a block using a small proof instead of the full block.

When it’s not worth reaching for

A Merkle tree adds real complexity: you need to maintain the tree structure, recompute affected branches on every write, and handle the odd-node-out case shown in the code above. For a dataset that’s small enough to hash and compare wholesale, or that changes so often the tree needs constant rebuilding anyway, plain hashing or a changelog/version vector approach is simpler and just as effective. The pattern earns its cost specifically when you have a large, mostly-static or append-heavy dataset, and a real need to either compare it cheaply across a network or prove small pieces of it without exposing the rest. Reaching for one because it sounds rigorous, on a dataset small enough to just hash outright, is adding a data structure you’ll have to maintain for a problem a single sha256sum already solves.

If you’re designing a sync or replication system and trying to decide between this and a simpler leader-based coordination approach, the two solve different problems: leader election picks who’s authoritative, a Merkle tree tells you cheaply whether two copies agree once you already know who’s talking to whom. Most real systems that need both use them together, one for coordination, one for efficient verification.