Loomio
December 29th, 2018 13:31

A blockchain-based voting platform

Maxime Suard
Maxime Suard Public Seen by 179

I am working on designing an open source blockchain-based voting platform. Looking for feedback and advice / AMA

MS

Michael Shea December 29th, 2018 13:41

For whom, and why?

Maxime Suard

Maxime Suard December 29th, 2018 13:47

A blockchain based voting platform where users can debate, issue proposals, upvote them and (if a threshold is reached) trigger a formal vote on these proposals.
--> Forum-like debate spaces where ideas are discussed and proposals are forged and upvoted
--> Secure, decentralized (as much as possible) voting protocol
--> Identification/authorization protocol for users to be allowed to vote

##Specifications:
#Identification/authorization of users:
--> Only citizens are allowed to access the debate space
--> only citizens aged 18/21 yo + are allowed to vote
#Voting protocol:
--> Individual votes must be kept secret at all times
--> It must be possible for a user to verify whether his/her ballot has been cast
--> It must be possible for a user to change his/her vote until the end of the vote (in order to make vote coercion more difficult)
--> It must be possible for anybody to verify the votes count after the vote
--> The intermediary result of the vote must be impossible to determine until the vote ends
--> ...

Please feel free to suggest other specs that I might have missed ;)

Maxime Suard

Maxime Suard December 29th, 2018 13:51

For everybody :) Because it's a tool that's needed if we want to implement actual democracy (!= election) and grassroots movements need a way to demonstrate a new governance model.

Marko Prljic

Marko Prljic December 29th, 2018 14:10

I came across recently a site / community with a really good way of visually showing yes/no votes on topics where you can comment/discuss as well, like Loomio or any forum. Can't find that site anymore, forgot its name.

Maxime Suard

Maxime Suard December 29th, 2018 14:19

The identification/authorization part is probably specific to local situations.

I am mostly working on the voting protocol at the moment. Here is how I see it:

Once a proposal has been upvoted enough to trigger a formal vote:

1) A group of N delegates is selected (could be random) which is large enough to be representative of the voters population. These delegates are given access to a special section of the app on which they are each going to generate a public/private keypair {pki, ski}.
They are going to broadcast their public keys pki, which are going to be combined to obtain a common public key Pk which will be used by the voters.
They are going to use a secret key sharing scheme (Shamir's secret sharing scheme) which consists for each of these delegates to generate a random polynomial function fi(x) or order M < N for which the constant parameter fi(x=0) is equal to their private key ski. They are going to chose N random values xij and send to every other delegate a different tuple {xj, fi(xj)}.
At the end of the vote, at least M out of N delegates will be needed to recompute all the private keys ski from the tuples {xj, fi(xj)}, and obtain the main private key Sk which will allow to decrypt ballots encrypted with Pk.

2) A smart contract is created which will receive the ballots form the voters, verify their validity, aggregate them, decrypt the aggregate and compute the result of the vote at the end of the voting process.

3) The vote opens.
Users authenticate on the app.
Users receive the address of the smart contract.
Users generate a public/private keypair which will be used for this vote only, and register their public key on the smart contract.
User receive the common public key Pk.
They cast their ballot, encrypt it with Pk (using a form of El Gamal crypto-system with an ephemeral key, which needs to verify multiplicative homomorphy and allow for Non-Interactive Zero-Knowledge proof that the content of the ballot is one out of several predefined choices). Predefined choices are a set of prime numbers.
They sign the encrypted ballot with their private key.
They send their encrypted and signed ballot to the smart contract.

4) Upon reception of the vote transaction:
The smart contract verifies that the ballot has been signed by an authorized user.
The smart contract verifies via NIZKP that the content of the ballot is a valid choice.
The smart contract aggregates the vote: E(V) = E(v1)E(v2)...E(vn) where E(vi) are the encrypted votes and E(V) is the product of the encrypted votes which equals the encrypted product of the votes (multiplicative homomorphy of El Gamal cryptosystem).

5) Once the vote closes:
At least M out of N delegates need to send their tuples {xj, fi(xj)} to the smart contract, which then computes the private key Sk
The smart contract then decrypts E(V) and obtains V which is the product of all votes.
Because valid votes are prime numbers the smart contract then computes the final result of the vote and broadcasts it.

Any comments on the protocol described above are welcome ;)

Maxime Suard

Maxime Suard December 29th, 2018 14:23

The part on which I am struggling at the moment is the Non-Interactive Zero-Knowledge Proof of the fact that an encrypted ballot is the encryption of one of the valid vote options.
Not sure if it actually is called NIZKP in this particular case.

It is needed because aggregating non-valid votes would mess up V and therefore the final votes count would be wrong.

Found some clues here: https://crypto.stackexchange.com/questions/59361/non-interactive-zkp-that-encrypted-additive-elgamal-message-is-in-set-of-valid-m/66028#66028

However the El-Gamal cryptosystem that I want to use needs to verify multiplicative (not additive) homomorphy

If someone knows about the detailed protocol to achieve this it would really help ;)

Posted the question here also: https://crypto.stackexchange.com/questions/66155/nizkp-that-el-gamal-ciphertext-is-encryption-of-a-prime-number-among-a-predefine

Josh Fairhead

Josh Fairhead December 30th, 2018 22:13

Two nice articles and a cartoon about voting brother:
https://pdaian.com/blog/vote-buying-on-chain-governance-and-quadratic-plutocracy/
http://hackingdistributed.com/2018/07/02/on-chain-vote-buying/
http://xkcd.com/2030 (note the ironic URL - don't be dissuaded by my response, just highlighting the problem space)

Josh Fairhead

Josh Fairhead December 30th, 2018 22:16

"It must be possible for a user to change his/her vote until the end of the vote (in order to make vote coercion more difficult)"

Perhaps it would be better to be a continuous signal thus turning the vote buy attack into vote rent attack = less feasible to pull off. I was discussing that with Jeff, the idea is called preference voting. (edit: sent Jeff an invite to see if he'll come over for a discussion, might be busy but you should have a chat if possible))

Maxime Suard

Maxime Suard December 31st, 2018 13:55

Interesting, I'm not sure I understand how this would work, will look into it ;)

MS

Michael Shea January 5th, 2019 11:29

Upvoting - private or public?

Can this be used as a form of intimidation ?

There is also the required separation of processes between registering to vote and voting. The issuance of ballots (or participation tokens) must be "firewalled" from the registration process to prevent ballot stuffing.

Another thought, to add to your list of requirements how will your system address all the means of election fraud/tampering. Here is a very partial list (there must be a more complete one online somewhere).
- ballot stuffing
- voter roll tampering - false registrations (dead persons, stolen identities,...)
- buying votes

Josh Fairhead

Josh Fairhead January 5th, 2019 20:28

This is quite interesting in signalling preferences: https://colony.io/budgetbox.pdf?mc_cid=2887bf737e&mc_eid=494078b35d

Maxime Suard

Maxime Suard January 25th, 2019 11:24

Public Gitlab repos (mostly empty for now): https://gitlab.com/echo-protocol

Josh Fairhead

Josh Fairhead January 26th, 2019 20:44

@willabramson This might be interesting to your lot ;)

Will Abramson

Will Abramson January 28th, 2019 10:39

Thanks, it makes for an interesting read. Will share with the lab. I am wondering why the cryptosystem wants to be multiplicative homomorphic rather than additive. What am I missing here?

Maxime Suard

Maxime Suard January 31st, 2019 16:09

Hey Will, thanks!

With a multiplicative homomorphic crypto system you can conduct votes with an unlimited amount of choices each represented by a prime number.
Ballots are encrypted and aggregated by multiplying the encryption ciphertexts.
Once the vote ends you can decrypt the aggregate and you get the product of all un-encrypted ballots.
You can then obtain the individual scores of each choices by computing the prime numbers decomposition of this decrypted aggregate.

So the multiplicative homomorphy takes advantage of the fact that any integer can be uniquely decomposed as a product of prime numbers.

Will Abramson

Will Abramson February 2nd, 2019 11:46

Ah I see, so the number of votes for each item is determined by the power to which the prime number that represents that item is raised?

Maxime Suard

Maxime Suard February 2nd, 2019 11:55

yep :)

Josh Fairhead

Josh Fairhead February 8th, 2019 09:00

I nearly understand this :p