Hands On Zero-Znowledge Proofs

Proof of Exclusion

A Proof of Exclusion is the logical complement of a Proof of Membership: it allows a prover to demonstrate that a specific commitment they know is not included in a public set of commitments, without revealing the commitment itself.

This primitive is particularly useful in privacy-preserving systems where users must show that they are not associated with certain entries, while still keeping their identity and data private.

For example, in cryptocurrency mixers, some deposits may originate from illicit or sanctioned sources. A user may wish to prove that their withdrawal is not linked to any of these flagged deposits—without revealing which deposit is theirs or which one they are excluding themselves from.

When combined with Proofs of Membership, this enables powerful privacy-preserving statements such as:

  • I am authorized to withdraw funds (membership)
  • and my deposit is not among the blacklisted ones (exclusion)

all without disclosing any identifying information.

Intuition behind Proof of Exclusion

At a high level, Proof of Exclusion mirrors Proof of Membership in terms of inputs and outputs, but its statement is inverted:

Statement: I know a commitment c such that c is not included in the Merkle tree with root merkleRoot.

However, proving non-inclusion is fundamentally more subtle than proving inclusion.

While a Merkle tree provides a direct and efficient proof that a value is in a set, there is no symmetric primitive for proving that a value is not in the set.

To overcome this, we change perspective: instead of proving absence directly, we prove that the commitment lies strictly between two consecutive values in a sorted representation of the set.

Proving Non-Inclusion via Sorted Merkle Trees

Sorted Merkle Trees

The first key idea is to sort all commitments before inserting them as leaves in the Merkle tree. This transforms the set into an ordered sequence.

The commitment list should contain:

  • every commitment with respect to which exclusion is being proven, and
  • the boundary values 0 and p, which act as the lower and upper limits of the ordered set.

Once commitments are sorted, proving that a value is not in the tree reduces to proving that:

  • There exist two values x and y in the tree such that:
x < c < y
  • And that x and y are adjacent in the sorted tree

This guarantees that there is no value equal to c anywhere in the tree.

Zero-Knowledge Non-Inclusion Statement

The resulting ZK statement becomes:

Statement: I know a commitment c and two bounds x and y included in the sorted Merkle tree such that:

  • x < c < y
  • x and y are consecutive elements in the tree

Critically:

  • The prover never reveals c, x, or y
  • The verifier learns only that c is not part of the committed set

Using the ZK-Toolbox (Developer View)

The developer interface for Proof of Exclusion is deliberately very similar to Proof of Membership, which makes both primitives composable.

Inputs and Outputs

  • Private input:
    • secret: the original secret
  • Public inputs:
    • commitments: the list of flagged or restricted commitments
    • nullifier: the original nullifier
    • nonce: a contextual binding value
  • Public output:
    • authHash: binds the secret and the nullifier to the nonce, preventing replay

Example

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

// step 1: generate the inputs
const commitments = [];
for (let i =0; i<100; i++){
	commitments.push(poseidon([randomBigInt32ModP()]));
}
const secret = randomBigInt32ModP();
const nullifier = randomBigInt32ModP();
const nonce = randomBigInt32ModP();
const privateInputs = { secret };
const publicInputs = { commitments, nullifier, nonce };

// step 2: generate the proof
const proofOfExclusion = new ProofOfExclusion();
const { proof, publicOutputs } = await proofOfExclusion.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 proofOfExclusion.verify(proof, publicInputs, publicOutputs);
console.assert(res);

Behind the Scenes: The CIRCOM Circuit

Here is the full circuit used by Proof of Exclusion:

pragma circom 2.0.0;

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

template LessThan254() {
    signal input in[2];
    signal output out;

    component n0b = Num2Bits_strict();
    n0b.in <== in[0];

    component n1b = Num2Bits_strict();
    n1b.in <== in[1];

    // numbers for high 4 bits
    component h0  = Bits2Num(2);
    component h1  = Bits2Num(2);
    for(var i = 252; i < 254; i++) {
        h0.in[i-252] <== n0b.out[i];
        h1.in[i-252] <== n1b.out[i];
    }

    component hiBitLt = LessThan(2);
    hiBitLt.in[0] <== h0.out;
    hiBitLt.in[1] <== h1.out;
    component hiBitEq = IsEqual();
    hiBitEq.in[0] <== h0.out;
    hiBitEq.in[1] <== h1.out;

    // number for lower 252 bits
    component n0  = Bits2Num(252);
    component n1  = Bits2Num(252);
    for(var i = 0; i < 252; i++) {
        n0.in[i] <== n0b.out[i];
        n1.in[i] <== n1b.out[i];
    }

    component lt = LessThan(252);
    lt.in[0] <== n0.out;
    lt.in[1] <== n1.out;

    out <== (hiBitEq.out * lt.out) + (hiBitLt.out * 1);
}

template ProofOfExclusion(levels) {
    
    // private inputs
    signal input secret;
    signal input bounds[2];
    signal input siblings[2][levels];
    signal input pathIndices[2][levels];
    
    // public inputs
    signal input nullifier;
    signal input nonce;
    
    // public outputs
    signal output roots[2];
    signal output lowerCheck;
    signal output higherCheck;
    signal output consecutiveCheck;
    signal output authHash;
    
    component commitmentHasher = Poseidon(2);
    commitmentHasher.inputs <== [secret, nullifier];
    
    component tree[2]; 
    
    // calculate the two Merkle roots
    // from the two Merkle proofs for the bounds
    for(var k=0; k<2; k++){
      tree[k] = MerkleTreeInclusionProof(levels);
      tree[k].leaf <== bounds[k];
      for (var i = 0; i < levels; i++) {
          tree[k].siblings[i] <== siblings[k][i];
          tree[k].pathIndices[i] <== pathIndices[k][i];
      }
      roots[k] <== tree[k].root;
    }
    
    // check that commitment is greater than the lower bound
    component lowerChecker = LessThan254();
    lowerChecker.in <== [bounds[0], commitmentHasher.out];
    lowerCheck <== lowerChecker.out;
    lowerCheck === 1;
    
    // check that commitment is less than the higher bound
    component higherChecker = LessThan254();
    higherChecker.in <== [commitmentHasher.out, bounds[1]];
    higherCheck <== higherChecker.out;
    higherCheck === 1;
    
    // extract index of the lower bound
    component lowerBound = Bits2Num(levels);
    lowerBound.in <== pathIndices[0];
    
    // extract index of the higher bound
    component higherBound = Bits2Num(levels);
    higherBound.in <== pathIndices[1];
    
    // check that the two bound index are consecutive
    component consecutiveChecker = IsEqual();
    consecutiveChecker.in <== [lowerBound.out + 1, higherBound.out];
    consecutiveCheck <== consecutiveChecker.out;
    consecutiveCheck === 1;
    
    // context binding
    component authHasher = Poseidon(3);
    authHasher.inputs <== [secret, nullifier, nonce];
    authHash <== authHasher.out;
}

component main {public [nonce]} = ProofOfExclusion(20);

What the Circuit Enforces

The circuit ensures four critical properties:

  1. Both bounds are in the tree
    Each of the two bound values is proven to be included via Merkle inclusion proofs.

  2. Strict ordering
    It enforces:

    bounds[0] < commitment < bounds[1]

  3. Adjacency
    The two bounds are consecutive in the sorted tree, meaning there is no other value between them.

  4. Context binding
    The commitment is bound to a nonce through authHash, preventing replay attacks.

External Checks and Design Tradeoffs

Some properties are deliberately verified outside the circuit for efficiency:

  • That both Merkle roots are equal
  • That the Merkle tree is indeed built from the sorted list of public commitments

Since the list of commitments is public, performing these checks off-circuit avoids:

  • introducing large public inputs (i.e the full list of commitments)
  • significantly increasing circuit constraints (i.e verifying that the full list of commitments is sorted and calculating the Merkle root)

The zk‑toolbox wrapper handles these validations transparently.

Linking Proof of Membership and Proof of Exclusion in Practice

In many real-world systems, we want to combine both primitives to express richer statements such as:

  • I am authorized to withdraw funds (Proof of Membership)
  • and my deposit is not among the blacklisted ones (Proof of Exclusion)

Crucially, both statements must refer to the same underlying commitment, yet we cannot reveal this commitment publicly.

The Core Challenge

How can a verifier be convinced that the two proofs refer to the same commitment if the commitment itself is hidden?

A naïve approach would be to merge both circuits into a single large circuit. However, this is unnecessary and undesirable as it increases circuit complexity, reduces modularity and makes independent auditing harder

The Elegant Solution: Binding via authHash

Instead, we rely on a key design feature shared by both proofs: the authHash.

In both Proof of Membership and Proof of Exclusion, the library outputs:

authHash = Poseidon(secret, nullifier, nonce)

This hash cryptographically binds the hidden commitment to a public, fresh nonce.

To link a Proof of Membership and a Proof of Exclusion together:

  1. The prover uses the same secret and the same nullifier (hence the same commitment) in both proofs
  2. The prover uses the same nonce in both proofs
  3. Each proof outputs an authHash
  4. The verifier simply checks:
authHash_membership == authHash_exclusion

If they match, the verifier is guaranteed that both proofs refer to the same hidden commitment without ever learning what that commitment is.

Conclusion and Applications

With Proof of Exclusion, we now have a complete toolkit to reason about presence, absence, and commitment in zero knowledge — paving the way for sophisticated privacy-preserving authorization, compliance, and identity systems:

  • Proof of Commitment: I know a secret tied to a public commitment
  • Proof of Membership: My commitment is in this set
  • Proof of Exclusion: My commitment is not in this set

Together, these primitives form the foundation of many real-world privacy-preserving protocols.

Example Applications

  1. Regulatory-compliant privacy systems
    Users can prove their assets or transactions are not linked to sanctioned or illicit entries while remaining anonymous.

  2. Anonymous credential systems
    Proving one does not belong to a revoked or banned group without revealing identity.

  3. Selective disclosure and compliance
    Demonstrating that a secret attribute does not fall into a disallowed range or category.

  4. Privacy-preserving KYC / AML filters
    Showing that a user is not part of a blacklist without revealing the user or the blacklist.

  5. Access control with revocation
    Enabling systems where users prove both membership in an authorized group and exclusion from a revoked group.