How Midnight Verifies tokens Without Computing It

Part 4 of building with Midnight. Part 1 | Part 2 | Part 3

Full source: https://github.com/tusharpamnani/midnight-quadratic-voting

Every article in this series has had one moment where Midnight forces you to think differently. In Part 1 it was the witness pattern; you don't compute inside the circuit, you verify. In Part 3 it was the commitment scheme; you don't share secret values, you prove knowledge of them.

This article has the same moment, and it's the clearest example yet.

Quadratic voting requires computing floor(sqrt(tokens)) for every voter. If you're thinking like a Solidity developer, your instinct is to implement a square root function and call it inside the contract. On Midnight, that instinct is wrong, and understanding why leads you directly to one of the most elegant patterns in ZK circuit design.

What Quadratic Voting Is and Why It's Hard in ZK

Standard voting gives each participant one vote regardless of their stake. Token-weighted voting gives proportional power to token holders; one token, one vote - which tends toward plutocracy. Quadratic voting is the middle ground: voting power scales as the square root of tokens committed.

weight = floor(sqrt(tokens))

The effect: doubling your tokens increases your influence by roughly 41%, not 100%. Whales can still participate but their marginal influence decreases. It's a mechanism design solution to concentration of power.

The ZK problem is this: sqrt is not a native operation in arithmetic circuits. ZK proof systems work over finite fields; addition and multiplication are cheap, but square roots require either expensive lookup tables or iterative algorithms that balloon the circuit size. For a practical on-chain implementation, neither is acceptable.

The solution isn't to compute the square root at all.

The verifySqrt Insight

Here's the core circuit from the contract:

circuit verifySqrt(tokens: Uint<64>, w: Uint<32>, w_sq: Uint<64>): [] {
    assert(w_sq <= tokens, "Weight too large: w^2 > tokens");
    const two_w = (w as Uint<64>) + (w as Uint<64>);
    const two_w_plus_1 = two_w + 1;
    assert(tokens - w_sq < two_w_plus_1, "Weight too small: use floor(sqrt(tokens))");
}

Three lines of arithmetic. No square root function anywhere. Let's understand exactly what this is doing.

The key mathematical insight: you don't need to compute floor(sqrt(tokens)). You only need to verify that a claimed value w satisfies the definition of floor square root.

w = floor(sqrt(tokens)) if and only if:

w² ≤ tokens < (w+1)²

Expand (w+1)²:

w² ≤ tokens < w² + 2w + 1

Rearrange the right side:

tokens - w² < 2w + 1

That's exactly what the two asserts check. The first assert checks w² ≤ tokens. The second checks tokens - w² < 2w + 1. Together they bound w to be exactly floor(sqrt(tokens)): no larger, no smaller.

The caller provides w and w_sq as witnesses, computed off-chain in TypeScript where you can use native math:

const w = Math.floor(Math.sqrt(Number(tokens)));
const w_sq = BigInt(w) * BigInt(w);

The circuit never computes a square root. It only verifies two inequalities. Both are just subtraction and comparison, cheap in any arithmetic circuit.

This is the witness pattern from Part 1 applied to a harder problem. In the bonding curve, calculateCost computed the integral off-chain and verifiedHalfProduct verified it with a multiplication check. Here, getSqrtWeight computes the square root off-chain and verifySqrt verifies it with two inequality checks. The structure is identical; the mathematical trick is different.

The Full Contract, Annotated

pragma language_version 0.22;
import CompactStandardLibrary;

// Public ledger state
export ledger committed_tokens: Map<Bytes<32>, Uint<64>>;
export ledger has_voted: Set<Bytes<32>>;
export ledger total_votes: Counter;

// Witnesses — computed off-chain, verified in-circuit
witness getVoterId(): Bytes<32>;
witness getCommittedTokens(): Uint<64>;
witness getSqrtWeight(): Uint<32>;
witness getWSquared(): Uint<64>;

Four witnesses. Notice getWSquared() exists separately from getSqrtWeight(), rather than computing w² inside the circuit (a multiplication), the caller provides it pre-computed and the circuit verifies the relationship. This is the same philosophy as the bonding curve: push arithmetic off-chain, verify the result cheaply.

circuit computeNullifier(voter_id: Bytes<32>): Bytes<32> {
    return persistentHash<Bytes<32>>(voter_id);
}

The nullifier is hash(voter_id). One voter ID maps to exactly one nullifier, deterministically, forever. This prevents double voting: once a nullifier is in has_voted, that voter ID can never vote again regardless of what proof they generate.

The comment in the source is worth quoting directly: "Current compiler signature restricts persistentHash to a single Bytes<32> argument. For now, we hash the voter_id directly." This is an honest acknowledgment of a current Compact compiler constraint. The README flags the consequence: same voter_id across different contracts produces the same nullifier, creating cross-contract linkability. The fix: hash(voter_id, contract_id), is straightforward once the compiler supports multi-argument hashing.

export circuit commit(voter_id: Bytes<32>, tokens: Uint<64>): [] {
    assert(!committed_tokens.member(disclose(voter_id)), "Already committed");
    committed_tokens.insert(disclose(voter_id), disclose(tokens));
}

This is the circuit where we need to be honest about the current privacy model.

Both voter_id and tokens are disclose()-d into the public ledger. The README lists these as private, but the compiler tells the true story: any value passed through disclose() into an export ledger field is fully visible on-chain. Right now, an observer can see which voter IDs have committed and exactly how many tokens each holds.

This is the same situation as the bonding curve balances from Part 1: public ledger, not private state. The genuinely private version would use persistentCommit to store a commitment to (voter_id, tokens, nonce) on-chain, with the actual values held in local private state. The vote circuit would then verify the commitment rather than checking the plaintext map. That's the architecture the README's privacy model describes and the next iteration of this contract should implement.

export circuit vote(): [] {
    const voter_id    = getVoterId();
    const tokens      = getCommittedTokens();
    const sqrt_weight = getSqrtWeight();
    const w_sq        = getWSquared();

    const computed_nullifier = computeNullifier(voter_id);

    // Verify the voter has a commitment
    assert(committed_tokens.member(disclose(voter_id)), "No commitment found");

    // Verify the committed amount matches the witness
    assert(committed_tokens.lookup(disclose(voter_id)) == disclose(tokens), "Token mismatch");

    // Verify the quadratic constraint in ZK
    verifySqrt(tokens, sqrt_weight, w_sq);

    // Prevent double voting
    assert(!has_voted.member(disclose(computed_nullifier)), "Already voted");

    // Record the vote
    has_voted.insert(disclose(computed_nullifier));
    total_votes.increment(disclose(sqrt_weight as Uint<16>));
}

Walk through the sequence of checks:

Membership check: the voter committed tokens in a prior transaction. Without this, anyone could vote with an arbitrary weight without having committed anything.

Token match: the tokens witness matches what's actually stored in the commitment map. This closes a subtle attack: without this check, a voter could commit 100 tokens then claim 10,000 tokens at vote time, pass the verifySqrt check with a legitimate w for 10,000, and vote with an inflated weight.

Quadratic constraint: verifySqrt runs. The circuit verifies w = floor(sqrt(tokens)) without computing a square root.

Double vote check: the nullifier hasn't been used. Combined with the deterministic nullifier derivation, this guarantees exactly one vote per committed voter ID.

State updates: nullifier recorded, total votes incremented by sqrt_weight. The global tally reflects the sum of all voters' square-root-weighted contributions.

The ordering of these checks matters. Membership before token match (can't verify a value that doesn't exist). Token match before verifySqrt (the constraint is meaningless if the token count can be faked). Double vote check before state update (record only after all validation passes).

What's Actually On-Chain

Being precise, same as the previous articles:

Data	On-chain?	Visible to observer?
Voter ID	Yes (committed_tokens key)	Yes
Token amount	Yes (committed_tokens value)	Yes
Square root weight	Yes (via total_votes increment)	Partially — total only
Nullifier	Yes (has_voted)	Yes
Individual vote weight	No	No
Whether a specific voter voted	Derivable from has_voted	Yes, via nullifier

The chain sees voter IDs and token amounts in the current implementation. The total_votes counter accumulates the global weighted tally but individual vote weights aren't stored separately: an observer can see the total but not decompose whose weight contributed what.

The nullifier being on-chain is intentional and necessary: it's the double-vote prevention mechanism. What it leaks is that a given voter ID has voted, derivable by anyone who knows the voter ID and can compute hash(voter_id). In the domain-separated future version, this becomes hash(voter_id, contract_id), still derivable by someone who knows the voter ID, but no longer linkable across contracts.

The Mental Model This Series Has Been Building

Step back and look at what the four contracts in this series have taught:

Bonding curve: the witness pattern. Expensive arithmetic off-chain, cheap verification in-circuit. The circuit doesn't trust the witness; it constrains it.

export ledger vs private state: the disclosure model. disclose() is a deliberate act, not a default. The compiler enforces it. Privacy is opt-out at the language level.

Escrow: multi-party coordination. Two private states, one proof. Commitment schemes bind parties to terms without revealing them. State machines enforce ordering cryptographically.

Quadratic voting: verification over computation. The circuit doesn't compute sqrt. It verifies that someone else's claimed sqrt satisfies the mathematical definition. The same pattern applies to any expensive function: compute off-chain, verify with cheaper constraints in-circuit.

That last principle is the most general. Anywhere you find yourself wanting to compute something expensive inside a ZK circuit; a square root, a logarithm, a hash of a large input - ask instead: what are the cheap constraints that a valid result must satisfy? Verify those instead.

What's Next

The natural extension of this contract, private token commitments using persistentCommit instead of plaintext export ledger maps, is exactly the bridge between this article and Part 2's commitment pattern. If you want a hands-on extension problem: refactor commit to store persistentCommit(voter_id, tokens, nonce) on-chain, move the actual values to private state, and update vote to verify the commitment before running verifySqrt. The quadratic constraint circuit stays identical, only the token retrieval and verification changes.

The allowlist contract, which uses Merkle trees, domain-separated nullifiers, and a proper off-chain membership proof system, is the next full article in this series. It takes the nullifier pattern introduced here and builds a complete private membership system around it.

Full source for this contract and the rest of the series: github.com/tusharpamnani/midnight-quadratic-voting