Merkle Trees: Finding What Differs Without Sending Everything

The problem. Two replicas hold millions of records and a few have drifted apart. Sending everything to compare is wasteful; sending a hash of everything only says 'they differ' without saying where. You want to find the differences with little traffic. This repair work, run in the background to bring replicas back in line, is called anti-entropy.

Build the tree. Hash each block of data to make the leaves. Then hash each pair of neighboring hashes together to make the next level, and repeat until one hash remains: the root. If a level has an odd number of nodes, carry the last one up (or hash it with itself). The root summarizes every block, and changing a single block changes every hash on its path to the root.

Compare. Two replicas exchange roots. Equal roots mean identical data, and the check cost one hash. Different roots mean you compare the two children. Descend only into children whose hashes differ. With one changed block among n, you compare about 2 log2 n hashes, not n. For a million blocks that is about 40 comparisons instead of a million.

import hashlib

def h(data):
    return hashlib.sha256(data).hexdigest()[:8]

def build(blocks):
    level = [h(b'leaf:' + b) for b in blocks]          # a prefix tells leaves from inner nodes
    tree = [level]
    while len(level) > 1:
        if len(level) % 2:
            level = level + [level[-1]]                # odd count: pair the last one with itself
        level = [h(('node:' + level[i] + level[i + 1]).encode()) for i in range(0, len(level), 2)]
        tree.append(level)
    return tree

def differing(a, b, depth=None, index=0):
    depth = len(a) - 1 if depth is None else depth
    if a[depth][index] == b[depth][index]:
        return []
    if depth == 0:
        return [index]
    found = []
    for child in (2 * index, 2 * index + 1):
        if child < len(a[depth - 1]):
            found += differing(a, b, depth - 1, child)
    return found

left = build([b'k1=a', b'k2=b', b'k3=c', b'k4=d'])
right = build([b'k1=a', b'k2=b', b'k3=CHANGED', b'k4=d'])
print(left[-1][0] == right[-1][0])     # False  the roots differ
print(differing(left, right))          # [2]    only block 2 has to be sent

Why the prefixes. Without a marker, an attacker could craft a data block whose bytes look like two child hashes joined together, making a leaf and an inner node collide. Hashing leaves and inner nodes with different prefixes closes that gap. Real systems do this; the sample does too.

Where it appears. Dynamo-style stores (Cassandra, Riak) compare Merkle trees between replicas to repair drift. Git stores objects under their content hash and links them in a Merkle structure. Blockchains put a transaction tree's root in each block header. Certificate transparency logs use a tree so anyone can check that a certificate is in the log without downloading it all.

An inclusion proof. To prove one block belongs to a tree with a known root, you only send the sibling hashes along its path, about log n of them. The verifier recomputes the root from the block and those siblings and compares. That is how a light client checks a transaction without holding the chain.

Limits. A tree is built over a fixed ordering of blocks, so when records are inserted in the middle every later block shifts and the tree changes a lot. Real systems build the tree over key ranges (a fixed hash space) so a record always lands in the same leaf, and they rebuild or update the tree as data changes, which costs CPU and I/O.