ZKP for the multi candidate elections

[descampsk]

Hello !

I am trying to extend your voting protocol with multiple candidates. I read the following papers :

• Anonymous voting by two-round public discussion - F.Hao, P.Y.A Ryan , P. Zielinski
• Proofs of Partial Knowledge and Simplied Design of Witness Hiding Protocols
• A Secure and Optimally EfficientMulti-Authority Election Scheme

But I can not achieve the ZKP protocol for multiple candidates. I understood the operation of the ZKP 1 out of 2 to ensure that the voter votes yes or not, but this protocol only works for two choices. When we got n Generators Gi = g^2im for the candidat i. For n choices, I think we should have 2n verifications :

• a1 = g^r1 x^d1
• b1 = h^r1 (y/G1)^d1
• a2 = g^r2 x^d2
• b2 = h^r2 (y/G2)^d2 ....
• an = g^rn x^dn
• bn = h^rn (y/Gn)^dn

But i don't achieve a way to calculate each rn and dn.

Can you give me a hint or an explication if you understand this 1 out of n ZKP ? I didnt find any informations on internet :(.

Thank you !

Kévin

[stonecoldpat]

Hey!

Yes! This is feasible to do, but that approach is quite heavy weight.

Another approach is to run an election for each candidate.... i.e. vote "yes" or "no" for each candidate. This still allows for multiple votes (i.e. I could vote "yes" for all candidates).

If we want to restrict the number of "yes" votes... i.e. we can only vote "yes" for 1 out of n candidates.... then a Chaum-pedersen equality proof must be used.... to show that the summation of all votes by the voter equals 1 (or k -> the threshold you allow).

I am about to board a plane - I'll spend some time explaining how to do the Chaum-pedersen equality proof approach in a day or two. Although more information can be found here https://eprint.iacr.org/2016/670 if needed before then.

[descampsk]

Thank you for your answer.

The Chaum-pedersen equality proof is used in the case we run an election for each candidate ?

I prefer to use the other approach with only one election because i use a system to allow the voters not to vote. I use a secret sharing protocol to share the private voting key of each voter between n administrators, thus the n administrators can cast a null vote instead each voter who hasn't cast his vote. A ZKP is used to verify that the administrator cast a null vote.

I will read this paper to try to understand better each solution.

If you can explain me the ZKP of the unique election's approach, it will be very appreciated :).

[descampsk]

I try this protocol and it seems it works :

ZKP multiple vote_eng.pdf

Can you give me your advice and tell me if you think it works really ? :)

[stonecoldpat]

Hey,

I've not forgotten about this issue. I've been stuck travelling past two weeks. I'll get a proper detailed reply shortly.

[mnkhbmb]

Hey guys, Any solution found?

[descampsk]

I use the protocol explains in the pdf two comments up. As said, it seems to work, but i don't have the time to prove that it works 100%.

[stonecoldpat]

Hey!

OK. So the table in the .pdf you sent looks like the table from the original paper here: http://homepages.cs.ncl.ac.uk/feng.hao/files/OpenVote_IET.pdf

I can see you are trying to perform the "a unique generator for each candidate" approach (i.e. the second option), and you want are trying to construct a 1 out of k zero knowledge proof, i.e. that you voted for one of the candidates.

It could be the notation - but when you describe g^{1} and g^{2} - do you literally mean g x g? or do you mean a unique generator such as g{2} = H( g || 2)? It is important that it is a unique generator, and not just g x g. So something like g{k} = H(g || k), where k is the candidate index. Although you need to confirm that if x = g_{k}, and we have point = (x,0) - that this is a real point on the curve. Note secp256k1 has the nice property that every point can effectively be a generator.

I've eye-balled and played on paper with the one out of k zero knowledge proof in the .pdf - it looks to be ok. You did say it is working right? I need to spend some time re-reading http://www.win.tue.nl/~berry/papers/crypto94.pdf to fully confirm that though (I have never implemented the k proof approach). I'm more amazed you managed to get that many variables into solidity? I barely got the 1 out of 2 zkp to fit!

The generator approach is a bit messy though in terms of trying performing an exhaustive search.... I'd propose doing the exhaustive search offline and then sending v' (i.e. the votes) to the contract to verify that g^{v} = g^{v'} - also some logic to count the votes up (i.e. 5 yes votes for candidate A, 10 yes votes for candidate B) - then the contract can independently verify the number of votes.

There are two easier ways to do multi-candidates (also outlined in that paper).

1. You can run the protocol in parallel - where you vote "yes" and "no" for each candidate. But - the person could vote "yes" for multiple candidates this way. I think another zkp can be attached to restrict the number of yes votes - Edit: I mentioned how in an earlier command. Use an equality proof.

2. You can use the Baudron et al approach - where each candidate is 2^{0}, 2^{m}, 2^{2m}... and m > n, where n is the maximum number of potential voters - this lets you deal with smaller numbers and should be easier to perform the exhaustive search.

I'm going to chat with Feng/Sia about this more. I'll drop a message when I do.

[stonecoldpat]

Also for the "spoiled votes". The election administrator can just release the private key for that - and the contract could count that as a no vote (i.e. creates a dummy no vote). No ZKP required there.

[descampsk]

Thank for your answer.

There is a error with my notation: it is g_{2} and not g^{2} = g x g.

And i use the Baudron et al approch where g{k} = g^{2^{k*m}} to calculate the result of the vote. Then g{k} is on the curve because g is generator of the curve and we just multiply g by an integer.

With this approch, it's no more possible to do the tally inside the Smart Contract. As you said, I insert a java child process in my application to compute the exhaustive search externaly and then, the Smart Contract only verify that this result is egal of the sum of all the votes.

With my tests, it seems it works. But i didnt test all possibilities ^^.

To resolve the problem of the solidity variables, i used 2d array because one array2D[10][2] can contains 10 elliptic points. It was not easy but i manage to write the zkp function in solidity ^^.

[stonecoldpat]

I just skimmed the function you wrote at: https://raw.githubusercontent.com/descampsk/wavevote/master/WaveVote_Contracts/WaveVote.sol

So it looks like you can support up to 10 candidates? What is the gas cost like - I imagine it must be exploding? The indentation should be fixed to make it easier to read too.

Edit: looks like msg.sender is there; i'd still recommend contract id in the challenge hash.

I'd advise using the .IsPubKey() method for every public key you are using... make sure they are valid points on the curve.

Hopefully soon I'll update the library to use the native elliptic curve maths - this should greatly reduce your gas cost (the 1-out-of-2 is 1.3m gas cheaper natively) - and I'm hoping to do it in a plug and play way.

[descampsk]

You are right ... The gas cost is exploding ... :( For 5 candidates, the verification of a vote costs around 8 Million gas ...

Actually i can support more candidates I think. The problem is that I didn't manage to use a 2D dynamic array in solidity :(. It's why I fix a limit to 10 candidates. But I can easily upgrade this limit.

I don't know why there is an indentation problem on GitHub. On Eclipse, it was correct. I will try to fix this.

I already include the msg.sender in the hash. But I can include the contract address too.

Ok, sometimes i use the .isPubKey, but i should use it systematically.

Oh that's a really nice news :) ! Don't hesitate to put a comment here when you will have updated the library !

Thanks for your remarks !

[teslaji]

Hi

I am following your project since many months. Saw your 2 videos and I am trying to write master thesis on multi candidate decentralized voting on ethereum over federated clouds. I saw that you used zkp for voter verification , which can be very heavy as you aforementioned.

However I was going through some other possible solution and what struck me that, my country (India) provides AADHAAR API which can be used for voter AUTH every time when voter is asked to vote. Which can completely eliminate the extra gas problem and zkp issues.

It is just that I am not sure whether it answer the problem of decentralization. I would be happy to get some guidance.

edit

forgot to mention, you are genius and thank you.

[stonecoldpat]

hey hey

Something like AADHAAR API would useful to authenticate the whitelist of voters with their Ethereum account (assuming we could somehow prove to the contract that AADHAAR API does indeed authenticate them).

The first zero knowledge proof (schnorr signature) i to authenticate the voter with their ephemeral voting key (i.e. this key is one-time use) and the second zero knowledge proof is to prove an encrypted vote is yes or no (or in the multi-candidate case; that it is one of the candidates). So I don't think it would really help there.

forgot to mention, you are genius and thank you.

That is really sweet! but this voting system would not have been possible without my amazing collaborators and PhD advisor.