What cryptocurrency designers need to know about voting

Sep 3, 2017 · 5 min read

So you want to create a new cryptocurrency, one that will last for the ages.

You can’t possibly anticipate every challenge it will face in the future. So there has to be some orderly way for the underlying code to update; something that resists being taken over by a minority interest.

You might be tempted to make it a dictatorship by some person or people you really, really trust; but in the long run, no matter how much you trust the person with that power today, the power itself would still be a single point of failure.

You might be tempted to say that you don’t need to plan for change, because if change is necessary enough, most people will agree to a hard fork, and the minority that remains will be left without value. But that is merely passing the buck to the future; in tough cases, how do people decide which side of the hard fork is more legitimate?

The obvious solution is to use some kind of voting. And that immediately puts you in the realm of voting theory.

If you know just one thing about voting theory, it should be: plurality voting is a terrible method, and there are many better options. But I’ll assume you already knew that, and were never considering using plurality. The next basic fact about voting theory is: voting between two options is easy, between three or more is hard.

If there are are only two options, just let each person pick one, and the majority rules. If you want, you can also set some higher supermajority threshold for overturning important parts of the status quo. In any case, the votes to change will either be above the threshold, so you change, or below, so you don’t; there are no other possibilities.

But with three or more options, there are a series of impossibility results that say that there’s no one perfect voting method. To my mind the most central of these is not the famous Arrow’s theorem, which only directly applies to ranked (ordinal preference) voting methods, but the less-known Gibbard-Satterthwaite theorem, which applies to any voting method. This states that with three or more voters and three or more options, there is no (non-dictatorial) voting method that is immune to strategy; that is, where each voter’s rationally optimal vote does not depend on how they think the others will vote.

For instance, in plurality voting, the obvious strategy is, guess which two candidates you think will get the most votes from other voters, and then vote for the one of those two that you prefer. If everybody does that, then being perceived as one of the two frontrunners is a self-fulfilling prophecy; even if everybody agrees that they’re two of the worst options, moving to a better option requires a simultaneous collective decision to change the perceived frontrunner(s), something that can be nearly impossible in practice.

Note that the above strategy is especially problematic because it’s dishonest. Voters not just semi-honestly saying they like a frontrunner as much as their true favorite, they’re dishonestly claiming to like the frontrunner more. That dishonesty makes any pathological equilibrium much stickier; it makes it a “strong equilibrium”. (In voting, anything that’s not a tie is an equilibrium, so you need to talk about “strong” equilibria.)

Is there a voting method which doesn’t encourage dishonest strategy? Yes; approval voting. (Also score voting, but any strong equilibrium of score voting is approval voting, so we’ll focus on approval). If voters have reasonably good information and a Condorcet winner exists, then the strong equilibrium of approval voting is to elect the Condorcet winner.

Can you do better than approval? Yes, probably. For instance, using the most realistic scenario and strategic models, Condorcet voting, Star voting, and 3–2–1 voting all have better voter satisfaction efficiency (that is, expected utility). Of those, I like 3–2–1 for the simplicity of the voting process and presentation of outcomes; but in a crypto context, where voters might have a higher tolerance for complexity, a Condorcet method (probably Ranked Pairs) might also work.

….

If you get the voting method right, is that all? Perhaps not. You might still worry about “tyranny of the majority”, where a majority votes to take from a minority in a way that is ultimately negative-sum for utility. Some might argue that a rational majority won’t tyrannize, because they know that it’s a pandora’s box; once the democratic theft starts, it won’t be long before almost everyone are losers. But still, additional safeguards are certainly reasonable.

For example, imagine a proposed protocol change that took all the coins from everybody who had voted against the proposal and redistributed those coins to those who voted for it. Rationally, you should vote for this proposal; if it fails, you are OK, and if it wins, you certainly don’t want to be one of the ones that voted against it.

Essentially, this proposal amounts to automated vote bribery. There’s already a solution to safeguard against bribery shenanigans in real-world elections: the secret ballot. Is that possible in a cryptocurrency?

Assuming the election is happening on the blockchain, it might seem hard. After all, in that case, all ballots must be posted publicly.

That’s where “homomorphic encryption” comes in. If C(cleartext, public key) is the encryption function and D(ciphertext, private key) is the decryption function, then homomorphic encryption means that there’s some way to implement “+” so that D(C(A,pubk)+C(B,pubk),privk)=A+B. That is to say, you can add things without decrypting them… such as vote tallies.

Using homomorphic encryption, voters could publicly post their encrypted ballot, along with a “zero-knowledge proof” (one that didn’t break the encryption) that the ballot was legal. Then anybody could add up all the ballots to get the encrypted tally. The election authority could then post a result, along with another zero-knowledge proof that the result agreed with the encrypted tally. Code on the blockchain could then check those proofs and automatically implement the voting outcome.

Now, homomorphic encryption is cutting-edge stuff, and any specific scheme could in principle be cracked in the future, breaking ballot secrecy. But in order to prevent automated bribery, the encryption only has to be good at the time the election is announced. Cracking it later would compromise secrecy, but wouldn’t allow auto-bribery.

Also, of course, people could break their own ballot secrecy by posting videos of themselves voting (or something like that). But refusing to post such video would still be (roughly speaking) a strong equilibrium which still prevented automated bribery.

So, are there any cryptocurrencies that are getting this stuff right? If you’ve read this far, and you keep up with the latest big ICOs, you probably know the answer: Tezos. If any other coins are anywhere close to that sophisticated about governance, I don’t know of them.

Tezos is using approval voting initially. That’s a reasonable starting point; since they can vote to change their own rules, they’ll probably end up improving that method appropriately. But they should definitely be thinking about the issues above.

Written by