zkConvex - A Large-Scale Anonymous Electronic Voting Scheme Based on zk-SNARKs

A large-scale anonymous electronic voting scheme based on zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) offers unique value and significance in ensuring the anonymity, security, and reliability of voting. zk-SNARKs is a cryptographic technology that enables one party (the prover) to prove to another party (the verifier) that a statement is true, without revealing any information other than the truth of the statement itself. Applying zk-SNARKs to electronic voting brings several key advantages:

1. Protection of Voter Identity Privacy: The connection between a voter’s choice and their personal identity is not disclosed; it’s impossible to identify from public information whether a specific voter has participated. This also enhances the fairness of the voting system.

2. Prevention of Vote Buying and Selling: Voters participate under pseudonyms and are unable to prove their own voting results. This means voters cannot sell their votes to third parties who may wish to purchase them.

3. Verifiable Voting Results: Everyone can verify the voting results based on the public counting proofs.

Convex Analysis

The governance of Convex relies on the vote-locking mechanism of CVX tokens, the native token of Convex. By locking CVX, one can vote on any proposal presented on Convex (published on snapshot). This proposal regarding Curve aims to add a gauge to the crvUSD/USD+ StableSwap-ng liquidity pool on the Arbitrum chain to determine the amount of CRV tokens the pool should receive as liquidity rewards.

In this case, to secure more liquidity rewards for their pool, project operators need to garner more votes for this proposal. There are two ways to achieve this:

1. The project operators buy CVX and lock these CVX for voting;

2. The project operators seek other CVX holders to vote for their pool.

The first method involves the project operators buying CVX, while the second method involves buying the voting rights represented by CVX, meaning the project operators need to bribe CVX holders to vote for them. In reality, the first method is more costly than the second, so project operators tend to prefer purchasing voting rights of CVX.

However, the second method may allow project operators with more resources to gain an unfair advantage, making it difficult for smaller or newer projects to compete. To address this issue, we employ a large-scale anonymous electronic voting scheme based on zk-SNARKs to assist Convex in private governance. This scheme involves five different participants and is defined by eight related functions. The entire voting process can be divided into five stages.

Participants Composition

The electronic voting scheme involves the following five participants: Proposers, CVX Holders $ID_s = \lbrace id_1, id_2, \dots, id_m \rbrace$, Cryptographic Coordinator, Pseudonym Registrar, and Counters $T_s = \lbrace T_1, T_2, \dots, T_m \rbrace$. Among them, proposers and CVX holders are inherent to Convex. Proposal-related information and voting results are still published on snapshot.

• Proposers: Also known as project operators, they can initiate proposals for their liquidity pools and are also CVX holders themselves.

• CVX Holders: Also known as voters, they can lock CVX tokens to vote. They vote under pseudonyms to ensure anonymity. As shown in the figure below, the voting results published on snapshot will not display the on-chain addresses of CVX holders, but their pseudonyms instead.

• Snapshot: Publishes proposal information, voting information, cryptographic public parameters, voting results, and proofs of correct counting. The voting results include not only those cast by CVX holders but also null ballots cast by snapshot.

• Cryptographic Coordinator: Responsible for generating cryptographic parameters and key pairs, and publishing the public parameters on snapshot.

• Pseudonym Registrar: Registers pseudonyms for CVX holders after they lock their CVX tokens and signs these pseudonyms.

• Counters: Responsible for calculating and verifying the voting results, and publishing the results and proofs of correct counting on snapshot, as shown in the figure below. Counters use partial decryption keys from a k-out-of-n encryption scheme.

Function Definitions

The voting scheme is defined by eight functions, namely:

$$VS = (Setup,PseudonymRegister,Register,Vote,ValidVote,Append,Tally,VerifyTally)$$

1. Setup

$Setup(λ,R) \to (PP,sk_T, sk_σ)$: On input of the security parameter $λ$ and the relation $R$ represented as an arithmetic circuit, generate the prover and verifier key pairs $(pk,vk) \gets KeyGen(λ,R)$, voting key pair $(pk_T,sk_T) \gets KeyGenE(λ)$, registrar key pair $(pk_R,sk_R) \gets KeyGenS(λ)$, commitment parameters from commitment setup $CR \times T \gets SetupC(λ)$, and public parameters $PP = (G,q,g,H,pk_T,pk_R,(pk,vk))$.

2. PseudonymRegister

$PseudonymRegister(id) \to (cr_{id},c_{id}, t_{id})$: On implicit input $PP$ and CVX holder identity id, randomly select a pseudonym $cr_{id} \gets CR$, compute $(t_{id},c_{id}) \gets Commit(PP,cr_{id})$, and return $(cr_{id},c_{id},t_{id})$, where $t_{id}$ is randomly selected from $T$.

3. Register

$Register(id,c_{id},L) \to (L,MR_L,S_R)$: On input of the CVX holder identity and $commitment(id,c_{id})$, and list $L$, add $(id,c_{id})$ to list $L$, compute $MR_L$, sign $(L,MR_L)$ with the registrar private key $sk_R$ to produce the signature $S_R$, and then return $(L,MR_L,S_R)$.

4. Vote

$Vote(id,sk_{id},pk_r,v) \to β$: On input of CVX holder identity $id$, voting public key $pk_T$, and CVX holder private key $sk_{id}=(t_{id},cr_{id})$, it generates a ballot $β=(e_v,cr_{id},π_{id})$, where $e_v=enc_{pk_v}(v;r)$. Additionally, compute a disjoint proof $Prove(pk,x,ω) \to π$, where $ω=(r,c_{id},v,t_{id}), x=(e_v,cr_{id},MR_L)$, and simulate a null ballot proof.

5. ValidVote

$ValidVote(β) \to 0/1$: On input of a ballot $β=(e_v,cr_{id},π_{id})$, check if it is valid, i.e., whether this proof is correct and well-formed, by completing the verification through executing $Verify(vk,(e_v,cr_{id}),π_{id}) \to 0/1$.

6. Append

$Append(snapshot,β) \to snapshot$: On input of a ballot $β$, according to $D_t$, append $β$ to snapshot. It generates and appends one or more null ballots $(e_0,c_{id},π_{id})$ according to the probability distribution $D_r$ and $D_t$. It computes $e_0=enc_{pk_r}(0;r)$ and disjoint proof $π_{id}$.

$Prove(pk,x,ω) \to π_{id}$, where $ω=(r,0),x=(e_0,cr_{id},MR_L)$, and simulates the other side of CVX holder proof.

7. Tally

$Tally(snapshot,sk_T) \to (s,Π)$,: On input of the public snapshot, calculate the voting results, return $(s,Π)$, where $s$ is the voting result, $Π$ is the proof of correct counting, with the following steps:

  - Run $ValidVote(β)$ and return $0$ in case of failure.

  - For each $cr_{id}$ appearing in the ballots, calculate $B_{cr_{id}}=Π_{e_v∈B(cr_{id})}e_v$, where $B(cr_{id})$ is the set of $(e_v,cr_{id},π_{id})$ identified by $cr_{id}$.

  - $Remove(cr_i,π_i)$ from each $B_{cr_i}$, mix the ballots $\lbrace B_{cr_1},B_{cr_2},...,B_{cr_k} \rbrace$, where $k$ is the number of pseudonyms $cr_i$, and return the mixed ballots $\lbrace B'_1,B'_2,...,B'_k \rbrace$ and proof of valid mixing.

  - For each $B'_i$ and voting option $v∈V$, apply the privacy equivalence test (PET) and provide corresponding proof.

  - Calculate the result $s$ for each voting $v$ based on the PET result and publish the proof.

8. VerifyTally

$VerifyTally(snapshot,s,Π) \to 0/1$: On input of $(s,Π)$,, if all proofs are valid, return $1$; otherwise, return $0$.

Implementation Phase

The flowchart of this electronic voting scheme illustrates the process of Convex’s private governance as follows.

Based on this flowchart, we divide the Convex private governance process into five stages:

1. Setup Phase

Given security parameters $λ$ and relation $R$, the Cryptographic Coordinator runs $Setup(λ,R)$ to:

  - Generate cryptographic parameters $(G,q,g)$, counting party threshold tuple $(k,n)$, voting key pair $(pk_T,sk_T)$, registrar key pair $(pk_R,sk_R)$, commitment function and its parameters $H:CR \times T \to C$, and the zero-knowledge proof key pair $(pk,vk)$ for relation $R$.

  - Publish public parameters $PP=(G,q,g,H,pk_T,pk_R,(pk,vk))$.

2. Registration Phase

CVX holders $(id)$ run $Register(id)$ to:

  - Choose a voting pseudonym $cr_{id}∈CR$.

  - Compute $c_{id}=H(cr_{id},t_{id})∈\lbrace 0,1 \rbrace^{O(λ)}$ using $t_{id}∈T$ and store $(cr_{id},t_{id})$ locally.

  - Send $c_id$ to the pseudonym registrar via an authentic channel.

  - The pseudonym registrar adds $(id,c_{id})$ to the pseudonym list $L$.

  - Compute the merkle tree root $MR_L$ based on the commitment order in list $L$.

  - Finally, sign $L$ and $MR_L$ and publish them on snapshot.

  - CVX holders verify $c_{id}∈L$ and merkle tree root $MR_L$.

3. Voting Phase

To cast a vote $v$, CVX holders run $Vote(id,sk_{id},pk_T,v)$, where $sk_{id}=(t_{id},cr_{id})$, including:

  - Compute $e_v=enc_{pk_T}(v;r)$, where $r∈Z_q$ is a random value for encryption. In the case of revoking a previous vote $v_{pre}$ and voting for $v_{new}$, CVX holders set $v=v_{new}-v_{pre}$.

  - Calculate zero-knowledge proof $π_{id}$ using proving key $pk$:

$$π_{id}=\lbrace (r,c_{id},v,t_{id})|(e_v=(g^r,g^v{pk_T}^r) \cap c_{id}=H(cr_{id},t_{id}) \cap c_{id}∈rt_L) \rbrace \cup \lbrace (r,g^0)|e_v=(g^r,g^0{pk_T}^r) \rbrace$$

  - Submit $β=(e_v,cr_{id},π_{id})$ to snapshot via an anonymous channel.

  - Snapshot runs $ValidVote(β)$, checks the validity of the proof on the ballot, and verifies if the ballot already exists on snapshot.

  - Snapshot runs $Append(snapshot,β)$, appending the ballot $β$ and null ballots to snapshot.

  - CVX holders verify if $β$ is appended to snapshot.

  - Snapshot generates null ballots as follows: Calculate $e_0=enc_{pk_T}(0;r)$, choose a $cr_{id}$ from $β$ on the snapshot, compute $π_{id}$:

$$π_{id}=\lbrace (r,c_{id},v,t_{id})|(e_0=(g^r,g^v{pk_T}^r) \cap c_{id}=H(cr_{id},t_{id}) \cap c_{id}∈rt_L) \rbrace \cup \lbrace (r,g^0)|e_0=(g^r,g^0{pk_T}^r) \rbrace$$

4. Counting Phase

Counters run $Tally(snapshot,sk_T)$, including:

  - Verify ballots on snapshot and select those with valid proofs.

  - Apply the homomorphic properties of the encryption scheme to calculate the final ballot for each $cr_{id}$ on the snapshot.

  - Shuffle, mix, and publish the final ballots without $cr_{id}$, providing proof of correctness.

  - Apply PET to the final ballots and select encrypted votes from the voting.

  - Decrypt ballots and publish results and decryption proofs on snapshot.

5. Verification Phase

Anyone can verify the correctness of the counting by running $VerifyTally(snapshot,s,Π)$, which verifies the results and all proofs published during the counting process. This implementation achieves large-scale electronic voting while ensuring anonymity, security, and reliability.

Compression

Recursive zk-SNARKs allow a prover to put "more knowledge" into a proof while ensuring that these proofs can still be verified by a verifier in constant or poly-logarithmic time. Using recursive zk-SNARKs as an "aggregator" of information enables independent "aggregation" of more computations than the largest (non-recursive) circuit can handle. More about recursive zk-SNARKs.

Future Work

• Performance and Scalability: As the number of voters increases, the system's performance and scalability will face challenges. Future research could focus on the study of fully recursive zk-SNARKs to support larger-scale elections.

• User Friendliness: An important task in promoting ZK technology is to address the current complexity of the system for ordinary users. Simplifying user interfaces and operational processes, and lowering the barrier for user adoption, will contribute to the widespread acceptance and adoption of the system.

• Compliance and Legal Challenges: Decentralization and compliance have always been antonyms; typically, only the government can prove your identity. However, this leads to the possibility of data being tampered with at the source (but if this identity is recognized by the government, then even the fake becomes real). ZK cannot solve the problem of a trusted source, but we might need to consider: what kind of world it would be if I could prove I am who I am.

If you are interested in integrating ZK technology into your project governance to enhance privacy, scalability, and achieve governance innovation, ZEROBASE offers end-to-end ZK services and comprehensive solutions. By collaborating with us, you can explore the extensive applications of ZK technology in project governance, providing the community with a more secure, transparent, and efficient electronic voting system.