Commitments, Merkle trees and nullifiers

Hash a secret together with a random salt and publish the result. The output reveals nothing about the secret (hiding), and later you can't claim you committed to something else, because that would mean finding a hash collision (binding).

Inside circuits the hash of choice is Poseidon. It is built from field arithmetic, so it costs a few hundred constraints where SHA-256 costs tens of thousands. Solana has a Poseidon syscall, sol_poseidon, with the circom parameters on BN254. It costs 61·n² + 542 compute units for n inputs, so a program can recompute the same hashes a circuit did.

Pair the commitments up and hash each pair, then pair the results, and keep going until one hash is left: the root. A tree of depth 12 holds 4,096 leaves, and proving one is inside takes 12 sibling hashes, 384 bytes in the clear. A program only has to store the 32-byte root.

A bare Merkle path gives you away, though: it says exactly which leaf you are. Zero-knowledge fixes that. The path goes in as a private input, and the circuit only outputs the root it rebuilds.

The allowlist circuit in this site's lab checks four things privately:

1. Your commitment is Poseidon(secret).
2. Hashing it up your path gives the public root.
3. Your nullifier is Poseidon(secret, scope).
4. The recipient is bound to the proof.

The verifier sees four numbers (root, scope, recipient, nullifier) and nothing else. In circom that comes to 3,370 constraints, and the proof is still 256 bytes.

If proofs reveal nothing, what stops someone from claiming twice? The nullifier. It's a hash of your secret and the claim's scope, so it's the same every time you claim this drop. The program keeps a list of used nullifiers, typically one small account per nullifier, and refuses repeats. Because the scope is part of the hash, your nullifier for one drop can't be linked to your nullifier for another.

The recipient matters too. A valid proof sitting in the mempool could be copied by someone else and sent with their own address. Making the recipient a public input, constrained inside the circuit, means changing it breaks the proof. The lab lets you try exactly that.

Light Protocol's ZK Compression stores accounts as leaves in state trees of height 26. A raw path in such a tree would be 832 bytes. Instead, one 128-byte Groth16 proof shows that up to eight accounts are in the tree. Address trees use the opposite kind of proof, non-inclusion, to show a new address hasn't been taken.

The trees and hashes would survive a quantum computer. The 128-byte proof wouldn't: Chapter 4 explains the difference.