Hands On Zero-Znowledge Proofs

Proof of Membership

In a Proof of Membership, a prover demonstrates that they know a secret corresponding to one element of a public set of commitments, without revealing which specific commitment matches their secret.

This primitive plays a central role in privacy-preserving systems. For instance, it is used in cryptocurrency mixers such as Tornado Cash to break the link between deposits and withdrawals.

The core idea is simple:

  • When a user makes a deposit, they generate a secret and publish only its commitment.
  • Later, to withdraw funds, they prove that they know the secret corresponding to one of the published commitments.
  • Crucially, the proof reveals neither the secret nor which commitment it corresponds to.

This allows any valid withdrawal to be linked to the set of deposits, but not to a particular one.

However, this immediately raises a challenge: what prevents the same deposit from being used multiple times? This is addressed using a nullifier scheme, which we introduce below.

In a nutshell, a practical Proof of Membership combines two ingredients:

  1. A zero-knowledge inclusion proof: showing that a commitment is part of a public set.
  2. A nullifier scheme: ensuring that the same secret cannot be used twice.

We present these two components separately before combining them.

Part I — Inclusion via Merkle Trees

Merkle Proofs Recap

To prove that a value belongs to a large collection efficiently, we typically use a Merkle tree:

  • The leaves are the commitment hashes
  • Internal nodes are hashes of their children
  • The root uniquely commits to the entire set

A Merkle inclusion proof allows one to show that a specific leaf belongs to the tree by revealing only:

  • the leaf value
  • the sibling hashes along the path to the root

A Merkle inclusion proof complexity is logarithmic in the size of the set, rather than linear.

From Merkle Proofs to Zero Knowledge

A classical Merkle proof is not zero knowledge, since the leaf (i.e., the commitment hash) is explicitly revealed.

To preserve privacy, we embed the Merkle inclusion check inside a SNARK circuit and prove it in zero knowledge.

The resulting statement becomes:

Statement: I know a secret such that the commitment H(secret) is included in the Merkle tree with root merkleRoot.

Formally:

Statement: I know a secret such that C(secret, merkleRoot) = true

where:

  • secret is a private witness
  • merkleRoot is a public value committing to the full set

This proves membership without revealing the committed value itself.

Part II — Preventing Double Use with Nullifiers

The Problem

If we only prove inclusion, a verifier cannot tell whether two distinct proofs refer to the same underlying secret or to different ones. This opens the door to double spending or multiple withdrawals using the same deposit.

The Nullifier Idea

To solve this, we introduce a nullifier.

A nullifier is a cryptographic value deterministically derived from the secret that enables verifiers to detect reuse of the same secret without learning anything about the secret itself.

Instead of committing only to secret, we commit to the pair:

commitment = H(secret, nullifier)

This yields the new statement:

Statement: I know a secret and a nullifier such that the commitment H(secret, nullifier) is included in the Merkle tree.

Formally:

Statement: I know secret and nullifier such that C(secret, nullifier, merkleRoot) = true

with:

  • secret: private witness
  • nullifier: revealed when proving
  • merkleRoot: public tree root

Why This Prevents Double Use

When producing a proof, the prover is forced to reveal the nullifier.

If a verifier maintains a record of all nullifiers already seen, then any attempt to reuse the same secret will reveal the same nullifier and the verifier can immediately reject repeated usage

This ensures one-time use per secret, while preserving anonymity among all commitments.

Using the ZK‑Toolbox (Developer View)

Using our zk‑toolbox library a commitment is defined as:

commitment = Poseidon(secret, nullifier)

Inputs and Outputs

  • Private input:
    • secret: the value whose membership is being proven
  • Public inputs:
    • commitments: the list of all commitments (Merkle tree leaves)
    • nullifier: ensures one-time use
    • nonce: binds the proof to a specific context
  • Public output:
    • authHash: binds the secret and nullifier to the nonce

Example

import { ProofOfMembership, randomBigInt32ModP, poseidon } from "@prifilabs/zk-toolbox";

// step 1: generate the inputs
let secret, nullifier, commitment;
const commitments = [];
const random = Math.floor(Math.random() * 100);
for (let i =0; i<100; i++){
	const s = randomBigInt32ModP();
	const n = randomBigInt32ModP();
	const c = poseidon([s, n]);
	if (random == i){
		secret = s;
		nullifier = n;
		commitment = c;
	}
	commitments.push(c);
}
const nonce = randomBigInt32ModP();
const privateInputs = { secret };
const publicInputs = { commitments, nullifier, nonce };

// step 2: generate the proof
const proofOfMembership = new ProofOfMembership();
const { proof, publicOutputs } = await proofOfMembership.generate(privateInputs, publicInputs);

// step 3: verify the output (optional) 
console.assert(publicOutputs.authHash == poseidon([privateInputs.secret, publicInputs.nullifier, publicInputs.nonce]));

// step 4: verify the proof
const res = await proofOfMembership.verify(proof, publicInputs, publicOutputs);
console.assert(res);

Behind the Scenes: The CIRCOM Circuit

We reuse a Merkle inclusion circuit originally developed for the Semaphore Protocol.

The circuit verifies that a leaf is correctly connected to the root via a Merkle path.

Merkle Inclusion Subcircuit

pragma circom 2.0.0;

include "../../../node_modules/circomlib/circuits/poseidon.circom";
include "../../../node_modules/circomlib/circuits/mux1.circom";

template MerkleTreeInclusionProof(nLevels) {
    signal input leaf;
    signal input pathIndices[nLevels];
    signal input siblings[nLevels];
    signal output root;

    component poseidons[nLevels];
    component mux[nLevels];

    signal hashes[nLevels + 1];
    hashes[0] <== leaf;

    for (var i = 0; i < nLevels; i++) {
        pathIndices[i] * (1 - pathIndices[i]) === 0;

        poseidons[i] = Poseidon(2);
        mux[i] = MultiMux1(2);

        mux[i].c[0][0] <== hashes[i];
        mux[i].c[0][1] <== siblings[i];

        mux[i].c[1][0] <== siblings[i];
        mux[i].c[1][1] <== hashes[i];

        mux[i].s <== pathIndices[i];

        poseidons[i].inputs[0] <== mux[i].out[0];
        poseidons[i].inputs[1] <== mux[i].out[1];

        hashes[i + 1] <== poseidons[i].out;
    }

    root <== hashes[nLevels];
}

Full Proof of Membership Circuit

pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/poseidon.circom";
include "./lib/MerkleTree/MerkleTree.circom";

template ProofOfMembership(levels) {
    
    // private inputs
    signal input secret;
    signal input siblings[levels];
    signal input pathIndices[levels];
    
    // public inputs
    signal input nullifier;
    signal input nonce;
    
    // public outputs
    signal output root;
    signal output authHash;
    
    // compute the commitment hash
    component commitmentHasher = Poseidon(2);
    commitmentHasher.inputs <== [secret, nullifier];
    
    // compute the merkle root from Merkle Proof values
    component tree = MerkleTreeInclusionProof(levels);
    tree.leaf <== commitmentHasher.out;
    for (var i = 0; i < levels; i++) {
        tree.siblings[i] <== siblings[i];
        tree.pathIndices[i] <== pathIndices[i];
    }
    
    root <== tree.root;
    
    // context binding
    component authHasher = Poseidon(3);
    authHasher.inputs <== [secret, nullifier, nonce];
    authHash <== authHasher.out;
}

component main {public [nullifier, nonce]} = ProofOfMembership(20);

Why We Still Use a Nonce

Even though the nullifier prevents reuse of the same secret, the nonce plays a distinct role:

  • The nullifier prevents reuse of the same secret
  • The nonce prevents replay of the same proof in a different context

This allows the same membership proof to be used multiple times legitimately (e.g., retries, delayed conditions), while preventing replay by observers.

Conclusion and Applications

Proof of Membership is a foundational primitive for privacy-preserving systems.

It enables:

  • anonymous authentication
  • mixers and privacy pools
  • anonymous voting
  • group membership proofs

without revealing identity or linkability between actions.

Conceptually, it realizes anonymous authorization: proving that someone in a group is allowed, without revealing who.

In our next chapter, Proof of Exclusion, we explore the dual problem: proving in zero knowledge that a secret does not belong to a set of commitments.