Why getting voting right is hard, Part I: Introduction and Requirements

Posted by ekr on 13 Dec 2020

This post originally appeared on the Mozilla Blog

Every two years around this time, the US has an election and the rest of the world marvels and asks itself one question: Why are American elections so hard? I'm not talking about US politics here but about the voting systems (machines, paper, etc.) that people use to vote, which are bafflingly complex. While it's true that American voting is a chaotic patchword of different systems scattered across jurisdictions running efficient secure elections is a genuinely hard problem. This is often surprising to people who are used to other systems that demand precise accounting such as banking/ATMs or large scale databases, but the truth is that voting is fundamentally different and much harder.

In this series I'll be going through a variety of different voting systems so you can see how this works in practice. This post provides a brief overview of the basic requirements for voting systems. We'll go into more detail about the practical impact of these requirements as we examine each system.

Requirements #

To understand voting systems design, we first need to understand the requirements to which they are designed. These vary somewhat, but generally look something like the below.

Efficient Correct Tabulation #

This requirement is basically trivial: collect the ballots and tally them up. The winner is the one with the most votes ^[1]. You also need to do it at scale and within a reasonable period of time otherwise there's not much point.

Verifiable Results #

It's not enough for the election just to produce the right result, it must also do so in a verifiable fashion. As voting researcher Dan Wallach is fond of saying, the purpose of elections is to convince the loser that they actually lost, and that means more than just trusting the election officials to count the votes correctly. Ideally, everyone in world would be able to check for themselves that the votes had been correctly tabulated (this is often called "public verifiability"), but in real-world systems it usually means that some set of election observers can personally observe parts of the process and hopefully be persuaded it was conducted correctly.

Secrecy of the Ballot #

The next major requirement is what's called "secrecy of the ballot", i.e., ensuring that others can't tell how you voted. Without ballot secrecy, people could be pressured to vote certain ways or face negative consequences for their votes. Ballot secrecy actually has two components (1) other people -- including election officials -- can't tell how you voted and (2) you can't prove to other people how you voted. The first component is needed to prevent wholesale retaliation and/or rewards and the second is needed to prevent retail vote buying. The actual level of ballot secrecy provided by systems varies. For instance, the UK system technically allows election officials to match ballots to the voter, but prevents it with procedural controls and vote by mail systems generally don't do a great job of preventing you from proving how you voted, but in general most voting systems attempt to provide some level of ballot secrecy.^[2]

Accessibility #

Finally, we want voting systems to be accessible, both in the specific sense that we want people with disabilities to be able to vote and in the more general sense that we want it to be generally easy for people to vote. Because the voting-eligible population is so large and people's situations are so varied, this often means that systems have to make accommodations, for instance for overseas or military voters or for people who speak different languages.

Limited Trust #

As you've probably noticed, one common theme in these requirements is the desire to limit the amount of trust you place in any one entity or person. For instance, when I worked the polls in Santa Clara county elections, we would collect all the paper ballots and put them in tamper-evident envelopes before taking them back to election central for processing. This makes it harder for the person transporting the ballots to examine the ballots or substitute their own. For those who aren't used to the way security people think, this often feels like saying that election officials aren't trustworthy, but really what it's saying is that elections are very high stakes events and critical systems like this should be designed with as few failure points as possible, and that includes preventing both outsider and insider threats, protecting even against authorized election workers themselves.

An Overconstrained Problem #

Individually each of these requirements is fairly easy to meet, but the combination of them turns out to be extremely hard. For example if you publish everyone's ballots then it's (relatively) easy to ensure that the ballots were counted correctly, but you've just completely give up secrecy of the ballot.^[3] Conversely, if you just trust election officials to count all the votes, then it's much easier to provide secrecy from everyone else. But these properties are both important, and hard to provide simultaneously. This tension is at the heart of why voting is so much more difficult than other superficially systems like banking. After all, your transactions aren't secret from the bank. In general, what we find is that voting systems may not completely meet all the requirements but rather compromise on trying to do a good job on most/all of them.

Up Next: Hand-Counted Paper Ballots #

In the next post, I'll be covering what is probably the simplest common voting system: hand-counted paper ballots. This system actually isn't that common in the US for reasons I'll go into, but it's widely used outside the US and provides a good introduction into some of the problems with running a real election.