a16z: How Cicada uses timelock puzzles and zero-knowledge proofs to enable on-chain voting

Cicada has novel privacy properties, minimizes trust assumptions, and is efficient enough to be used on the Ethereum mainnet.

**Written by:**Michael Zhu

Compiled by: Lynn, MarsBit

All voting systems that function in any meaningful way rely on integrity and transparency. On the face of it, this makes the blockchain an ideal platform to build these systems on – indeed, many decentralized organizations have embraced permissionless voting as a means of expressing collective intent, often wielding vast wealth or tweaking key protocol parameters in the case of. But on-chain voting also has disadvantages. Privacy is still unexplored and undeveloped, which is not good for Web3 voting systems—in most of the on-chain voting protocols currently in use, ballots and voting results are completely public. Without privacy, voting results can be easily manipulated and voter incentives misaligned, potentially leading to undemocratic outcomes.

That's why we're releasing Cicada: a new, open-source Solidity library that leverages timelock puzzles and zero-knowledge proofs to enable private on-chain voting. Compared to existing systems, Cicada has novel privacy properties, minimizes trust assumptions, and is efficient enough to be used on the Ethereum mainnet.

In this post, we survey the state of voting privacy and provide a high-level description of how Cicada works (formal proofs are forthcoming). We also encourage developers to check out the GitHub repository - Cicada can be tweaked and extended in many ways to support different voting schemes and features, and we hope to work with the community to explore these possibilities.

Brief Survey of Private Polls

In any voting system (on-chain or otherwise), there are many different levels of privacy to consider. Disclosure of individual ballots, running counts, and voter identities all affect voter motivation in different ways. Which privacy properties are necessary depends on the context of the vote. A few that appear frequently in the cryptography and social science literature:

• Ballot Privacy: Secret ballots, also known as "Australian ballots", were developed for real-world voting systems as a way to preserve individual voter preferences and mitigate bribery and coercion (set on-chain, we may requires a stronger property than ballot privacy - see "receiptlessness" below). Vote privacy can also mitigate social desirability bias — someone has less pressure to vote based on what others think of their choices.
• Privacy of in-progress counts: Many voting systems hide in-progress counts, or how many votes have already been cast for each option, while voters are still voting, to avoid affecting turnout and voter incentives. We've seen this happen in the real world; for example, US senators who vote later are more likely to align with their party than senators who vote earlier. And on-chain: in token-weighted voting, whales can lull their opponents into a false sense of security by keeping them ahead (some may be too lazy to vote, assuming they'll win anyway), and then cast their own vote at the last minute Come and decide the result.
• Voter anonymity: In many real-world voting systems, your vote is not public, but the fact that you voted is often public. This is important to prevent voter fraud, because publishing voter records allows people to check whether others have voted in their name. On-chain, however, we can prevent voter fraud while preserving anonymity using cryptographic primitives—for example, with Semaphore, you can prove in zero knowledge that you are a valid voter who hasn't voted yet.
• No Receiptability: Individual voters provide a "receipt" of their ballot to prove how they voted to a third party, which could otherwise result in a ticket sale. A closely related but stronger property is coercion resistance, which prevents someone from coercing voters into voting in a certain way. These properties are particularly attractive in a decentralized environment, where voting rights can be made liquid through smart contract markets. Unfortunately, they're also difficult to implement—in fact, Juels et al. point out, it's impossible in a permissionless environment without trusted hardware.

Cicada focuses on in-progress vote count privacy, but (as we discuss later) it can be combined with zero-knowledge group membership proofs to achieve voter anonymity and ballot privacy.

Introducing Cicada: Vote Counting Privacy from the Homomorphic Timelock Problem

To achieve the privacy of ongoing vote counting, Cicada leverages cryptographic primitives that (to our knowledge) have never been used on-chain before.

First, the time-lock puzzle (Rivest, Shamir, Wagner, 1996) is an encrypted puzzle that encapsulates a secret that can only be revealed after some predetermined amount of time elapses—more specifically, the puzzle can be repeated by Do some non-parallel calculations to decrypt. Timelocked puzzles are useful in the context of voting to achieve privacy in running statistics: users can submit their votes as timelocked puzzles so that they are kept secret during the voting process but can be revealed after voting. Unlike most other private voting structures, this enables statistical privacy to operate 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 parties: Anyone can solve a timelock puzzle to ensure that the result is revealed after voting.

Second, an isomorphic timelock puzzle (Malavolta Thyagarajan, 2019) has the additional property that some computations on encrypted values are possible with knowledge of the secret key, decryption of the puzzle, or use of a backdoor. In particular, a linearly homomorphic timelock puzzle allows us to combine puzzles together to produce a new puzzle that encapsulates the sum of the secret values of the original puzzle.

As the paper's authors point out, linearly homomorphic timelock puzzles are a particularly well-suited primitive for private voting: votes can be encoded as puzzles, and they can be homomorphically combined to obtain an encoded final Counting Puzzles. This means that only one calculation is required to reveal the final result, rather than solving a unique puzzle for each vote.

A new structure: efficiency and tradeoffs

There are several issues to consider for a voting scheme to be practical on-chain. First, an attacker may try to manipulate votes by casting an incorrectly encoded ballot. For example, we might want the timelock puzzle for each ballot to be encoded as a boolean value: "1" for the proposal being voted on, and "0" for no. An ardent proposal supporter might try to code something like "100" to expand their effective voting power.

We can prevent this attack by having the voter submit a zero-knowledge proof of the validity of the vote along with the vote itself. However, zero-knowledge proofs are computationally expensive—to keep the cost of voter participation as low as possible, proofs should be (1) efficiently computable client-side and (2) efficiently verifiable on-chain.

To make the proofs as efficient as possible, we use a custom sigma protocol—zero-knowledge proofs designed for specific algebraic relations, rather than a general proof system. This makes the prover time extremely fast: generating a ballot validity proof in Python takes 14ms on an off-the-shelf laptop.

While the validator for the sigma protocol is conceptually simple, it requires a fairly large number of modular exponentiations. Malavolta and Thyagarajan's linear homomorphic scheme uses Paillier encryption, so these exponentiations will perform modulo N^2 for some RSA modulo N. For reasonable sizes of N, exponentiation is very expensive (millions of gas) on most EVM chains. To reduce costs, Cicada uses Exponential ElGamal - Exponential ElGamal still provides additive homomorphisms, but works on smaller moduli (N instead of N^2).

One downside of using ElGamal is that the final step of decrypting the count requires bruteforcing the discrete log (note that this is done off-chain and effectively verified on-chain). Therefore, it only works if the expected final number of votes is fairly small (say less than 2^32, or about 4.3 million votes). In the original Paillier-based scheme, counts can be efficiently decrypted regardless of their size.

Choosing the RSA modulus N also involves trade-offs. Our implementation uses a 1024-bit modulus for gas efficiency. While this is well above the largest RSA modulus ever publicly factored (829 bits), it is below the commonly 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 if N is considered in the future. It is reasonable to use a relatively small modulus, assuming that counts and votes are made public after the timelock expires. (This can also be easily updated in the future if the decomposition algorithm improves.)

Anonymity and Voter Eligibility

As mentioned above, Cicada provides run count privacy - a time-locked puzzle property that keeps vote counts private during voting. However, each individual ballot is also a timelock puzzle, encrypted under the same public parameters. This means that just as the count can be decrypted (by performing the necessary calculations), so can each vote. In other words, Cicada guarantees ballot privacy only during voting — if curious observers wish to decrypt a particular voter's ballot, they can do so. Decrypting any individual ballot is as expensive as decrypting the final count, so naively it takes O(n) work to fully decrypt a ballot with n voters. But all of these votes can be decrypted in parallel (assuming there are enough machines), taking the same amount of wall-clock time as it takes to decrypt the final tally.

For some votes, this may not be desirable. While we are happy with running vote counting privacy temporarily, we may want voting privacy indefinitely. To achieve this, we can combine Cicada with an anonymous voter eligibility protocol, instantiated with zero-knowledge proof of group membership. That way, even if the ballot is declassified, all it reveals is that someone voted that way — and we already know that from the count.

In our repository, we include an example contract that uses Semaphore for voter anonymization. Note, however, that the Cicada contract itself makes no assumptions about how voter eligibility is determined or enforced. In particular, you can replace Semaphore with e.g. Semacaulk or ZK Proof of State (as suggested here and here).

Statistical Authority

One of our first priorities in designing Cicada was to avoid the need for a statistical agency: many private voting structures require a semi-trusted statistical agency (or delegated committee, coordinated via secure multi-party computation) to receive and aggregate votes. In a blockchain context, this means that these schemes cannot be executed by smart contracts alone, requiring some human intervention and trust.

In most structures, the counting authorities are not trusted for integrity (they cannot manipulate the vote count), but are trusted for liveness - if they are offline, they cannot calculate the final result, delaying the vote indefinitely. In some structures, they are also trusted to maintain privacy—that is, they know how each individual votes, but are expected to publish the results of the vote without revealing this information.

While statistical authorities are a reasonable (and necessary) assumption in many real-world scenarios, they are not ideal in a blockchain environment, where our goal is to minimize trust and ensure censorship resistance.

Cicada explores one of many directions in the field of on-chain voting privacy and complements much of the research being done by other groups. As mentioned above, Cicada is closely related to anonymous group membership technologies such as semaphores, ZK proof-of-storage, and rate-limit invalidators. Cicada can also integrate the optimistic proof checker proposed by the Nouns Vortex team to reduce the gas burden of voters.

There is also an opportunity to adapt Cicada to support different voting schemes (e.g. token-weighted voting, quadratic voting) - more complex schemes may be too computationally expensive for Ethereum mainnet, but they may be practical at L2. With this in mind, we welcome your contributions, forks, and suggestions on where to take Cicada next.

*Acknowledgments: Cicada was co-developed with Joseph Bonneau. Thanks to Andrew Hall for background information on the historical background of voting privacy. Thanks also to Robert Hackett for his feedback on this article. Special thanks to Stephanie Zinn for editing. *