Implementing zk-SNARKs in a Voting System on the Celo Blockchain

Technical Tutorials
,
Implementing zk-SNARKs in a Voting System on the Celo Blockchain
none 0.0 0
1

Introduction

Blockchain technology has opened new possibilities for creating transparent and secure voting systems. However, one of the key challenges in blockchain-based voting is preserving voter privacy while ensuring the integrity of the election. This is where Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) come into play.

zk-SNARKs allow for the creation of cryptographic proofs that verify the validity of a statement without revealing any underlying information about it. By leveraging zk-SNARKs in a blockchain-based voting system, we can ensure that:

  1. Voter Privacy: Individual votes remain confidential and anonymous.
  2. Proof of Validity: Each vote is valid without revealing voter identity or preferences.
  3. Prevention of Double Voting: The system enforces that each voter can only cast one vote.
  4. Transparency: The tallying process is publicly verifiable without exposing individual votes.

In this tutorial, we will explore how to build a zk-SNARK-powered voting system on the Celo blockchain

Key Features of the system:

The system leverages zk-SNARKs to ensure:

  1. Privacy: Votes remain anonymous, even as tallies are publicly verifiable.
  2. Integrity: Votes are verified for validity without revealing their content.
  3. Scalability: The zk-SNARKs’ succinct proofs allow efficient on-chain verification.
  4. Accountability: Prevents double voting and ensures eligible participation.

Prerequisites

To follow this tutorial, you should have:

  • A solid grasp of cryptographic principles, particularly zk-SNARKs.
  • Experience in Solidity and blockchain development.
    You can follow the pathway here to get a good foundation on zkSnarks

The Circuit

pragma circom 2.1.6;

include "circomlib/poseidon.circom";
// include "https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom";

template MerkleProof (n) {

    //public inputs
    signal input leaf;              // Precomputed hash of the transaction (leaf)
    signal input pathElements[n];   // Precomputed sibling hashes
    signal input pathIndices[n];    // 0 = left, 1 = right (must be Boolean)
    signal input root;              // Precomputed Merkle tree root


    signal output isValid;            // 1 if the proof is valid, 0 otherwise

     
     signal intermediateHashes[n + 1];   // Array to store intermediate hashes
     signal leftCombination[n];          // Array for left combinations
     signal rightCombination[n];         // Array for right cobinations
     signal selectedLeft[n];             // Array for selected left branch
     signal selectedRight[n];            // Array for selected right branch


     
     intermediateHashes[0] <== leaf;     // Initialize with the leaf hash


    // Compute the root based on the path provided
    for (var i = 0; i < n; i++) {
        // Ensure pathIndices[i] is Boolean
        pathIndices[i] * (1 - pathIndices[i]) === 0;

        // Compute both possible branches
        leftCombination[i] <== intermediateHashes[i] + pathElements[i]; // Left sibling
        rightCombination[i] <== pathElements[i] + intermediateHashes[i]; // Right sibling

        // Select the correct branch
        selectedLeft[i] <== leftCombination[i] * (1 - pathIndices[i]); 
        selectedRight[i] <== rightCombination[i] * pathIndices[i];

        // Update intermediate hash
        intermediateHashes[i + 1] <== selectedLeft[i] + selectedRight[i];
    }

    // Validate that the computed root matches the provided root

    signal difference;
    difference <== intermediateHashes[n] - root;
    isValid <== 1 - difference * difference; // isValid == 1 if difference == 0


}

component main = MerkleProof(3);

If you want to see a well detailed break down of how this circuit work, you check out that part of the pathway here

How it Works

  1. Registration Phase
  • Eligible voters are added to a Merkle tree as leaves. Each leaf contains:
    • A hash of the voter’s identity or unique identifier (e.g., hashed public key).
  • The root of the Merkle tree is publicly committed as the “voter list.”
  1. Voting Phase
  • Voters submit their votes along with a Merkle proof showing their inclusion in the registered voter list.
  • Votes are encrypted using the voter’s private key or another cryptographic mechanism to ensure secrecy.
  • The submitted proof consists of:
    • The voter’s position in the tree (key).
    • The sibling hashes required to recompute the Merkle root.
  1. Verification Phase
  • The voting system uses a Merkle tree inclusion verifier circuit to:
    • Verify that the provided proof correctly reconstructs the root of the registered voter tree.
    • Ensure that only eligible voters cast votes.
  • This prevents unauthorized voting or duplicate votes.
  1. Vote Tallying Phase
  • Once voting ends:
    • Votes are decrypted (if encrypted) and counted.
    • Since the inclusion proofs verify the authenticity of votes, the tally reflects valid votes only.

Smart Contract Implementation

The Celo smart contract will:

  1. Store the Merkle tree root of eligible voters.
  2. Verify zk-SNARK proofs submitted by voters.
  3. Record valid votes while ensuring privacy.

Verifier Contract

The Verifier contract is generated by snarkjs during the trusted setup process. Below is an example of what the Verifier contract might look like:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

library Pairing {
    struct G1Point {
        uint256 X;
        uint256 Y;
    }
    struct G2Point {
        uint256[2] X;
        uint256[2] Y;
    }

    // Add pairing-related functions (e.g., point addition, scalar multiplication, pairing check)
}

contract Verifier {
    using Pairing for *;

    struct Proof {
        Pairing.G1Point A;
        Pairing.G2Point B;
        Pairing.G1Point C;
    }

    function verifyProof(
        uint256[2] memory a,
        uint256[2][2] memory b,
        uint256[2] memory c,
        uint256[] memory input
    ) public view returns (bool) {
        // Perform pairing and proof verification logic
        // For demonstration purposes, this is simplified
        return true;
    }
}

1. Pairing Library

The Pairing library includes cryptographic operations necessary for proof verification:

  • G1Point and G2Point Structures: Represent elliptic curve points used in zk-SNARKs.
  • Pairing Checks: Validate that the mathematical relationships required for proof verification are satisfied.

2. Proof Structure

The Proof structure defines the zk-SNARK proof components:

  • A and C are points in G1 (elliptic curve group).
  • B is a point in G2 (a different elliptic curve group used in zk-SNARKs).

3. verifyProof Function

The verifyProof function checks the validity of a zk-SNARK proof:

  • Inputs:
    • a, b, c: Components of the zk-SNARK proof.
    • input: Public inputs used in the proof (e.g., Merkle root).
  • Logic:
    • Performs cryptographic operations to validate the proof using the pairing check.
    • Returns true if the proof is valid; otherwise, false.

Example of the verifier’s main function:

function verifyProof(
    uint256[2] memory a,
    uint256[2][2] memory b,
    uint256[2] memory c,
    uint256[] memory input
) public view returns (bool) {
    // Example: Perform pairing checks
    // Pairing checks ensure the proof is valid mathematically
    return pairingCheck(...);
}

The Verifier contract enables the Voting contract to validate proofs without revealing private data.

Voting Contract

The Voting contract uses the Verifier contract to validate zk-SNARK proofs and records valid votes. Here’s the complete implementation:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./Verifier.sol"; // Import Verifier contract

contract Voting is Verifier {
    bytes32 public merkleRoot; // Root of the Merkle tree for voter eligibility
    mapping(bytes32 => bool) public nullifiers; // Prevent double voting
    mapping(address => bool) public hasVoted; // Track if a voter has voted

    event VoteSubmitted(address indexed voter, bytes32 voteHash);

    constructor(bytes32 _merkleRoot) {
        merkleRoot = _merkleRoot;
    }

    function submitVote(
        uint256[2] memory a,
        uint256[2][2] memory b,
        uint256[2] memory c,
        uint256[] memory input, // Public signals
        bytes32 voteHash // Hash of the vote (encrypted or plain)
    ) external {
        // Verify the proof using the Verifier contract
        require(verifyProof(a, b, c, input), "Invalid proof");

        // Ensure the input's root matches the stored Merkle root
        require(bytes32(input[0]) == merkleRoot, "Invalid Merkle root");

        // Prevent double voting
        require(!nullifiers[voteHash], "Vote already submitted");
        nullifiers[voteHash] = true;

        // Record the vote
        emit VoteSubmitted(msg.sender, voteHash);
    }

    function updateMerkleRoot(bytes32 newRoot) external {
        merkleRoot = newRoot;
    }
}

The Voting contract manages the voting process, using the Verifier contract to validate zk-SNARK proofs. Let’s break it down:

1. State Variables

  • merkleRoot: The root of the Merkle tree representing eligible voters. It’s a public reference used to verify a voter’s eligibility.
  • nullifiers: A mapping to prevent double voting by ensuring each vote hash is used only once.
  • hasVoted: Tracks whether a voter (identified by their wallet address) has already submitted a vote.

2. Constructor

The constructor initializes the merkleRoot with the value corresponding to the eligible voters’ tree.

3. submitVote Function

This function processes a vote submission:

  • Inputs:
    • a, b, c: zk-SNARK proof components.
    • input: Public signals from the proof (e.g., Merkle root, vote hash).
    • voteHash: A hash of the voter’s encrypted vote.
  • Logic:
    1. Proof Validation:
    • Calls verifyProof in the Verifier contract to validate the zk-SNARK proof.
    1. Merkle Root Check:
    • Confirms that the input[0] matches the stored merkleRoot.
    1. Prevent Double Voting:
    • Ensures the voteHash hasn’t already been used.
    1. Record the Vote:
    • Emits an event to log the submitted vote.

Example:

function submitVote(
    uint256[2] memory a,
    uint256[2][2] memory b,
    uint256[2] memory c,
    uint256[] memory input,
    bytes32 voteHash
) external {
    // Verify the zk-SNARK proof
    require(verifyProof(a, b, c, input), "Invalid proof");

    // Check if the Merkle root matches
    require(bytes32(input[0]) == merkleRoot, "Invalid Merkle root");

    // Prevent double voting
    require(!nullifiers[voteHash], "Vote already submitted");
    nullifiers[voteHash] = true;

    // Record the vote
    emit VoteSubmitted(msg.sender, voteHash);
}

4. updateMerkleRoot Function

The owner of the contract can update the Merkle root to add new eligible voters or adjust the tree. Only authorized users can call this function (using onlyOwner).

Example:

function updateMerkleRoot(bytes32 newRoot) external onlyOwner {
    merkleRoot = newRoot;
}

How the Contracts Work Together

  1. Proof Generation:
  • Off-chain, a voter generates a zk-SNARK proof using their Merkle leaf and a sibling path.
  • The proof confirms their membership in the Merkle tree (eligible voters) without revealing their identity.
  1. Vote Submission:
  • The voter sends the proof and their vote hash to the Voting contract.
  1. Proof Verification:
  • The Voting contract uses the Verifier contract to check the proof.
  • If valid, the vote is recorded, ensuring privacy and integrity.
  1. Event Emission:
  • The contract emits events to log valid votes, enabling off-chain or on-chain tallying.

Real World Implementation

This contract tutorial aim to give you a basic knowledge/idea on how to start the implementation and of such a system, If you want to go deeper and understand how the backend and frontend of a zk system works together, you can check out these links below.

[ZK Learning Group 2] Circom workshop #3 - building an end-to-end zkSNARK app

privacy-scaling-explorations/zkp-app-boilerplate: Build your zkp app with typescript, hardhat, circom, and snarkjs!

Building a Zero Knowledge web app with Halo 2 and Wasm (part 1) | by Yu Jiang Tham | Medium

Building a Zero Knowledge web app with Halo 2 and Wasm (part 2) | by Yu Jiang Tham | Medium

Conclusion

NOTE: This article is just a technical illustration of how a decentralized voting system powered by zk proofs would work. Check the Resource section for further research and knowledge on zkproofs

We encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy

Resources

Circom docs
SnarkJS
0xparc Circom Workshop

About the author

I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.

linkedIn
Twitter