a16z: A detailed explanation of the working principle of Cicada, a ZK-based on-chain voting project

a16z's explanation of Cicada, an on-chain voting project based on zero-knowledge proofs.

Original Article: “Building Cicada: Private on-chain voting using time-lock puzzles” by Michael Zhu, a16z

Translation: Kxp, BlockBeats

All voting systems require honesty and transparency to be effective. On the surface, blockchain seems like the ideal platform for building these systems. In fact, many decentralized organizations have already adopted permissionless voting to express collective will, often in exercising important financial powers or adjusting critical protocol parameters. However, on-chain voting has some drawbacks, and for Web3 voting systems, privacy issues have not been fully explored, which has negative implications. In most on-chain voting protocols used today, ballots and voting results are completely public. The lack of privacy protection means that voting results can be easily manipulated, and may also lead to inconsistent voter incentives, potentially resulting in undemocratic outcomes.

To address this, we introduce Cicada: a new, open-source Solidity library that leverages time-lock puzzles and zero-knowledge proofs to achieve on-chain private voting. Compared to existing systems, Cicada has unique privacy properties, minimizes reliance on trust, and is highly efficient for use on the Ethereum mainnet.

• Ethereum Ecosystem Weekly Report: Cancun EIP list confirmed, EIP-4844 Devnet 6 to launch next week, Optimism completes mainnet Bedrock upgrade…
• Quick Overview of Five GameFi Projects Worth Paying Attention to in ETHGlobal Hackathon
• Long push: 9 promising projects that have received VC investment recommendations

In this article, we survey the current state of voting privacy and provide a high-level overview of how Cicada works (formal proofs will be provided in subsequent articles). We also encourage developers to visit the GitHub repository for more information – Cicada can be flexibly adjusted and extended according to different voting schemes and features. We look forward to working with the community to explore these possibilities.

Overview of Voting Privacy

In any voting system (on-chain or otherwise), we need to consider many different levels of privacy. The disclosure of individual ballots, ongoing vote tallies, and voter identities all affect voters in different ways. The required privacy properties also vary depending on the voting context, and here are some properties that are frequently mentioned in cryptographic 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 to reduce bribery and coercion (in the on-chain environment, we may need more powerful mechanisms than secret voting, see “non-receipt” below for details). Ballot privacy can also reduce social expectation bias – people are less likely to vote based on other people’s views of their choices.

· Vote privacy: Many voting systems hide ongoing vote tallies during the voting period, i.e. the number of votes received by each option, to avoid influencing voting rates and voter incentives. We have seen this in the real world: for example, US senators who voted later are more likely to be aligned with their party than those who voted earlier. In token-weighted voting on-chain, whales can maintain their false sense of security by keeping their opponents ahead (some people may be too lazy to vote because they think those people will win anyway), and then cast their own votes at the last minute to sway the results.

· Voter anonymity: In many real-world voting systems, your ballot is kept secret, but whether or not you voted can usually be known by others. This can serve as a protection against voter fraud, because publishing a record of who voted can allow people to check if someone voted in their name. However, on-chain, we can use cryptographic primitives to prevent voter fraud while maintaining anonymity – for example, using Semaphore, you can prove in a zero-knowledge way that you are a qualified voter and have not yet voted.

· No receipt: Voters should not provide a “receipt” of their ballot to a third party to prove how their vote was cast, as this may lead to vote selling. Coercion-resistance is another closely related property that prevents someone from being forced to vote in a certain way. In a decentralized environment, these properties are especially attractive because voting rights can become fluid through smart contract markets. Unfortunately, these properties are very difficult to achieve. In fact, Juels et al. pointed out that these features are impossible to achieve without trusted hardware in an unlicensed setting.

Cicada focuses on continuous vote tally privacy, but (as we will discuss later), it can be combined with zero-knowledge group member proof to achieve voter anonymity and vote privacy.

Cicada: Achieving tally privacy using homomorphic time-lock puzzles

To achieve continuous vote tally privacy, Cicada draws on a cryptographic primitive that has never been used on-chain (to our knowledge).

First, time-lock puzzles (Rivest, Shamir, Wagner, 1996) are cryptographic puzzles that can only be revealed after a predetermined time period has passed – more specifically, by repeating certain non-parallelizable computations. Time-lock puzzles are useful in the context of voting for achieving continuous vote tally privacy: users can submit their ballots as time-lock puzzles, which will keep their ballots secret during the voting process but can be revealed after the vote. Unlike most other private voting constructions, this eliminates the need for reliance on a tallying authority (such as election officials computing paper or digital ballots), threshold encryption (several trusted parties must cooperate to decrypt a message), or any other trusted party: anyone can solve the time-lock puzzle to ensure the result is revealed after the vote.

Secondly, homomorphic time-lock puzzles (Malavolta & Thyagarajan, 2019) have an additional property that allows for some computation of the encrypted values in the presence of knowledge of the key, the puzzle solution, or the use of a backdoor. In particular, linear homomorphic time-lock puzzles enable 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 time-lock puzzles are particularly well-suited for private voting: ballots can be encoded as puzzles and they can be homomorphically combined to obtain a puzzle that encodes the final tally. This means that only one computation is needed to reveal the final tally rather than solving a unique puzzle for each ballot.

A New System: Efficiency and Trade-offs

For a voting scheme to be practical on-chain, there are several other factors to consider. First, attackers may attempt to manipulate the voting results by submitting ballots with incorrectly encoded votes. For example, we might expect each ballot’s time-lock puzzle to encode a boolean value: “1” indicating support for the proposed measure, “0” indicating opposition. A zealous supporter might try to increase their effective voting weight by using an encoding like “100”.

We can prevent this attack by requiring voters to submit a zero-knowledge proof in addition to their ballot itself. However, zero-knowledge proofs can require significant computational resources – to keep the cost of participation as low as possible, the proof 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 a specific algebraic relation, rather than a general-purpose proof system. This greatly speeds up proof time: generating a vote validity proof using Python on a off-the-shelf laptop takes only 14 milliseconds.

While the verification process for this sigma protocol is conceptually simple, it actually requires several large modular exponentiations. Malavolta and Thyagarajan’s linear homomorphic scheme uses Blockingillier encryption, so these exponentiations are performed modulo an RSA modulus N^2. For a fairly large N, these exponentiations are infeasible on most EVM chains (requiring millions of gas). To reduce this cost, Cicada instead uses exponential ElGamal, which still provides additive homomorphism, but operates modulo a smaller modulus (N instead of N^2).

One disadvantage of using ElGamal is that, when decrypting the statistical result, it requires the exhaustive search of discrete logarithms (note that this is done off-chain and efficiently verified on-chain). Therefore, it is only suitable for cases where the expected final statistical result is relatively small (e.g., less than 2^32, around 4.3 million votes). In the original Blockingillier-based scheme, it is possible to decrypt efficiently regardless of the size of the statistical result.

The choice of RSA modulus N also involves trade-offs. Our method uses a 1024-bit modulus to improve gas efficiency. Although this is far larger than the largest RSA modulus factored publicly (829 bits), it is smaller than the typically recommended size of 2048 bits for RSA encryption or signing. However, in our application, we do not need long-term security: once the election is over, there is no risk if N is factored in the future. After the time lock expires, assuming that the statistical result and ballots will become public, it is reasonable to use a relatively small modulus. (This can also be easily updated in the future if factoring algorithms improve.)

Anonymity and Voter Eligibility

As mentioned above, Cicada provides ongoing privacy for vote tallies—the time lock puzzle can keep the statistical result confidential during the voting period. However, each ballot is also a time lock puzzle, encrypted under the same public parameters. This means that, just as the statistical result can be decrypted (by performing the necessary computation), each ballot can also be decrypted.

In other words, Cicada only guarantees ballot confidentiality during the voting period. If a curious observer wants to decrypt a specific voter’s ballot, they can also do so after voting ends. The cost of decrypting any one ballot is the same as the cost of decrypting the final statistical result, so fully decrypting a vote containing n voters requires O(n) work. However, all of these ballots can be decrypted in parallel (assuming sufficient computers), and the time required for this process is the same as that required to decrypt the final statistical result.

For some elections, this may not be ideal. Although we are satisfied with temporary tally privacy, we may want permanent ballot privacy. To achieve this, we can combine Cicada with an anonymous voter eligibility protocol, using zero-knowledge group membership proofs. This way, even if a ballot is decrypted, it only reveals how someone voted, which has already been disclosed in the statistical result.

In our repository, we provide an example contract using 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 a ZK state proof.

Vote Counting Agencies

When designing Cicada, one of our primary goals was to avoid reliance on vote counting agencies: many private voting schemes require a semi-trusted counting agency (or committee collaborating via secure multi-party computation) that receives and tallies votes. In a blockchain environment, this means that these schemes cannot be solely conducted via smart contracts and require some human intervention and trust.

In most systems, the counting agencies are trusted in terms of honesty (they cannot manipulate the vote count), but they must also maintain liveness—if they go offline, the final result cannot be computed and the voting outcome will be indefinitely stalled. In certain systems, the counting agencies are also trusted in terms of preserving privacy. That is, they know how each voter voted but will publish the voting results without revealing this information.

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

Conclusion

Cicada explores numerous directions in the area of on-chain voting privacy and complements research being conducted by other teams. As mentioned above, Cicada works in conjunction with anonymous group membership technologies such as Semaphore, ZK storage proofs, and rate-limiting nullifiers. Cicada can also be combined with the optimistic proof checker proposed by the Nouns Vortex team to alleviate voters’ gas burden.

Additionally, we have the opportunity to tailor Cicada to support different voting schemes (such as weighted voting, quadratic voting), although more complex schemes may be too computationally expensive for the Ethereum mainnet but may be feasible on Layer 2 networks. With this in mind, we welcome any suggestions regarding the future direction of Cicada.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!