Nullifiers, Merkle membership and the privacy-pool pattern

Understand the commitment + Merkle-membership + nullifier pattern that underlies privacy pools and mixers: how a deposit hides in an anonymity set, how a withdrawal proves membership in zero knowledge, why the nullifier (not the proof) prevents double-spending, and the specific security pitfalls — nullifier design errors, under-constrained membership, stale roots and anonymity-set collapse — that turn a sound cryptosystem into a drainable contract.

Track

Engineering

Module

12 · Applied Zero-Knowledge: commitments, proving systems & on-chain privacy

Prerequisites

Merkle trees · Commitment schemes in depth: Pedersen, KZG and IPA · On-chain cryptography and zero-knowledge verification

On a transparent ledger every transfer links a sender to a receiver forever. A privacy pool breaks that link with a deliberately simple trick: everyone deposits the same fixed amount into a common contract, and later anyone can withdraw that amount by proving — without saying which deposit is theirs — that they own one of the deposits that has not yet been spent. An observer sees a deposit and, much later, a withdrawal, but cannot tell which deposit funded which withdrawal.

The construction rests on three primitives from earlier lessons working together: a hiding commitment, a Merkle tree for succinct membership, and a zero-knowledge proof so the withdrawer reveals nothing but the fact of membership. A fourth piece, the nullifier, is what stops the obvious attack — withdrawing the same deposit twice. Getting these four to interlock correctly is the whole game, and the ways they fail are precise.

To deposit, a user samples two independent secrets — a secret s and a nullifier seed n — and forms a commitment C = H(s, n) using a circuit-friendly hash such as Poseidon. The contract appends C as a new leaf in an append-only Merkle tree and updates the root. The user keeps the "note" (s, n, leaf_index) privately; it is the only thing that can later open the commitment.

synthetic — deposit and the two-secret design (illustrative)
# Deposit
s = random(31 bytes)              # spending secret
n = random(31 bytes)              # nullifier seed  (INDEPENDENT of s)
C = Poseidon(s, n)                # commitment leaf
tree.insert(C)                    # contract updates the Merkle root
note = (s, n, leaf_index)         # kept private by the user

# Why two secrets, computed into different values:
#   C = Poseidon(s, n)            depends on BOTH
#   N = Poseidon(n)               depends on ONLY n
# => from N you cannot recover C, and from C you cannot predict N,
#    so an observer cannot link a withdrawal's N to a deposit's C.

The two-secret design is the hinge of unlinkability. The commitment binds both secrets, but the nullifier is derived from only one of them. So the value the contract will see at withdrawal time (the nullifier) cannot be matched back to the value it saw at deposit time (the commitment) without knowing the secrets — which only the owner does.

To withdraw, the user computes the nullifier N = H(n) and generates a zero-knowledge proof whose public inputs are the current Merkle root, the nullifier N, and the withdrawal recipient; and whose private witness is the note and the Merkle authentication path. The circuit checks three things: that recomputing C = H(s, n) and hashing it up the authentication path yields the published root (membership), that N = H(n) is correctly derived from the same seed bound into C, and that the recipient is bound into the statement so the proof cannot be replayed to a different address.

synthetic — the withdrawal circuit and the contract check (illustrative)
# Circuit (private: s, n, path, pathIndices; public: root, N, recipient)
assert Poseidon(s, n) == leaf
assert merkle_root(leaf, path, pathIndices) == root   # membership
assert N == Poseidon(n)                               # nullifier binding
# recipient is a public input, mixed into the Fiat-Shamir transcript,
# so a valid proof is bound to THIS recipient (anti-replay / front-running)

# Contract (Solidity-shaped)
function withdraw(bytes proof, uint root, uint N, address recipient) external {
    require(knownRoots[root], "unknown or stale root");  # root must be valid
    require(!spent[N], "nullifier already used");        # uniqueness lives HERE
    require(verifier.verify([root, N, uint(recipient)], proof), "bad proof");
    spent[N] = true;                                     # mark BEFORE paying
    pay(recipient, DENOMINATION);
}

The uniqueness key is the nullifier, recorded in the contract's spent set — never the proof bytes. This is the single most important design rule of the pattern, and the reason is covered next.

The pattern is sound only if each piece is constrained correctly. Every item below is a concrete, documented failure class for pool/mixer-style systems, not a hypothetical.

Double-spend via the proof, not the nullifier

Succinct proofs are often malleable: an attacker can derive a different valid proof for the same statement without the witness. A contract that detects replays by hashing the proof bytes is defeated by a mutated-but-valid proof. Uniqueness must key on the nullifier the circuit binds to the secret.

Under-constrained membership or nullifier

If the circuit assigns the Merkle path or the nullifier without constraining it (the <-- vs <== mistake), a malicious prover can produce a "valid" proof for a leaf that is not in the tree, or a nullifier that does not match the spent note — forging withdrawals from nothing. A historical mixer double-spend came from exactly this class of under-constraint.

Stale or attacker-chosen root

Pools accept a set of recent roots so proofs stay valid as the tree grows. If the contract accepts arbitrary or never-expiring roots, an attacker can submit a proof against a root they constructed, or replay membership in a tree state that no longer reflects reality.

Missing recipient / domain binding

If the recipient is not bound into the proof, a relayer or front-runner can take a valid withdrawal proof from the mempool and redirect the payout to themselves. Every public input the payout depends on must be inside the proven statement.

Anonymity-set collapse

The cryptography can be perfect while the metadata leaks everything: depositing and withdrawing within minutes, using a unique amount, reusing an address, or always using the same relayer can narrow the set to one. The anonymity set is a property of user behaviour and pool size, not of the proof.

synthetic — the canonical double-spend, and the fix (illustrative)
// WRONG: proofs are malleable, so this detects nothing.
//   require(!usedProof[keccak256(proof)], "replayed");
//   attacker mutates (A,B,C) -> (A',B',C'), same statement, new hash, passes.

// RIGHT: uniqueness is the nullifier the circuit binds to the secret.
require(!spent[N], "already spent");
require(verifier.verify([root, N, recipient], proof), "bad proof");
spent[N] = true;

When a withdrawal proof verifies, the contract has established a precise statement: the caller knows the opening of some unspent leaf under a valid root, and the published nullifier is bound to that leaf, and the payout goes to the bound recipient — all under the circuit's constraints, the commitment scheme's assumption, and correct Fiat–Shamir. That is exactly what prevents theft and double-spends, and no more.

It does not establish that the depositor was entitled to the funds, that the withdrawal was voluntary, that the anonymity set is large enough to actually hide the user, or that the circuit faithfully encodes membership (an under-constraint silently breaks that). For RootRaven, the pattern is a textbook case of the evidence model: a valid proof attests to a membership-and-nullifier statement under stated assumptions; it is never evidence that the transaction was legitimate, safe, or that the privacy the user wanted was actually achieved. Report the statement and its assumptions, and report the anonymity set as a separate, measured quantity.

Expected direction: Problem 1 (de-anonymisation on immediate withdrawal) is NOT a cryptographic bug — the proof and nullifier are correct. It is anonymity-set collapse: with only one deposit between deposit and withdrawal, or a withdrawal timed tightly to a single deposit, the observer links them by timing/behaviour regardless of the proof. The fix is operational: fixed denominations, a large pool, and waiting (so many indistinguishable deposits exist), plus avoiding address reuse and varying relayers/timing. Anonymity set size is a user/behaviour property, not something the proof provides. Problem 2 (accepting any root ever seen, without expiry) IS a contract-level security bug: an attacker can submit proofs against arbitrary or stale roots, including roots that no longer reflect the real tree, undermining the membership guarantee and enabling replay in outdated state. The fix is to accept only a bounded window of recent valid roots (a rolling set) and reject unknown or expired roots. The cryptography being sound does not save a contract that trusts the wrong root.

Why are the commitment and the nullifier computed from different inputs, and what property does that give?

The commitment C = H(s, n) depends on both secrets while the nullifier N = H(n) depends only on the seed, so from N you cannot recover C and from C you cannot predict N. This unlinkability means an observer cannot match the nullifier seen at withdrawal to the commitment seen at deposit without the secrets.

Why must double-spend protection key on the nullifier rather than the proof?

Because succinct proofs are typically malleable — an attacker can derive a different valid proof for the same statement without the witness — so any replay check on the proof bytes is defeated. The nullifier is derived deterministically from the secret and bound into the circuit, so recording spent nullifiers reliably blocks a second withdrawal.

What is an under-constrained membership/nullifier bug and why is it catastrophic?

It is a circuit that assigns the Merkle path or nullifier without constraining it (the <-- vs <== mistake), letting a malicious prover produce a valid proof for a leaf not in the tree or a mismatched nullifier — forging withdrawals from nothing. It is catastrophic because it breaks soundness invisibly: a passing proof attests to something false, draining the pool with no on-chain trace of an error.

What determines the anonymity set, and why can it be one even with a flawless proof?

The anonymity set is determined by pool size and user behaviour — number of indistinguishable same-denomination deposits, timing, address reuse, relayer choice — not by the proof. A flawless proof over a pool where only one deposit matches the withdrawal's timing/amount links deposit to withdrawal with certainty, so the user is hidden among exactly one person.