Merkle trees: an interactive anti-entropy simulator

A Merkle tree is a tree of hashes. Each leaf is the hash of a piece of data, each parent is the hash of its children, and so the single hash at the root summarises everything below it. Two replicas can compare their roots in one step and, if they differ, walk down only the branches whose hashes differ to find exactly which keys are out of sync, comparing a few dozen hashes instead of every key.

In the playground, two replicas hold the same keys. Tap keys to change them on replica B and watch the comparison go down the tree from the root, a level at a time, skipping every subtree that already matches.

How a Merkle tree works

1. Hash the leaves: sort the data by key and hash each item, or each range of keys.
2. Hash pairs: each parent is the hash of its two children’s hashes together.
3. Repeat up to a single root hash. Changing any item changes its leaf, every hash on the path above it, and the root.
4. Compare: if two roots match, the data matches. If not, compare the children, and keep descending only where hashes differ.

Finding what differs between replicas

Replicas drift apart: a write that reached two of three replicas, a node that was down for an hour, a disk that lost a file. Background repair, called anti-entropy, finds and fixes these differences, and the hard part is finding them without shipping all the data. With Merkle trees each difference costs about two comparisons per level, so the work grows with the number of differences times the depth, not with the number of keys. In the playground’s first preset, one changed key out of 32 is found with 11 comparisons. At a larger scale:

Differences that sit close together in key order share most of their path, so they cost less than ones spread out. Walked level by level, the comparison takes one round trip per level, so real systems send the whole tree at once, which is small, or use wider trees with fewer levels.

When a Merkle tree does not help

When most keys differ, walking the tree costs more than comparing every key: with half of 32 keys changed, the playground compares 63 hashes instead of 32. Anti-entropy works because replicas are usually almost the same. The tree also has to be kept current. Some systems build it on demand by reading all the data, which is expensive enough that repairs are scheduled; others maintain it as writes arrive, which costs on every write. In practice each leaf covers a range of keys rather than one, so the tree stays small, and a mismatched leaf means comparing or streaming that range.

Where Merkle trees are used

• Replica repair: Amazon’s Dynamo paper described Merkle trees per key range for anti-entropy, and Cassandra and Riak use them to repair replicas.
• Git: a commit points to a tree whose id is the hash of its entries, so two repositories can tell which objects they lack by comparing hashes.
• Blockchains: a Bitcoin block header holds the Merkle root of its transactions, so a light client can check that a transaction is in a block with a short proof.
• Integrity: certificate transparency logs, ZFS and IPFS use hash trees so any tampering or corruption changes a hash that is checked.

That last idea is the Merkle proof: to show one item belongs to a tree, give its sibling hashes on the way up, about log₂ N of them, and the reader recomputes the root. For a million items that is 20 hashes.

A Merkle tree in code

import hashlib

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

def build(items):                      # items: a power of two, in key order
    levels = [[h(item) for item in items]]
    while len(levels[-1]) > 1:
        below = levels[-1]
        levels.append([h(below[i] + below[i + 1]) for i in range(0, len(below), 2)])
    return levels                      # levels[-1][0] is the root

def differences(a, b, level=None, i=0):
    """Indexes of the leaves that differ, visiting only subtrees whose hashes differ."""
    level = len(a) - 1 if level is None else level
    if a[level][i] == b[level][i]:
        return []                      # everything below matches
    if level == 0:
        return [i]
    return differences(a, b, level - 1, 2 * i) + differences(a, b, level - 1, 2 * i + 1)

In a system design interview

Merkle trees come up in the replication part of a distributed key-value store or file sync: “Writes go to three replicas and succeed at a quorum, so replicas can miss writes. Read repair fixes keys that get read; for the rest, each node keeps a Merkle tree per key range and compares it with the other replicas in the background, streaming only the ranges whose hashes differ.” Expect the follow-ups: how often repair runs, what it costs to build the trees, how deletes are repaired without bringing data back (tombstones kept longer than the repair interval), and how the tree is kept current as data changes.

Read the guide to Merkle trees, try quorum reads and writes to see how replicas fall behind in the first place, or watch a strong candidate design a distributed key-value store.

Questions people ask