TL;DR
- You'll learn what hashes and commitments are, why they're the "glue" of ZK systems, and how a Merkle tree lets you prove one item is in a huge list with just a handful of hashes.
In Post 2, nearly every use case quietly depended on two things: "commit to some data without revealing it" and "prove this item is in that set". Today we build both, with zero ZK math. These are ordinary cryptographic tools, but once circuits show up you'll see them everywhere.
Building block 1: hashes
A hash function takes any input and spits out a fixed-size fingerprint:
sha256("dev") = ef260e9a...
sha256("devs") = 03f53542... # small change, totally different output
Three properties make hashes useful:
- Deterministic: same input, same output, every time.
- One-way: given the output, you can't find the input (except by guessing).
- Collision-resistant: you can't find two different inputs with the same output.
Building block 2: commitments
A commitment is a sealed envelope. You put a value inside, seal it, and hand it over. Later you can open it to show what was inside, but:
- Hiding: nobody can peek inside before you open it.
- Binding: you can't swap the contents after sealing.
The simplest commitment is a hash with some randomness thrown in:
commitment = sha256(value + random_salt)
Why the salt? Without it, if I commit to my vote with sha256("yes"), you can just hash "yes" and "no" yourself and compare. The salt makes guessing useless. (Remember this one, it comes back as a gotcha.)
Where you'll see it in ZK: "I know the secret behind this commitment" is one of the most common statements ever proven. The commitment is public, the secret is the witness.
Building block 3: Merkle trees
Now the fun one. Say a voting app has 1,000,000 registered voters, and you want to prove you're one of them. You could post the whole list on-chain... but that's a million entries. Expensive, and it outs everyone.
A Merkle tree squeezes the whole list into a single 32-byte hash called the root:
- Hash every item. These are the leaves.
- Pair up neighbors and hash each pair together.
- Repeat until only one hash is left: the root.
The magic: inclusion proofs
To prove "cherry" is in the tree, I don't send you the list. I send you only the siblings along the path from cherry up to the root, one hash per level.
You recompute: hash cherry, combine with sibling 1, combine with sibling 2, ... and check you land on the root. If you do, cherry was in the tree. If anything was tampered with, the hashes won't line up.
For a million leaves the tree is 20 levels deep, so the proof is 20 hashes. That's log₂(n), and that's why Merkle trees are everywhere.
Hands-on: a tiny Merkle tree
Here's the core of it:
from hashlib import sha256
def h(*parts: bytes) -> bytes:
return sha256(b"".join(parts)).digest()
def build(leaves):
level = [h(leaf) for leaf in leaves]
levels = [level]
while len(level) > 1:
if len(level) % 2: # odd count: duplicate the last node
level = level + [level[-1]]
level = [h(level[i], level[i + 1]) for i in range(0, len(level), 2)]
levels.append(level)
return levels
def prove(levels, index):
path = []
for level in levels[:-1]:
if len(level) % 2:
level = level + [level[-1]]
sibling = index ^ 1 # flip the last bit: 4<->5, 6<->7
path.append((level[sibling], sibling > index))
index //= 2
return path
def verify(root, leaf, path):
node = h(leaf)
for sibling, sibling_on_right in path:
node = h(node, sibling) if sibling_on_right else h(sibling, node)
return node == root
And using it:
fruits = [b"apple", b"banana", b"cherry", b"date", b"elderberry"]
levels = build(fruits)
root = levels[-1][0]
proof = prove(levels, 2) # prove "cherry"
assert verify(root, b"cherry", proof)
assert not verify(root, b"durian", proof) # wrong leaf -> fails
$ python3 merkle.py
root: 3c9fc6e9...
proof size: 3 hashes for 5 leaves
all checks passed
Two details worth noticing:
-
index ^ 1finds your sibling: XOR-ing the last bit turns 4 into 5 and 5 into 4. - The bool in each path step says which side the sibling is on, because
h(a, b) != h(b, a). Get the order wrong and nothing verifies. In Post 8, those left/right choices become the bits of the leaf's index, inside a circuit.
Gotcha: a Merkle proof is not private
When I first got this working, I thought: great, I've proven membership without revealing the list! True. But look at what I sent: the leaf itself ("cherry") and the path. The path plus the sibling positions tells you exactly which leaf I am.
So a plain Merkle proof is succinct but not zero-knowledge. For anonymous voting, that's a deal-breaker: the verifier learns which voter you are.
The fix is to put the Merkle check inside a ZK circuit, where the leaf and path are private inputs and only the root is public. That's exactly what we'll do in 8th post, and that's why I wanted you to see the plain version first.
(Bonus gotcha: in production trees you should hash leaves and inner nodes differently, e.g. with a prefix byte, so an attacker can't pass off an inner node as a leaf. I kept it simple here.)
Recap
- Hash: a one-way fingerprint. Commitment: a sealed envelope (hash + salt).
- Merkle tree: commits to a whole list with one root. Inclusion proof: log₂(n) sibling hashes.
- A plain Merkle proof reveals which leaf you are. Making it private needs a circuit.
Next up: we've done enough theory. In next post, we'll write, prove and verify an actual zero-knowledge proof.
Further reading
- Merkle tree (Wikipedia): including the second-preimage attack from the bonus gotcha.
- ZKDocs: commitments and other primitives: short, precise definitions.
- RareSkills ZK Book: the next step if you want the math behind hiding and binding.
Series codebase
All the code from posts in this series will be in this GitHub repo: Zero-Knowledge from zero knowledge

Top comments (0)