Hacker News new | past | comments | ask | show | jobs | submit login
A Peer to Peer Voting Algorithm [pdf] (vixra.org)
105 points by xorxorxorxor 13 days ago | hide | past | web | favorite | 57 comments





Scrolling through the posts I haven't seen any non-democracy focussed post. So let me add other options for digital voting that might be important:

Shareholders voting for trust of the board (not sure how to say this in English). These votes are usually influenced by who owns how much stock, so it's less about democracy and more about showing publicly that you have the support of the most influential stake holders.

Instead of an open source maintainer making a biased single-person decision how two branches should be merged or how a merge conflict should be resolved it could be done via voting.

Wether a transaction is accepted or not is voted on my distributed ledger participants, wether they know it or not. The moment you put your block on top of what you perceive as the ledgers top you vote for that previous block to be accepted.

Which picture is funny enough to get onto the front page of 9gag is voted on by the viewers.

Given incomplete data and a very short time till death doctors need to make decisions which procedure to apply to an emergency patient. This could be voted on given how many talents could be connected to a case in an instant digitally.

Which players should be matched together for a new round of Dota could be voted on digitally instead of leaving that completely to a digital choice algorithm.

It could be a way to lead humans and AI into a cooperative work environment. Having a few differently trained AIs and experts voting on which path to take with the business for instance.


Here's a technical overview of the topic. It's not a trivial problem at all.

https://pdfs.semanticscholar.org/e734/d63888d81075efa0402599...


From the intro:

> Elections hold a vulnerability that can bring democracies to a halt. [This vulnerability] makes it possible for people to elect a malicious authority that will later refuse to organize future elections.

> This paper is […] aimed to tackle this problem from a cryptographic point of view. […] The algorithm still requires authorities to inscribe voters.

This sounds pretty useless. First, it requires an _already_ honest authority to register people in the system before any elections can take place. In addition, this authority needs to be trusted _forever_, as it needs to add more people to the system as they are born.

Even if this problem was solved, this paper doesn't even question what power means. If a ruling authority already has the power to stop regular elections from happening, it also has the power to ignore any results that come out of this scheme, to pressure people to not vote through new laws or force, and to imprison anyone who does.

An example (and this applies irrespectively of what opinions you hold about it): in Spain, a referendum was convoked to decide about the independence of the region of Catalonia. The government declared this referendum unconstitutional, although it still took place. People voted for independence and won. Still, the results were void, and the people who convoked the referendum are now sitting in court, charged with rebellion. Does it really matter if this referendum was held using physical ballots and boxes, or using digital signatures? You can't remove a central authority just by pretending it doesn't exist.


There's a liberal/whig/enlightenment core belief that force can be reasoned out of existence through a sufficient amount of research and debate. That asking the soldier "Why are you pointing the gun at me, your brother, for the proven-corrupt king?" will turn the gun into a flower. That believing hard enough will bring tinkerbell back to life.

Still things have gotten a lot less bloody over the last 500-years or so?

Yes but if there was solid proof it would be easier to get international pressure working on the government.

Regardless of whether this should be used to elect politicians, it appears to be a pretty interesting technical achievement. As far as I know, counting votes in public without a central authority, while also not revealing the individual ballots, has not been accomplished before.

But the code appears to be missing from the pdf and the links at the end. Has it been removed, or will it be posted later?


For something as important as an election, it should be simple enough for people to understand the process and believe in the result.

Another solution to adding more trust into the elections: People could be able to annotate their physical ballot with a token, each vote with each token is then published and people can see for themselves that their vote has been taken into account.


> each vote with each token is then published and people can see for themselves that their vote has been taken into account.

Generally this is precisely what you want to avoid because then the parties can verify who cast what vote by simple intimidation. The party in power or with physical control of an area can "check" who you voted for before providing you benefits/take revenge. This is not imagination - a lot of US democracy ran like this well into the 1920s and many non U/Canada/Western Europe democracies face these challenges.

There is a reason Indian elections happens as it does in 6-7 phases with central paramilitary forces essentially flooding the areas that are voting to prevent (realistically reduce) intimidation and strong arm, ensuring voting officials come from a different part of the country to prevent influence and mixing up counts from polling booths to reduce chances of "area" wise retribution by political parties. It is very complex and expensive but the exercise seems to give roughly what majority wants and has seen many cases of powerful strongmen and women being voted out of power.


It seems to be a common theme of western people in HN trying to protect against a malicious vote counter, often overlooking the very real intimidation problems.

I maintain that paper ballots are the best voting mechanism. They are cheap, prevent intimidation, scale and reasonably trustworthy.

I say they scale because you can parallelize easily by getting more citizens counting ballots. This is a good thing. The more people involved in counting the more you have to coerce to reasonably affect the outcome.

Electionic voting machines like in the US seem insane to me. All the power is in a select few who create the machines.

If you can't source enough trustworthy volunteers to count paper ballots then your democracy might be screwed anyways.


On the other hand, Indian elections have been electronic for almost a One and a half decades. These are standalone units with no networking. They added paper trail audit recently.

https://en.m.wikipedia.org/wiki/Electronic_voting_in_India


Sure it's possible to augment paper ballots with technology, but that just increases complication. If you still have a paper trail audit, why not just use paper to begin with? Either you audit the paper trail to have faith in the results or you trust the output of the machines.

Only auditing the paper trail when the electronic results seem suspicious is a vulnerability in my opinion.

All these technical solutions target the non-problem of counting results quickly. You can scale up paper ballot counting by including more people, which also strengthens trust in your democracy.


> you still have a paper trail audit, why not just use paper to begin with?

Basically because of ballot stuffing, booth capturing, ballot tampering, fake ballots etc etc. Paper ballots have been a major vurnerebility from experience of several decades in rough and tumble politics. The article on EVMs I linked has descriptions of it. The EVMs rate limit voting to prevent this from being a major motivation for political parties. The approach that seems to be tried and tested and working well seems to be to use dumb unconnected and robust electronic voting machines which can't be hacked without physical possession and the using massive security to prevent physical possession to attackers.


At all the voting booths I've been to in Canada it would be super obvious if you tried to stuff the ballot. Even in the latest Russian election it was dead obvious with many incidents being captured on camera. Why are people allowed to loiter around the box?

The problem is they have no protocol for better protecting the ballot box and responding to ballot stuffing attempts and incidents. If you're not going to protect the ballot box it doesn't matter what tech you use for voting.


If someone is being coerced, couldn't they just lie and say they had a different token?

Yes that works with one person-person engagement, not when an entire entire locality covered is threatened by a political party. All this and more has actually happened in the hundreds of elections in India since democracy was established leading to the multitude of checks and balances in the process

As a professional developer, I wouldn't trust myself to audit a voting system and swear on my life it's safe to use for my country.

Now, let's step back and remember that MOST PEOPLE DON'T KNOW WHAT AN URL IS. They can't tell the difference between an app and a web site. Internet, the browser and Google.

A good part of them still think the Sun goes around the Earth.

Even with current simple paper based systems, elections are being influenced. There is no way in hell that anything electronic is going to be kept safe by the general population, unless we duplicate the votes on paper for review, which for me kinda defeat the purpose of going digital.

Elections are not a technical problem. Actually the more technical you get, the smarter you try to make it, the farther away you are from helping society.

Now an electronic system to make polls for the general population, or for small entities, make sense. So it's still a good subject for research.

But if people that have a hard time to read out loud must inspect a hard drive to make sure it hasn't been tempered with, it's game over.


Votes being indistinguishable after castion is a pretty importsnt feature for hindering large scale fraud, as a second party has no way of verifying your choice afterwards.

If you generate ie. random 32 bytes attached to vote, nobody will infer anything from it, except you, who know it.

Yes, and then your coercers will ask it from you so they can verify you did as demanded. Then need to provide 32 random and unique bytes attached to a vote that has the stipulated outcome. Good luck achieving that by randomly guessing a token.

I might be mistaken. But either you have the ability to verify your specific vote was cast, for the person you expected to cast it for. Or you don't.

It would seem impossible to offer election confidence to the majority of people without a simple system that has this property.

If kidnapping and torture are on the table for your threat model. I think most people's voting record could be figured out with near 100% accuracy if they get access to your computer logins, emails, hacker news account, and all your social media accounts. Which according to your coercion model, they totally could. No need to go after your vote token specifically.

So unless the voting system singles you out in particular (which a random token wouldn't. Every vote would have one). Ruling it out as a solution because of a super low probability scenario seems like a misattribution of probability in the face of clear value (ie. easy and private verifiability by all parties).

Having secure elections is how we create a world where no one has to worry about coercers coming after them.


You underestimate this treat model. We know from the history that if votes can be checked, the misuse will increase.

* In traditional families women will effectively lose their vote.

* Vote buying becomes possible.

* fellow party or church members start to check the votes.

The ability to use smartphones to take pictures in ballot box is already threatening secret ballot. Let's remove secret ballot so that we can have secret ballot is not valid solution.


It seems like the argument here reduces to "personally verifiable votes should never exist".

> In traditional families women will effectively lose their vote.

People can lie. That's the only recourse they have today right? Would producing a "plausible deniability token" to show to adversaries suffice here to provide usable cover?

> Vote buying becomes possible.

This is already possible. Though you are right that it is not strictly verifiable today. But I would argue that we lack data on how many people would take money to vote X in todays system, and then vote Y instead and lie about it. If this set is tiny, then this problem doesn't grow much does it?

> fellow party or church members start to check the votes

This should simply be illegal. Bright line. Your vote is private and no-one or organization shall be allowed to force you to disclose it.

---

It seems again like the arguments here are sort of baby/bath water. There are outlier problems preventing this from being perfect. Yes. But the benefit of a truly verifiable election would inoculate us against mass election hacking. Which increasingly seems like a genuine threat we need to deal with. Are the outlier problems not worth the price of preserving democracy?


> There are outlier problems preventing this from being perfect

These are not outlier problems. I have been election official in Finland and it's not rare to see husband trying to make his wife to show the ballot. Smartphones are already creating problems that are hard to quantify.

The real solution comes from doing basic things right. Electoral observation can be improved. Paper ballots standard where ballots can be quickly counted using electronica counters from multiple suppliers (different parties can bring their own) can make voting both secure and safe.


Outlier probably wasn't the right phrasing on my part for this specific issue of spousal voting pressure. Thanks for calling that out. You were right to.

The way I think about this though is that we should view these concerns as needing tailored (sometimes orthogonal) solutions. There is an analog here to testimony in court. Defendants have the right to know the evidence against them. Including the identity of witnesses and the nature of their evidence and statements. This often puts witnesses at risk for retribution. It's a huge problem. But do we do away with requiring this kind of evidence disclosure? Not having it makes it easy for evidence to be fabricated without consequence. And for defendants to not know who or what is being used against them in court. This would potentially have even more dire repercussions. So currently, we find other ways to help ensure the safety of witnesses and accept this major issue.

In the same way we might find other solutions to the issue of Spousal pressure. Opt-in voting receipt print outs. Support programs for domestic abuse, etc...

This is for sure a problem. And maybe even a major one (like witness safety). But overall, the alternative of having insecure and unverifiable elections is increasingly seeming like the more important issue to address. Most complex systems are about balancing tradeoffs. And it should be unsurprising, that a stable election system is too.


I don't think, here in the UK at least, that vote fraud in counting stations and total reporting is considered a big issue.

Whereas we know that there are (patriarchal) religious groups that apply huge pressure


Paper voting is pretty effective at preventing mass election hacking.

Software can never prevent mass election hacking, as hardware can always deliberetly miss-implement your algorithm.

I'm also curious what is supposed to happen if you go check, and your vote doesn't match. Sure, the government investigates, but, a, why would you trust the government, and b, why would they trust that you weren't simply paid to cast doubt on the election?


> If kidnapping and torture are on the table for your threat model. I think most people's voting record could be figured out with near 100% accuracy if they get access to your computer logins, emails, hacker news account, and all your social media accounts. Which according to your coercion model, they totally could. [Note the removed last sentence.]

I agree, but it's not necessary to kidnap the person. It's a scary word.

A personal token makes this too easy. For example, you can be "encouraged" to send an email to bigbrother@example.com with your national ID number and your token. Or the day after the election, in each office at work everyone can just meet and show their token while cheering for the current government.

I guess that in a some society people is more careful with the things they post and the things they like in fb, and the things they say in public. At least the vote can be (almost) secret, and they can disagree safely.


Some schemes could require the person to remember a passphrase (not printed out) that is mixed in with the one-time-token to compute the final verifier token.

> you can be "encouraged" to send an email to bigbrother@example.com with your national ID number and your token

Would the system providing some sort of plausible deniability token give enough cover for this? Is this a problem at scale?

Also... they can do this to you for your email, and social media logins too right?

> Or the day after the election, in each office at work everyone can just meet and show their token while cheering for the current government.

I don't understand why this is fundamentally different than todays world where people wear MAGA hats or drive around with Obama/Biden bumper stickers. Sure it's not cryptographically verifiable. But it's certainly "good enough" for all practical purposes.


You can buy a fake MAGA hat or Obama sticker. The ability to lie about your vote is a feature not a bug.

---

If each one has a secret passphrase, nobody can verify that the total is calculated correctly.

If people can choose their own passphrase, they can be forced to use one. I like "Fr33dom!"

If the passphrase is calculated automatically, just make the combination of the token with a different passphrase generate a nonsensical result (if you have 10 parties, generate a number between 1 and 100000 for security reasons), so people can't lie. And make people send the email with the national ID, token and passphrase.

Here in Argentina the old method (100 year ago) to vote was that everyone go to the local voting site, and everyone vote in public raising their hand, someone count the votes and send the result to the central location. (The historical details may be inaccurate. But it was something similar.)

Obviously, people can be forced to not go to vote, or people that voted against the local political chief can be pressure to change their votes, or never vote again, or just hit until they understand their error.

It was a long fight to get secret votes, some people even died for the right of a secret vote. I guess other countries have similar stories.

It's difficult to imagine the problems without a recent similar story in your own country. Let's assume you are from USA. Just imagine that during McCarthyism people that were requested testify in the committee has to first say their national ID, token and passphrase to be sure that they didn't vote for the Communist party. Anyone that refuses gets blacklisted automatically for national security reasons.


We seem to be focusing on defending against different things. I am focusing more on mechanisms to defend the integrity of the election itself against hacking or election fraud. Which seems like a dominating concern in the modern context.

Different threats require separate considerations for sure.

To be crystal clear. I'm still for secret voting, and being able to lie about your vote if you want to. But without an ability for the voter to verify their vote, you must trust the entities themselves that are holding the election. Both that they are acting in good faith. AND that they managed to secure the election against outside tampering. The very people that you are worried might compel you to declare your vote are the ones running the election systems themselves in many situations.

We need to be able to operate with less trust here, not more.

> If each one has a secret passphrase, nobody can verify that the total is calculated correctly.

It's possible we are misunderstanding each other. There would be a verifiable ledger. With opaque tokens for each vote. The total can be verified by counting. Just like normal. We could use our signature method of choice to sign and verify the integrity of each vote and all the votes. The body holding the election would be able to verify the total counts are correct and not tampered with.

For a specific vote, an opaque identifier that nobody except the voter can resolve, provides a mechanism for the voter to self verify their vote was counted in the way they expected.

A passphrase was just one idea to avoid printing the token on your vote receipt. But if we really want to go down the rabbit whole of having cover. There are many other ways to provide plausible deniability. You could opt to not get a print out of your token. And your deniability would be you don't have it, and you can simply lie about which vote is yours (even though you know the one that is yours).

> It was a long fight to get secret votes

I'm still saying we keep voting secret. What we are discussing is the ability for a voter to verify their vote was counted. But it's still meant to be secret. In fact, something analogous to the 5th amendment to the constitution could help enshrine the right to a private secret vote as a fundamental right.

> Just imagine that during McCarthyism people that were requested testify in the committee has to first say their national ID, token and passphrase to be sure that they didn't vote for the Communist party.

We make it a constitutional right to have your vote be secret. Make this clearly illegal. If you are worried about the central government not obeying laws, then nothing really helps you. The central government ultimately wields the final say in all matters here. They can put you to death if they like. A verifiable election system is meant to help ensure we never devolve to a government that does what you are worried about.

---

Ultimately all of your examples about being forced to declare things apply also to your credentials to your personal devices and online account. All of which contain more less enough information to both figure out what your vote was, and much more.


You can use zero knowlege proofs for that, you don't need to reveal which vote is yours, just the proof that you've voted.

This seems to be a favourite topic for people here - make votes able to be checked by voters.

I've seen many proposed implementations but they all fail because if I can prove my vote to myself in any way, someone else can make me prove it to them either to buy or coerce my ballot.


Not necessarily. You could provide people with a 4 digit code they can use alongside their id to verify that their vote was counted as they intended, but also give them access to a tool that allows them to receive a code that “proves” their vote was counted for any arbitrary party. That way you can verify you own code because you know the real reference code, but anyone else can’t rely on your vote truthfully being anything beyond them trusting you, which is already the case for the current system.

Not sure I'm seeing the 'proof' there. By what mechanism do these two codes prove anything much?

If the 'real' code shows one thing and the 'fake' codes another what assurance do you have that the counting was done with your 'real' code and the voting machine didn't put another one in there?


Here's one way to do it that requires basically zero trust in the software:

1) When voters enter the booth, they throw a large number of multi-sided dice.

2) The resultant throw is scanned via computer-vision. Voter verifies it is correct, and it becomes the voter's ID. Voter votes normally and the vote is recorded alongside that generated "ID".

3) The voter receives a print-out that contains their (ID, vote), however it is randomly shuffled in among other real (ID, vote) pairs. The print-out is guaranteed to have at least one vote for each candidate.

4) The entire list of (ID, vote) pairs can be published nationally. Everyone can verify that the right number of votes were counted, and that their vote was accurately counted since they can find both their ID and vote in the national list.

They can show their receipt to others but cannot prove which one of the many IDs on the receipt was actually theirs.


OK, OK, thankyou!

I can see that working, particularly part 3 there being key.

Seriously I've been asking for years and this is the first time anyone's actually spelled out a scheme that allows the person to go back and prove the vote to themselves and have genuine plausible deniability to others who may seek to coerce them. Thanks :)


A simple, two-option system that allows for private vote verification:

  Vote: 0 for Gore, 1 for Bush
  Provide, in the polling booth: a random salt of either 0 or 1
  Publish: vote XOR salt
Now, if you want to lie about what vote you cast, you also lie about the random salt. But you can always check for yourself.

Now, the issue becomes obvious - if someone can falsify votes, why can't they falsify salts as well? Less obviously, this is true of any verification system - abstractly, you can always count the vote one way, and "verify" it the other way. So what you have to do is have completely different possession chains for the vote roll and the salt roll. Make it so that at no point does any one person have access to all three of 1) the voter id, 2) the vote cast, and 3) the salt. This means that nobody has the required information, or access, to undetectably falsify a vote.

Extending this to handle more than two options, and making it easy enough to comprehend that the average voter won't get caught out if they try to lie, is left as an exercise for the reader. But it's possible.


If nobody has access to all three pieces of information, including the voter, how can they verify their own vote?

The voter, and only the voter, has access to all three pieces of information.

If they have access, so does someone trying to coerce them...

No, they don't. That's the point. The voter can lie about the salt. Only the voter knows they are lying, because they were alone in the polling booth.

Then how can they be sure their vote was counted correctly?

By comparing their private knowledge of 1) who they voted for and 2) the salt they were shown in the booth with 3) the public hash of the two.

In any case it was only meant as an existence proof, not a practical system. I like aeternus's suggestion much more, since it has the useful property that everyone can see all the votes - just not whose is whose. (Although I'm not sure what function the receipt serves)


> I've seen many proposed implementations but they all fail because if I can prove my vote to myself in any way, someone else can make me prove it to them either to buy or coerce my ballot.

There is a way to prove that your vote was counted without being able to prove what you voted for by using homomorphic encryption. So, if someone wanted to coerce you or pay you for voting at all for whomever you want, they could do it, but that's fine. Microsoft is actually working with Galois on a system operating on this principle[1], and here's a good video explaining the basic concepts of how it works[2].

[1] https://blogs.microsoft.com/on-the-issues/2019/05/06/protect...

[2] https://www.youtube.com/watch?v=BYRTvoZ3Rho


That's kind of interesting and I can see that being a good halfway point, to prove you weren't disenfranchised, at least.

>For something as important as an election, it should be simple enough for people to understand the process and believe in the result.

In my county in California, the first voter to arrive has the responsibility of verifying that the ballot scanner is empty and that its printout reads all 0's. That person then serves as a witness to the poll workers applying tamper-evident seals to the scanner door and data module.

This takes no more than two or three minutes to accomplish, and anyone with reasonably working eyeballs can carry this out. You lose this scrutability when you introduce cryptographic proofs and multi-step algorithms into the process.


How does anybody know it's not just a friend that was told to come early? This sounds like such a ridiculously easy rule to get around that it's almost unnecessary to even have it

I mean anything is easy if you have a perfect conspiracy between the precinct workers, county inspector, results auditors, and public witness.

Yeah, but the conspiracy to carry it out would need to be absurdly large.

This paper doesn't address the first step; but takes issuing of public key cryptography as fiat. If we can solve this first problem the consequence ranges far beyond democracy.

Interesting, I think it can be applied to the current political crisis in Algeria https://medium.com/hirak-tech/alg%C3%A9rie-comment-faire-soi...

One thing i was thinking about yesterday: apply Netflix’s interactivity functionality from Bandersnatch to political debates and rallys such that viewers can make choices and answer polls and vote in real time as they watch a debate or townhall or anything like that.

This is very interesting to me since I'm actively watching elections being stolen by the central govt in India. This is an amazing idea. It would be causing a great amount of debate when I introduce this in my friends group!!!

Could tell more on election stealing in India. There were some allegations about the correctness of EVMs. Is there any thing more substantive than that.

There is a more simple way to do basically the same thing:

See: https://news.ycombinator.com/item?id=19137493


I don't think your solution works.

Suppose N=20. Imagine the server and 19 of the voters are compromised, and are trying to de-anonymize your vote. It "randomly" creates a group composed of you and 19 voters that are collaborating with the server to de-anonymize your vote.

Assuming that the server has M collaborators, it can discover the votes of M / (N - 1) of the citizens.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: