Zero-Knowledge Proofs for Voting

By Florian Kluge (@zktrivo) and Phil Kelly, with thanks to Dennison and Raf at Tally for many ideas sparked during collaboration conversations

Even if you don’t have a passion for voting, please read on. Spending 30 minutes studying the application of zero-knowledge proofs (ZKPs) to voting may be the best investment of time you can make right now in building your knowledge of ZKP technology and its application.

ZK voting:

Uses foundational architecture patterns. Surprisingly, the design and architecture are an intense workout, as you’ll see later. If you master the patterns set out below, you’ll have the foundations for many other zk use cases.
Shows how multi-chain services can be built. While there are other approaches to voting and zero knowledge proof-based off-chain smart contracts, amongst other drawbacks, they don’t fully serve a multi-chain world in a way that allows reuse of code, infrastructure and proofs, and composition. This approach does.
Is simple to grasp in use-case concept. The basic mechanics of a voting use case are simple and familiar to all of us.
Illustrates zk benefits beyond privacy. While privacy dominates many zk conversations, voting also showcases transaction cost savings and data flexibility.
Involves important augmentative technology and techniques. Homomorphic encryption, sequencing, and data availability services all play a role.
Surfaces questions about future industry structure. You can easily debate the future of Web3 in this voting example. For example, will voter eligibility be a function within the voting app or will it be fed from independent identity utilities that serve many Dapps? Will each element of the vote be created from scratch each time or will there be storage and reuse of proofs?

Why an off-chain approach has high value and is safe, efficient, and flexible

Our approach involves taking as much of the voting process as possible off chain (although you could also categorize this approach as using an app with an embedded rollup). To many Web3 natives, the idea of programs running off chain at first might sound like the opposite of everything blockchain stands for (even when Vitalik repeatedly declares that to be a very powerful element of the future of Web3 and Web2). However, when off-chain processes are wrapped in zk circuits, they become as trustworthy as on-chain activity, while escaping privacy, cost, and computational limitations that are imposed by a chain. In addition, off-chain processes can be designed to be uncensorable. Using off-chain zk circuits with a chain like Mina which is purpose-built for zk and designed to augment other L1s, is the perfect way to extend on-chain processes and escape the constraints that have limited blockchain’s progress to date.

In our approach, by referencing on-chain data (for example, NFT holdings) a voter can prove off chain that they are eligible to vote and how many votes they are allowed. A voter can be assigned votes, cast the votes, and have them counted, all off chain. Proofs of this off-chain activity are rolled up using recursion into a single small proof for verification (or a series of small proofs if interim results are desired) on Mina, for a very small transaction cost. That verification result can then be bridged back to Ethereum (or other chains in the future) for the execution of a vote result, for example, release of funds. Beyond the base scenario, the verifications could be bridged to multiple other chains and could also be stored and reused as inputs to later decisions.

Other approaches to voting have traditionally been on chain, either L1 or L2, and have been disadvantageous in scale, privacy and data constraint challenges. There have been attempts to introduce partial privacy by assigning votes as tokens that can be put through a mixer into a fresh wallet before voting takes place, but this approach is cumbersome.

However, our approach, while requiring (in the base scenario) a round trip from Ethereum to Mina and back, has the following very impactful benefits:

The ability to write and run the zk circuits off chain, using Typescript libraries, without any need for trusted set up, with recursion capabilities and WASM to allow efficient running in a browser
Mina’s gasless transaction model
The potential to re-use and compose the proofs, based on the permanent record of the verifications in Mina.

What are the challenges in on-chain voting that off-chain voting can help with?

Cost savings

Allowing voting to happen mostly off chain avoids transaction costs for the set up of the vote, and any transactions required for allocation and delegation, vote casting, and counting. Using ZKPs and recursion, the only on-chain cost is for verification of the proof of each major group of activities, and potentially the cost of bridging a result back to an execution contract.

Privacy

Off-chain voting can allow privacy for individual eligibility (what tokens do you hold and where does that give you the right to vote), actions (how are you or the holder of a given token voting), and vote progress (how have the first 10% of the population voted). Private voting, in turn, can deliver:

Basic privacy (by not revealing crypto holdings associated with a voting address)
Prevention of social pressure in voting
Avoidance of herd mentality in voting, apathy based on vote momentum, and gaming in vote casting
Avoidance of vote buying (because a potential buyer cannot see how a voter voted)

Data flexibility

Avoid constraints of a chain’s data formats (allowing an infinite number of formats a vote could have, for example, “rank these 20 options and allocate funds to each”)

Interoperability

As the Web3 world matures, voting is likely to be based on multi-chain presence of a DAO and with results that have the potential to be executed on multiple chains. ZKPs are an efficient way to represent state across chains.

How can this approach support multi-chain voting?

Very simply: SnarkyJS will be able to work with ECDSA and other cryptography schemes from most or all chains after custom gates are supported in its underlying proof system. Custom gates are on the near-term roadmap. Recursion can be used to compose proofs based on state from multiple chains and to deliver efficiency by drastically reducing the number of on-chain verifications. Mina can efficiently verify and persist verifications. In the future, data and arbitrary message bridges can represent this state back onto any chain.

Voting Process and High-level Design

We all know voting intuitively, but what are the process steps?

What are the privacy design points?

One of the nice things about the voting use case is that it illustrates that there are multiple ways to achieve privacy, as well as multiple privacy “settings”. For example, we can decide to:

Obscure a voter’s details supporting eligibility, such as token holdings
Obscure a voter’s identity in vote possession or in community discussions
Obscure the way a voter voted
Obscure all or part of the interim results (for example, show nothing, or show the percentage of votes cast but not how they were cast)
Obscure some of the final results (for example, the voting scores of candidates that were not selected in a vote)
Obscure all of the final results from some community members (unlikely, but there are some edge cases, for example, who was given a grant for a dev project)

There is, of course, no universal right answer on which option to deploy, and organizations will likely want a wide range of options depending on the circumstances. Configurability and flexibility in a ZK voting system are therefore important. The proposed architecture assumes full obscuring of voter details, vote possessions, and vote casting until a final result is revealed.

The off-chain voting process we propose is shown here in greater detail:

A vote begins with a central authority (for example, a delegation of DAO members) defining a vote and declaring it. This would happen in a Web2 application, and the vote would include things like defining the voting structure (for example, yes/no, ranked choice, choose 3, allocate 100 points between 4 choices, etc.), the basis for vote eligibility and the number of votes per voter (for example, based on the number of tokens, length of membership of DAO, social graph factors, etc.). The vote set-up would then be processed in a proof aggregator and a voting contract:

Proof aggregator — A recursive proof that allows off-chain proving and aggregation of votes
Voting contract — the on-chain contract that verifies the off-chain proof, specifies voting-related parameters, holds a stake of the tally sequencers, and manages the distributed key generation (DKG) procedure

The eligibility prover would allow the voter to show they possessed the credentials to vote (for example, token ownership). This could be done by allowing the voter to prove this without doxxing their holdings. They would connect the voting app (downloaded in their browser) to a wallet that they possessed and would sign to show ownership. The zkApp would then calculate vote eligibility and the number of votes, and create a proof of the supporting evidence. Since there are lots of possible sources of evidence of eligibility, with a range of cryptography schemes, SnarkyJS will have custom gates, programmable to efficiently consume schemes into its Plonk-based proof system.

Having been assigned votes, the voter can now cast them by making choices in the Web2 part of the voter app, which are then homomorphically encrypted and sent to the proof aggregator (still off chain) along with proof of eligibility.

The proof aggregator verifies the proof and ingests the vote into a tallying mechanism that adds the vote to the running total without decrypting it. When the vote closes, the grand total result is published and then decrypted by a threshold of key holders. This result is then proved.

In fact, this is proof that:

1. The summation of the underlying proofs is proven.

2. The verification of the underlying proofs is proven.

3. The decryption of homomorphic cryptography was properly done, and the proof sent to Mina chain for verification.

The verification is completed on Mina and stored in the next block update. The update is then reflected in the next run of the Mina Ethereum zkBridge, which then reflects the Mina state root update inside a smart contract on Ethereum. The same update could be replicated on multiple different chains to consume the result in a multi-chain fashion. Finally, the result can cause the execution of a smart contract app on Ethereum (or another chain), which is triggered to check for verification of proof in the Mina state root stored on Ethereum. Upon finding verification of proof, the executing smart contract executes and the process is complete.

Architecture Principles

Crafting an ideal voting system is an art and determining what constitutes the ideal solution is equally challenging as each use case has unique requirements. For instance, government elections must accommodate millions of voters, while company-wide voting necessitates different trust assumptions than a decentralized public DAO on a blockchain. Although the elements of a voting system hinge on the specific use case and the intended operating environment, we can examine various technical solutions and approaches and explore one in depth. Also note that, given the very different needs of voting systems, they must be configurable and extensible wherever possible, which is one of the reasons we built SnarkyJS to be accessible to non-cryptographers.

Goals for most systems, however, are likely to include a design that is:

Decentralized so that the design does not rely on a single actor to initiate an action and cannot be censored (see the Tally Sequencer in the diagram)
Private so the voter’s identity remains undisclosed
Fully anonymous so that individual votes cannot be traced back to any identity and stay hidden until the result is counted and the election period is over

Decentralization and Censorship Resistance

In the world of blockchains, one of the primary objectives is to maximize censorship resistance while reducing trust assumptions and the influence of centralized authorities. This goal is no different for a reliable voting system. Individual votes and election results shape the world we inhabit, so the decision-making system employed must be as secure and censorship-resistant as possible. While off-chain voting has advantages, relying solely on one or a few sequencers to tally a result still retains some risk. Fortunately, a system based on SnarkyJS code allows the voter to bypass any third-party (for example a blocked sequencer) and directly communicate with the settlement layer, Mina, to trustlessly cast their vote, thanks to the ability of SnarkyJS to generate proofs directly in a web browser. Instead of relying on a network of tallying sequencers, the users can generate the same recursive proofs, effectively becoming a tallying sequencer themselves. In addition, the Mina smart contract can be used to directly submit and verify a user’s vote and thereby eliminating any risk of censorship.

Another important element of decentralization (and privacy) is control of the decryption keys for the homomorphic encryption and is covered in the privacy section below.

Privacy (including Privacy with Homomorphic Encryption)

In this use case, privacy related to entitlement to vote is handled by allowing a voter to run a trusted proof of entitlement locally without revealing their data, and then include the proof along with their vote.

Privacy of the vote itself is more difficult because it could include complex data (for example, ranked choices, and write in responses) that need to be read and collated in the tally, but then concealed until the voting period ends. Fortunately, this level of privacy is possible with homomorphic encryption! This section provides a brief overview of what homomorphic encryption means. If you would like to see a longer post on homomorphic encryption, please comment on and like this post, and we’ll add it to our plan.

Encryption is a straightforward concept — it involves concealing the content of a message from a third party. Let’s say you want to share jokes with your friend during class, but you don’t want the teacher to see them. To protect your jokes, you encrypt them and give the encrypted message to your friend. Your friend can then decrypt the message and enjoy the joke. Homomorphic encryption, on the other hand, is slightly more complex. It describes a property that enables us to execute operations on encrypted data (cipher text) while preserving the underlying data structure. Essentially, you can encrypt data, perform operations (like addition or multiplication) on the encrypted data, and obtain a result that mirrors the plain text space after you decrypt it.

Although homomorphic encryption may seem intimidating, it’s quite simple to understand. The term “homomorphic” comes from the ancient Greeks and means “same form.” This property allows for structure-preserving mapping between two groups. The good news is that SnarkyJS enables you to implement various cryptography schemes, including homomorphic encryption libraries. As the SnarkyJS ecosystem continues to expand, you will have access to even more of these libraries and more tools to leverage zero knowledge for a private and anonymous future. By using homomorphic encryption with SnarkyJS, you can prove the encryption, decryption, and counting of all votes without revealing any information. Isn’t that amazing?

It’s worth noting that there are different types of homomorphic encryption, but this example voting system requires only partial homomorphic encryption. This means that you can execute only one specific operation, such as addition or multiplication. However, this is more than enough for the voting example.

To begin, we’ll break down the language and explain the practical benefits of this voting system. It allows voters to cast their votes while keeping their choices hidden from any third party. This privacy is achieved using encryption technology that ensures that the contents of the votes are preserved until the final result is calculated and the voting period ends.

To ensure that only authorized individuals can access the contents of the votes, we use two keys: a private key for decryption and a public key for encrypting the votes. This prevents anyone from freely accessing the content of the votes, but we also need to ensure that no single entity holds the private key and can abuse its power.

To accomplish these objectives, you can use distributed key generation (DKG). This technology allows multiple parties to contribute to the creation of a secret key while ensuring that no single entity knows the entire key. After all votes are cast, verified, and aggregated on the blockchain, a threshold number of the initial parties that generated the private key comes together to compute the secret key needed to decrypt the final result (likely with staked funds to incent good behavior). This approach ensures that the decryption key remains private until the voting period ends, without the need for a central authority.

In summary, this voting system uses homomorphic encryption and DKG to preserve the privacy of the votes, prevent abuse of power, and ensure a censorship-resistant and decentralized voting process.

Efficiency

There are two key aspects to efficiency:

Recursion of votes in individual elections (in the Tally Sequencer)
Reuse of voting artifacts, including outcomes either on individual chains or by broadcasting vote results across multiple chains using Mina as a place for persistence and to serve multiple chains.

Recursion

Recursion is one of the bases of scalability, efficiency, extensibility, configurability, and ease of use from a developer’s perspective.

Our solution ensures that the user experience is seamless by leveraging recursion and off-chain computation. Instead of users having to pay transaction fees or gas for verifying each proof, aggregation of votes happens off chain. With recursion, you essentially roll up proofs, and verify just the final recursive proof on chain, instead of verifying thousands of underlying proofs / votes. This verification method significantly reduces transaction fees while maintaining a high quality of user experience. Pasta curves, used within SnarkyJS’ proving system, are uniquely advantaged for efficient recursion, and allow you to build unlimited levels of recursion into an application. With the use of WASM, users can easily generate a proof of their vote within their browser without needing to run additional software.

Mina’s Role as a Settlement and Persistence Layer

Mina was designed (amongst other things) to be an excellent venue for fast, low cost verification of proofs and persistence of the verifications, in particular the recursive proofs emitted from SnarkyJS, based on Pasta curve pairs. As such, it can be a natural general settlement layer not only for voting systems but other zk applications. And since part of the Mina ecosystem’s focus is on bridging of the Mina state to other chains, we anticipate a future where Mina serves as a cross chain settlement layer for all kinds of zk applications, facilitated by zk bridges. That could allow projects to write a zkApp once, and use it across chains. It could also allow for composability and reuse of proofs, also across chains, EVM and non-EVM.

Evaluation

We used four main dimensions for evaluating a solution:

Cost to build
Cost to operate, in particular transaction costs
Latency and user experience
Solution longevity

Cost to Build

Overall, we score our solution as Very Good on this dimension, at least for a basic build. Much of the purpose-built functionality here is a straightforward Web2 code build that could likely be built to POC level in under 20 hours. Using SnarkyJS, a non-cryptographer can also rapidly build the ZKP elements, including recursion (again, to POC level rapidly). The homomorphic encryption is based on an existing open-source library and should take less than 5 hours to implement. Verification on Mina, storage, and bridging of state back to Ethereum all come out of the box (the smart contract layer of Mina and the Mina-Ethereum bridge are currently in late-stage testing).

Note that there are second-order features, such as extensively decentralized sequencing for parts of the off-chain architecture (for example, setting up a vote, tallying), and the potential to have permanent off-chain storage of vote elements, that could considerably add to the cost and time to build.

Cost to Operate

We score our solution as Very Good. Depending on your definition of cost, all ZKPs are somewhat computationally expensive, but this is accounted for in user experience. Meanwhile, after recursion in SnarkyJS, the transaction / proof verification cost for the entire vote on Mina would be pennies in current conditions and finally there is a bridging cost if execution on another chain is intended.

User Experience

We score UX as Good. Proving eligibility and casting the vote can be done from a web browser, thanks to SnarkyJS. Proof generation currently could take of the order of tens of seconds, but for a long-running vote this latency is perfectly acceptable and can be a background process. Proving speed throughout the industry is improving in leaps and bounds as we all turn our attention from features to performance, not least with the aid of hardware acceleration.

Solution longevity

We score solution longevity as Excellent. While there may be simpler ways to administer votes using zk and blockchain, taking this approach is an investment in a professional grade multi-chain solution for the future.

Transaction costs are permanently suppressed.
In the future, Mina can bridge results to multiple chains.
As part of the Mina roadmap, proof verifications will persist on Mina and therefore allow proofs to be reused and composed.

Final words

We have built an open-source solution as a limited POC, which we will make available in the O(1) GitHub repo after further review. We are happy to receive feedback and welcome your comments.

You can access SnarkyJS in the O(1) Labs open-source repository. While you’re there, please give the repository a star to help others discover the project!
You can learn about SnarkyJS in the zkApps section of the Mina docs.
Join zkApp developers and SnarkyJS conversations on Mina Protocol Discord.
We hope you enjoy using SnarkyJS to build zkApps, smart contracts powered by zero-knowledge proofs.