Partnered With:

Cicada: On-chain private voting through time-locked puzzles and zero-knowledge proofs.

Read this article in 18 Minutes

Cicada, a new open-source Solidity library, utilizes time-lock puzzles and zero-knowledge proofs to enable on-chain private voting.

Original Title: "Building Cicada: Private on-chain voting using time-lock puzzles"

Original Source: a16z

Original Author: Michael Zhu

Translation: Kxp, BlockBeats

All voting systems rely on honesty and transparency to be effective. On the surface, blockchain seems to be the ideal platform for building these systems. In fact, many decentralized organizations have already adopted permissionless voting to express collective will, usually in exercising important financial powers or adjusting key protocol parameters. However, there are some drawbacks to on-chain voting, 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 are easily manipulated, and may also lead to inconsistent voter incentives, potentially resulting in undemocratic outcomes.

For this purpose, we have launched Cicada: a new, open-source Solidity library that utilizes 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 in use on the Ethereum mainnet.

In this article, we conducted research on the current state of voting privacy and provided a high-level introduction to Cicada's working principles (formal proof will be provided later). We also encourage developers to visit the GitHub repository for more detailed information - Cicada can be flexibly adjusted and expanded 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 votes, ongoing vote tallies, and voter identity can all affect voters in different ways. The required privacy attributes also vary in different voting scenarios, and here are some attributes that are frequently mentioned in cryptographic and social science literature:

· Ballot Privacy: Secret ballot, 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. In a blockchain environment, we may need stronger mechanisms than secret ballots, please refer to the "Receiptlessness" section below. Ballot privacy can also reduce social expectation bias - people are less likely to vote based on how others perceive their choices.

· Ballot Privacy: Many voting systems hide ongoing vote tallies, or the number of votes received for each option, from voters during the voting period to avoid influencing voter turnout and motivation. We have seen this in the real world, for example, late-voting US senators are more likely to align with their party than early-voting senators. In token-weighted voting on the blockchain, whales can maintain their false sense of security by keeping their opponents ahead and then casting their own votes at the last minute to sway the outcome.

· Voter anonymity: In many real-world voting systems, your ballot is kept secret, but whether or not you voted can often be known by others. This can serve as a protection against voter fraud, as publishing records of who voted can allow people to check if someone voted in their name. However, on the blockchain, 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.

· Non-receiptability: Voters should not provide a "receipt" of their ballot to a third party to prove how they voted for someone, 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. These properties are particularly attractive in a decentralized environment, as 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 in an unlicensed setting without trusted hardware.

Cicada focuses on continuous voting and tallying privacy, but (as we will discuss later) it can be combined with zero-knowledge group membership proofs to achieve voter anonymity and ballot privacy.

Cicada: Using Homomorphic Timelock Puzzles to Achieve Voting Privacy

In order to achieve continuous privacy-preserving vote counting, Cicada has borrowed cryptographic primitives that have never been used on-chain (to our knowledge).

First of all, the time-lock puzzle (Rivest, Shamir, Wagner, 1996) is a cryptographic puzzle that can only reveal its secret after a predetermined period of time has passed - more specifically, the puzzle can only be decrypted by repeating certain non-parallelizable calculations. Time-lock puzzles are very useful for achieving continuous voting privacy in the context of voting: users can submit their votes as time-lock puzzles, which will keep their votes confidential during the voting process, but can be disclosed after the voting. Unlike most other private voting structures, this eliminates the need for a trusted third party (such as election officials counting paper or digital ballots), threshold encryption (several trusted parties must cooperate to decrypt a message), or any other trusted party to achieve vote privacy: anyone can solve the time-lock puzzle to ensure that the results are revealed after the vote.

Secondly, the homomorphic time-lock puzzle (Malavolta Thyagarajan, 2019) has an additional feature that allows for some calculations to be performed on encrypted values, even when the key is known, the puzzle is decrypted, or a backdoor is used. Specifically, 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 pointed out by the paper's author, the linear homomorphic time-lock puzzle is particularly suitable for private voting: votes can be encoded as puzzles and homomorphically combined to obtain the encoded final tally of puzzles. This means that only one calculation is needed to reveal the final tally result, instead of solving a unique puzzle for each vote.

全新体系：效率与权衡

translates to

New System: Efficiency and Trade-offs

There are several factors to consider for a voting scheme that can be practically applied on the blockchain. First, attackers may attempt to manipulate the voting results by submitting incorrectly encoded ballots. For example, we may expect each ballot's time-lock puzzle to encode a boolean value: "1" indicating support for the proposal being voted on, and "0" indicating opposition. A zealous supporter may try to increase their effective voting power by using an encoding like "100".

We can prevent this type of attack by requiring voters to submit a zero-knowledge proof in addition to their ballot. However, zero-knowledge proofs may require significant computational resources - to keep the cost of participation as low as possible for voters, the proof should be (1) efficiently computed on the client-side and (2) efficiently verified on the chain.

In order to make the proof as efficient as possible, we use a custom sigma protocol. This is a zero-knowledge proof designed for specific algebraic relationships, rather than a general proof system. This greatly speeds up proof time: generating a proof of ballot validity using Python on a ready-made laptop takes only 14 milliseconds.

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

One disadvantage of using ElGamal is that when decrypting the statistical results, it requires exhaustive search of discrete logarithms (note that this is done off-chain and verified efficiently on-chain). Therefore, it is only suitable for situations where the expected final statistical results are relatively small (e.g. less than 2^32, about 4.3 million votes). In the initial Paillier-based scheme, the decryption can be done efficiently regardless of the size of the statistical results.

Choosing an RSA modulus N also involves trade-offs. Our method uses a 1024-bit modulus to improve gas efficiency. Although this is far higher than the largest RSA modulus factored publicly (829 bits), it is lower than the 2048-bit size typically recommended for RSA encryption or signing. However, in our application, we do not require 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 the tally and votes become public, it is reasonable to use a relatively small modulus. (If factoring algorithms improve, this can also be easily updated in the future.)

匿名性和选民资格

translates to

Anonymity and Voter Qualifications

As mentioned above, Cicada provides continuous privacy for vote counting - time-lock puzzles can keep the results confidential during the voting period. However, each ballot is also a time-lock puzzle encrypted under the same public parameters. This means that, just like the statistical results can be decrypted (by performing the necessary calculations), each ballot can also be decrypted.

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

For some voting scenarios, this may not be ideal. Although we are satisfied with the temporary privacy of vote counting, we may want to have permanent ballot privacy. To achieve this, we can combine Cicada with anonymous voter eligibility protocols to achieve zero-knowledge group membership proof. In this way, even if the decrypted vote is revealed, it will only disclose how a person voted, which has already been disclosed in the statistical results.

In our repository, we provide an example contract that uses Semaphore for voter anonymity. Please note that the Cicada contract itself does not make any assumptions about the determination or enforcement of voter eligibility. Specifically, you can replace Semaphore with Semacaulk or ZK-SNARKs.

Vote Counting Organization

One of our primary goals in designing Cicada was to avoid reliance on vote counting agencies: many confidential votes require a semi-trusted counting agency (or a committee that collaborates through secure multi-party computation) that receives and aggregates votes. In the context of blockchain, this means that these schemes cannot be solely implemented through smart contracts, but require some human intervention and trust.

In most systems, statistical agencies are trustworthy in terms of integrity (they cannot manipulate vote counts), but they must also remain active - if they go offline, the final result will not be calculated and the voting result will be indefinitely stalled. In some systems, statistical agencies are also trusted in maintaining privacy. That is to say, they know how each voter voted, but will release the voting results without disclosing this information.

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

Conclusion

Cicada has explored many directions in the field of on-chain voting privacy, complementing the research being conducted by other teams. As mentioned above, Cicada works in conjunction with anonymous group member 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 here to reduce the gas burden on voters.

In addition, we also have the opportunity to adjust Cicada to support different voting schemes (such as weighted voting, square voting). Although more complex schemes may be too computationally expensive for the Ethereum mainnet, they may be feasible on Layer 2 networks. Therefore, we welcome any suggestions regarding the future development direction of Cicada.