Blind-OVOTE, a voting rollup with voter anonymity
Aragon ZK Research guild presents Blind-OVOTE.
TL;DR: Blind-OVOTE is a L2 voting solution which combines the validity rollup (~“zkRollup”) ideas with blind signatures over elliptic curves inside zkSNARK, to provide gasless anonymous voting with onchain binding execution on Ethereum. Due its drawbacks it does not fit for all use cases, but it can be useful for some use cases.
We present Blind-OVOTE, a L2 validity rollup combined with blind signatures over elliptic curves inside zkSNARK. The main objective is to provide offchain anonymous voting with onchain binding execution on Ethereum, without getting into costly recursive proofs approaches.
In this post, we provide a high level overview of the system, its properties and its drawbacks. We also provide a protoype implementation of the system in Rust.
In the section Conclusions we provide also a comparison with the OVOTE presented in July.
The full design can be found in the technical document: https://research.aragon.org/docs/blind-ovote
OVOTE was presented last July, and is a L2 design for voting using validity-proofs (zkSNARK proofs), which is similar to a ‘zkRollup’ but for voting. The main idea is that the votes are aggregated offchain, and proved onchain through a zkSNARK proof, resulting in constant gas costs while scaling up to thousands of voters through a single Ethereum transaction.
→ More details can be found at:
- Overview article: https://research.aragon.org/ovote.html
- Document: https://research.aragon.org/docs/ovote
2.2. Blind Signatures over Elliptic Curve
The main idea is that one party has a message and blinds it, then sends the blinded message to a signer. The signer generates a signature of that blinded message, who sends it to the initial party, who unblinds the signature, obtaining a valid signature for the original message, while the signer does not know what it is signing, but the signature can be verified for the original message for the signer’s public key.
We will use this concept for authorizing users public keys without the authority knowing them.
For this project we use the arkworks set of libraries, making use of the Groth16 scheme and the pairing-friendly bn254 elliptic curve, as is the only current available pairing curve in the EVM and we want to verify the proofs in Ethereum. This constrains the other cryptographic primitives we use, as for example we use Poseidon hash over the scalar field of bn254, and the BabyJubJub elliptic curve for the signing keys.
3. System overview
The complete flow can be found at section 4 of the Blind-OVOTE document.
3.1. Contract timeline
3.2. Circuit proof
The SNARK circuit defines a set of constraints that must be satisfied in order to accept a given result in the smart contract.
The checks defined by the circuit constraints are:
- Voters public keys and weights are signed by the Authorities keys
- Vote values are signed by each corresponent Voter key
- Vote value is binary (either 0 or 1)
- Result is correct by combining votes with weights
- There are no repeated Voters public keys in a results publication
The following properties are shared with OVOTE:
- Universal verifiability The way we use the validity proofs makes the results verfiable by any actor
- Offchain/gasless voting: users vote offchain, and the Blind-OVOTE node aggregates the computation & verification of all the votes and census-proofs, in a small zkSNARK proof (Validity-proof), which is sent to the SmartContract.
- Scalability: in a similar fashion than validity rollups (~‘zkRollups’) and OVOTE, Blind-OVOTE scales to thousands of users under a single ethereum tx (results + proof publication).
- Chain agnostic census: the census is build off-chain, and the zkSNARK proof of correct results computation can be published into any EVM chain (furthermore, into any chain that supports Pairing computation). So a Blind-OVOTE census could be used in Ethereum mainnet, but also in Polygon or GnosisChain.
In addition, Blind-OVOTE has the following property:
- User anonymity: by the usage of blind signatures, user identity is kept anonymous in front of all the different parties (Authority, Rollup Node, Ethereum).
In the cases where the census is accepted to be correct and the Authorites to perform honestly (assumption that can be minimized with the implication of several Authorities), the following property also applies:
- Binding execution: Due to the universal verifiability property, the proof verification can trigger on-chain actions (e.g. moving funds of a DAO) in a trustless way, directly from the voting process result.
As with OVOTE, there some UX friction when having an interactive census creation due the nature of the scheme of blind signatures.
One additional drawback of the current design is that that the census is not auditable, so that the unforgeability property is lost when Blind-OVOTE is used with a single authority, which would be able to add fake voters and it would not be possible to detect this. A mitigation to this was described in the section “Multiple Authorities” of the Blind-OVOTE document.
4.2. Gas costs
As a validity rollup, gas costs of Blind-OVOTE are mainly the cost of Groth16 zkSNARK onchain verification. At the current EVM status, verifying a Groth16 proof is about 250k gas.
This cost is constant for any number of votes being aggregated.
We did a protoype implementation of this scheme using arkworks.
First we implemented the blind signatures verification scheme inside a snark circuit (R1CS constraints), together with a Rust library implementing the whole signature scheme over the BabyJubJub elliptic curve.
And secondly, we implemented the Blind-OVOTE scheme, making use of the blind-signatures and adding all the vote verification logic inside the snark circuit.
Both implementations can be found in the following Github repositories:
- aragonzkresearch/ark-ec-blind-signatures`: Blind signatures over elliptic curve implementation (native & R1CS constraints)
- aragonzkresearch/blind-ovote: Blind-OVOTE scheme implementation, contains the library to be used in Voter’s browsers, Authority server, and Rollup node.
6. Conclusions and comparison to OVOTE and future work
Both schemes, OVOTE and Blind-OVOTE, aim for scalability, where users vote off-chain but the results are verified on-chain, aggregating the census proofs verification and voters signatures in a single zkSNARK proof which is sent in a single Ethereum transaction.
The main difference between OVOTE and Blind-OVOTE is the approach used for the census.
In the case of OVOTE, the census is contained in a MerkleTree which can be publicly audited. Anyone can verify that all of the voters’ public keys are in the Census Tree and that no extra keys were added.
In the case of Blind-OVOTE we use blind signatures over the user’s public keys. The benefit of this approach is the voter’s anonymity, but it comes with the drawback of non-auditability of the whole census. This is mitigated by having more than one Authority participating in the census creation, as explained in section “Multiple Authorities” of the Blind-OVOTE document.
As previously mentioned, Blind-OVOTE does not use recursive proofs to keep the number of constraints low while using R1CS tooling. A potential next step is to look into recursive proofs as they can enable, for example, the voters to generate a zkproof of membership in the browser without revealing who they are in the census (built for instance as a MerkleTrees). These zkproofs can be aggregated into a single zkproof which can then be verified in Ethereum. Proof recursivity would also allow for further designs where different results from different aggregators are merged into a single proof while avoiding double vote counting.
While not an ideal solution, Blind-OVOTE might be another step towards a future of highly scalable voting systems with off-chain aggregation and on-chain verification in Ethereum.
Technical document: https://research.aragon.org/docs/blind-ovote