Explaining the Cicada Principle by a16z: How to Achieve Privacy-Enabled Voting on a Blockchain through Time-Locked Puzzles and ZK Proofs?

How to Achieve Private Voting on a Blockchain with Cicada Principle, Time-Locked Puzzles, and ZK Proofs: Explained by a16z

Original Author: Michael Zhu, a16z crypto Research Engineer Source: a16zcrypto Translation: DeFi之道

In general, all voting systems rely on good integrity and transparency in order to function in any meaningful way. From this perspective, blockchain has become an ideal implementation path for building such a system, and in fact, many decentralized organizations have already expressed collective intent by adopting permissionless voting, often achieved by mobilizing large amounts of funds or adjusting key protocol parameters. However, on-chain voting also has drawbacks, namely insufficient privacy, which is particularly detrimental to web3 voting systems. In most of the current on-chain voting protocols, the ballots and the counting are completely public, without privacy, which makes the voting results vulnerable to manipulation and voter incentive distortion, and may ultimately lead to undemocratic outcomes.

This is why we released Cicada: a new open-source Solidity library that leverages time-locked puzzles and ZK zero-knowledge proofs for on-chain voting. Compared to existing systems, Cicada has novel privacy properties, minimizes trust assumptions, and is sufficiently efficient to be used on the Ethereum mainnet.

In this article, we investigate the overview of voting privacy and explain how Cicada works (with formal proofs provided). We also encourage developers to check out the GitHub repository – Cicada can be adjusted and extended in multiple ways to support different voting schemes and features, and we look forward to exploring these possibilities with the community.

Overview of Privacy Voting Background

In any voting system, many different layers of privacy need to be considered. The disclosure of individual ballot data, the continuity of counting, and the identity of voters all affect voter incentives in different ways, and which privacy attributes are necessary depends on the specific rules of the vote. Here are some of the things that often appear in cryptography and related scientific literature:

• Details on Base’s Current Progress: Genesis Window to Open, A...
• What does a decentralized database mean for Web3?
• Analysis of the Health Status of the Gaming Industry

Ballot Privacy : Anonymous voting, also known as “Australian ballot,” is a voting method developed for physical real-world voting systems, with the goal of protecting individual voter preferences and reducing bribery and coercion (in on-chain settings, we may need stronger attributes than ballot privacy – see “No Receipt” below). Voting privacy also alleviates social expectation bias – that is, the pressure to vote based on what others think of your choice is reduced.

Privacy of Vote Counting Results: Many voting systems hide vote counting results while voters are still voting so that the number of votes cast for each option is unknown to prevent affecting voter turnout and motivation. We can see many similar situations in the real world, such as U.S. senators who start voting later compared to those who vote earlier are more likely to ally with their party. On-chain: In token-weighted voting, whales can keep their opponents ahead, creating a false sense of security (some people may be too lazy to vote, thinking they will win no matter what), and then vote at the last minute to change the result.

Anonymous Voting: In many real-world voting systems, individual votes are private, but the fact that you voted is usually public, which is important for preventing voter fraud because publishing records of who voted can allow people to check if anyone else voted on their behalf. However, on-chain, we can use encryption primitives to maintain anonymity while preventing voter fraud—for example, using Semaphore, you can prove that you are a qualified voter who has not yet voted without zero-knowledge.

Receiptless Voting: Individual voters provide their own “receipts” for their ballots to prove to third parties how they voted, or else it may lead to vote selling. A closely related property is coercion-resistance, which can prevent someone from forcing a voter to vote in a certain way. These properties are particularly attractive in a decentralized environment, where voting rights can flow through smart contract markets. Unfortunately, it is also difficult to achieve. In fact, Juels et al. claim that it is impossible without trusted hardware in an untrusted environment. Cicada focuses on running vote counting privacy, which can be combined with zero-knowledge proof to achieve voter anonymity and ballot privacy, among other features.

Cicada Overview: Computing Privacy from Homomorphic Timelock Puzzles

To achieve vote counting results, Cicada draws on encryption primitives that have never been used on-chain (to our knowledge) before.

First, timelock puzzles (Rivest, Shamir, Wagner, 1996) are an encryption puzzle that encapsulates a secret that can only be revealed after a predetermined period of time—more specifically, the puzzle can be decrypted by repeating some operations that cannot be computed in parallel. Timelocked puzzles are very useful in the context of voting and can achieve vote counting result privacy: users can submit their ballots as timelocked puzzles, making them completely private during the voting period, but public after the vote. This can be done without relying on vote-counting institutions (such as election workers counting paper or digital ballots), threshold encryption (where multiple trusted parties must cooperate to decrypt a message), or any other trusted party, unlike most other private voting structures. Privacy-preserving vote counting can solve the timelock puzzle to ensure that the results are published after the vote.

Secondly, homomorphic timelock puzzles (Malavolta Thyagarajan, 2019) have an additional property: the ability to perform some computation on the encrypted value given knowledge of the key, the ability to decrypt the puzzle, or a backdoor. Specifically, linear homomorphic timelock puzzles allow us to combine puzzles, producing a new puzzle that encapsulates the secret values of the original puzzles.

As the authors of the paper note, linear homomorphic timelock puzzles are particularly well-suited to private voting primitives: ballots can be encoded as puzzles, and they can be homomorphically combined to obtain a puzzle encoding of the final vote count. This means that only a single computation is required to reveal the final vote count, rather than solving a unique puzzle for each ballot.

New Structure: Efficiency and Tradeoffs

For a voting scheme to be practical to implement on-chain, additional factors must also be considered. First, an attacker may attempt to manipulate the vote by casting ballots that encode incorrect choices. For example, we may want each ballot’s timelock puzzle to encode a boolean value: “1” for support of a proposal and “0” for opposition. Ardent supporters of the proposal may attempt to amplify their effective voting power by encoding, say, “100”.

We can prevent this attack by having voters submit a zero-knowledge proof of the validity of their ballot alongside the ballot itself. While zero-knowledge proofs may be computationally expensive—in order to minimize the cost of voter participation, the proof should be (1) efficiently computable by clients and (2) efficiently verifiable on-chain.

To make the proof as efficient as possible, we use a custom sigma protocol—a zero-knowledge proof designed for specific algebraic relations—rather than a general-purpose proof system. This achieves extremely fast proof times: generating a ballot validity proof using Python on a off-the-shelf laptop takes only 14ms. While the validator for this sigma protocol is conceptually simple, it requires some large modular exponentiations. Malavolta and Thyagarajan’s linear homomorphic scheme uses Blockingillier encryption, so these exponentiations would be modulo N^2 for some RSA modulus N, making them prohibitively expensive on most EVM chains (millions of gas). To reduce this cost, Cicada switches to exponential ElGamal, which still provides additive homomorphism, but with a much smaller working modulus (N instead of N^2).

One disadvantage of using ElGamal is that the final step of decrypting the tally requires brute-forcing the discrete logarithm (note that this is done off-chain and validated on-chain). Therefore, it is only suitable for cases where the expected final tally is quite small (e.g. less than 2^32, or approximately 4.3 million votes). In the original scheme based on Blockingillier, counting can be efficiently decrypted regardless of its size.

Choosing RSA modulo N also involves trade-offs. Our implementation uses a 1024-bit modulus for gas efficiency. While this is far larger than the largest RSA modulus ever used (829 bits), it is lower than the typically recommended size of 2048 bits for RSA encryption or signing. However, our application does not require long-term security: once the election is over, there is no risk in considering N. Assuming that both tallying and voting are made public after the timelock period, it is reasonable to use a relatively small modulus.

Anonymity and Voter Eligibility

As mentioned above, Cicada provides privacy for running the tally—the timelock puzzle property preserves the confidentiality of the tally during the voting period. However, each individual vote is also a timelock puzzle encrypted under the same public parameters. This means that just as the tally can be decrypted (by performing the necessary computation), so can each individual vote—i.e., Cicada only guarantees vote privacy during the voting period—if curious observers wish to decrypt a particular voter’s vote, they can do so. Decrypting any individual vote is as expensive as decrypting the final tally, so it takes O(n) work to fully decrypt a ballot with n voters. However, all of these ballots can be decrypted in parallel (assuming enough machines), so the time required is the same as for decrypting the final tally.

For some votes, this may be unacceptable. While we are satisfied with the temporary running tally privacy, there may be times when we want indefinite voting privacy. To achieve this, we can combine Cicada with an anonymous voter eligibility protocol, instantiated via zero-knowledge group membership proofs. This way, even if votes are decrypted, they only reveal that someone voted in this way, without knowing who exactly.

Tallying Authorities

One of our primary goals in designing Cicada was to avoid the need for a tallying authority: many private voting schemes require a semi-trusted tallying authority (or quorum, or coordination via secure multi-party computation) to receive and aggregate ballots, and if forced into a blockchain environment, this means that these schemes cannot be fully executed by smart contracts, requiring some human intervention and centralized trust.

In most structures, the integrity of the tallying organization is not trusted, but their activeness is trusted – if they go offline, the final result cannot be calculated, leading to an indefinite delay in the voting results. In some structures, they also have a certain degree of privacy, meaning that they know how everyone voted, but it is expected that the voting results will be published without revealing this information.

In real-world scenarios, the tallying organization is a reasonable and necessary organization, but it is not necessary in the blockchain environment. Our goal is to minimize trust and ensure a certain degree of review resistance.

Cicada only explores one of the many directions in the field of on-chain voting privacy and supplements related research being conducted by other teams. As mentioned above, Cicada is closely related to anonymous technologies such as Semaphore, ZK storage proofs, and RLN (Rate-Limiting Nullifier), and Cicada can also integrate the optimistic proof checker proposed by the Nouns Vortex team to reduce the gas burden on voters.

In addition, Cicada can be adjusted to support different voting schemes (such as token-weighted voting, secondary voting), more complex schemes may be too costly to calculate for the Ethereum mainnet, but they are practical on L2. Considering this, we welcome your contributions, forks, and suggestions, and we look forward to discussing where to take Cicada next.