Blind-OVOTE: OVOTE with Blind Signatures for voter anonymity

🛠 Product Discussions & Suggestions Technical
1

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.

1. Introduction

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

2. Preliminaries

2.1. 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:

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.

2.3. zkSNARKs

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

blind-ovote-overview
blind-ovote-overview642×705 51.7 KB

The complete flow can be found at section 4 of the Blind-OVOTE document.

3.1. Contract timeline

blind-ovote-timeline-of-a-multisig-process-in-the-contract
blind-ovote-timeline-of-a-multisig-process-in-the-contract926×452 21.9 KB

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

4. Properties

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.

4.1. Drawbacks

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.

5. Implementation

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:

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.

More details:

Technical document: https://research.aragon.org/docs/blind-ovote

blind-ovote-document-screenshot
4 Likes
2

Hey Arnau!

First of all, thanks a lot for posting this. It’s simply wonderful to read about new advancements in privacy centric governance solutions. :heart:

While we don’t have the “end solution” involving recursive proofs, solutions like this may be interesting for some use cases. As we have seen, most of the times the market highly value solutions that may not be the best in terms of guarantees, but are simply good enough in relation to the pain they solve.

You propose as a way to mitigate the Census creation limitation (authority) may be to have “multiple authorities”. Those could either run on trust (trusted members from your community), but could they also run on economic incentives?

For instance, what about a third party providing census generation services, and charging a fee for that? I am aware it’s not the ideal solution, as a 100% trustless system would be preferred, but while we don’t have that, could this be a “good-enough” solution?

Basically, the business model of these “census service providers” could be to simply sign blind signatures in exchange for a small fee. The value they provide is basically to act honestly. They could even put collateral at stake, and if they behaved badly, they could be slashed, therefore aligning incentives.

The smart contract holding the collateral could be plugged in to a dispute resolution system to handle disputes.

Regarding limitations, this could be sensitive to bribing. In some cases, a briber could collude with the authorities if the economic gain of behaving badly was > than the cost of slashing. In order to mitigate this, DAOs could assess the risk of using this voting solution by comparing the economic value/impact of a potential vote vs the collateral staked by Authorities. ANT could be used as collateral.

Regarding use cases, this could work for voting that had censuses medium to large, not for very small censuses. For those, anonymous onchain capabilities that offer Ovote are probably enough.

Curious to hear your thoughts on this!

1 Like
3

Hi Arnau,

This is brilliant! As always amazing work.

A few quick questions:

  1. is there still friction in the census creation where all the voters would have “sign up” or “reconnect” their wallets?
  2. When you say multiple authorities, is there a preferred # for efficiency and accountabilty?

If anonymous voting becomes a key pain-point due to regulation, @Joan_Arus comment may prove fruitful. It would be great to map out what the costs (both financial and in sweat) would be to provide these services (after verifying a potential client base).

Thanks Arnau!

1 Like
4

@Joan_Arus :

Those could either run on trust (trusted members from your community), but could they also run on economic incentives?
For instance, what about a third party providing census generation services, and charging a fee for that? I am aware it’s not the ideal solution, as a 100% trustless system would be preferred, but while we don’t have that, could this be a “good-enough” solution?

Right, it could be analyzed. Kind of an “Oracle that builds the Census”. Initially OVOTE & Blind-OVOTE were designed for use cases where the community itself can build their census, without needing for example token-based voting. But it is in the lines of research to find trustless approaches for token-based censuses, and meanwhile maybe a oracle approach as you mention could work.


@Anthony.Leuts :

  1. Yes, in fact in Blind-OVOTE the voter needs a bit of more synchronous interaction with the census creator (compared to OVOTE)
  2. Yes, as more authorities, the bigger the proof generation time. Aproximately with 6 authorities it should be doable at least for censuses of 5000 voters (which gives similar proving cost than 8000 voters with 3 authorities for example).

In general, Blind-OVOTE can be seen as another small step in the direction of scalable offchain-voting with onchain trustless-execution, with the extra feature of anonymous votes being aggregated through a single eth tx (although drawbacks with the census), but still far from the end/ideal design as it has the mentioned drawbacks.

2 Likes
5

Cool thanks!

1 Like
6

Hello, this is excellent research! Could you please ellaborate on exactly what it looks like to “synchronise interaction with the census creator”?

Also do you have any examples you can think of of organisations who would be the first to consider using this tool?

Thank you!

1 Like
7

Right, in OVOTE the census is created from voter’s public keys, which are inserted into a MerkleTree, and the Merkle-Root is stored in the smart contract. Then the voters just need to retreive their MerkleProofs from the CensusCreator (and furthermore, the MerkleTree could be directly published), which will be used to generate the zkSNARK proof of membership.
On the other hand, in Blind-OVOTE the census is created in a more interactive approach, where the voter authenticates with any choosen mean with the Census Creator (eg. with Ethereum signatures, traiditional OAuth, email, etc. Anything that allows the CensusCreator to know that the user is who is claiming to be), then the CensusCreator gives a ‘blind-sig-token’ (an elliptic curve point needed to blind the msg to be signed) to the voter, the user then blinds their publickey (to be used to vote, only known by the voter), and sends the blinded pubK to the CensusCreator. Then the CensusCreator blind-signs the package and gives it back to the user.

So, in OVOTE the MerkleTree can be built and published (on a server, on IPFS, etc), and the voters just need to retreive their MerkleProofs (siblings). But in Blind-OVOTE, it is needed a bit of more synchronous interaction between the voter and the Census Creator, in which first, the voter requests the ‘blind-sig-token’, then the voter sends the blinded-msg, and finally the authority sends back the blinded-signature.



Regarding examples of organizations who would be interested in Blind-OVOTE: clearly not real DAOs, understanding that DAOs need fully trustless systems and the census approcah of Blind-OVOTE would not fit there. But, there might be cases which already have a more trusted & centralized nature, such as a company (imagine a SmartContract controlled by all the workers of a company). For those cases, as the Census is already determined by an Authority (eg. who is a worker comes determined by the authority of the company itself), if needed by many authorities (like 3 different keys). For these kind of cases then it might fit a census approach such as in Blind-OVOTE, as probably having anonymous voting while aggregating all the votes in a single Ethereum transaction (to save gas) is a combination of features needed.
But, we are aware that this does not cover the main DAOs usecases, and is in our plans to keep researching in the direction of having fully-trustless voting systems, with anonymity while aggregating the computation in a single proof which is sent onchain.

3 Likes
8

Thank you :slight_smile: So happy to see the kind of work you are doing!