# An election protocol for implementing random ballot in an accountable manner

Long ago, I proposed that the use of random ballot was a good way to elect a house of representatives. At the time I was only half serious. These days I genuinely think it’s a good idea.

To remind you how this works: Conceptually the idea is that everyone votes as they would under first past the post. Then when it comes time to actually pick the winning candidate, rather than the candidate with the most votes winning you pick a vote at random and use that. Thus the more votes you have, the higher the probability of winning, but you are never certain to win unless you get 100% of the votes.

This subject occasionally comes up in conversation and people complain that the problem with random ballot is that elections have to be accountable and that it’s impossible to make it accountable: You cannot verify the randomization because it’s not repeatable.

Fortunately, this isn’t true. This post is a proposed protocol for how to implement random ballot in a way that has the randomization be fully repeatable and difficult to tamper with. It uses physical sources of randomness as inputs to an electronic voting procedure. The electronic voting is open source, fully deterministic and all inputs to it are published so they may be verified by third parties.

The basic approach is that rather than actually picking a vote at random we tally the votes as we do under first past the post and then use a random number generator to draw a candidate from the resulting distribution. The only tricky bit, which is what this election protocol is designed to ensure, is being able to trust and verify our random number generator.

Edit: It’s been pointed out to me since that there exist much more sensible cryptographic schemes for generating random numbers reliably. Some variation on these should be used instead of the one I proposed here. e.g. each candidate + the people organising the vote counting simultaneously provide a random seed according to this scheme after the votes are counted, then the seeds are revealed, then the calculation is done. So the current details of random number generation are wrong, but I’ll leave them in for posterity. The rest remains valid.

The goals of this design are as follows:

1. No individual constituency can conspire to change their answer
2. No central power can conspire to change the overall answers
3. Once we have counted our votes and obtained our initial random data, everything from that point on is deterministic and verifiable

It involves three components:

1. Whatever is currently used for tallying votes. i.e. we count up the votes each candidate gets in exactly the same way we currently do
2. A number of lottery ball machines with 256 balls in it labelled 0 to 255
3. An open source program which implements our voting procedure

These are deployed as follows:

Firsts votes are counted. These vote counts are published as they currently are. Recounts may be demanded at this point. No recounts are permitted once we start rolling the metaphorical dice, so the whole election is stalled until everyone agrees to stop recounting.

A thing worth noting here is that recounting is much less valuable for random ballot than it is for first past the post: In first past the post if you have 51% of the vote and your opponent has 49%, you’ve won everything and so your opponent really really wants a recount because they’ve got nothing to lose by it. In random ballot you’re near as dammit tied and a recount can make your opponent’s situation worse as well as better, and isn’t likely to do much of either.

Now we have our votes counted it’s time to generate random numbers.

This is where our lottery balls come in. The goal is to generate 64 bits of random data for each constituency, i.e. 8 draws of one byte balls from the lottery machines.

First, each constituency draws 4 balls. They write down the numbers for these but do not publish them.

Then two central authorities which are physically separated and kept out of communication each draw two balls. These results are published.

The random data for each constituency is then the sequence of 4 balls they’ve drawn and 4 balls drawn by the central authority.

What’s the reasoning here?

Well, if the constituency is solely responsible for choosing the random data then they have the possibility of doing something like rejection sampling – they rerun the vote until they get the result they want.

If a single central authority then adds a source of randomness to the mix and they have access to the numbers from some of the constituencies (which they’re not supposed to have, but information can leak), then they can in theorydo similar: Rerun the experiment until they get a more pleasing distribution of seats.

By having two central authorities who are not communicating with eachother you remove the possibility of either of them doing this (they could manage to find a side channel and communicate, but this is hard enough that it makes an already hard problem essentially impossible).

So now we have our vote counts and we have our random numbers. What do we do?

Well, we publish all of these in the open for a start. This makes it possible to verify our calculations.

We now feed them in to our program. The program does the following:

1. It concatenates all the numbers together into a single 64-bit integer
2. It hashes that integer (this makes the ability to control any small number of balls in the sequence much less useful)
3. It uses this hashed integer to seed a pseudo random number generator. I don’t know enough about PRNGs to comment on what is a good one here, but we don’t need fast performance here (even taking seconds per number would be more than fast enough enough) so lets assume it’s one good enough for cryptographic use.
4. It sorts all the candidates by name
5. It shuffles that list (this helps a little bit in protecting us against attempts to bias the PRNG towards low or high numbers. I’m not sure it’s a necessary step)
6. We now generate a random number between 0 and the total number of votes
7. We use this number to sample from the distribution we got from our vote count (basically counting off from the left until the running total is larger than the vote number we picked)
8. That sample is our elected candidate

Although there are a lot of “If you could get a hidden communication channel in here and run a lot of simulations really fast and somehow rig the lottery machine to produce the answer you wanted” holes in this, I think they’re almost impossibly difficult to get anything through. The way we combine different information sources means that you need to subvert a lot of different features of the system in order to get a useful influence on the output. I’m reasonably confident that any interference with this procedure is significantly harder and more likely to be detected than more traditional forms of vote rigging, and that the way the information is used in the system is transparent enough to satisfy any reasonable desire for accountability.

This entry was posted in voting on by .

## 11 thoughts on “An election protocol for implementing random ballot in an accountable manner”

1. Pingback: David R. MacIver

2. Ovidiu

First of all, you should define the problem: what to expect from your voting system and what are the constraints, then pros and cons. I also read your previous article and I have some suggestions.
1. House of representatives should be… representative for (one, few or all from below):
a. voters; b. all citizens; c. minorities (the problem of inclusion); d. you name it
2. Is there a method to extract a sample S from a population, with some degree of confidence? I think the answer resides in statistics and probabilities, and you have a math background which will make the solution easier to find (I also have to write it down for myself). Then, some of the next steps are: computational simulation, implementation and security issues.
3. May the result of S be better than empirical evidence of actual voting systems, when it comes to representation and constraints defined at point 1?
4. Some pros and cons for using statistics and probabilities, as I see them. Pros: representation, non-corruption, non-perpetuation of elites (oligarchy). Cons: no choice, no parties, and the most important – possible incompetence of some MPs. But, to fight the cons, I argue that parties are oligarchic organizations (Michels) and MPs incompetence and lack of choice will lead in a mid- or long-term future to a couple of important changes: investments in (children) people’s education and the need for participation and deliberation without expecting the job to be done by representatives alone.
In conclusion, I think random ballot as random extraction of a sample from a population might give the optimum representation, plus some indirect pros.

1. david Post author

Hi,

I think it may be possible that you don’t understand what I’m proposing. Either that or I’m misunderstanding what you’ve written!

What I’m proposing is not a pure sortition, where you just elect random members of the population, which is what I think you’ve interpreted as. Instead it’s a random ballot, where people vote for candidates in much the same way as more traditional methods and a candidate with e.g. 60% of the vote is elected 60% of the time.

3. Ovidiu

Hi again,
I understand that you propose a system already described by Akhil Reed Amar: CHOOSING REPRESENTATIVES BY LOTTERY VOTING, while I support a pure Athenian lottery vote where everyone would vote for himself. I have two main issues concerning your choice: representation and party as mediator. I don’t think that your system would make any difference as long as parties control the system and fair representation will be done through them. I’ve just bought a book, Lotteries in public life edited by P. Stone, to better understand the problem, but I am a truly supporter of a participative-deliberative (e-)democracy abiding inclusion (A. Sen, D.A. Crocker, J.J. Rousseau, Aristotle etc.), but with great respect for liberalism (Rawls, Locke) and even libertarianism (R. Nozick) . I am not against political parties, but I don’t like them as mediators in voting system.
Do you really think your lottery voting would make a difference if parties, campaigns and thresholds (ante or post voting) are still the main performers of the show?

1. david Post author

Ah! I do indeed. Thank you, I’d never seen this paper. I’m not surprised the idea is not novel (indeed I never expected it to be), but I hadn’t seen specific prior work on it before. I will read this with interest.

One advantage of this system is that it’s largely party independent. In particular, small parties and independent candidates have much more capability to get in than they do in majoritarian systems: This is basically a feature of its strong proportional representation party (which is really a very powerful property). If about 10% of votes go to people not affiliated with a political party, about 10% of elected candidates will not be affiliated with a political party.

It still runs into the problem that in most current representative based systems a party is responsible for forming the government. I agree this is an issue that should be changed, but I think it’s out of the remit of the specific mechanism you use to elect representatives and also I don’t have any good proposals for how best to change it.

I don’t think I understand your objections on grounds of representation. Could you elaborate?

1. Ovidiu

Hi,
On the problem of representation, there is no doubt, parties will do better with random ballot, although there may be an issue concerning the number of constituencies, which must be large enough to efficiently include all parties.
But, if voting instead of pure lottery:
1. parties will choose their candidates and they will be as representative as always
2. (very) small parties won’t pass the election threshold (and I bet there will always be a threshold)
3. candidates are normally required to make a proof of some votes (a list of signatures from citizens), this requires money, resources etc.
4. candidates may be forced to make a deposit and, on top of that, they need money for campaigns, real money. And this is a terrible issue, only people with some consistent income may become MPs. I am not a socialist, but as you might experience on your own, representative democracy leads to political clientelism or, even worse, to oligarchy (and mostly due to campaigns).
So, while parties (except the very small ones) will do just fine from the perspective of representation, it is not the same for citizens.

It is true that one may say that a bunch of incompetence will get in parliament with pure lottery voting. Well, besides this is elitism, MP is a politician and this demands moral values and not really professionalism, which is required for governments. But, we will get as many incompetent MPs as we have incompetent people in our society (a reason to invest in education and for citizens to become more active). Yet, we will a have an outstanding representation on two important grounds: gender(women representation) and age (I need to elaborate on this in the near future, to make some prove that these two are the most important and not religion, ethnicity, income, profession etc.).

4. Paul Crowley

You should use a secure coin flip algorithm for the randomness, ideally one with perfect binding.

Here’s how I’d do it:

– Votes are placed in multiple boxes.
– Each box is numbered.
– A list of boxes is published, including the number of votes in each box.
– Observers can check that box i contains N[i] votes as it should.
– From this we tally the total number of votes
– A canonical ordering of the list of candidates is produced.
– Each candidate and the presiding officer publishes their commitment – ideally all at once, on stage, in the form of big QR codes that observers can photograph.
– Once everyone is satisfied that commitments have been published and agreed upon, each candidate publishes the fixed-length secret they committed to, followed by the presiding officer.
– The secrets are all hashed together, in candidate order, to seed an RNG.
– The RNG produces numbers from 0 to N-1.
– The Kth vote in box J will have number K + sum(i=1..J-1 N[i])
– The first non-spoiled vote selected by the RNG decides the election.
– A canonical ordering of the list of candidates is produced.

The worst attack I see here is that if the last candidate is in cahoots with the presiding officer and knows the secret they’re going to reveal, they can decide whether or not to reveal their secret or say “oops, I’ve lost it sorry”, knowing which ballot number will be selected in each instance. It may help to add more neutral parties to the end alongside the presiding officer – all of them would have to reveal their secret to the last candidate in advance for this trick to work.

1. david Post author

This seems like an entirely sensible protocol. Possibly a bit fiddly compared to counting methods though? Can you think of a reason it’s superior to counting all the ballots and using a normal “select from distribution” algorithm given the resulting seeded PNRG?

One of the reasons I like doing it based on counts rather than actually selecting for individual ballots is that I think it’s more robust to certain types of vote tampering. Things which involve selection of individual physical ballots feel fragile to sleight of hand. Counting on the other hand gives you room to get recounts up front and also provides an explicit feedback mechanism – as well as attempting to avoid any known types of tampering you can also e.g. go “Hmm. The Nasty party got 30% of the popular vote and 50% of the seats. That’s so unlikely as to basically guarantee they cheated”

Another reason which is I admit purely social is that it de-emphasises the arbitrariness of it. This has no practical consequences but definitely makes what’s a very hard sell slightly less hard.

1. Paul Crowley

I think you’re right, counts are better. I hadn’t quite understood that part of your proposal. If you could get away with not revealing the rest of the ballots at all, then you could avoid a certain amount of “Under sortition, the LOSER can WIN!” bollocks, but I don’t see anyone buying that so it’s probably best to avoid a situation where the whole election comes down to a dispute on whether a specific ballot paper is spoiled.