a16z: How Cicada Implements On-chain Voting with Time-lock Puzzles and ZK Proofs
a16z: Cicada's On-chain Voting with Time-lock Puzzles and ZK Proofs
Author: Michael Zhu | Translated by: Lynn, MarsBit
All voting systems, no matter how they operate meaningfully, rely on integrity and transparency. On the surface, this makes blockchain an ideal platform for building these systems – in fact, many decentralized organizations have already embraced permissionless voting to express collective intent, often when wielding significant wealth or adjusting key protocol parameters. But on-chain voting has its drawbacks, and privacy remains unexplored and undeveloped, which is detrimental to Web3 voting systems – in most of the on-chain voting protocols currently in use, ballots and voting results are completely public. Without privacy, the results of voting can be easily manipulated and voters misincentivized, potentially leading to undemocratic outcomes.
That’s why we’re releasing Cicada: a new, open-source Solidity library that leverages time-lock puzzles and zero-knowledge proofs to achieve private on-chain voting. Compared to existing systems, Cicada has novel privacy properties that minimize trust assumptions, and is sufficiently efficient to be used on the Ethereum mainnet.
In this article, we investigate the state of voting privacy and provide a high-level description (formal proofs forthcoming) of how Cicada works. We also encourage developers to check out the GitHub repository – Cicada can be adjusted and expanded in many ways to support different voting schemes and features, and we look forward to collaborating 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 levels of privacy to consider. The disclosure of individual ballots, the running tally of votes, and the identity of voters all affect voter incentives in different ways. Which privacy properties are necessary depends on the context of the vote. Several frequently appearing ones in cryptographic and social science literature:
- After facing multiple lawsuits from cryptocurrency investors, is NB...
- Uncovering “Fake KOL” ben.eth: How to create a meme coi...
- Tornado Cash DAO has passed a proposal for the return of control to...
-
Ballot privacy: Secret ballot, also known as “Australian ballot,” was developed for real-world voting systems as a way to keep individual voter preferences confidential and to 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 – the pressure for someone to vote based on others’ perceptions of their choices.
-
Privacy of ongoing vote counting: Many voting systems hide ongoing vote counting or how many votes each option has received while voters are still voting, to avoid affecting voter turnout and incentives. We’ve seen this in the real world; for example, late-voting US Senators are more likely to vote with their party than early-voting Senators. On-chain: In token-weighted voting, whales can deceive opponents into a false sense of security by keeping them ahead, assuming they won’t vote anyway, and then swing the result by voting their own tokens at the last minute.
-
Voter anonymity: In many real-world voting systems, your vote is not public, but the fact that you voted often is. This is important for preventing voter fraud, because public records of who voted can allow people to check whether someone else voted in their name. In chains, we can prevent voter fraud while preserving anonymity using cryptographic primitives – for example, 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, or else risk vote-selling. A closely related but more powerful property is coercion resistance, which can prevent someone from coercing a voter to vote in a certain way. These properties are particularly attractive in decentralized environments, where voting rights can be implemented with liquidity through smart contract markets. Unfortunately, they are also difficult to achieve – in fact, Juels et al. have shown that this is impossible in a permissionless setting without trusted hardware.
Cicada focuses on ongoing vote privacy, but (as we’ll discuss later) it can be combined with zero-knowledge group proofs to achieve voter anonymity and ballot privacy.
Introducing Cicada: Voting Privacy from Homomorphic Timelock Puzzles
To achieve privacy in ongoing voting, Cicada leverages cryptographic primitives that (to our knowledge) have never before been used on-chain.
First, a timelock puzzle (Rivest, Shamir, Wagner, 1996) is an encryption puzzle that encapsulates a secret that can only be revealed after some pre-determined amount of time has passed – more specifically, the puzzle can be decrypted by performing some non-parallelizable computation repeatedly. Timelock puzzles are useful for achieving privacy in running tallies in the context of voting: users can submit their ballots as timelock puzzles, such that they are secret during voting but can be revealed after voting. Unlike most other private voting schemes, this makes running tallies privacy-preserving without relying on any tallying authority (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: anyone can solve a timelock puzzle to ensure that the result is revealed after voting.
Second, a homomorphic timelock puzzle (Malavolta Thyagarajan, 2019) has the additional property that some computations on the encrypted value are possible, given knowledge of the secret key, decryption of the puzzle, or use of a backdoor. In particular, a linear homomorphic timelock puzzle allows us to combine puzzles together, producing a new puzzle that encapsulates the sum of the secret values of the original puzzles.
As the paper authors note, linear homomorphic timelock puzzles are a particularly suitable primitive for private voting: ballots can be encoded as puzzles, and they can be combined homomorphically to obtain a puzzle that encodes the final tally. This means that only one computation is needed to reveal the final result, rather than solving a unique puzzle for each ballot.
A New Scheme: Efficiency and Tradeoffs
To make the voting scheme practical on-chain, several issues must also be considered. First, an attacker may try to manipulate voting by casting an incorrectly encoded ballot. For instance, we might want each ballot’s timelock puzzle to be encoded as a Boolean value: “1” indicating support for the proposal being voted on, “0” indicating opposition. An enthusiastic proposal supporter might try to encode, say, “100” to magnify their effective voting power.
We can prevent this attack by having voters submit a zero-knowledge proof of the validity of their ballot at the same time they submit the ballot itself. However, the computation cost of zero-knowledge proofs is high – to minimize the cost for voters to participate, the proof should be (1) efficiently computable by the client 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 a specific algebraic relation, rather than a general purpose proof system. This makes the prover’s time very fast: generating a ballot validity proof in Python takes 14 ms on an off-the-shelf laptop.
While the verifier for this sigma protocol is conceptually simple, it requires a fair amount of large modular exponentiations. Malavolta and Thyagarajan’s linear homomorphic scheme uses Blockingillier encryption, so these exponentiations will be performed modulo some RSA modulus N squared for certain RSA moduli N. For reasonable-sized N, taking exponentiations is very expensive on most EVM chains (millions of gas). To reduce the cost, Cicada uses exponential ElGamal – exponential ElGamal still provides additive homomorphism, but works on smaller moduli (N instead of N squared).
One disadvantage of using ElGamal is that the last step of decrypting the count requires brute-forcing a discrete log (note that this is done off-chain and validated on-chain). Therefore, it only works for cases where the expected final vote count is fairly small (e.g., less than 2^32, or about 4.3 million votes). In the original Blockingillier-based scheme, the count could be decrypted efficiently regardless of its size.
Choosing an RSA modulus N also involves tradeoffs. Our implementation uses a 1024-bit modulus to improve gas efficiency. While this is far larger than the largest RSA modulus publicly factored to date (829 bits), it is smaller than the typically recommended size of 2048 bits used for RSA encryption or signing. However, our application does not require long-term security: once the election is over, there is no risk in the future if N is considered. Assuming counting and voting are made public after the time lock expires, using a relatively small modulus is reasonable. (If factoring algorithms improve, this can also be easily updated in the future.)
Anonymity and Voter Eligibility
As mentioned above, Cicada provides privacy for running tallies – the time-lock puzzle property maintains the confidentiality of the tallies 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 counting 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 expensive as decrypting the final tally, so naively decrypting all n voters’ ballots requires O(n) work. But all of these ballots can be decrypted in parallel (assuming enough machines), costing clock time equivalent to decrypting the final tally.
For some ballots, this may not be desirable. While we are comfortable with temporary running tally privacy, we may want indefinite ballot privacy. To achieve this, we can combine Cicada with the anonymous voter eligibility protocol and instantiate it using zero-knowledge proof of membership. This way, even if a ballot is decrypted, all it reveals is that someone voted in this way–we already know that from the tallying.
In our repository, we include an example contract that uses Semaphore for voter anonymity. Note, however, that the Cicada contract itself makes no assumptions about how voter eligibility is determined or enforced. In particular, you could replace Semaphore with, for example, Semacaulk or ZK state proofs (as suggested here and here).
Tabulation Authorities
One of our primary goals in designing Cicada was to avoid the need for tabulation authorities: many private voting schemes require a semi-trusted tabulation authority (or authorization committee, coordinated 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 degree of human intervention and trust.
In most schemes, the tabulating authorities are trusted in terms of integrity (they cannot manipulate the vote count), but untrusted in terms of liveness–if they go offline, the final result cannot be calculated, delaying the outcome indefinitely. In some schemes, they are also trusted to maintain privacy–that is, they know how everyone voted but are expected to publish the vote tally without revealing this information.
Although tabulation authorities are a reasonable (and necessary) assumption in many real-world scenarios, they are not ideal in a blockchain setting, and our goal was to minimize trust and ensure auditability.
Cicada explores one of many directions in the field of on-chain voting privacy and complements much of the other research being done. As mentioned, Cicada is closely related to anonymous composition techniques such as Semaphore, ZK storage proofs, and rate limiters. Cicada can also integrate with the optimistic proof checker proposed by the Nouns Vortex team to alleviate voters’ gas burden.
There is also an opportunity to adjust Cicada to support different voting schemes (such as token-weighted voting, quadratic voting) – more complex schemes may be too costly to compute for the Ethereum mainnet, but they may be practical on L2. With this in mind, we welcome your contributions, forks, and suggestions on where to take Cicada next.
