ZK Membership Proofs on Midnight

Part 5 of Midnight in Practice. Part 1 | Part 2 | Part 3 | Part 4

Full source: github.com/tusharpamnani/midnight-allowlist

Every contract in this series has introduced one primitive that changes how you think about ZK development. The bonding curve introduced the witness-verify pattern. The escrow introduced commitment schemes for multi-party coordination. The QV contract introduced verification-over-computation for expensive arithmetic.

This article introduces a different class of problem: proving membership in a set without revealing which member you are.

The allowlist contract solves it using a Sparse Merkle Tree; a data structure that lets anyone prove their leaf is included in a tree of up to one million members, using only twenty hash operations inside a ZK circuit, without revealing their leaf, their position, or their secret.

By the end of this article you'll understand why Merkle trees are the standard structure for ZK membership proofs, how the circuit reconstructs a root from a private path, what nullifiers are doing cryptographically, and why the contract computes the nullifier inside the circuit rather than accepting it as a plain argument.

The Problem: Membership Without Identity

The naive approach to allowlisting is just a mapping:

export ledger allowlist: Map<Bytes<32>, Boolean>;

export circuit check(address: Bytes<32>): [] {
    assert(allowlist.member(disclose(address)), "Not allowed");
}

This works, but it's fully public. Every allowed address is visible on-chain. Whoever calls check reveals their address. For a token mint, an airdrop, or any access-gated system where the membership list itself is sensitive; a list of credentialed institutions, KYC-verified wallets, private beta testers, this model fails.

What you want is: a user proves they are in the allowlist without the chain learning which member they are.

Merkle trees make this possible.

Why Merkle Trees Work for ZK Membership

A Merkle tree is a binary tree where every leaf is a hash of some data, and every internal node is a hash of its two children. The root is a single 32-byte value that commits to the entire set.

The key property: given any leaf, you can prove it's in the tree by providing the sibling hashes along the path from leaf to root; the Merkle path. Anyone who knows the root can verify the proof by recomputing the path. Nobody learns anything about other leaves.

For this allowlist, each leaf is hash("zk-allowlist:leaf:v1" || secret). The root is stored on-chain. The Merkle path and the secret stay entirely off-chain as witnesses. The circuit recomputes the root from the path and asserts it matches the on-chain value.

The tree in this implementation has depth 20, supporting up to 2²⁰ = 1,048,576 members. That's the range of the proof: one path, twenty sibling hashes, one root check.

The Ledger: Minimal Public Surface

export ledger merkle_root: Bytes<32>;
export ledger admin_commitment: Bytes<32>;
export ledger used_nullifiers: Set<Bytes<32>>;

Three fields. That's the entire public surface of this contract.

merkle_root is the single commitment to the entire membership set. One 32-byte value represents up to a million members. Updating the set means updating one hash.

admin_commitment is the governance primitive; a hash of the admin's secret credential. We'll cover this in detail below, but notice the design: the admin's identity is never on-chain. Only a commitment to their secret is. Authorization happens entirely inside a ZK proof.

used_nullifiers is the replay protection set. Once a nullifier appears here, it can never be used again. The set grows with every successful verifyAndUse call and is never pruned.

Compare this to a naive allowlist that stores all member addresses: this contract reveals nothing about who is allowed. An observer sees a root, a commitment blob, and a set of 32-byte values with no meaning outside the context of a specific secret and context string.

The Witnesses: Everything Private

witness getSecret(): Bytes<32>;
witness getContext(): Bytes<32>;
witness getSiblings(): Vector<20, Bytes<32>>;
witness getPathIndices(): Vector<20, Boolean>;
witness getAdminSecret(): Bytes<32>;

Five witnesses. Four are for the membership proof, one is for governance.

getSiblings() returns a Vector<20, Bytes<32>>: the twenty sibling hashes along the Merkle path. In the TypeScript layer, these come from tree.getMerklePath(leafIndex). They are computed locally and fed into the proof server. They never appear on-chain.

getPathIndices() returns Vector<20, Boolean>: the direction bits. At each level, false means the current node is a left child (sibling goes right), true means it's a right child (sibling goes left). This determines which side each sibling hash goes in hashLevelNode.

getContext() is the scoping mechanism for nullifiers: more on this shortly.

getAdminSecret() is used only in setRoot. The admin proves knowledge of the secret whose commitment matches admin_commitment without ever disclosing the secret itself.

The hashLevelNode Circuit

circuit hashLevelNode(is_right: Boolean, current: Bytes<32>, sibling: Bytes<32>): Bytes<32> {
    if (is_right) {
        return persistentHash<Vector<3, Bytes<32>>>([
            pad(32, "zk-allowlist:node:v1"),
            sibling,
            current
        ]);
    } else {
        return persistentHash<Vector<3, Bytes<32>>>([
            pad(32, "zk-allowlist:node:v1"),
            current,
            sibling
        ]);
    }
}

This is the building block for the entire Merkle path reconstruction. It computes one level of the tree: given the current hash and its sibling, produce the parent hash.

The is_right flag controls which side the current node occupies. If the current node is a right child, the sibling goes left; so the hash is H(domain || sibling || current). If it's a left child, the hash is H(domain || current || sibling). Getting this wrong produces the wrong root and the assertion fails.

The domain separator "zk-allowlist:node:v1" is padded to 32 bytes and prepended to every node hash. This is the same domain separation philosophy from the QV nullifier discussion, it prevents a hash computed for one purpose from being confused with a hash computed for another. A leaf hash, a node hash, and a nullifier hash all use different tags even though they all call persistentHash.

The Vector<3, Bytes<32>> type annotation tells persistentHash the exact structure of its input. This is the multi-argument pattern the QV contract couldn't use due to an earlier compiler constraint; by Compact 0.22 it works cleanly for vectors of fixed-length byte arrays.

The verifyAndUse Circuit, Step by Step

This is the circuit that does the actual work. Let's walk through each of its six numbered steps.

Step 1: Witness loading

const secret = getSecret();
const context = getContext();
const siblings = getSiblings();
const path_indices = getPathIndices();

All four private inputs are loaded from witnesses. From this point forward, the circuit operates on these values without them ever being disclosed unless explicitly wrapped in disclose().

Step 2: Leaf computation

const leaf = persistentHash<Vector<2, Bytes<32>>>([
    pad(32, "zk-allowlist:leaf:v1"),
    secret
]);

The member's leaf is derived from their secret inside the circuit. The domain tag "zk-allowlist:leaf:v1" ensures a leaf hash is structurally different from a node hash even if the same secret were somehow used at both levels.

Notice what doesn't happen here: the leaf is never disclose()-d. It stays entirely within the witness data space of the proof. The chain never learns the leaf value.

Step 3: Nullifier verification

const computed_nullifier = persistentHash<Vector<3, Bytes<32>>>([
    pad(32, "zk-allowlist:nullifier:v1"),
    secret,
    context
]);
assert(computed_nullifier == nullifier, "Proof integrity error: ...");

This is the most important step to understand correctly. The nullifier parameter is provided by the caller as a public input to verifyAndUse. But the circuit doesn't trust it; it recomputes the nullifier from the private secret and context witnesses and asserts the two match.

Why does this matter? Without this check, a caller could pass any arbitrary nullifier value. They could reuse a nullifier from a different context, fabricate one entirely, or replay a proof with a different nullifier to bypass the double-use check. By recomputing the nullifier inside the circuit and binding it to the private secret and context, the contract ensures that:

1. The nullifier is deterministically derived from the prover's actual secret, not fabricated
2. The same secret in a different context produces a different nullifier, context scoping works
3. Nobody can use someone else's nullifier, the secret is the key

One design decision worth calling out explicitly: the nullifier is a circuit argument rather than computed purely internally with no public exposure. The circuit could derive computed_nullifier and insert it directly without ever surfacing it as a parameter, and the proof would be equally valid. But making it an explicit public argument means the TypeScript client must compute the nullifier locally before invoking the contract. This gives the client the ability to query used_nullifiers on the ledger first and abort early if the nullifier is already recorded, saving the user from generating an expensive ZK proof that would fail on-chain anyway. Proof generation takes meaningful time. Fast UI feedback before that step is worth the minor architectural exposure of making the nullifier a parameter rather than a purely internal value.

Step 4: Merkle path reconstruction

const h0  = hashLevelNode(path_indices[0],  leaf,  siblings[0]);
const h1  = hashLevelNode(path_indices[1],  h0,    siblings[1]);
// ... 18 more levels ...
const calculated_root = hashLevelNode(path_indices[19], h18, siblings[19]);

Twenty calls to hashLevelNode, each feeding the output of the previous as input. This is the full depth-20 Merkle path unrolled manually.

The reason for manual unrolling rather than a loop has two layers. The deeper one is fundamental to all ZK circuits: they must compile to a fixed-size mathematical constraint system. Any loop must have statically determinable bounds; the circuit size has to be known at key generation time. A loop over a runtime-length vector is impossible in any ZK circuit system, not just Compact.

The shallower reason is specific to Compact v0.22: the compiler could struggle with variable shadowing, loop state management, and sequential hashing bounds inside a for...in loop over vectors. Manual unrolling is bulletproof; it produces a mathematically sound constraint system without hitting compiler edge cases. It's verbose, but it compiles cleanly every time. If Compact's loop handling matures in later versions, this could be condensed. For now, twenty explicit lines is the right tradeoff.

Step 5: Root assertion

assert(calculated_root == merkle_root.read(), "Membership verification failed: ...");

The locally reconstructed root must match what's stored on-chain. This single assertion is the entire membership proof. If the prover provided the wrong secret, the wrong siblings, or the wrong path indices, calculated_root will differ from merkle_root at some level of the tree and the proof will fail to generate.

An invalid proof doesn't just fail at the assert; it fails at the proof generation stage. The proof server cannot produce a valid ZK proof for a circuit that would fail its assertions. This means an invalid membership attempt never even reaches the chain.

Step 6: Nullifier recording

assert(!used_nullifiers.member(disclose(nullifier)), "Dual-usage detected: ...");
used_nullifiers.insert(disclose(nullifier));

Two things happen here. First, the check: if this nullifier is already in used_nullifiers, the transaction fails. Second, the insert: the nullifier is disclose()-d into the public set, permanently marking it as used.

The disclose() on the nullifier is intentional and necessary. The nullifier needs to go on-chain so future proofs can check against it. But notice what it reveals: a 32-byte hash of (domain || secret || context). An observer learns that some secret with some context was used, not which secret, not which context, not which member.

The Admin Pattern: ZK Governance

export circuit setRoot(new_root: Bytes<32>): [] {
    const derived_commitment = persistentHash<Vector<2, Bytes<32>>>([
        pad(32, "zk-allowlist:admin:v1"),
        getAdminSecret()
    ]);
    assert(derived_commitment == admin_commitment.read(), "Unauthorized: ...");
    merkle_root.write(disclose(new_root));
}

This is the same pattern as the escrow's deriveKey but applied to governance. The admin never stores their identity on-chain. admin_commitment is just hash(domain || adminSecret). Authorization is proven in ZK: the caller demonstrates they know the secret whose commitment matches the on-chain value.

The setup circuit is a one-time initialization:

export circuit setup(initial_commitment: Bytes<32>): [] {
    assert(admin_commitment.read() == pad(32, ""), "Setup failed: Administrator already configured");
    admin_commitment.write(disclose(initial_commitment));
}

The zero-bytes default check works because Compact ledger state variables are zero-initialized by the underlying Midnight ledger if they haven't been written to. Bytes<32> fields start as 32 zero bytes; no explicit initialization needed, no null or undefined state possible. pad(32, "") generates exactly those 32 zero bytes, so the assertion admin_commitment.read() == pad(32, "") is a clean "has this ever been written?" check. Once setup writes a real commitment, it can never be called again.

Notice that setup takes initial_commitment as a circuit argument, not derived from a witness. The admin computes hash(domain || adminSecret) off-chain and passes it in. The secret itself never appears in the transaction.

The Off-Chain Layer: What allowlist-utils.ts Actually Does

The TypeScript layer in allowlist-utils.ts handles everything the circuit can't do; stateful data management, Merkle tree construction, and local proof verification before submission.

generateProof does three things:

1. Finds the leaf index for the given secret in the local tree
2. Calls tree.getMerklePath(leafIndex) to get siblings and path indices
3. Verifies the path locally with tree.verifyPath() before constructing the proof object

That last step is the key one. Local verification before submission is a development-time safeguard; it catches malformed proofs before they hit the proof server, which would generate a valid ZK proof for an invalid membership claim and then have it rejected on-chain. Better to fail fast locally.

The proof object itself is structured as:

{
    proof: hex-encoded JSON of witness data,  // private inputs
    publicInputs: {
        root: string,      // current tree root
        nullifier: string  // hash(secret, context)
    },
    meta: { context, treeDepth, generatedAt, verified }
}

The witness object inside the hex-encoded proof contains secret, leaf, leafIndex, siblings, and pathIndices, all the private inputs the proof server needs. In a production deployment these would be consumed by the proof server and discarded; here they're serialized for CLI inspection and local verification.

verifyProof mirrors the circuit's logic in TypeScript: recompute the leaf, walk the path, check the root, recompute the nullifier, compare. It's the same five checks the circuit performs, run locally without a proof server. Useful for debugging and for the test suite's 17 forgery attack tests.

The Concatenation Bug the Tests Found

The test suite discovered a real vulnerability worth understanding:

hashNullifier("alice", "ctx1") === hashNullifier("alic", "ectx1")

The original implementation hashed domain || secret || context by simple concatenation. "alice" + "ctx1" and "alic" + "ectx1" both produce the string "alicectx1", identical inputs, identical hashes, identical nullifiers.

The fix was a 4-byte big-endian length prefix before the secret:

hash(domain || len(secret) || secret || context)

Now len("alice") = 5 and len("alic") = 4, the inputs are structurally distinct. The contract's persistentHash<Vector<3, Bytes<32>>> call naturally avoids this issue because it operates on fixed-length Bytes<32> values rather than variable-length strings. But the off-chain TypeScript hashing needed the explicit length prefix fix.

This is a classic lesson in hash function design: whenever you concatenate variable-length inputs, you need either fixed-length encoding, length prefixes, or a structured type system to prevent collisions across different field boundaries. The Compact circuit is immune because Bytes<32> is always exactly 32 bytes. The TypeScript layer isn't, and the test suite proved it.

What's Actually on the Chain

Being precise, as always:

Data	On-chain	Observer learns
Merkle root	Yes	The set has this root: nothing about members
Admin commitment	Yes	Someone controls this contract: not who
Nullifier	Yes (after use)	Some secret+context was used: not which
Secret	No	Nothing
Leaf hash	No	Nothing
Leaf index	No	Nothing
Merkle path	No	Nothing
Member count	No	Nothing

The root encodes the full membership set as a single hash. The nullifier set grows with usage. An observer watching the chain can count how many times the allowlist has been used but cannot learn anything about who used it or who is allowed.

The General Pattern

Strip the allowlist semantics and what remains is a reusable primitive for any ZK set membership proof on Midnight:

1. Off-chain: build a Merkle tree of commitments to private identities

leaf = hash(domain_leaf || secret)
tree.insert(leaf)
root = tree.root

2. On-chain: store only the root

export ledger merkle_root: Bytes<32>;

3. In the circuit: reconstruct the root from a private path

// 20 levels of hashLevelNode, unrolled
assert(calculated_root == merkle_root.read(), "Not a member");

4. Bind usage to a scoped nullifier computed inside the circuit

const nullifier = persistentHash([domain_nullifier, secret, context]);
assert(computed_nullifier == provided_nullifier, "Nullifier mismatch");
assert(!used_nullifiers.member(disclose(nullifier)), "Already used");
used_nullifiers.insert(disclose(nullifier));

Private airdrops, ZK KYC, anonymous credentials, private DAO membership - all of them are variations on this structure. The tree depth controls the maximum set size. The context string controls the scope of each nullifier. The domain separators ensure hash outputs from different parts of the system never collide.

What's Next

The six contracts across this series; bonding curve, state model analysis, escrow, quadratic voting, allowlist, cover the core primitive set for ZK DeFi and governance on Midnight: algorithmic markets, private state management, multi-party coordination, mathematical verification, and membership proofs.

The natural extension from the allowlist is combining it with the QV contract: members of a private allowlist get quadratic voting power, their membership proven anonymously, their vote weight proven without revealing their token allocation. That's a full private governance primitive and a meaningful next build.

Full source: github.com/tusharpamnani/midnight-allowlist