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

All voting systems rely on integrity and transparency to function in any meaningful way. At face value, this makes blockchains an ideal platform to build these systems on – and indeed, many decentralized organizations have embraced permissionless voting to express collective intent, often in the context of wielding substantial treasuries or tuning critical protocol parameters. But there are drawbacks to on-chain voting, and privacy remains unexplored to the detriment of web3 voting systems – in the majority of on-chain voting protocols used today, ballots and vote tallies are fully public. Without privacy, voting results are susceptible to manipulation and misaligned voter incentives, potentially leading to undemocratic outcomes. 

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

In this post, we survey the landscape of voting privacy and provide a high-level description of how Cicada works (with formal proofs to come). We also encourage developers to check out the GitHub repository – Cicada can be adapted and extended in many ways to support different voting schemes and features, 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 running tally, and voter identities can all influence voter incentives in different ways. Which privacy properties are necessary depends on the context of the vote. A few that frequently arise in cryptography and social science literature:

• Ballot privacy: The secret ballot, also called “the Australian ballot” was developed for real-world voting systems as a way to keep the preferences of individual voters private, 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 also mitigates social desirability bias – there is less pressure for someone to vote based on what others think of their choice.

• Running tally privacy: Many voting systems hide the running tally, or how many votes have been cast for each option, while voters are still casting ballots to avoid impacting turnout and voter incentives. We’ve seen this play out in the real world; for example, US 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 lull their opponents into a false sense of security by letting them hold the lead (some may not bother to vote, assuming they will win regardless) and then cast their ballot at the last minute to swing the outcome.

• Voter anonymity: Your vote is private in many real-world voting systems, but the fact that you voted is often public. This can be important as a safeguard against voter fraud, because publishing records of who voted allows people to check whether someone else cast a ballot in their name. On-chain, however, we can prevent voter fraud while preserving anonymity using cryptographic primitives – with Semaphore, for example, you can prove in zero knowledge that you are an eligible voter who hasn’t cast a ballot yet. 

• Receipt-freeness: Individual voters provide a “receipt” of their ballot to prove how they voted to third parties, which otherwise might lead to vote selling. A closely related but stronger property is coercion-resistance, which prevents someone from coercing a voter to vote a certain way. These properties are especially appealing in a decentralized setting, where voting power can be made liquid via smart contract marketplaces. Unfortunately, they are also very difficult to achieve – in fact, Juels et al. state that it is impossible in a permissionless setting without trusted hardware.

Cicada is focused on running tally privacy, but (as we discuss later) it can be composed with zero-knowledge group membership proofs to obtain voter anonymity and ballot privacy as well. 

Introducing Cicada: Tally privacy from homomorphic time-lock puzzles

To achieve running tally privacy, Cicada draws from cryptographic primitives that (to our knowledge) have never been used on-chain before. 

First, a time-lock puzzle (Rivest, Shamir, Wagner, 1996) is a cryptographic puzzle that encapsulates a secret which can only be revealed after some predetermined amount of time has elapsed – more specifically, the puzzle can be decrypted by repeatedly performing some non-parallelizable computation. Time-lock puzzles are useful in the context of voting for achieving running tally privacy: Users can submit their ballots as time-lock puzzles, so that they are secret during the vote but can be revealed afterwards. Unlike most other private voting constructions, this enables running tally privacy without relying on tallying 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 parties: anybody can solve a time-lock puzzle to ensure results are revealed after the vote.

Second, a homomorphic time-lock puzzle (Malavolta Thyagarajan, 2019) has the additional property that some computation on the encrypted value is possible knowing the secret key, decrypting the puzzle, or using a backdoor. In particular, a linearly homomorphic time-lock puzzle allows us to combine puzzles together, producing a new puzzle that encapsulates the sum of the original puzzles’ secret values.

As the authors of the paper note, linearly homomorphic time-lock puzzles are a particularly suitable primitive for private voting: Ballots can be encoded as puzzles, and they can be homomorphically combined to obtain a puzzle encoding the final tally. This means that only one computation is needed to reveal the final tally, instead of solving a unique puzzle for every ballot.

A new construction: efficiency and tradeoffs

There are several more considerations to make for a voting scheme to be practical on-chain. First, an attacker may try to manipulate the vote by casting an incorrectly encoded ballot. For example, we might expect each ballot’s time-lock puzzle to encode a boolean value: “1” to support the voted-upon proposal, “0” to oppose it. An ardent supporter of the proposal may instead attempt to encode e.g. “100” to amplify their effective voting power.

We can prevent this sort of attack by having voters submit a zero-knowledge proof of ballot validity alongside the ballot itself. Zero-knowledge proofs can be computationally expensive though – to keep the costs of voter participation as low as possible, the proof should be (1) efficiently computable client-side and (2) efficiently verifiable on-chain.

To make proving as efficient as possible, we use a bespoke sigma protocol – a zero-knowledge proof designed for a specific algebraic relation, as opposed to a generalized proof system. This enables extremely fast prover times: generating a ballot validity proof in Python takes 14ms on an off-the-shelf laptop. 

Though the verifier for this sigma protocol is conceptually simple, it requires a few large modular exponentiations. Malavolta and Thyagarajan’s linearly-homomorphic scheme uses Paillier encryption, so these exponentiations would be performed modulo N^2 for some RSA modulus N. For a reasonably sized N, the exponentiations are prohibitively expensive (millions of gas) on most EVM chains. To reduce this cost, Cicada instead uses exponential ElGamal – exponential ElGamal still provides additive homomorphism, but works over a much smaller modulus (N instead of N^2).

One downside of using ElGamal is that the last step of decrypting the tally requires brute-forcing a discrete log (note that this is done off-chain and efficiently verified on-chain). As such, it is only suitable if the expected final tally is reasonably small (e.g. less than 2^32, or about 4.3 million votes). In the original Paillier-based scheme, the tally can be efficiently decrypted regardless of its size.

Selecting the RSA modulus N also involves a tradeoff. Our implementation uses a 1024-bit modulus for gas efficiency. While this is well above the largest RSA modulus ever publicly factored (which was 829 bits) it is below the normally recommended size of 2048 bits for use with RSA encryption or signatures. However, we don’t need long-term security in our application: once an election is finished there is no risk if N is factored in the future. The tally and ballots are assumed to become public after the time-lock expires, so 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

Cicada, as described above, provides running tally privacy – the time-lock puzzle property keeps the tally private for the duration of the vote. 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 requisite computation), so can each individual ballot. In other words, Cicada only guarantees ballot privacy for the duration of the vote – if a curious observer wishes to decrypt a particular voter’s ballot, they can do so. Decrypting any individual ballot is as expensive as decrypting the final tally, so naively it requires O(n) work to fully decrypt a vote with n voters. But all of these ballots can be decrypted in parallel (assuming 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 satisfied with temporary running tally privacy, we may want indefinite ballot privacy. To accomplish this, we can combine Cicada with an anonymous voter eligibility protocol, instantiated by zero-knowledge group membership proofs. This way, even if a ballot is decrypted, all it would reveal is that someone voted that way – which we would already know from the tally.

In our repository we include an example contract that uses Semaphore for voter anonymity. Note, however, that the Cicada contract itself makes no assumptions on how voter eligibility is determined or enforced. In particular, you could replace Semaphore with e.g. Semacaulk or ZK state proofs (as proposed here and here). 

Tallying authorities

One of our priorities in designing Cicada was to avoid the need for tallying authorities: Many private voting constructions require a semi-trusted tallying authority (or committee of authorities, coordinating via secure multi-party computation) who receives and aggregates the ballots. In a blockchain context, this means that these schemes cannot be conducted by a smart contract alone and that some human intervention and trust is needed.

In most constructions, tallying authorities are not trusted for integrity (they cannot manipulate the vote count), but they are trusted for liveness – if they go offline, the final result cannot be computed, indefinitely stalling the outcome of the vote. In some constructions they are also trusted to maintain privacy – that is, they learn how each individual votes but are expected to publish the vote result without revealing this information.

Though tallying authorities are a reasonable (and necessary) assumption in many real-world scenarios, they are not ideal in a blockchains context, where our objective 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 ongoing research being done by other teams. As mentioned above, Cicada goes hand-in-hand with anonymous group-membership technologies like Semaphore, ZK storage proofs, and rate-limiting nullifiers. Cicada could also integrate the optimistic proof checker proposed by Nouns Vortex team to reduce the gas burden on voters. 

There are also opportunities 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 could be practical on L2s. With that in mind, we welcome your contributions, forks, and suggestions on where to take Cicada next. 

Acknowledgements: Cicada was developed jointly with Joseph Bonneau. Thanks to Andrew Hall for supplying context around the historical context of voting privacy. Thanks also to Robert Hackett for feedback on this post. Special thanks to Stephanie Zinn for editing. 

***

Views expressed in “posts” (including articles, podcasts, videos, and social media) are those of the individuals quoted therein and are not necessarily the views of AH Capital Management, L.L.C. (“a16z”) or its respective affiliates. a16z is an investment adviser registered with the U.S. Securities and Exchange Commission. Registration as an investment adviser does not imply any special skill or training. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party information; a16z has not reviewed such material and does not endorse any advertising content contained therein.

This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities, digital assets, investment strategies or techniques are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments or investment strategies will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.

Additionally, this material is provided for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. Investing in pooled investment vehicles and/or digital assets includes many risks not fully discussed herein, including but not limited to, significant volatility, liquidity, technological, and regulatory risks. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures/ for additional important information.