SNARVs: Succinct NonInteractive Arguments of Voting  protocols for costeffective, offchain evoting.
Posted 20221125 by Vincenzo Iovino ‐ 7 min read
SNARVs: Succinct NonInteractive Arguments of Voting  protocols for costeffective, offchain evoting.
20221125 by Vincenzo Iovino and Matan Prasma.
Currently, voting protocols for DAOs are carried out without any privacy, that is, the preference of each voter is publicly visible to everybody. Moreover, to tally the result, a large amount of gas is consumed on the Ethereum network. To address this problem, Aragon's ZKresearch team has developed OVOTE${}^{(1)}$ as a solution to minimise gas consumption onchain. This is done by moving the voting procedure offchain and verifieng the result using an onchain SNARK proof. Generalpurpose SNARKs like the one of $\text{Groth}^{(2)}$, allow the proof to be verified in constant time, precisely using $3$ pairings and $t$ exponentiations where $t$ is the number of elements of the public statement.
SNARV
In an upcoming paper$^{(3)}$ we propose a general model that encompasses both anonymous and nonanonymous evoting, which we call Succinct NonInteractive Arguments of Voting (SNARV). Both OVOTE and two new protocols, BatRaVot and SchnorrVot, on which we'll ellaborate in a subsequent post, can be seen as special cases of SNARV.
A SNARV is comprised of the following algorithms.

There is a parameters generation (PPT) algorithm Gen that, on input the security parameter, outputs the public parameters pp.

We suppose that at most $n$ voters $V_1,...,V_n$, with corresponding public keys (PKs) $PK_1,...,PK_n$, can register themselves in the system at any moment. Each voter $V_i$ keeps private the corresponding secretkey (SK) $SK_i$. The pair $(PK_i,SK_i)$ is produced by voter $V_i$ by means of a setup algorithm Setup on input the public parameters pp.

From the $n$ possible PKs, an administrator may compute a census $r$ by means of a census algorithm Census, executed with input the list of all PKs $(PK_1,...,PK_n)$. The census can be used to increase efficiency by replacing the list of all PKs with a shorter string, so that verification of the election will be done with respect to the census and not the full list of PKs.

Each voting procedure (i.e. election) is identified by a public election identifier $id$. In the voting phase, a generic voter $V_i$ can submit to a Blockchain, possibly different from Ethereum, the first message $(i,v_i,Blt_i)$, where $Blt_i$ is a bit string called the ballot of voter $i$ computed by means of a voting algorithm Vote that takes as input the election identifier $id$, the voter's preference $v_i$ and its SK $SK_i$.

There is a ballot verification algorithm BalVerify that on input the PK $PK$ of a voter, an election identifier $id$, a voter's preference $v\in {0,1}$ ($0$ denotes NO and $1$ denotes YES) and ballot $Blt$ returns $1$ or $0$ depending on whether the ballot was genuinely computed by the voter in an election for identifier $id$ or not. The ballot verification allows to discard (offchain) invalid ballots, including double votes. The votes corresponding to the valid ballots can then be publicly tallied.

Let $m_0,m_1$ be the number of NO and YES cast by eligible voters and let $S_0,S_1\subseteq [n]$ be the set of indices of voters who submitted a NO or YES respectively. Thus, $m_0 = \#S_0$ and $m_1 = \#S_1$. Now, a Prover Prov wants to convince a Verifier Ver with low resources (e.g., a smart contract that implements a transfer of funds) that the election result is $(m_0,m_1)$. The prover algorithm Prov, on input $(S_0,S_1)$ is $(PK_i,v_i,Blt_i)_{i\in S_0}$ $(PK_i,v_i,Blt_i)_{i\in S_1}$, the election identifier $id$, the census $r$ and the claimed result $(m_0,m_1)$, outputs a proof $\pi$ of the fact that $(m_0,m_1)$ is the tally of the election.

There is a verifier algorithm Ver that, with RAM access to all possible PKs $(PK_1,...,PK_n)$, the election identifier $id$, the census $r$, the claimed result $(m_0,m_1)$ and a proof $\pi$ outputs $1$ or $0$ to denote acceptance or rejection of the result. If the output is $1$ the funds are transferred, and are not transferred otherwise.

There is publickey verification algorithm PKVerify that, on input the public parameters pp and a PK $PK$, outputs a bit $1$ to denote that the publickey is honestly computed with respect to the public parameters.
Security
For security, we require that no adversary is able to forge a proof for e.g., a number of YES strictly greater than the number of observed signatures for a given election.
More formally, we define a strong soundness experiment for a given SNARV. During the experiment, an adversary can corrupt voters getting their secretkeys or controlling the generation of their publickeys. For any integer $n$, a set $C\subsetneq [n]$ and a list of $nC$ elements ${SK_i}_{i\in [n]C}$, we assume to have a VoteOracle algorithm (for noncorrupted users) $VO_{(\{SK_i\}_{i \in [n]C},[n]C)}(\cdot,\cdot,\cdot)$ that, on input $(id,v,i)$, outputs $Vote(id,v,SK_i)$ if $v\in\{0,1\}$ and $i\in [n]C$ and ERROR otherwise.
Consider the following strong soundness experiment parameterized by an integer $n$, a security parameter $\lambda$, a SNARV $%(Gen,Setup,Vote,BalVerify,Prov,Ver,PKVerify)$ and an efficient adversary $A := \{A_\lambda\}_\lambda$.

Parameters Generation Phase. We sample a random string of $\lambda$ bits, $\leftarrow \{0,1 \}^\lambda$ and generate the public prameters $\textit{pp} \leftarrow Gen(1^\lambda;s).$

Corruption Phase. The adversary $A$ chooses a set of "corrupted users" $C\leftarrow A(s)$ such that $C \subsetneq [n]$.

Setup Phase. We generate public and secretkeys for all noncorrupted users: $\forall i\in[n]C$, $(PK_i,SK_i)_{i\in [n]C}\leftarrow Setup(1^\lambda)$.

Voting Phase. The adversary $A$ is allowed to query VoteOracle to produce verifiable Ballots for any noncorrupted user. Then, $A$ is required to output an election result $(id,m_0,m_1)$ together with a proof $\pi$ of its correctness and the list of PKs for the corrupted users it has chosen in the start.
$(id,m_0,m_1,S_0,S_1,\pi,\{PK_i\}_{i\in C}) \leftarrow A' (\{ PK_i \}_{i\in [n]C}).$
where $A'$ stands for $\;A^{VO_{(\{SK_i\}_{i\in [n]C},[n]C)}(\cdot,\cdot,\cdot)}$
Using the PKs from the setup algorithm together with the PKs of the corrupted users that $A$ provided, a census $r$ is created. $r\leftarrow Census(PK_1,...,PK_n)$.
 Winning Conditions. For any $v \in \left\{0,1\right\}$, let $S_v^q\subseteq [n]$ be such that $i\in S_v^q$ iff $A$ asked the query $(id,v,i)$ to VoteOracle. The output of the experiment is $1$ ($A$ wins) iff all the following conditions hold:
 $\textit{Ver}(PK_1,...,PK_n,id,r,m_0,m_1,\pi)=1$.
 $S_0\cup S_1 \setminus (S_0^q\cup S_1^q\cup C) \neq \emptyset.$
 $\forall i\in[n]:\ \textit{PKVerify}(\textit{pp},PK_i)=1$.
 $\forall i\neq j\in [n]:\ PK_i\neq PK_j$.
A SNARV satisfies strong soundness if for all efficient adversaries $A$, the probability that $A$ wins in the strong soundness experiment is a negligible function of the security parameter $\lambda$.
With this mind, we prove
$\underline{Theorem}:$ Under the Computational DiffieHellman assumption, our SNARV protocols BatRaVot and SchnorrVot satisfy strong soundness.
Conclusion
Our new model SNARV serves as a general framework for evoting protocols. OVOTE and two other voting protocols BatRaVot and SchnorrVot are examples of SNARVs and one can reason about security of these protocols in a unified way.
Furthermore, as we will explain in an upcoming post, BatRaVot and SchnorrVot improve on the gas cost compared to OVOTE when the number of voters is not too large, and offers additional security guarantees.
A short version of the document is accessible here.
References
(1) Arnaucube, Pau Escrich, Roger Baig, and Alex Kampa. Ovote (v0.5) : Offchain voting with onchain trustless execution. 2022. https://github.com/aragonzkresearch/research/blob/main/ovote/ovote.pdf.
(2) Jens Groth. On the size of pairingbased noninteractive arguments. 2016.
(3) Vincenzo Iovino, Alex Kampa and Matan Prasma. SNARV: Succinct NonInteractive Arguments of Voting (in preparation).