Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Anonymous Voting with Cairo (Merkle Tree + Nullifier)

Draft: Generated By AI, need audits

This is the same pattern behind Semaphore: prove membership in a set without revealing which member you are, and stop double-use with a nullifier.

Semaphore is a generic privacy layer. Leveraging zero-knowledge technology, users can prove their membership in groups and send messages (extending from votes to endorsements) off-chain or across blockchains, all without revealing their personal identity.

Semaphore

1. The protocol, conceptually

Setup (public, done once)

  • Build a Merkle tree whose leaves are commitment_i = Poseidon(secret_i) for every eligible voter, where secret_i is a value only voter i knows (derived from their keypair, or a fresh random identity secret they generate and register).
  • Publish the tree root. The candidate list is public.

Don’t who does the setup knows the secret?

Good catch — that line was ambiguous. The setup authority (registrar/contract) never learns the secret. Here’s the actual flow:

  1. Voter generates the secret locally, on their own device — e.g. a random felt252, or something derived from a keypair they control. It never leaves their machine.
  2. Voter computes commitment = Poseidon(secret) locally and sends only the commitment to the registrar as their registration.
  3. Registrar collects all commitments (one per eligible voter, submitted via whatever KYC/eligibility process you use to confirm who is allowed to register — that part is off-chain/identity-specific and separate from the crypto) and builds the Merkle tree from those commitments as leaves.
  4. Registrar publishes the root. At no point does it see or need the secret — a commitment is a one-way hash, so it can build the tree and verify “this person is eligible” without ever learning what secret produced the commitment.

So the trust split is:

  • Registrar is trusted to only accept one commitment per eligible voter (this is where identity/eligibility checking actually happens — it’s a real-world problem, not a crypto one: they still need some way to know “this commitment belongs to a legitimate registered voter” without learning who).
  • Registrar is not trusted with any voter’s secret, and can’t link a commitment back to a person later, because Poseidon is one-way and the commitment reveals nothing about the secret.

This is exactly the same split you’d trust a passport office with in the physical world: they verify you’re a real, unique citizen and issue you a credential, but they don’t get to see how you later use it.

One nuance worth naming: the registrar (or whoever controls the registration process) does typically know which real-world identity submitted which commitment at registration time, even though the commitment itself doesn’t reveal the secret. So anonymity here means “an observer of the vote can’t tell which registered voter cast it,” not “the registrar has zero knowledge of who registered.” If you need to hide that too, you’d want a decentralized/verifiable registration process rather than a single trusted registrar — but that’s a separate, harder problem from the vote-anonymity piece you asked about originally.

Voting (per voter, off-chain, private) A voter proves, in zero knowledge:

  1. Membership: “I know a secret such that Poseidon(secret) is a leaf in the tree with this root, at some position I’m not revealing” — via a standard Merkle inclusion proof done inside the circuit.
  2. Correct nullifier: “This public value nullifier = Poseidon(secret, election_id) was computed from that same secret.”

The circuit outputs three public values: root, nullifier, candidate_id. The secret and the Merkle path (siblings + left/right bits) stay private witness inputs — they never appear in the proof or on-chain.

Voting (per voter, off-chain, private) A voter proves, in zero knowledge:

  1. Membership: “I know a secret such that Poseidon(secret) is a leaf in the tree with this root, at some position I’m not revealing” — via a standard Merkle inclusion proof done inside the circuit.
  2. Correct nullifier: “This public value nullifier = Poseidon(secret, election_id) was computed from that same secret.”

The circuit outputs three public values: root, nullifier, candidate_id. The secret and the Merkle path (siblings + left/right bits) stay private witness inputs — they never appear in the proof or on-chain.

Verification (on-chain / anyone)

  • Check root matches the known tree root (so they used the real voter list).
  • Check the STARK proof verifies against the program (this proves the person really does know a valid secret + path — that’s “the vote belongs to a valid voter”).
  • Check nullifier hasn’t been seen before — that’s “not voted twice”.
  • Record nullifier as spent, tally candidate_id.

Why the nullifier prevents double voting but preserves anonymity

nullifier = H(secret, election_id) is deterministic per voter per election, but election_id is not mixed with candidate_id. So:

  • The same voter always produces the same nullifier in this election → second attempt is rejected.
  • Nullifier reveals nothing about which leaf/secret produced it (one-way hash), so it can’t be linked back to an identity.
  • Different elections use different election_id → same voter’s nullifiers in different elections are unlinkable to each other.

Do not include candidate_id in the nullifier — if you did, a voter could vote once per candidate instead of once total.

2. How the voter generates their commitment

This happens entirely on the voter’s own device, before registration, and the secret never leaves it. Two things matter here:

  1. secret must come from a real entropy source. Cairo programs are deterministic — there’s no “random()” you can call inside a circuit and still have a verifiable proof — so the randomness has to be generated by the OS/wallet outside Cairo, and only the resulting felt252 is fed in as an input.
  2. Hashing it (Poseidon(secret)) can be done either with the same Cairo code used everywhere else, or client-side in JS if the voter is using a web wallet. Both give the identical result since Poseidon is a fixed, public function.

Cairo side — a tiny reusable executable, same hash used by the circuit and the registrar so everything stays consistent:

#![allow(unused)]
fn main() {
use core::poseidon::poseidon_hash_span;

/// Run locally by the voter. `secret` is supplied as an input generated by a
/// secure RNG outside Cairo (wallet / OS urandom) — never hardcoded, never logged.
#[executable]
fn generate_commitment(secret: felt252) -> felt252 {
    poseidon_hash_span(array![secret].span())
}
}

Realistic client side — most voters won’t run cairo-run by hand; this lives in a wallet or web app using starknet.js, which has the same Poseidon implementation:

import { ec, hash } from "starknet";

// 1. Generate a fresh, secret felt (cryptographically random, within the field).
function generateSecret() {
  // 31 random bytes keeps it safely below the STARK field prime.
  const randomBytes = crypto.getRandomValues(new Uint8Array(31));
  const hex = "0x" + Buffer.from(randomBytes).toString("hex");
  return BigInt(hex);
}

const secret = generateSecret();

// 2. Commitment = Poseidon(secret) — same function the Cairo code uses.
const commitment = hash.poseidonHashMany([secret]);

// 3. Voter stores `secret` locally (encrypted, or derived deterministically
//    from their wallet key so it can be re-derived instead of stored — see
//    note below), and submits ONLY `commitment` to the registrar.
console.log("Submit to registrar:", commitment.toString());
console.log("Keep private, never submit:", secret.toString());

Two options for where secret comes from:

  • Fresh random secret (shown above) — simplest, but the voter must securely back it up; lose it and they lose their ability to vote, since there’s no way to re-derive it.
  • Deterministic derivation from their wallet key — e.g. secret = Poseidon(sign(wallet_private_key, "vote-identity-v1")) (sign a fixed, app-specific message with their existing wallet, then hash the signature). This way the voter doesn’t need to separately store anything — they can always regenerate the same secret later just by signing that same message again with the same wallet. This is generally the more practical choice for a real deployment.

Either way, only commitment — never secret — gets sent anywhere during registration. The registrar adds commitment to the list described next.

3. The Cairo circuit (proved off-chain)

This is a plain Cairo program (Cairo 1, using core::poseidon), not a Starknet contract. You run it through Cairo’s prover (proof mode) to get a STARK proof; only the public outputs + proof get submitted on-chain.

use core::poseidon::poseidon_hash_span;
use core::array::ArrayTrait;

/// Recompute the Merkle root from a leaf and its authentication path.
/// `path`: sibling hash at each level (private).
/// `path_indices`: 0 = current node is the left child, 1 = right child (private).
fn compute_merkle_root(
    leaf: felt252, path: Array<felt252>, path_indices: Array<felt252>
) -> felt252 {
    let mut current = leaf;
    let mut i: u32 = 0;
    let len = path.len();
    loop {
        if i == len {
            break;
        }
        let sibling = *path.at(i);
        let idx = *path_indices.at(i);
        current =
            if idx == 0 {
                poseidon_hash_span(array![current, sibling].span())
            } else {
                poseidon_hash_span(array![sibling, current].span())
            };
        i += 1;
    };
    current
}

/// The voting circuit.
/// Private witness: `secret`, `merkle_path`, `path_indices`.
/// Public inputs / outputs: `root`, `candidate_id`, `election_id`, and the
/// derived `nullifier` (also public, computed inside the circuit).
#[executable]
fn main(
    secret: felt252,
    merkle_path: Array<felt252>,
    path_indices: Array<felt252>,
    root: felt252,
    candidate_id: felt252,
    election_id: felt252,
) -> (felt252, felt252, felt252) {
    // 1. Re-derive the public identity commitment from the private secret.
    let leaf = poseidon_hash_span(array![secret].span());

    // 2. Prove that leaf is really in the tree with the claimed root.
    let computed_root = compute_merkle_root(leaf, merkle_path, path_indices);
    assert(computed_root == root, 'invalid merkle proof');

    // 3. Deterministic, one-time-per-election nullifier (does NOT include candidate_id).
    let nullifier = poseidon_hash_span(array![secret, election_id].span());

    // Public outputs the on-chain verifier will see.
    (root, nullifier, candidate_id)
}

Key point: secret, merkle_path, path_indices are witness inputs known only to the prover (the voter’s machine). The STARK proof attests the computation was done correctly without revealing them. Only (root, nullifier, candidate_id) and the proof leave the voter’s machine.

4. The Starknet contract (verifies proof, stores state)

#![allow(unused)]
fn main() {
#[starknet::contract]
mod Voting {
    use starknet::storage::{Map, StorageMapReadAccess, StorageMapWriteAccess,
                             StorageMapWriteAccess as _};
    use starknet::get_caller_address;

    #[storage]
    struct Storage {
        merkle_root: felt252,
        election_id: felt252,
        nullifiers: Map<felt252, bool>,
        votes: Map<felt252, u128>, // candidate_id -> tally
    }

    #[constructor]
    fn constructor(ref self: ContractState, root: felt252, election_id: felt252) {
        self.merkle_root.write(root);
        self.election_id.write(election_id);
    }

    #[external(v0)]
    fn cast_vote(
        ref self: ContractState,
        proof: Span<felt252>,   // serialized STARK proof from step 2
        root: felt252,           // public output of the circuit
        nullifier: felt252,      // public output of the circuit
        candidate_id: felt252,   // public output of the circuit
    ) {
        assert(root == self.merkle_root.read(), 'wrong merkle root');
        assert(!self.nullifiers.read(nullifier), 'nullifier already used');

        // Delegate to a deployed STARK verifier contract (e.g. the "Integrity"
        // verifier on Starknet) that checks `proof` against this program's hash
        // and the public inputs (root, nullifier, candidate_id, election_id).
        let ok = verify_vote_proof(proof, root, nullifier, candidate_id, self.election_id.read());
        assert(ok, 'invalid proof');

        self.nullifiers.write(nullifier, true);
        let current = self.votes.read(candidate_id);
        self.votes.write(candidate_id, current + 1);
    }

    #[external(v0)]
    fn tally(self: @ContractState, candidate_id: felt252) -> u128 {
        self.votes.read(candidate_id)
    }
}
}

verify_vote_proof is a stand-in for a real STARK verifier call — Starknet doesn’t ship a generic “verify any Cairo proof” opcode, so in practice you either:

  • Call an already-deployed STARK verifier contract for your prover (e.g. the open-source Integrity verifier on Starknet mainnet, built for exactly this “prove a Cairo program off-chain, verify on-chain” flow), or
  • Skip the separate proof entirely and just run the membership/nullifier logic as a normal Starknet contract call — since Starknet itself is a validity rollup, the sequencer proves correct execution of every transaction anyway. The catch: calldata (your secret, Merkle path) would then be public in the transaction, breaking anonymity. This only works if the private witness never appears in calldata — which is why the off-chain-proof approach above is the one to use for genuine privacy.

5. How the registrar builds the root

Building the tree needs no secrets and no proof — every commitment is already public, so this is just deterministic hashing that the registrar (or anyone else, for that matter — the computation itself is not privileged) runs once.

#![allow(unused)]
fn main() {
use core::poseidon::poseidon_hash_span;
use core::array::ArrayTrait;

/// Round n up to the next power of two (fixed tree depth requires a full tree).
fn next_pow2(n: u32) -> u32 {
    let mut p: u32 = 1;
    loop {
        if p >= n {
            break p;
        }
        p = p * 2;
    }
}

/// Pad the commitment list to a power-of-two length with a fixed, public
/// "empty leaf" value (0), so every voter's proof has the same fixed depth.
fn pad_leaves(mut leaves: Array<felt252>) -> Array<felt252> {
    let n = leaves.len();
    let target = next_pow2(n);
    let mut i = n;
    loop {
        if i == target {
            break;
        }
        leaves.append(0);
        i += 1;
    };
    leaves
}

/// Hash one full level of nodes pairwise into the level above it.
fn hash_level(level: Array<felt252>) -> Array<felt252> {
    let mut next: Array<felt252> = ArrayTrait::new();
    let mut i: u32 = 0;
    let len = level.len();
    loop {
        if i >= len {
            break;
        }
        let left = *level.at(i);
        let right = *level.at(i + 1);
        next.append(poseidon_hash_span(array![left, right].span()));
        i += 2;
    };
    next
}

/// Build the full tree from the list of registered commitments.
/// `commitments[i] = Poseidon(secret_i)`, submitted by voter i at registration —
/// the registrar never sees `secret_i`, only this hash.
/// Returns the root, plus every level of the tree (level 0 = padded leaves),
/// so paths can be extracted for any voter afterward.
fn build_merkle_tree(commitments: Array<felt252>) -> (felt252, Array<Array<felt252>>) {
    let leaves = pad_leaves(commitments);
    let mut levels: Array<Array<felt252>> = ArrayTrait::new();
    levels.append(leaves.clone());

    let mut current = leaves;
    loop {
        if current.len() == 1 {
            break;
        }
        let next = hash_level(current.clone());
        levels.append(next.clone());
        current = next;
    };

    let root = *current.at(0);
    (root, levels)
}

/// Given the full tree and a leaf's index, extract the sibling path a voter
/// needs to build their proof (the `merkle_path` / `path_indices` witness
/// from the circuit in section 2).
fn get_merkle_path(
    levels: @Array<Array<felt252>>, leaf_index: u32
) -> (Array<felt252>, Array<felt252>) {
    let mut path: Array<felt252> = ArrayTrait::new();
    let mut indices: Array<felt252> = ArrayTrait::new();

    let mut idx = leaf_index;
    let num_levels = levels.len();
    let mut level_i: u32 = 0;
    loop {
        if level_i == num_levels - 1 {
            break; // stop one level below the root
        }
        let level = levels.at(level_i);
        let is_right = idx % 2 == 1;
        let sibling_idx = if is_right { idx - 1 } else { idx + 1 };
        let sibling = *level.at(sibling_idx);
        path.append(sibling);
        indices.append(if is_right { 1 } else { 0 });
        idx = idx / 2;
        level_i += 1;
    };
    (path, indices)
}
}

Registrar’s actual workflow:

  1. Collect one commitment = Poseidon(secret) per eligible voter, in some agreed, fixed order (e.g. order of registration, or sorted). This ordering must be public and fixed, since everyone needs to reconstruct the same tree.
  2. Call build_merkle_tree(commitments) → get root and levels.
  3. Publish two things publicly: the full ordered commitments list, and the root (e.g. write root into the Starknet contract’s merkle_root storage via an owner-only admin function, and put the commitment list on IPFS/a public endpoint).

Important: this whole step is not actually privileged. Since the commitment list is public and hashing is deterministic, any voter (or anyone) can independently rebuild the exact same tree from the published commitments and call get_merkle_path on their own leaf index to get their own path — they don’t need to trust the registrar’s path extraction, only trust that the published root was computed correctly from the published commitments (which anyone can verify by recomputing it).

The registrar’s only genuinely privileged, trust-requiring step is deciding which commitments get added to the list in the first place — i.e. the real-world eligibility/identity check (“is this a unique, legitimate voter”), which is outside the cryptography entirely.

Minimal admin setter on the contract side:

#![allow(unused)]
fn main() {
#[external(v0)]
fn set_merkle_root(ref self: ContractState, new_root: felt252) {
    // add an owner/admin check here in a real deployment
    self.merkle_root.write(new_root);
}
}

6. Summary — does this answer your questions?

  • “Validate the vote belongs to a valid voter” → the STARK proof of Merkle membership (step 2) does this; it succeeds only if the prover knew a secret whose commitment is a real leaf, and it does so without revealing which leaf.
  • “How proof is generated” → a Cairo program is executed with the private witness (secret + path) and public inputs, then run through Cairo’s STARK prover (proof mode) to produce a proof plus the public outputs.
  • “Not voted twice” → the nullifier, derived from the same secret and a fixed election_id, is deterministic per voter per election; the contract stores used nullifiers and rejects repeats.
  • “Can it be done in Cairo?” → yes — this is a native fit. Poseidon (a STARK-friendly hash) and STARK proving are exactly what Cairo/Starknet were built for; this pattern is production-proven via Semaphore-style systems.

Reference: The Cairo Book — see the chapters on Poseidon/hashing, #[executable] programs and proof mode, and Starknet contract storage (Map) for the primitives used above.

Is it ok (commitment and public key/user identity) are linked and stored in blockchain.

The ZK proof itself is fine

Your circuit never outputs the leaf/commitment value — only (root, nullifier, candidate_id). So even if a public mapping public_key → commitment exists on-chain, the proof doesn’t reveal which leaf/commitment was used to generate it. Anonymity within the proof still holds: an observer of the vote transaction can’t tell which of the N registered commitments produced it, mapping or no mapping.

The real problem: who submits the vote transaction

The actual leak isn’t in the circuit — it’s in the transaction metadata. If the same public key that’s publicly linked to commitment is also the one that signs and pays for the cast_vote transaction, you’ve completely undone the anonymity, regardless of how clever the ZK proof is:

on-chain record:  public_key_X  →  commitment_X        (public, from registration)
vote tx:          sender = public_key_X, proof = P, nullifier = N, vote = candidate_id

Anyone watching the chain sees “public_key_X submitted this vote transaction” directly in the transaction’s sender field — a completely separate, non-cryptographic channel that bypasses the whole point of the ZK proof. The proof hides which leaf was used, but the transaction sender openly says “voter X did this,” so the hiding was moot.

This is a very common mistake in naive designs: people build a solid anonymity circuit and then submit the proof from the same wallet used to register, which leaks identity for free at the transaction layer.

The fix: decouple registration identity from vote-submission identity

The account that submits the vote transaction must not be linkable to the account that registered. A few standard approaches:

  • Relayer / paymaster: voter generates the proof locally, then sends it to a relayer service (or uses a gasless/meta-transaction relayer) that submits the transaction on their behalf, paying gas from an unrelated account. The relayer sees the proof but not the secret, and the on-chain sender is the relayer, not the voter.
  • Fresh burner address: voter funds a brand-new, never-before-used address (ideally funded in a way that doesn’t trace back to them — e.g. via a mixer or a relayer-funded faucet) and submits the vote transaction from that address instead of their registered one.
  • Account abstraction: have the vote-casting be sponsored/submitted through a paymaster contract so the underlying signer’s address never appears as the transaction’s fee-paying sender.
#![allow(unused)]
fn main() {
// Contract accepts the vote from ANY caller — it doesn't matter who submits
// it, since the proof itself carries all the authorization needed. This is
// what makes the relayer pattern possible: sender identity is irrelevant to
// validity, only to metadata privacy.
#[external(v0)]
fn cast_vote(
    ref self: ContractState,
    proof: Span<felt252>,
    root: felt252,
    nullifier: felt252,
    candidate_id: felt252,
) {
    // no get_caller_address() check anywhere — anyone can relay this call
    ...
}
}

Notice the contract already supports this — cast_vote never checks get_caller_address(), precisely because the proof (not the sender) is what proves legitimacy. That design choice is what makes decoupling possible; if you did add a caller check tied to the registered public key, you’d force voters to submit from their known address and destroy the anonymity regardless of the ZK layer.

Secondary correlation risks worth knowing

Even with a relayer, be aware of:

  • Timing correlation: registering and then voting within seconds of each other, especially if few people are active at that moment, can narrow the anonymity set probabilistically.
  • IP-level metadata: if the relayer or RPC endpoint logs the requester’s IP, that’s another channel outside the cryptography entirely.

None of this touches your circuit design — it’s still correct — but it’s the part that actually determines whether real-world anonymity holds in practice.