48. Merkle trees in pure Python

A Merkle tree lets you prove membership of an item in a large set with a small proof, by repeatedly hashing pairs of nodes up to a single root.

python
import hashlib

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

def merkle_root(leaves: list[bytes]) -> bytes:
    if not leaves:
        return b""
    level = [h(leaf) for leaf in leaves]
    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])   # duplicate last if odd count
        level = [h(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
    return level[0]

Duplicating the last node when the level has an odd count is one common convention (others exist, e.g. promoting it unchanged); the important part is that both the prover and verifier agree on the same rule.

Read in another language

How to study this topic

Scoring

Check your understanding

Badges