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
| Word | What it means |
|---|---|
| Leaf | the hash of one item on the list |
| Node | the hash of two hashes joined |
| Root | the single hash at the top of the tree |
| Sibling | the other hash in a pair |
| Membership proof | the 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
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
docker exec jupyter python3 steps/membership.pyShown 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 list | Levels above the leaves | Hashes in a proof |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 3 | 3 |
| 1024 | 10 | 10 |
| 1048576 | 20 | 20 |
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
docker exec jupyter grep -n def merkle.pyShown here, not run. Press Start lab to type it into your own lab’s terminal.