a16z: How Cicada leverages timelock puzzles and ZK proofs for on-chain voting

Original author:Michael Zhu

Original Compilation: Lynn, MarsBit

Original author:Original Compilation: Lynn, MarsBitAll 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 for building these systems—indeed, many decentralized organizations have embracedvote without permissionto express collective intentions, often while wielding substantial wealth or tweaking key protocol parameters. But on-chain voting also has disadvantages,

Privacy remains unexplored and unexplored

, not good for Web3 voting systems - in most on-chain voting protocols in use today, 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 review the

GitHub repository

- Cicada can be adapted and extended in many ways to support different voting schemes and features, and we hope to work with the community to explore these possibilities.

• A Brief Survey of Private VotingIn 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 "Secret Ballots"

• australian vote

• ”, was developed for real-world voting systems, as a way to preserve the preferences of individual voters, and mitigate bribery and coercion (in an on-chain setting, we may need a stronger property than vote privacy — see below "No Receiptability"). Vote privacy can also mitigate social desirability bias — someone has less pressure to vote based on what others think of their choices.

• 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.pointed outReceiptlessness: 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 are also difficult to implement—in fact, Juels et al.

pointed out

, which is not possible 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 ProblemRivest, Shamir, Wagner, 1996 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 (Malavolta Thyagarajan, 2019 ) is a cryptographic puzzle that encapsulates a secret that can only be revealed after some predetermined amount of time has elapsed—more specifically, a puzzle that can be decrypted by repeatedly performing some non-parallel computations. 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 (

) has the additional property that some computations on encrypted values ​​are possible with knowledge of the secret key, decryption 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: Efficiencies 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 against. 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 14 ms 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 (eg 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.herehereandhereand

here

suggested).

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 votes 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.