Cicada: On-Chain Private Voting via Timelock Puzzles and ZK

All voting systems need to rely on integrity and transparency to be effective. On the surface, blockchain appears to be the ideal platform for building these systems. In fact, many decentralized organizations have already adopted permissionless voting to express collective will, often in the context of exercising significant financial power or adjusting key protocol parameters. However, on-chain voting has some drawbacks, and privacy concerns have not been fully explored for Web3 voting systems, which has negatively affected it. In most on-chain voting protocols in use today, the ballots and voting results are fully public. The lack of privacy protection means that voting results are susceptible to manipulation, while also leading to inconsistent incentives for voters, potentially leading to undemocratic outcomes.

To that end, we're launching Cicada: a new, open-source Solidity library that leverages timelock puzzles and zero-knowledge proofs for on-chain private voting. Compared with existing systems, Cicada has unique privacy properties, minimizes reliance on trust, and is also very efficient on the Ethereum mainnet.

In this paper, we survey the current state of voting privacy and provide a high-level introduction to how Cicada works (formal proofs will follow). We also encourage developers to head over to the GitHub repository for details - Cicada can be flexibly adjusted and extended for different voting schemes and features. We look forward to working with the community to explore these possibilities together.

Voting Privacy Overview

In any voting system (on-chain or otherwise), we need to consider many different levels of privacy. Disclosure of individual ballots, ongoing vote counts, and voter identity all affect voters in different ways. The desired privacy properties vary from vote to vote, but here are some that are often addressed in the cryptography and social science literature:

**·**Ballot Privacy: Secret voting, also known as "Australian ballot", is a way to protect the privacy of individual voters in real-world voting systems and reduce bribery and coercion (on the chain In the above environment, we may need a more powerful mechanism than secret voting, see "no receipt" below for details). Vote privacy can also reduce social desirability bias—people are less likely to vote based on what other people think of their choices.

**·**Privacy of Vote Counting: Many voting systems hide ongoing vote counts, i.e. the number of votes each option received, during voter voting to avoid impact on turnout and voter incentives. We've seen this happen in the real world: for example, U.S. senators who vote later are more likely to align with their party than senators who vote earlier. In the Token-weighted voting on the chain, giant whales can maintain their false sense of security by keeping their opponents ahead (some people may be too lazy to vote because they think these people will win anyway), and then vote for themselves at the last moment. votes to determine the outcome.

· Voter Anonymity: In many real-world voting systems, your vote is kept private, but whether you voted or not is often known to others. This could serve as a protection against voter fraud, since publishing records of who voted would allow people to check whether someone voted in their name. On-chain, however, we can use cryptographic primitives to prevent voter fraud while maintaining anonymity — for example, using a Semaphore, you can prove in a zero-knowledge way that you are an eligible voter and have not yet voted.

· No Receiptability: Voters should not provide a "receipt" of their ballot to a third party to prove how their vote was cast for someone, which could lead to a sale of the ballot. Coercion-resistance is another closely related property, preventing someone from being forced to vote in a certain way. These properties are especially attractive in a decentralized environment, where voting power can become liquid through a smart contract marketplace. Unfortunately, these properties are very difficult to achieve. Indeed, Juels et al. point out that these properties are impossible to achieve in a permissionless setting without trusted hardware.

Cicada is focused on continuous vote count privacy, however (as we will discuss later), it can be used in conjunction with zero-knowledge group membership proofs for voter anonymity and ballot privacy.

Cicada: Vote Counting Privacy Using Homomorphic Timelock Puzzles

To achieve continuous vote count privacy, Cicada borrows cryptographic primitives that have never been (to our knowledge) used on-chain.

First, the time-lock puzzle (Rivest, Shamir, Wagner, 1996) is a cryptographic puzzle whose secrets can only be revealed after a predetermined period of time has elapsed—more specifically, only by repeatedly executing a certain These non-parallelizable calculations are used to solve puzzles. Timelock puzzles are useful in the context of voting for ongoing vote count privacy: users can submit their votes as timelock puzzles, so that their votes will remain private during the voting process, but can be accessed after voting was disclosed. Unlike most other private voting structures, this enables ballot counting privacy to be achieved without relying on statistical agencies (such as election workers counting paper or digital ballots), threshold encryption (several trusted parties must cooperate to decrypt a message) or any other trusted party: anyone can solve the timelock puzzle to ensure the result is revealed after voting.

Second, the homomorphic timelock puzzle (Malavolta Thyagarajan, 2019) has the additional property that some computations can be performed on encrypted values with knowledge of the secret key, decryption of the puzzle, or use of a backdoor. In particular, the linear homomorphic timelock puzzle allows us to combine puzzles together to generate a new puzzle that contains the sum of the secret values of the original puzzles.

As the paper authors point out, linear homomorphic timelock puzzles are particularly suitable for private voting: votes can be encoded as puzzles, and they can be homomorphically combined to obtain puzzles encoding the final statistics. This means that only one calculation is required to reveal the final tally, rather than solving a unique puzzle for each vote.

New System: Efficiency and Tradeoffs

For a voting scheme that can be practically applied on-chain, there are several factors to consider. First, an attacker could attempt to manipulate voting results by submitting incorrectly encoded ballots. For example, we might expect each ballot's timelock puzzle to encode a boolean value: "1" for the voted resolution, and "0" for against. An ardent supporter might try to use a code like "100" to increase their effective voting power.

We can prevent this attack by requiring voters to submit a zero-knowledge proof in addition to submitting the ballot itself. However, zero-knowledge proofs can be computationally expensive - to keep the cost of voter participation as low as possible, proofs should be (1) efficiently computed on the client side and (2) efficiently verified on-chain.

To make the proof as efficient as possible, we use a custom sigma protocol. This is a zero-knowledge proof designed for specific algebraic relations, not a general proof system. This greatly speeds up proof times: on an off-the-shelf laptop, it takes only 14 milliseconds to generate a ballot validity proof in Python.

Although the verification process of this sigma protocol is conceptually simple, it actually requires several large modulo exponential operations. Malavolta and Thyagarajan's linear homomorphic scheme uses Paillier encryption, so these exponential operations will be performed modulo some RSA modulus N^2. For a reasonably large N, these exponentiation operations are prohibitive on most EVM chains (requiring millions of gas). To reduce this cost, Cicada uses the exponent ElGamal instead, which still provides additive homomorphism, but operates on a smaller modulus (N instead of N^2).

One downside of using ElGamal is that it requires exhaustive discrete logarithms to decrypt the statistics (note that this is done off-chain and efficiently verified on-chain). Therefore, it should only be used if the expected final count is relatively small (eg, less than 2^32, about 4.3 million votes). In the original Paillier-based scheme, it can be efficiently decrypted regardless of the size of the statistics.

Choosing the RSA modulus N also involves trade-offs. Our method uses a modulus of 1024 bits to improve gas efficiency. While this is well above the maximum RSA modulus for factorization (which is 829 bits), it is below the 2048-bit size generally recommended for RSA encryption or signing. In our application, however, we don't need long-term security: once the election is over, there is no risk if future N is factorized. After the timelock expires, it is reasonable to use a relatively small modulus, assuming that statistics and votes will become public. (This can also easily be updated in the future if the factorization algorithm improves.)

Anonymity and Voter Eligibility

As mentioned above, Cicada provides continuous vote tally privacy - a timelock puzzle keeps tallies secret during voting. However, each ballot is also a timelock puzzle, encrypted under the same public parameters. This means that just as the statistics can be decrypted (by performing the necessary calculations), so can each vote.

In other words, Cicada only guarantees the secrecy of ballots during voting. If a curious observer wants to decipher a particular voter's ballot, they can do so after polls close, too. The cost of decrypting any one ballot is the same as the cost of decrypting the final tally, so fully decrypting a ballot with n voters requires O(n) work. However, all these votes can be decrypted in parallel (assuming there are enough computers) in a process that takes the same amount of time as decrypting the final tally.

For some polls, this may not be ideal. While we are happy with temporary vote count privacy, we may wish to have permanent vote privacy. To achieve this, we can combine Cicada with an anonymous voter eligibility protocol via zero-knowledge proof of group membership. That way, even if the ballots are declassified, it will only reveal how someone voted, which is already revealed in the tally.

In our repository, we provide an example contract that uses Semaphore for voter anonymity. Note that the Cicada contract itself makes no assumptions about the determination or enforcement of voter eligibility. In particular, you can replace Semaphore with Semacaulk or ZK Proof of State.

Vote counting agency

One of our first goals when designing Cicada was to avoid reliance on vote counting agencies: many private votes require a semi-trusted counting agency (or committee cooperating via secure multi-party computation) that receives and aggregates votes. In the context of blockchain, this means that these schemes cannot be carried out through smart contracts alone, but require some human intervention and trust.

In most regimes, statistical agencies are trusted in terms of integrity (they cannot manipulate vote counts), but they must also remain active - if they are offline, final results cannot be calculated and voting results stalled indefinitely. In some systems, statistical agencies are also trusted to maintain privacy. That is, they know each voter's vote, but publish the results without revealing this information.

While statistical agencies are reasonable (and necessary) in many real-world scenarios, they are not ideal in the context of blockchains, where our goal is to minimize trust and ensure censorship resistance.

Conclusion

Cicada explores many directions in the field of on-chain voting privacy and complements ongoing research by other groups. As mentioned above, Cicada complements anonymous group membership technologies such as Semaphore, ZK proof-of-storage, and rate-limiting nullifiers. Cicada can also be combined with the optimistic proof checker proposed by the Nouns Vortex team to reduce the gas burden of voters.

Also, we have the opportunity to tune Cicada to support different voting schemes (e.g. weighted voting, quadratic voting), while more complex schemes may be computationally expensive for Ethereum mainnet, they may be feasible on Layer 2 networks of. With this in mind, we welcome any suggestions for the future direction of Cicada.