The views, opinions, and creative abuses of language in this post are my own and do not represent those of my employer (Shielded Technologies) or the Midnight Network.

“I don’t want to belong to any club that will accept me as a member” — or how to prove you’re NOT a member, without revealing who you are

“A serious and good philosophical work could be written consisting entirely of jokes.” — Ludwig Wittgenstein

---

Groucho Marx didn’t want to belong to any club that would have him. What he never explained was how he’d actually prove he wasn’t a member. A zero-knowledge proof of non-membership does exactly that — it lets someone demonstrate that an element is absent from a set, without revealing the element or the set’s contents. Think: proving you’re not on a sanctions list, that a credential hasn’t been revoked, that you haven’t already voted.

Proving non-membership is harder than proving membership. Membership proofs have well-worn primitives — Merkle trees, accumulators — where you show a path from your element to a known root. Non-membership requires proving a negative: that no path exists, or that the position where your element would be is empty.

This post walks through four patterns for non-membership on Midnight, from native and battle-tested to production-grade with off-chain infrastructure. All contracts compile against Compact v0.31.0 and are included in full.

Overview

Technique	Set size	Off-chain infra	Native support	Difficulty
Nullifier pattern	Unlimited	None	Full	Beginner
Attribute blocklist	~32 entries	None	Full	Intermediate
Sparse Merkle tree	Millions (with collision risk)	Tree service	Manual	Advanced
Indexed Merkle tree	Millions	Sorted-leaf service	Manual	Advanced

Pattern 1: Nullifier-Based Prevention

“I didn’t do it, nobody saw me do it, you can’t prove anything.” — Bart Simpson
”No two substances are entirely alike.” — Gottfried Wilhelm Leibniz

The Midnight-native approach. Instead of proving “I am NOT in set S,” you prove “my deterministic nullifier has NOT been published on-chain.” The blockchain itself enforces uniqueness.

How it works

1. User holds a secret key (never leaves the ZK proof)
2. User derives a deterministic nullifier: persistentHash(domain, secret, context)
3. Circuit checks the nullifier is NOT in the on-chain Set<Bytes<32>>
4. Circuit inserts the nullifier, permanently marking it “used”

The nullifier is a one-way hash of the secret — recovering the secret means inverting persistentHash, which the stdlib’s preimage resistance makes computationally infeasible. The hash function does not erase the in-circuit taint label (the stdlib explicitly notes it’s “insufficient to protect its input from disclosure”), which is why every ledger write of a witness-derived hash still calls disclose(). The cryptographic hiding and the type-system hiding are two different things; this pattern relies on the cryptographic one. Domain separation — different hash prefixes for different purposes — prevents cross-contract correlation.

Why this counts as non-membership

“If it looks stupid but it works, it isn’t stupid.” — Murphy’s Laws of Combat
”Le mieux est l’ennemi du bien.” — Voltaire

The Set of spent nullifiers is the “used” list. The circuit proves the user’s nullifier isn’t in it. But the check is plain Compact — Set.member() returns false — not a ZKP of non-membership in the cryptographic sense. The privacy comes from the nullifier being unlinkable to any identity, not from hiding the set query.

The contract

The core of performAction — derive a nullifier, check it’s not spent, then record it:

const nul = deriveNullifier(sk, action);

// NON-MEMBERSHIP CHECK: nullifier must NOT be in the set.
// `assert` is implicitly disclosing, so no wrapper is needed here.
assert(!spentNullifiers.member(disclose(nul)), "Action already performed");

// Record the nullifier (future attempts will fail)
spentNullifiers.insert(disclose(nul));

Full contract: contracts/nullifier-pattern.compact

Does it scale?

A reasonable worry: spent nullifiers accumulate forever. Does the cost of checking membership grow with the set? On Midnight specifically, no — Compact’s Set<T> ADT gives amortized constant-time member(), insert(), and remove(). The contract pays the same circuit cost whether spentNullifiers holds 10 entries or 10 million. The set is on-chain state that grows linearly with use, but the per-proof cost is flat.

This is the pattern’s central practical advantage over older accumulator-based nullifier schemes (Zcash-style, where non-membership requires an in-circuit cryptographic accumulator proof). On Midnight, the chain just queries its own Set — no accumulator, no path proof, no witness fetch of the set. Storage growth is real but cheap, and pruning isn’t possible without losing the security property (a removed entry could be replayed).

Privacy analysis

Visible on-chain	Hidden
A nullifier was inserted	Which member acted
A Merkle root check passed	The secret key
Which action type was performed	The link between identity and nullifier

When to use this

This pattern fits whenever the question is “has this identity performed action X before?” — voting, credential redemption, airdrop claims, rate limiting. It handles unlimited set sizes, requires no off-chain infrastructure, and uses only native Compact primitives.

It does NOT work for “is this identity absent from an externally maintained list?” — for that, you need the next two patterns.

---

Pattern 2: Attribute-Based Blocklist Exclusion

“I am not a crook.” — Richard Nixon
”The class of all classes which are not members of themselves.” — Bertrand Russell

Exhaustive inequality checking. The blocklist stores hashes of blocked attribute values — revoked credential IDs, sanctioned jurisdiction codes, flagged device fingerprints. The user proves their attribute hash (derived inside the circuit from a witness-provided credential) doesn’t match any entry.

How it works

1. Admin publishes attribute hashes to a public on-chain Set<Bytes<32>>
2. User holds a credential with an attribute (witness-provided, never disclosed)
3. Circuit hashes the attribute with the same domain separator used to create blocklist entries
4. Circuit iterates over each entry and asserts inequality
5. If the attribute hash matches any entry, the assertion fails and no valid proof exists

The attribute value never leaves the ZK proof. The blocklist is public — you can see what’s blocked, but not who just proved they aren’t.

The tradeoff

“I’ve got a little list — they’d none of ‘em be missed!” — Ko-Ko, The Mikado
”There is no royal road to geometry.” — Euclid

Circuit cost grows linearly with blocklist size. Each entry adds a hash comparison to the proof. At 8 entries, negligible. At 100, noticeable. Past 1,000, impractical. The blocklist is fully public — that’s a feature (transparency about who’s blocked) but it limits the pattern to cases where the blocklist contents can be public.

The contract

The core of proveNotBlocked — hash the user’s credential attribute, then check it against every blocklist entry:

// Hash the user's credential attribute (private — stays in the proof)
const attribute = getCredentialAttribute();
const myAttrHash = hashAttribute(attribute);

// NON-MEMBERSHIP CHECK: assert attribute hash != each active entry
for (const i of 0..8) {
  const entry = blocked[i];
  if (disclose(i < count)) {
    assert(myAttrHash != entry, "Attribute is on the blocklist");
  }
}

Full contract: contracts/blocklist-exclusion.compact

Scaling the blocklist

The contract above caps at 8 entries. To handle larger lists:

• Increase the vector size: Vector<32, Bytes<32>> handles 32 entries, Vector<64, Bytes<32>> handles 64. Each doubles the comparison gates in the proof.
• Batch across transactions: Split a 200-entry blocklist into 8 batches of 25. The user proves non-membership against each batch in separate transactions. A Map<Uint<64>, Boolean> tracks which batches have been cleared.
• Hierarchical hashing: Hash the blocklist into a Merkle tree and use the sparse Merkle tree pattern (Pattern 3) for the actual non-membership proof. This is the crossover point where Pattern 3 becomes worth the complexity.

When to use this

Good for small, stable, public blocklists — jurisdiction screening, credential revocation from a small issuer, device attestation against a known set. The simplicity is the selling point: no off-chain infrastructure, no custom data structures, just a loop and some comparisons.

---

Pattern 3: Sparse Merkle Tree Non-Membership

“Space is big. Really big. You just won’t believe how vastly, hugely, mind-bogglingly big it is.” — Douglas Adams
”The eternal silence of these infinite spaces frightens me.” — Blaise Pascal

Read this section as the pedagogical version. Pattern 4 (Indexed Merkle Tree, below) is what production systems actually use. Pattern 3 is presented in full because the indexed-tree fix only makes sense once you’ve seen the naive sparse approach it improves on — same on-chain footprint, same trust model, but proof size scales with set size instead of key-space and the birthday-paradox footgun goes away.

The general-purpose technique. A sparse Merkle tree has 2^D leaf positions, each either occupied (element present) or empty (default value). Non-membership means the leaf at position H(element) is empty. An authentication path lets the circuit verify this against the on-chain root.

The architecture

graph LR
    subgraph On-chain
        root["sparseRoot<br/>(Bytes&lt;32&gt;)"]
    end

    subgraph Off-chain Service
        tree["Full sparse MT<br/>(all 2^D leaves)"]
    end

    subgraph User's Wallet
        witness["Witness:<br/>- leaf<br/>- siblings<br/>- directions"]
        proof["ZK proof:<br/>path valid,<br/>leaf empty,<br/>root matches"]
    end

    tree -->|update root| root
    tree -->|auth path| witness
    witness --> proof
    proof -.->|verify against| root

The tree data isn’t the secret — the query is. The ZK proof hides which position was checked. An observer learns only that “someone proved non-membership for something.”

The Compact idiom: folding

Compact uses const for all bindings — you can’t accumulate a running hash through a loop with reassignment. But Compact’s built-in fold expression carries an accumulator across a vector traversal, exactly like the Compact stdlib’s own merkleTreePathRoot implementation. The circuit folds from leaf to root in one expression:

const computedRoot = fold(
  (acc: Bytes<32>, sibling: Bytes<32>, goesRight: Boolean) =>
    goesRight ? hashNode(sibling, acc) : hashNode(acc, sibling),
  leafValue,
  siblings,
  directions
);

Multi-vector fold iterates over siblings and directions in lockstep. The accumulator starts at leafValue and hashes upward through each level. No pre-computed intermediates needed from the witness — the circuit computes the root directly.

The contract

proveNonMembership and proveMembership share an internal helper that does the member check, fetches the proof, folds, and confirms the root. Each public circuit then adds its own one-line assertion on the leaf value:

export circuit proveNonMembership(element: Bytes<32>): [] {
  const leafValue = verifySparseMemberAndPath(element);
  assert(leafValue == pad(32, ""), "Leaf is not empty — element IS in the set");
  proofCount.increment(1);
}

export circuit proveMembership(element: Bytes<32>): [] {
  const leafValue = verifySparseMemberAndPath(element);
  assert(leafValue != pad(32, ""), "Leaf is empty — element is NOT in the set");
  proofCount.increment(1);
}

Full contract: contracts/sparse-merkle-non-membership.compact

A footgun: position collisions

The position derivation above takes the first D bits of persistentHash(element). At depth 20, that’s 2^20 ≈ 1M positions — sounds like plenty, until the birthday paradox kicks in around √(2^20) ≈ 1,000 inserts. Past that point, two distinct elements will eventually hash to the same leaf position.

The effect is not a security break. An attacker cannot trick the chain into accepting X as “not in the set” once X has been added — the leaf at position(X) is non-empty, so the proof fails. That direction is sound.

The break runs the other way: legitimate non-membership proofs get rejected. If Y was inserted first at position p, and a user later tries to prove non-membership of X where position(X) == p, the leaf isn’t empty — it holds Y’s marker — and the proof fails even though X genuinely isn’t in the set. A false rejection. Rarer at deeper trees, but rarer is not zero, and a stuck user is a stuck user.

The naive fix — use the full hash bit-width as the path (depth = 256) — produces a tree nobody wants to prove. The real fix is a different layout, which is what production systems use.

The production fix: indexed Merkle trees

Aztec, Polygon ID, and Semaphore-v4 all skip prefix-sparse and reach for a different structure: an indexed Merkle tree. Leaves are sorted by key and each stores a pointer to the next-larger key. Non-membership of X is shown by exhibiting the predecessor leaf low where low.key < X < low.nextKey. Tree depth scales with the number of active entries, not the key bit-width — log(1M) ≈ 20 levels for a million entries, regardless of hash size.

The benefits stack: no collision risk (each leaf stores its actual key, so positions are unique by construction), shallower proofs, smaller witnesses, no false rejections. The cost lives in insertion — each new entry requires two Merkle updates: the predecessor’s nextKey pointer, plus the new leaf written with the predecessor’s old nextKey.

Pattern 4 below implements this layout in Compact. Read Pattern 3 here as the teaching version and Pattern 4 as the production-ready version of the same idea.

The off-chain service

The contract above assumes an off-chain service that:

1. Maintains the full sparse Merkle tree. For depth 20, this is up to 1M leaves. In practice, sparse trees are stored compactly — only non-empty subtrees are materialized, with default hashes computed lazily.

2. Serves authentication paths. Given an element, the service hashes it to find the leaf position, then returns the leaf value, sibling hashes, and path directions.

3. Updates the on-chain root. When elements are added or removed, the service recomputes the root and calls updateRoot().

This service is a trust point: it must return correct paths, and it learns which element is being queried. Mitigations include running the service locally, fetching the entire tree, or querying via a private information retrieval protocol.

Trust model

“Trust, but verify.” — Ronald Reagan
”Covenants, without the sword, are but words.” — Thomas Hobbes

Concern	Risk	Mitigation
Service availability	Users can’t generate proofs if service is down	Replicate tree data, allow local copies
Path correctness	Malicious service returns wrong siblings	Circuit catches this — proof verification fails
Query privacy	Service sees which element is checked	Fetch entire tree locally; use PIR
Root integrity	Admin could set a fraudulent root	Add root update proofs (old + new root verification)
Update authority	Single admin controls the set	Multi-sig admin or governance-controlled updates

When to use this

When the set is too large for exhaustive comparison (Pattern 2) and the non-membership question is about an external set rather than a self-generated nullifier (Pattern 1). Think sanctions lists with thousands of entries, large-scale credential revocation, or any scenario where you need to prove absence from an arbitrary, externally managed set.

The cost is real: you need off-chain infrastructure, a trusted (or verifiable) admin for root updates, and the circuit is heavier than the other patterns. But it’s the only approach that scales to large sets — and Pattern 4 below is the variant that actually scales without the collision footgun.

---

Pattern 4: Indexed Merkle Tree Non-Membership

“Between two evils, I always pick the one I never tried before.” — Mae West
”Order is heaven’s first law.” — Alexander Pope (Essay on Man, Epistle IV)

Production-grade non-membership. Same on-chain footprint as Pattern 3 — just a root and a member registry — but the off-chain tree is sorted by key, and each leaf stores a pointer to the next-larger key. Non-membership becomes a range bracket: show the predecessor leaf whose key is less than the target and whose nextKey is greater.

How it works

1. The off-chain tree starts with a sentinel leaf at position 0: { key: 0, nextKey: 2^248 - 1 }. Every real key inserts between this sentinel and itself, then between itself and whatever was its nextKey.
2. When the admin inserts K, the tree:
   • Finds the predecessor low where low.key < K < low.nextKey
   • Rewrites low’s nextKey to K
   • Writes a new leaf { key: K, nextKey: low's old nextKey } at the next free position
3. The admin pushes the new root on-chain via updateRoot().
4. For non-membership of T, the user’s witness returns the predecessor leaf and a Merkle path. The circuit checks:
   • low.key < T < low.nextKey (range bracket — both compares are native Uint<248>)
   • The predecessor leaf hashes into the on-chain root (fold)

If both hold, T can’t be in the set: the sorted ordering would require it to sit between low and low.nextKey, but low’s nextKey is some other value, not T.

Why this fixes Pattern 3’s collision problem

Pattern 3 derived tree position from hash(element). Collisions hurt liveness; false rejections happen at scale. Pattern 4 stores each key in its own leaf with no positional hashing. Every key occupies exactly one position; positions are unique by construction. Tree depth scales with the number of active entries, not the key bit-width.

Key encoding

Compact’s < operator works on Uint<N> but not on Field or Bytes<32>. So keys are typed as Uint<248> — 31 bytes of entropy. Users derive a key by truncating a 256-bit hash to 248 bits; the collision bound is roughly 2^124, far past anything realistic.

The contract

struct IndexedLeaf {
  key: Uint<248>,
  nextKey: Uint<248>
}

witness getPredecessorProof(target: Uint<248>):
  [IndexedLeaf, Vector<8, Bytes<32>>, Vector<8, Boolean>];

export circuit proveNonMembership(target: Uint<248>): [] {
  // ... member check (same as Pattern 3) ...

  const proof = getPredecessorProof(target);
  const low = proof[0];
  const siblings = proof[1];
  const directions = proof[2];

  // Range bracket — native Uint<248> compares
  assert(low.key < target,       "Predecessor key >= target");
  assert(target < low.nextKey,   "Target >= predecessor's nextKey");

  // Verify the predecessor is in the tree (fold leaf to root)
  const leafHash = hashLeaf(low);
  const computedRoot = fold(
    (acc: Bytes<32>, sibling: Bytes<32>, goesRight: Boolean) =>
      goesRight ? hashNode(sibling, acc) : hashNode(acc, sibling),
    leafHash, siblings, directions
  );
  assert(computedRoot == indexedRoot, "Predecessor proof mismatch");

  proofCount.increment(1);
}

Full contract: contracts/indexed-merkle-non-membership.compact

Pattern 3 vs Pattern 4 at a glance

	Pattern 3 (prefix-sparse)	Pattern 4 (indexed)
Collision risk	Yes (birthday paradox)	None
Tree depth	Key bit-width	log(active entries)
Per-proof witness	Leaf value + siblings	Leaf struct + siblings
Insertion logic	Hash to position, update one leaf	Find predecessor, update two leaves
Range comparison	None needed	Two Uint<248> compares per proof

The insertion side is where Pattern 4 gets more involved. This demo does insertion off-chain admin-side (same trust model as Pattern 3’s updateRoot). A production deployment would add an in-circuit insertion proof — predecessor inclusion + range + two-leaf root transition. That’s a real chunk of work, but the simplification is worth it for a teaching demo.

When to use this

When you’d otherwise reach for Pattern 3, but you actually need to scale. Specifically: dynamic revocation lists, sanctions screening at the 10k+ entry scale, anywhere “false rejection rate climbs with insertions” is unacceptable. Circuit cost is slightly heavier than Pattern 3, but the operational guarantees are what production systems converged on.

---

Final Comparison

	Nullifier	Attribute blocklist	Sparse Merkle tree	Indexed Merkle tree
What it proves	”I haven’t done X"	"My attribute isn’t in list L"	"Element E is not in set S"	"Key K is not in set S”
Set owner	Self-generated	Admin-maintained	Admin-maintained	Admin-maintained
Set visibility	Public (nullifier hashes)	Public (attribute hashes)	Root only (contents hidden)	Root only (contents hidden)
Max set size	Unlimited	~32 (circuit cost)	2^depth (collisions at √2^depth)	2^depth (no collisions)
Off-chain infra	None	None	Tree service required	Sorted-leaf service required
Circuit cost	O(1) per check	O(n) in list size	O(depth) per proof	O(depth) + 2 range compares
Compact support	Native (Set, persistentHash)	Native (loop + comparison)	Manual (fold)	Manual (fold + Uint<248>)
False rejections	None	None	Yes (birthday paradox)	None
Production ready	Yes	Yes	Teaching version only	Yes (admin insert), proof of insert is future work

Which pattern fits which problem

“For every complex problem there is an answer that is clear, simple, and wrong.” — H. L. Mencken
”A place for everything, and everything in its place.” — Mrs. Beeton’s Book of Household Management

The comparison table above lays out the dimensions. This one collapses them into a decision: given a use case, which pattern do you reach for?

Use case	Pattern
Anonymous voting (one vote per registered voter)	Pattern 1 (nullifier)
Coupon, ticket, or claim redemption	Pattern 1 (nullifier)
Private double-spend prevention	Pattern 1 (nullifier)
Jurisdiction screening against a small sanctions list	Pattern 2 (blocklist)
Credential revocation for a small issuer (≤~32 active revocations)	Pattern 2 (blocklist)
Teaching the sparse-Merkle non-membership idea	Pattern 3
Large dynamic revocation list, public key	Pattern 4 (indexed Merkle)
Sanctions screening with thousands of entries	Pattern 4 (indexed Merkle)
Non-membership of a private element in a public set	Pattern 4 wrapped in a higher-level protocol
Constant-size proofs at any scale	Cryptographic accumulators (RSA, KZG) — not Compact-native today

All Kidding Aside

“In theory, there is no difference between theory and practice. In practice, there is.” — Yogi Berra
”Seek simplicity, and distrust it.” — Alfred North Whitehead

Non-membership proofs on Midnight work today, with some tradeoffs. The nullifier pattern covers the most common cases — voting, credential single-use, double-spend prevention — with no infrastructure and no compromises. Blocklist exclusion handles modest-sized sets with nothing more than a loop. The sparse Merkle tree gets the basic idea across but ships a birthday-paradox footgun. Indexed Merkle is the variant production systems converged on, and Pattern 4 brings it into Compact.

All four contracts compile against Compact v0.31.0. They’re starting points, not production code — a real deployment needs hardened witness implementations, off-chain services (for Patterns 3 and 4), in-circuit insertion proofs for Pattern 4, and thorough testing of the privacy properties under realistic conditions.

All source code — contracts, witnesses, off-chain trees, and a sparse Merkle tree visualizer — is at github.com/shieldedtech/spike-non-membership.