Building a Decentralized Voting System with Noir: A Step-by-Step Guide

Simeon Cholakov & Simão Amaro
18 min read

At Three Sigma, we recognize the intricate opportunities within the Web3 space. Based in Lisbon, our team of experts offers premier services in development, security, and economic modeling to drive your project's success. Whether you need precise code audits, advanced economic modeling, or comprehensive blockchain engineering, Three Sigma is your trusted partner.

Explore our website to learn more.

We are not just experts in code, economic auditing, and blockchain engineering—we are passionate about breaking down Web3 concepts to drive clarity and adoption across the industry.

1. Introduction

In this guide, we’ll develop a decentralized voting system step by step, using Noir, a domain-specific language (DSL) designed for building privacy-preserving Zero-Knowledge (ZK) programs. Along the way, we will explain key components such as the Noir standard library and its oracle integration.

By following this technical walkthrough, you’ll learn how to develop zero-knowledge circuits building a decentralized voting system with Noir.

2. Noir Standard Library

Cryptographic Primitives

Noir's Cryptographic Primitives library offers essential tools for secure application development, including ciphers, hash functions, elliptic curve operations, digital signatures.

Additionally, it includes utilities such as BigInt, Black Box Functions, BN254, Containers, is_unconstrained, Merkle Trees, Options, Zeroed and more.

1// Example of using a hash function
2let data = "Noir data";
3let hash_value = sha256(data);
4assert(hash_value == expected_hash, "Hash values should match");
5
6// Example of performing elliptic curve operations
7let g = ec::G1::generator();
8let private_key = 12345u64;
9let public_key = g * private_key; // Scalar multiplication on the curve
10
11// Example of verifying a Schnorr signature
12let message = "Sign this message";
13let signature = schnorr::sign(private_key, message);
14let is_valid = schnorr::verify(public_key, message, signature);
15assert(is_valid, "Schnorr signature verification failed");
16
17// Example of ECDSA signature verification
18let ecdsa_signature = ecdsa::sign(private_key, message);
19let ecdsa_is_valid = ecdsa::verify(public_key, message, ecdsa_signature);
20assert(ecdsa_is_valid, "ECDSA signature verification failed");
21
22// Example of EdDSA signature verification
23let eddsa_signature = eddsa::sign(private_key, message);
24let eddsa_is_valid = eddsa::verify(public_key, message, eddsa_signature);
25assert(eddsa_is_valid, "EdDSA signature verification failed");
26
27// Example of BigInt
28let big_number = BigInt::from(12345678901234567890u64);
29
30// Example of Black Box Functions
31let commitment = black_box::commit("secret data");
32assert(verify_commitment(commitment, "secret data"), "Commitment verification failed");
33
34// Example of BN254
35let point = bn254::G1::generator();
36let scalar = 12345u64;
37let result_point = point * scalar;
38
39// Example of Containers
40let mut vec = Vec::new(); // Vec
41let mut bounded_vec = BoundedVec::<u32, 3>::new(); // BoundedVec
42let mut map = HashMap::new(); // HashMap
43
44// Example of is_Unconstrained
45let x = unconstrained();
46assert(is_unconstrained(x), "x should be unconstrained");
47
48// Example of Merkle Trees
49let leaves = vec![hash1, hash2, hash3, hash4];
50let tree = MerkleTree::new(leaves);
51let proof = tree.generate_proof(0); // Generate proof for the first leaf
52assert(tree.verify_proof(proof, hash1), "Merkle proof verification failed");
53
54// Example of Options
55let maybe_value: Option<u32> = Some(42u32);
56match maybe_value {
57    Some(value) => log("Value is present: {}", value),
58    None => log("No value present"),
59}
60
61// Example of Zeroed
62let mut counter = zeroed::<u32>();  // Initializes counter to 0
63counter = counter + 1;
64
To learn more about the Noir Standard Library, check out the Noir documentation

3. Oracles in Noir

Introduction to Oracles

In Noir, oracles are essential components that allow a Zero-Knowledge (ZK) circuit to interact with external data sources securely. Oracles enable the incorporation of real-world data into ZK proofs without compromising the privacy and integrity of the proof system. This capability is crucial for many blockchain applications, where external data (like asset prices, weather information, or any off-chain data) needs to be included in on-chain operations.

How Oracles Work in Noir

An oracle in Noir is essentially a bridge between the external world and the ZK circuit. It fetches data from an external source, inputs this data into the circuit, and ensures that the data used in the proof is both valid and authentic. The use of oracles typically involves the following steps:

  1. Requesting Data: The oracle requests specific data from an external source.
  2. Data Validation: The data received is validated to ensure its integrity and correctness.
  3. Incorporating Data into the Proof: The validated data is then used within the ZK circuit to prove certain statements or conditions without revealing the data itself.

Oracles are particularly powerful because they allow smart contracts and ZK circuits to remain deterministic while still using external data that may change over time.

If you want to learn more about Oracles in Noir you can check the official documentation.

4. Example application

Introduction

In this guide, we’ll explore the development of a decentralized voting system that ensures privacy and security through advanced cryptographic techniques. This system leverages zero-knowledge circuits to process and verify votes, ensuring that each vote is both unique and anonymous, while also maintaining the integrity of the entire voting process.

We’ll begin by setting up the project environment, installing the necessary tools, and then proceed to develop a circuit that validates votes and computes necessary cryptographic proofs. Following this, we’ll create a Solidity smart contract to manage the voting process on the blockchain, including proposal creation, vote casting, and result tallying. This contract will interact seamlessly with the zero-knowledge proofs generated by our Noir circuit, ensuring that the system is both robust and secure.

Whether you're a seasoned blockchain developer or new to zero-knowledge proofs, this tutorial will equip you with the knowledge and tools needed to build robust, privacy-focused applications using Noir and Solidity. Let's dive in!

Installation

Installing Noirup

Run the following script in your terminal:

1curl -L https://raw.githubusercontent.com/noir-lang/noirup/main/install | bash
NOTE: The default backend for Noir (Barretenberg) doesn't provide Windows binaries at this time. For that reason, Noir cannot be installed natively. However, it is available by using Windows Subsystem for Linux (WSL). If you are a Windows user, follow this guide.

Creating the Project

Feel free to use whatever versions, just keep in mind that Nargo and the NoirJS packages are meant to be in sync. For example, Nargo 0.31.x matches [email protected], etc.



In this guide, we will be pinned to 0.31.0.

Create a new Nargo project by running:

1nargo new circuits
NOTE: You can name the project as you want, but in production, it is common practice to name the project folder, circuits, for clarity amongst other folders in the codebase (like: contracts, scripts, and test).

Development

Writing the Circuit

We will develop a circuit that processes a vote commitment, validates the vote, and computes a nullifier, ensuring both the privacy and integrity of the vote. The circuit will also include a test to verify its correctness by simulating a valid scenario.

main() function

The main() function is the core of the our circuit. It processes a vote commitment, verifies the integrity of a vote, and computes a nullifier to ensure that each vote is unique and anonymous. This function leverages cryptographic techniques like Pedersen hashing and Merkle tree verification to maintain the security and privacy of the voting process.

1fn main(
2    root: pub Field,
3    index: Field,
4    hash_path: [Field; 2],
5    secret: Field,
6    proposalId: pub Field,
7    vote_commitment: pub Field,
8    vote_opening: Field,
9    salt: Field
10) -> pub Field {

Parameters

This function takes several parameters:

  • root: pub Field: This is the public root of the Merkle tree. The Merkle tree is a data structure that allows for efficient and secure verification of the contents of a large dataset. In this context, it’s used to verify that the vote belongs to a valid tree of registered votes, ensuring the integrity of the entire voting process.
  • index: Field: The index in the Merkle tree where the note commitment (a commitment to the vote) is stored. It helps locate the specific vote within the tree, which is essential for verifying that the vote is part of the recognized and registered votes.
  • hash_path: [Field; 2]: The Merkle proof, which is an array of hashes needed to recompute the root of the Merkle tree from the note commitment. This proof is used to verify the path from the leaf (the vote commitment) to the root, ensuring that the vote has not been tampered with.
  • secret: Field: A private field representing the voter's secret. This secret is combined with the voter's choice to create a unique and secure commitment using the Pedersen hash. This prevents anyone from determining the actual vote while allowing the system to verify the integrity of the commitment.
  • proposalId: pub Field: A public field representing the ID of the proposal being voted on. It ensures that the vote is associated with the correct proposal, preventing any mix-up or misattribution of votes.
  • vote_commitment: pub Field: The commitment of the vote, which is a public hash that represents the voter's choice and secret. This commitment ensures that the vote remains hidden but can still be verified as authentic.
  • vote_opening: Field: The actual vote (e.g., 0 or 1) that the voter made. This is used to check against the commitment to ensure that the vote corresponds to what was committed to by the voter, without revealing what the vote was.
  • salt: Field: A random field used to generate the nullifier, which provides additional privacy by preventing the linking of votes to specific voters, even if they use the same secret and proposal ID across multiple votes.

Commitment Verification

The function starts by computing a new commitment (computed_vote_commitment) using the vote_opening and secret fields. This commitment is then checked against the provided vote_commitment to ensure that the vote has not been altered and that the opening (actual vote) corresponds to the commitment made by the voter.

1 let computed_vote_commitment = std::hash::pedersen_hash([vote_opening, secret]);
2  assert(vote_commitment == computed_vote_commitment);


Why we use Pedersen Hash
: Pedersen hash is used here because it is collision-resistant and homomorphic. Collision resistance ensures that it’s nearly impossible for two different inputs to produce the same hash, which is crucial for the security of the vote. The homomorphic properties allow certain operations to be performed on the encrypted data (like summing commitments) without decrypting it, maintaining the privacy of the voter's choice.

Why we use assert: The assert statement is essential for enforcing that the computed commitment matches the provided commitment. This ensures that the vote has not been tampered with and that the commitment accurately reflects the voter's original choice.

Vote Range Checking

Next, the function ensures that the vote_opening is within the valid range (e.g., 0 or 1 for binary choices). This step is crucial for preventing invalid votes (such as a vote of 2 in a yes/no scenario) from being counted.

1let vote_opening_int = vote_opening as i32;
2
3    assert(vote_opening_int >= 0);
4    assert(vote_opening_int <= 1);

Nullifier Calculation

The function then computes a nullifier using the root, secret, proposalId, and salt fields. The nullifier is a unique value that prevents linking a specific vote to a voter while still allowing the vote to be counted. This is crucial for maintaining voter privacy while ensuring that each vote is unique and cannot be duplicated.

1    let nullifier = std::hash::pedersen_hash([root, secret, proposalId, salt]);

Why we use Pedersen Hash: Again, Pedersen hash is used here due to its cryptographic properties, ensuring that the nullifier is unique and secure. The use of salt adds randomness, which is crucial for preventing any linkage between different votes cast by the same voter.

Merkle Tree Integrity Check

The function generates a note_commitment from the secret and then uses this commitment along with the index and hash_path to recompute the Merkle root (check_root). It asserts that this computed root matches the provided root, verifying the integrity of the Merkle tree.

1let note_commitment = std::hash::pedersen_hash([secret]);
2    let check_root = std::merkle::compute_merkle_root(note_commitment, index, hash_path);
3    assert(root == check_root);


Why we compute the Merkle root
: The Merkle root computation is essential because it ensures that the vote is included in the valid and authenticated set of votes. This helps maintain the integrity of the voting system by verifying that no unauthorized votes have been inserted into the voting process.

Finally, the function returns the computed nullifier, which serves as a key component in preserving the voter's anonymity while ensuring that the vote is unique and counted.

1 nullifier
2}

If every step was followed correctly your main.nr file should look like this:

1fn main(
2    root: pub Field,
3    index: Field,
4    hash_path: [Field; 2],
5    secret: Field,
6    proposalId: pub Field,
7    vote_commitment: pub Field,
8    vote_opening: Field,
9    salt: Field
10) -> pub Field {
11    let computed_vote_commitment = std::hash::pedersen_hash([vote_opening, secret]);
12    assert(vote_commitment == computed_vote_commitment);
13
14    let vote_opening_int = vote_opening as i32;
15
16    assert(vote_opening_int >= 0);
17    assert(vote_opening_int <= 1);
18
19    let nullifier = std::hash::pedersen_hash([root, secret, proposalId, salt]);
20
21    let note_commitment = std::hash::pedersen_hash([secret]);
22    let check_root = std::merkle::compute_merkle_root(note_commitment, index, hash_path);
23    assert(root == check_root);
24
25    nullifier
26}

Testing the Circuit

Build in/output files

Change directory into circuits and build in/output files for your Noir program by running:

1cd circuits
2nargo check

Prover.toml file will be generated in your project directory, to allow specifying input values to the program.

Execute the Noir program

Now that the project is set up, we can execute our Noir program.

Fill in input values for execution in the Prover.toml file:

1hash_path = [
2  "0x1efa9d6bb4dfdf86063cc77efdec90eb9262079230f1898049efad264835b6c8",
3  "0x2a653551d87767c545a2a11b29f0581a392b4e177a87c8e3eb425c51a26a8c77"
4]
5index = "0"
6proposalId = "0"
7root = "0x215597bacd9c7e977dfc170f320074155de974be494579d2586e5b268fa3b629"
8salt = "0xabc123" 
9secret = "1"
10vote_commitment = "0x07ebfbf4df29888c6cd6dca13d4bb9d1a923013ddbbcbdc3378ab8845463297b" 
11vote_opening = "1"

Here is an explanation of each input parameter:

  • hash_path: An array of hashes used to verify that a specific vote commitment is part of the Merkle tree by recomputing the Merkle root from the leaf (vote commitment) to the root.
  • index: Specifies the position of the vote commitment within the Merkle tree. In this case, 0 indicates it's the first position.
  • proposalId: The unique identifier for the proposal being voted on. Here, 0 signifies the first or primary proposal.
  • root: The Merkle root representing the combined commitment of all votes. This is crucial for verifying the integrity of the voting process.
  • salt: A random value used to create the nullifier, ensuring the vote is anonymous and unlinkable, even if the same secret is reused.
  • secret: A private value known only to the voter, used with the vote_opening to generate a secure vote_commitment, ensuring uniqueness and security.
  • vote_commitment: A cryptographic hash representing the voter's choice and secret, used to verify that the vote is authentic without revealing the actual choice.
  • vote_opening: The actual vote cast (e.g., 0 for "No" or 1 for "Yes"), used with the secret to generate the vote_commitment and verify the vote's consistency.

Now let’s execute our Noir program:

1nargo execute circuits

Proving Backend

Each proving backend offers its own tools for working with Noir programs, such as generating and verifying proofs, and creating verifier smart contracts.

You can find a full list of compatible proving backends in Awesome Noir.

For our purposes, we’ll install bb, a CLI tool from the Barretenberg proving backend by Aztec Labs.

Barretenberg is a library for creating and verifying proofs. You can define the circuits used for proofs either with the Barretenberg standard library or by using an IR called ACIR.

This tool will generate proofs using ACIR and witness values as input.

Installation

Run the following script in your terminal:

1curl -L https://raw.githubusercontent.com/AztecProtocol/aztec-packages/master/barretenberg/cpp/installation/install | bash

Install the version of bb compatible with your Noir version; as we use Noir v0.31.0 run:

1bbup -v 0.41.0
NOTE: Currently the binary downloads an SRS that can be used to prove the maximum circuit size. This maximum circuit size parameter is a constant in the code and has been set to 2^{23}as of writing. This maximum circuit size differs from the maximum circuit size that one can prove in the browser, due to WASM limits.

Prove an execution of the Noir program

Using Barretenberg we will, prove the valid execution of our Noir program running:

1bb prove -b ./target/circuits.json -w ./target/circuits.gz -o ./target/proof

The proof generated will then be written to ./target/proof.

Verify the execution proof

Once a proof is generated, we can verify correct execution of our Noir program by verifying the proof file.

Compute the verification key for the Noir program by running:

1bb write_vk -b ./target/circuits.json -o ./target/vk

And verify your proof by running:

1bb verify -k ./target/vk -p ./target/proof
NOTE: If successful, the verification will complete in silence; if unsuccessful, the command will trigger logging of the corresponding error.

Smart Contract Development

Writing the Voting Contract

We will develop the Solidity smart contract that manages a decentralized voting system. The Voting contract is the core of our system. It handles proposal creation, vote casting, and vote counting while ensuring the security and integrity of the voting process. The contract leverages cryptographic techniques and a Merkle tree structure to maintain voter privacy and prevent fraud.

Key Components

Constructor

The constructor initializes the contract with a Merkle root and a verifier contract:

1constructor(bytes32 _merkleRoot, address _verifier) {
2    merkleRoot = _merkleRoot;
3    verifier = UltraVerifier(_verifier);
4}
5
6
  • merkleRoot: Represents the root of the Merkle tree, which ensures that only authorized votes are included.
  • verifier: An instance of the UltraVerifier contract that verifies zero-knowledge proofs associated with each vote.

propose() Function

This function allows users to create a new proposal with a description and a voting deadline:

1function propose(
2    string memory description,
3    uint256 deadline
4) public returns (uint256) {
5    proposals[proposalCount] = Proposal(description, deadline, 0, 0);
6    proposalCount += 1;
7    return proposalCount;
8}
9
10
  • description: A brief description of the proposal.
  • deadline: The time until which voting on the proposal is allowed.

castVote() Function

The castVote() function is the most critical part of the contract, handling the process of casting and verifying votes:

1function castVote(
2    bytes32[] memory proof,
3    uint256 proposalId,
4    uint256 vote,
5    bytes32 nullifierHash
6) public returns (bool) {
7    require(!nullifiers[nullifierHash], "Proof has been already submitted");
8    require(
9        block.timestamp < proposals[proposalId].deadline,
10        "Voting period is over."
11    );
12    nullifiers[nullifierHash] = true;
13
14    bytes32 leaf = keccak256(
15        bytes.concat(
16            keccak256(
17                abi.encode(
18                    merkleRoot,
19                    bytes32(proposalId),
20                    bytes32(vote),
21                    nullifierHash
22                )
23            )
24        )
25    );
26    require(MerkleProof.verify(proof, merkleRoot, leaf), "Invalid proof");
27
28    if (vote == 1) {
29        proposals[proposalId].forVotes += 1;
30    } else {
31        proposals[proposalId].againstVotes += 1;
32    }
33
34    return true;
35}
36
37
  • Nullifier Check: Ensures that the vote hasn't been cast already using the same nullifierHash, preventing double voting.
  • Merkle Proof Verification: A cryptographic proof that verifies the validity of the vote based on the Merkle root and other parameters.
  • Vote Counting: Depending on the vote value (1 for "for", 0 for "against"), the contract updates the vote count for the proposal.

Fix for Second Preimage Attack in the castVote() Function

To prevent second preimage attacks, the contract uses a specific leaf encoding method:

1bytes32 leaf = keccak256(
2    bytes.concat(
3        keccak256(
4            abi.encode(
5                merkleRoot,
6                bytes32(proposalId),
7                bytes32(vote),
8                nullifierHash
9            )
10        )
11    )
12);

Leaf Hash Encoding: By encoding the Merkle root, proposal ID, vote, and nullifier hash together, this method ensures that each leaf in the Merkle tree is unique and secure. This mitigates the risk of an attacker finding two different inputs that hash to the same value, thus preserving the integrity of the voting process.

Here is the full contract:

1//SPDX-License-Identifier: MIT
2pragma solidity 0.8.21;
3
4import {UltraVerifier} from "../../circuits/contract/plonk_vk.sol";
5import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
6
7contract Voting {
8    UltraVerifier verifier;
9
10    struct Proposal {
11        string description;
12        uint256 deadline;
13        uint256 forVotes;
14        uint256 againstVotes;
15    }
16
17    bytes32 merkleRoot;
18    uint256 proposalCount;
19    mapping(uint256 proposalId => Proposal) public proposals;
20    mapping(bytes32 hash => bool isNullified) nullifiers;
21
22    constructor(bytes32 _merkleRoot, address _verifier) {
23        merkleRoot = _merkleRoot;
24        verifier = UltraVerifier(_verifier);
25    }
26
27    function propose(
28        string memory description,
29        uint256 deadline
30    ) public returns (uint256) {
31        proposals[proposalCount] = Proposal(description, deadline, 0, 0);
32        proposalCount += 1;
33        return proposalCount;
34    }
35
36    /// @param vote - Must be "1" to count as a forVote
37    function castVote(
38        bytes32[] memory proof,
39        uint256 proposalId,
40        uint256 vote,
41        bytes32 nullifierHash
42    ) public returns (bool) {
43        require(!nullifiers[nullifierHash], "Proof has been already submitted");
44        require(
45            block.timestamp < proposals[proposalId].deadline,
46            "Voting period is over."
47        );
48        nullifiers[nullifierHash] = true;
49
50        bytes32 leaf = keccak256(
51            bytes.concat(
52                keccak256(
53                    abi.encode(
54                        merkleRoot,
55                        bytes32(proposalId),
56                        bytes32(vote),
57                        nullifierHash
58                    )
59                )
60            )
61        );
62        require(MerkleProof.verify(proof, merkleRoot, leaf), "Invalid proof");
63
64        if (vote == 1) {
65            proposals[proposalId].forVotes += 1;
66        }
67        // vote = 0
68        else {
69            proposals[proposalId].againstVotes += 1;
70        }
71
72        return true;
73    }
74}
75

If you want to add the full system, you can include some Foundry tests. To do this, you should install Foundry by following this guide.

Here is the Foundry test:

1// SPDX-License-Identifier: UNLICENSED
2pragma solidity 0.8.21;
3
4import "../lib/forge-std/src/Test.sol";
5import "../src/Voting.sol";
6import "../../circuits/contract/plonk_vk.sol";
7
8contract VotingTest is Test {
9    Voting public voteContract;
10    UltraVerifier public verifier;
11
12    bytes32[] proof;
13    bytes32[] emptyProof;
14
15    uint256 deadline = block.timestamp + 10000000;
16
17    bytes32 merkleRoot;
18    bytes32 nullifierHash;
19
20    function readInputs() internal view returns (string memory) {
21        string memory inputDir = string.concat(vm.projectRoot(), "/data/input");
22
23        return vm.readFile(string.concat(inputDir, ".json"));
24    }
25
26    function setUp() public {
27        string memory inputs = readInputs();
28
29        merkleRoot = bytes32(vm.parseJson(inputs, ".merkleRoot"));
30        nullifierHash = bytes32(vm.parseJson(inputs, ".nullifierHash"));
31
32        verifier = new UltraVerifier();
33        voteContract = new Voting(merkleRoot, address(verifier));
34        voteContract.propose("First proposal", deadline);
35
36        string memory proofFilePath = "./circuits/proofs/foundry_voting.proof";
37        string memory proofData = vm.readLine(proofFilePath);
38
39        proof = abi.decode(vm.parseBytes(proofData), (bytes32[]));
40        // emptyProof = abi.decode(vm.parseBytes(proofData), (bytes32[]));
41    }
42
43    function test_validVote() public {
44        voteContract.castVote(proof, 0, 1, nullifierHash);
45    }
46
47    function test_invalidProof() public {
48        vm.expectRevert();
49        voteContract.castVote(emptyProof, 0, 1, nullifierHash); // passing an empty proof
50    }
51
52    function test_doubleVoting() public {
53        voteContract.castVote(proof, 0, 1, nullifierHash);
54
55        vm.expectRevert("Proof has been already submitted");
56        voteContract.castVote(proof, 0, 1, nullifierHash);
57    }
58
59    function test_changedVote() public {
60        vm.expectRevert();
61
62        voteContract.castVote(proof, 0, 0, nullifierHash); // attempting to vote against after a vote for
63    }
64}

Now it’s your turn to expand the circuit, add more tests, and continue learning!

For reference you can check the GitHub repo with the full code.

5. Conclusion

In conclusion, Noir offers a streamlined and accessible approach to zero-knowledge proof development, enabling developers to build privacy-preserving applications without needing deep cryptographic knowledge. Through the creation of a decentralized voting system, we showcased how Noir simplifies the integration of complex cryptographic techniques, making it easier to implement secure and anonymous on-chain solutions.

This concludes Part II of our Noir Language Deep-dives!

Reach out to Three Sigma, and let our team of seasoned professionals guide you confidently through the Web3 landscape. Our expertise in smart contract security, economic modeling, and blockchain engineering, we will help you secure your project's future.

Contact us today and turn your Web3 vision into reality!

References: Noir Docs, Awesome Noir Repo