Yesterday I wrote about Ron Rivest’s ThreeBallot voting system. Today I want to start a discussion of problems with the system. (To reiterate: the purpose of this kind of criticism is not to dump on the designer but to advance our collective understanding of voting system design.) Charlie Strauss and Andrew Appel have more thorough criticisms, which I’ll get to in future posts. Today I want to explain what I think is the simplest problem with ThreeBallot: it has no natural way to handle write-in votes.
(For background on how ThreeBallot works, see the previous post.)
The basic principle of ThreeBallot voting is that each voter fills out three ballots. Every candidate’s name must be marked on either one or two of the three ballots – to vote for a candidate you mark that candidate on exactly two of the three ballots; all other candidates get marked on exactly one of the three ballots. The correctness of ThreeBallot depends on what I’ll call the Constraint: each voter creates at least one mark, and no more than two marks, for each candidate.
But how can we maintain the Constraint for write-in candidates? The no-more-than-two part is easy, but the at-least-one part seems impossible. If some joker writes in Homer Simpson on two of his ballots, does that force me and every other voter to write in Homer on one of my three ballots? And how could I, voting in the morning, know whether somebody will write in Homer later in the day?
We could give up on the Constraint for write-in candidates. But the desirable features of ThreeBallot – the combination of auditability and secrecy – depend on the Constraint.
In particular, it’s the at-least-one part of the Constraint that allows you to take home a copy of one of your ballots as a receipt. Because you have to mark at least one ballot for every candidate, a receipt showing that you marked one ballot for a particular candidate (a) doesn’t force you to help that candidate, and (b) doesn’t prove anything about how you really voted – and that’s why it’s safe to let you take a receipt. If we throw out the at-least-one rule for write-ins, then a receipt showing a write-in is proof that you really voted for that write-in candidate. And that kind of proof opens the door to coercion and vote-buying.
Alternatively, we can declare that people who cast write-in votes don’t get to take receipts. But then the mere existence of your receipt is proof that you didn’t vote for any write-in candidates. I don’t see any way out of this problem. Do you?
There’s an interesting lesson here about election security, and security in general. Systems that work well in the normal case often get in trouble when they try to handle exceptional or unusual cases. The more complicated the system is, the more likely such problems seem to be.
In the next post I’ll talk about some other instructive problems with ThreeBallot.
Do you know blogs about Free digital camera and Free dvd decoder?
My comments:
4.1 So why is it so hard to add phantom voters and votes? This is the usual way to fix an election. And they don’t check their ballots.
4.4 point 2 – so why trust the ballot printer? If there are a lot of posts/issues to vote on, the voter cannot be relied on to check that the ballot copy is accurate. I suppose this might be handled by allowing a hands-off visual comparison before taking the copy.
4.7 If the checker prints the user-chosen ballot copy, then checker is free to modify the other ballots to plump illegally where there are >2 choices.
5.31 The one-ballot with exchanged receipt obviously violates vote confidentiality if exchanged with another person, or if officials know or manipulate which receipts are exchanged. And if they don’t watch, the voter can avoid exchanging, or choose a ballot which satifies who’s manipulating them.
It is a nicer way to assure a anonymous vote and allow voters to perform some checks on vote validity themselves.
But:
– It increases the vote effort and complicates voter checking.
– You still have to trust a lot of machinery.
– If there are problems, and there are likely to always be problems, the solutions for a particular vote are not simple or fast.
tOM
Ok I read the thing. A few questions:
1) How are you going to stop a voter from fleeing with one of the three ballots (the one with the people they don’t like on it)?
A little slight of hand and a blank piece of paper the same color as a ballot goes in.
2) What are you going to do about the voter who puts in a stack of their three ballots instead of one at a time? Was that three ballots or two, do you feel lucky punk? Well, do ya?
3) No mention of the human element. OK so you have a machine that beeps when a ballot is wrong, then what? Go and erase stray marks and add others? How many times can each voter do that before the system is too backed up to function? How many times will a voter get beeped at before he or she gives up in disgust?
Important rule of machines. If the people who need to use them can’t understand them or don’t like them, your machines don’t work. No matter how clever they are in theory.
I read a good book recently on that subject “The Change Function: Why Some Technologies Take Off and Others Crash and Burn” by Pip Coburn.
Lots of technology described there that worked technologically but were a bigger pain to start using than the problem they were designed to solve was worth. Guess what happened to them?
What I’m confused about is why write-in candidates are necessary or a good thing in any way. Why can’t you have a listing with all the candidates? Why is it necessary for people to write the candidate? Really weird.
Casualreader and todd johnson: I encourage you to read the original proposal first. Your comments refer to things that are all already adequately addressed by the proposal.
Karl-Friedrich Lenz: Regarding absentee ballots: The proposal already acknowledges that it doesn’t improve the situation for absentees. But look at one of the problems the proposal is trying to solve: Guaranteeing anonymous voting. Well, absentee voting, by its very nature, already violates that anyway. No system that allows people to vote from an outside, unmonitored location can provide for anonymous voting.
There are three separate points I’d like to comment on: reducing voter confusion about the system, dealing with write-in candidates, and preferential voting.
1. I also believe that the “mark two ballots for positive vote and at least one ballot for all candidates” rules is going to confuse the heck out of most voters out there. We can work around this by having a voting machine which just takes a normal set of votes and prints out a valid ThreeBallot. To avoid machine based fraud, we can specify a standard format for ballots that include the rules for voting in that race (which office/issue, list of candidates, number of candidates to be voted for), and there would be up to three different machines used in an election: a ballot generator/printer, a ballot verifier, and a ballot counter. We can also specify that no polling station may have ballot generators/printers verifiers made by the same company.
With these machines, the ThreeBallot voting process would go something like this:
a) Voter signs in with the poll worker; has her identity/voter status verified and checked off the list; receives a ThreeBallot and goes to a voting booth.
b) Insert ballot into voting machine. The machine reads the election data from the ballot, then presents each race to the voter for her vote(s). The voter vote as she wishes. The machine will notify the voter if she tries to over-vote for any given race.
c) When the vote signifies that she is finished, the machine prints her votes while randomizing the marks on each third of the ThreeBallot.
d) The voter goes to the vote verification booth, where she inserts her marked up ballot into the verifier; the verifier shows her how she voted. If she agrees that the votes are valid, she hits a button and the verifier will cut the ThreeBallot, return them and a copy of a randomly selected sub-ballot (appropriate marked, perhaps by printing it using a different color ink or on colored paper).
e) The voter casts her ballots into the box. This is witnessed by a poll worker, who then also checks her vote off the list. She can optionally exchange her receipt with other finished voters.
By initially giving the ballot to the voter, the chance of ballot box stuffing is reduced. (Though the three-ballot system already has other built-in check to detect such cheating.) By using a voting machine, we can separate the voting interface (how someone votes) from the security regime. By having a separate vote verifier, we give the voter a second chance to check her votes. And by having a standardized format for ballots, we can reduce the capacity for a voting machine to tamper with a given race, when as a part of testing it would have to correctly present any number of different elections based on the different ballots it receives. This removes one more potential area for vote tampering by encoding the election “software” into the ballots themselves, and the machines just have to correctly apply the rules.
2. Building off of the above idea for implementing a three-ballot system, we would need to make two modifications to the voting system to accommodate write-in candidates: provide entries on the ballots for write-ins for each race, and provide a masking function to insure that an individual “receipt” cannot definitively identify a voter’s actual votes.
The first modification is relatively simple: include for every appropriate election one or more “write-in” candidate line items, or to use Ron Rivest’s language: add rows. The number of line items added would equal the number of candidates one can vote for in a particular race: e.g. one for each US senator/congressman, but two or more for judges, boards of supervisors, school boards, etc. This essentially allows the voter to write-in an entire ballot (of people; this is clearly not germane to things like ballot initiatives). Note that the write-in lines do not contain any names whatsoever.
When the voter is in the voting booth as per above, she gets another option for every race: write-in. Choosing “write-in” is like choosing any other candidate for that race, with the same rules applying on over-voting. The difference is that for each write-in slot selected, the voter is required to enter a name. When she’s done voting, the machine now spits out the three-ballot, as well a chit for each write-in candidate, with that candidate’s name and position on it. In the verification process, the voter inserts the three-ballot and the chit(s), and the verifier does its thing. The voter then casts the sub-ballots and chits.
Now, when the ballots are being counted, there will be a normal tally for the “pre-printed” candidates and there a leftover tally of votes without names for each race. Since the ballots treat each write-in just like the “regular” candidates, we can be sure that the tally for the write-in accurately represents the *count* of the votes for these write-ins. To figure out the distribution of these non-specific write-in votes, we just have to tally the chits.
My worry is that this solution seems too simple to have been missed by Ron Rivest and those who have already commented on the ThreeBallot system, and that there must be a gaping hole somewhere. Of course, this system essentially creates a second tier of ballots, which clearly introduces complexity as well as open up potential vulnerabilities to vote tampering. Since the ThreeBallots would still have to add up, there remains a way to detect fraud. And the complexity can be reduced by letting the voter use a machine to vote, and the machines masks the details of how to properly mark a ThreeBallot.
3. Assuming that this idea for write-ins does work, we can extend it to preferential voting (though it rapidly turns into two, mostly parallel voting tallying systems). For preferential voting, we treat all preferential votes as variants of write-in votes, and every candidate receiving a preferential vote would also generate a chit that has the additional information on ranking. As in the write-in system, the ThreeBallots tally would only indicate which (non-write-in) candidates got votes, and the chits would also have to be tallied to figure out the preferences. In this case, ThreeBallot is being used as an accounting overlay on the traditional voting system (as represented by the chits).
So what have I overlooked?
I’m confused as with CasualReader. Because, if you have to cast a vote for everyone, then you lose “If anybody modifies a ballot after it is cast, there is a one-third chance that the voter will have a copy of that ballot and will therefore be able to detect the modification.” — you really get a “1 / (N+1)” chance.
But it seems to me that the only way to enforce the requirement that every voter votes for every candidate at least once (and only once) is if the system 1) asks for one vote 2) automatically generates 1 vote per candidate 3) asks for which vote you would like a receipt. It seems to me as though such a system could easily go back and add in votes for the beginning of the day to match write-ins at the end of the day.
OK, I’m not understanding the system. If there has to be one mark per candidate, doesn’t that mean N+1 ballots, where N is the number of candidates in a race? If so, then how do you eliminate the extra yes votes for the minor party candidates?
Maybe you could run through a 3 candidate race example?
Or do you just mark all the candidates with a “yes” and a “no” on every ballot with two yesses for the one you want and two nos for everyone else? Plus it will kind of give teh game away when you show the coercer the ballot with one “no” (for your actual candidate) and all the rest “yes”.
Do you have a different ballot for each race going on? Or do you have to keep track of every candidate you voted for on each ballot?
Do you have one entirely false ballot and two entirely true ballots or a mixture of true and false such that adding up each race will give you two true and one false?
If it is all one or all the other , the guy who is coercing you might get a little suspicious when you show him the copy of the ballot where you voted for the “kicking puppies initiative”.
The method also doesn’t stop ballot box stuffing.
How do you stop someone from voting for the same candidate 3 times? Instead of plus two minus one?
If this is done on computers, you don’t need three ballots, just an option for “print my receipt with the following races switched”.
Biggest problem with this can be summed up in two words “butterfly ballot”.
If people couldn’t figure that out, how the heck are they going to understand this? I’m no dummy and I can’t figure it out from the descriptions of someone who is also no dummy.
Oh, I see, thanks Ed.
My confusion was on the counting end — I’d thought that all three of person N’s ballots were attached to one another somehow and counted together, with the tally only including the person actually voted for. I see now that that was mistaken and that the actual proposed system, despite its flaws, is much more clever than that.
To solve this problem, one would have to make sure at the point of voting that all the three ballots had the same write-in candidate, and that either one or two of them were marked for him. Then the number of votes for that candidate is the number of votes he got, minus the number of ballots on which he was written in.
This would require a more complicated machine than one that simply counts the number of ovals filled in. It might do OCR to check that the names were the same (“Print in block capital letters, one letter to each box”), or might photocopy the first ballot’s candidate onto the other two ballots, showing the result to the voter for his confirmation. Although more complicated, these don’t seem unworkable. The machine already has to have some sort of photocopying ability, in order to print out the receipt that the voter takes home.
Klimax,
Paper ballots have their problems too. The most common attacks on paper-ballot systems involve adding ballots to the box, substituting ballots, or losing the ballot box entirely. There are many historical examples of fraud in paper-based elections.
(My point is not that paper is terrible, just that paper-only systems are not a perfect solution either.)
K-F,
Handling absentees votes differently is acceptable, because knowing that somebody cast an absentee vote doesn’t tell you anything about how they voted. Write-in votes are different. If I know that Alice cast a write-in vote, and that Bob did not cast a write-in vote, then I know something interesting about their votes.
Normally few people cast write-in votes, but occasionally there is a race where write-ins are important. We wouldn’t want to lose the secret ballot with respect to those write-in candidates.
Todd,
It’s a basic principle of ThreeBallot that voters must make at least one mark for *every* candidate. Here’s why:
Suppose there are N voters and a count shows they made a total of M marks for candidate Smith. We know that N of those marks were mandatory (one mandatory mark for Smith per voter), so we can deduce that the other M-N marks represent votes for Smith. That’s how we know how many votes Smith got.
If the rules don’t require one mandatory mark for each candidate, then we can’t tell how many of the marks for Smith are mandatory marks and how many represent votes. In other words, we can’t tell how many votes each candidate got.
I’m probably being dense here, but I’m not seeing the problem. Suppose we phrase the restriction as, you have to vote twice for the candidate you support, and once for a candidate you don’t.
“If we throw out the at-least-one rule for write-ins, then a receipt showing a write-in is proof that you really voted for that write-in candidate.”
With this wording of the restriction, it’s not; you may have voted for the write-in candidate, or you may have chosen a write-in as your one non-support. There’s still no way to tell what was on your other two ballots. So, secrecy is preserved.
As far as I’m seeing, so is auditability; you can still tell if someone modified the one you chose to keep as your receipt.
So…what am I missing? And does the same thing-I’m-missing prevent this from working in races with more than 2 candidates? If so, that seems a bigger problem than write-ins; some states already disallow write-ins, but no state can restrict all races to just two candidates.
Assuming you can’t make ThreeBallot work with write-in, does that stop the show in any way for all other ballots, which are the clear majority in all elections?
The same question could be raised for absentee votes sent by mail. ThreeBallot does not seem to work well with those.
One answer might be to say that you don’t want different voting procedures for reasons of equality.
However, there are already different procedures (e.g. absentee vote and vote at the polling station).
One other answer might be that you don’t want voting staff to know that someone has cast a write-in vote, since that would conflict with the privacy requirement.
That would probably mean that the voting machine would need to recognize the fact that the line for write-in is not blank and act accordingly (don’t give receipt, discard other two ballots).
I do NOT understand problems with voting.In Czech Republic we have very simple system.Voter goes first to voting commision consisting of several townfolks,they check his ID card and cross out his name in the list of voters.Then he goes behind “curtain” and put the paper with party to a envelope and put it to ballot box.Both thinks achieved.Security of voting and secrecy.Unfortunately I do not know if it can be applied to other countries-mostly non-european…
Grant,
Your first suggestion, of having lots of 26-way races, would make the ballot really big and would require machine-aided preparation, both of which are logistically challenging. A bigger problem is that it exposes you to another attack discovered by Charlie Strauss. I’ll describe that attack in a later post, but the basic idea is that when there are lots of races, or large races, it’s possible to “reassemble” the ballots on the bulletin board into the original groups of three in which they were cast — and then a receipt allows the voter’s entire ballot-triple to be recovered, violating the secret ballot.
Your second suggestion is, I think, what I was trying to describe in the main post. You can apply the Constraint to the ovals on the ballot form (i.e., that the designated write-in slot on the ballot must get either one or two marks). But a write-in vote not only fills the oval but also designates a candidate by name. There’s no practical way to apply the Constraint to write-in *candidates*, which is what you need to guarantee correct counting and privacy with respect to votes for those candidates.
This seems like the sort of case that can be patched around, though. On the theoretical level, one could use a 26-way race for each letter of a write-in candidate’s name. More practically, one could reserve a certain number of ballot rows for write-in candidates and allow a voter to write any candidate’s name into any of these slots. This is just off the top of my head and there may be a flaw in it, but my intuition is that this objection is not particularly fatal.