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

Author: Michael Zhu, a16z

Compiled by: Lynn, MarsBit

All voting systems that operate in any meaningful way rely on integrity and transparency. On the surface, this makes blockchains an ideal platform for building these systems—indeed, many decentralized organizations have adopted permissionless voting to express collective intent, often in the context of wielding significant wealth or adjusting key protocol parameters. However, on-chain voting also has drawbacks; privacy has yet to be explored and developed, which is detrimental to Web3 voting systems—most on-chain voting protocols currently in use have completely public ballots and voting results. Without privacy, voting outcomes can be easily manipulated, and voter incentives misaligned, potentially leading to undemocratic results.

This is why we are releasing Cicada: a new, open-source Solidity library that utilizes time-lock 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 article, we investigate 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 adjusted and extended in many ways to support different voting schemes and functionalities, and we hope to collaborate with the community to explore these possibilities.

A Brief Survey of Private Voting

In any voting system (on-chain or otherwise), there are many different layers of privacy to consider. The disclosure of individual ballots, the ongoing tallying of votes, and voter identities all affect voter incentives in different ways. Which privacy properties are necessary depends on the context of the voting. Several frequently encountered in the cryptographic and social science literature include:

• Ballot privacy: Secret ballots, also known as "Australian ballots," were developed for real-world voting systems as a way to maintain individual voter preferences and mitigate bribery and coercion (in an on-chain setting, we may need a stronger property than ballot privacy—see "receipt-freeness" below). Ballot privacy can also mitigate social expectation bias—there is less pressure on someone to vote based on how others perceive their choice.
• Privacy of ongoing tallying: Many voting systems hide the ongoing tally while voters are still casting their votes, or how many votes have been cast for each option, to avoid influencing turnout and voter incentives. We have seen this in the real world; for example, U.S. senators who vote later are more likely to align with their party than those who vote earlier. And on-chain: in token-weighted voting, whales can deceive their opponents into a false sense of security by allowing them to maintain a lead (some may be lazy to vote, assuming they will win anyway), then cast their own votes at the last moment to sway the outcome.
• 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 for preventing voter fraud, as public records of voters allow people to check if others have voted in their name. However, on-chain, we can prevent voter fraud while preserving anonymity using cryptographic primitives—e.g., through Semaphore, you can prove in zero-knowledge that you are a qualified voter who has not yet voted.
• Receipt-freeness: Individual voters provide a "receipt" of their ballot to prove how they voted to a third party, which could otherwise lead to vote selling. A closely related but stronger property is anti-coercion, which prevents someone from coercing a voter to vote in a certain way. These properties are particularly appealing in decentralized environments, as voting rights can be made liquid through smart contract markets. Unfortunately, they are also difficult to achieve—in fact, Juels et al. point out that this is impossible in permissionless environments without trusted hardware.

Cicada focuses on the privacy of ongoing tallying, but (as we discuss later) it can be combined with zero-knowledge group member proofs to achieve voter anonymity and ballot privacy.

Introducing Cicada: Tallying Privacy from Homomorphic Time-Lock Puzzles

To achieve privacy of ongoing tallying, Cicada leverages cryptographic primitives that, to our knowledge, have never been used on-chain before.

First, time-lock puzzles (Rivest, Shamir, Wagner, 1996) are cryptographic puzzles that encapsulate a secret, which can only be revealed after a predetermined amount of time has passed—more specifically, the puzzle can be decrypted by repeatedly performing some non-parallel computations. Time-lock puzzles are useful in the context of voting for achieving privacy of ongoing statistics: users can submit their ballots as time-lock puzzles, keeping them confidential during the voting process but allowing them to be revealed afterward. Unlike most other private voting structures, this means that the privacy of ongoing statistics does not need to rely on trusted authorities (like election staff counting paper or digital ballots), threshold encryption (where several trusted parties must cooperate to decrypt a message), or any other trusted party: anyone can solve a time-lock puzzle to ensure that the results are revealed after voting.

Second, a homomorphic time-lock puzzle (Malavolta Thyagarajan, 2019) has the additional property that some computations on the encrypted value are possible given the secret key, the decryption puzzle, or a backdoor. In particular, a linear homomorphic time-lock puzzle allows us to combine puzzles together to produce a new puzzle that encapsulates the sum of the secret values of the original puzzles.

As the authors of the paper 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 yield a puzzle encoding the final tally. This means that the final result can be revealed with a single computation, rather than solving a unique puzzle for each ballot.

A New Structure: Efficiency and Trade-offs

To make a voting scheme practical on-chain, several issues need to be considered. First, an attacker might try to manipulate the vote by casting an incorrectly encoded ballot. For example, we might want each ballot's time-lock puzzle to encode a boolean value: "1" for supporting the proposal being voted on, "0" for opposing it. An enthusiastic supporter of a proposal might try to encode, say, "100" to inflate their effective voting power.

We can prevent this attack by having voters submit a zero-knowledge proof of ballot validity alongside their ballot submission. However, the computational cost of zero-knowledge proofs is high—proofs should be (1) efficiently computable on the client side and (2) efficiently verifiable on-chain.

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

While the verifier of this sigma protocol is conceptually simple, it requires a significant amount of large modular exponentiation. Malavolta and Thyagarajan's linear homomorphic scheme uses Paillier encryption, so these exponentiations will be performed modulo some RSA modulus N as N^2. For reasonably sized N, exponentiation is very expensive on most EVM chains (millions of gas). To reduce costs, Cicada uses exponential ElGamal—exponential ElGamal still provides additive homomorphism but works on smaller moduli (N instead of N^2).

One downside 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 verified effectively on-chain). Therefore, it is only suitable for cases where the expected final tally is relatively small (e.g., less than 2^32, or about 4.3 million votes). In the initial Paillier-based scheme, the tally could be effectively decrypted regardless of its size.

Choosing the RSA modulus N also involves trade-offs. Our implementation uses a 1024-bit modulus to improve gas efficiency. While this is far above the largest RSA modulus ever publicly factored (829 bits), it is below the generally recommended size of 2048 bits for RSA encryption or signatures. However, our application does not require long-term security: once the election is over, there is no risk in considering N in the future. Assuming that the tally and ballots are made public after the time-lock period expires, 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 privacy of ongoing tallying—the time-lock puzzle property keeps the tallying private during the voting period. However, each individual ballot is also a time-lock puzzle encrypted under the same public parameters. This means that just as the tally can be decrypted (by performing the necessary computations), each ballot can be as well. In other words, Cicada only guarantees ballot privacy during the voting period—if a curious observer wishes to decrypt a specific voter's ballot, they can do so. Decrypting any individual ballot is as costly as decrypting the final tally, so naively requires O(n) work to fully decrypt the ballots of n voters. However, all of these ballots can be decrypted in parallel (assuming there are enough machines), with the elapsed wall-clock time being the same as that required to decrypt the final tally.

For certain ballots, this may be undesirable. While we are satisfied with temporary ongoing tallying privacy, we may wish for indefinite ballot privacy. To achieve this, we can combine Cicada with an anonymous voter eligibility protocol instantiated through zero-knowledge group member proofs. This way, even if the ballots are decrypted, what is revealed is merely that someone voted in this way—we already know this from the tally.

In our repository, we include an example contract that uses Semaphore for voter anonymity. However, note that the Cicada contract itself makes no assumptions about how to determine or enforce voter eligibility. In particular, you can replace Semaphore with, for example, Semacaulk or ZK state proofs (as suggested here and here).

Statistical Authority

One of our primary goals in designing Cicada was to avoid the need for a statistical authority: many private voting structures require a semi-trusted statistical authority (or authorized committee coordinating through secure multiparty computation) to receive and aggregate ballots. In a blockchain environment, this means that these schemes cannot be executed solely by smart contracts and require some human intervention and trust.

In most structures, the tallying authority is untrusted in terms of integrity (they cannot manipulate the ballot counts), but trusted in terms of liveness—if they go offline, the final results cannot be computed, indefinitely delaying the voting outcome. In some structures, they are also trusted to maintain privacy—that is, they know how everyone voted but are expected to publish the results without revealing this information.

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

Cicada explores one of many directions in the realm of on-chain voting privacy and complements much of the ongoing research by other teams. As mentioned above, Cicada is closely related to anonymous group member technologies such as Semaphore, ZK storage proofs, and rate-limiting invalidators. Cicada can also integrate with the optimistic proof checker proposed by the Nouns Vortex team to alleviate the gas burden on voters.

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