Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

Merkle trees and membership proofs

After this lesson: I can verify a Merkle membership proof against a root.

65 min lesson2 commandsZero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Proving one name is on a long list

A Merkle tree turns a whole list into one short hash, the root. A membership proof then shows that one item is on the list using only a few hashes, not the whole list.

Zero-knowledge systems use it to prove you belong to a group, and blockchains to prove a payment is in a block.

By the end of this lesson

Note

I can verify a Merkle membership proof against a root.

Key words

WordWhat it means
Leafthe hash of one item on the list
Nodethe hash of two hashes joined
Rootthe single hash at the top of the tree
Siblingthe other hash in a pair
Membership proofthe siblings on the path from a leaf to the root

The cells students fill in are left blank in this preview.

A tree is hashes of hashes

Hash every item to make the leaves. Join the leaves in pairs and hash each pair to make the next level. Repeat until one hash is left: the root.

Change any item and its leaf changes, then its parent, and so on up to the root. So the root stands for the whole list. Module 37 (Blockchain) linked blocks with hashes in a line; a tree links them in pairs.

Try it: a tree of four rooms

Code: python
import hashlib

def leaf(item):
    return hashlib.sha256(("leaf:" + item).encode()).hexdigest()

def node(left, right):
    return hashlib.sha256(("node:" + left + right).encode()).hexdigest()

# Four rooms booked in a shared building.
a = leaf("room-1")
b = leaf("room-2")
c = leaf("room-3")
d = leaf("room-4")
left = node(a, b)
right = node(c, d)
root = node(left, right)
print("root:", root[:16])

# A proof that room-3 is booked: d, then left.
check = node(left, node(leaf("room-3"), d))
print("room-3 proof gives the root:", check == root)
# Swap left and the inner node in the outer call and run again.

A proof is the siblings going up

To show one item is on the list, give its siblings: the hash beside it, then the hash beside its parent, and so on. The checker hashes the item, joins each sibling on the correct side, and compares the result with the root.

A list of 8 needs 3 siblings, and a list of about a million needs only 20.

Check that dev is on the list

Command
docker exec jupyter python3 steps/membership.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Read what the lab printed

Eight names gave a root starting fb53457810bd44ae. The proof for dev, the fourth name, has 3 hashes, each marked L or R for the side it sits on. Hashing dev up the path gave the root, so the answer was True.

The name dan with the same proof gave False. Nobody can make a path that turns another name into this root.

Worked example: how long a proof is

Items on the listLevels above the leavesHashes in a proof
422
833
10241010
10485762020

The cells students fill in are left blank in this preview.

A common mistake

Warning

Many people think the siblings can be joined in any order. They cannot: node(a, b) and node(b, a) are different hashes. The position of the item tells you the side. An even position at a level means the sibling goes on the right.

List the functions in merkle.py

Command
docker exec jupyter grep -n def merkle.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

About this lab and its source: Zero-knowledge proofs lab: commitments, Schnorr, Fiat-Shamir and Merkle proofs in Python

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.