Proposal for enhanced verifiable paper ballots

A number of municipalities have been installing electronic voting systems in the interest of preventing election problems like those which occurred in Florida. In response to widespread concerns that the machines might not record votes legitimately, printers have been added to maintain a "paper trail". Unfortunately, it's not clear how this paper trail can be used to verify election results, other than by hand-counting all the ballots; if ballots are to be hand-counted, it's not clear what benefit the machines provide.

I would propose a system whose deployment cost would be between that of DRE and optical-scan systems, but which would be more resistant to insider and outisder tampering.

Election procedure

I would use optical-scan ballots as the "official" vote recording medium. All other records would be subservient to the paper ballots unless evidence suggests that the ballots were tampered with after they were initially scanned in which case forensics should be used to determine how they should be counted. For voters who are unable to directly cast optical-scan ballots, I would have available electronic machines which would, after the voter made all appropriate selections, print out a pre-completed paper ballot for the person to submit in the usual way.

To protect paper ballots against alteration, there would be a 'check field' which indicated how many other marks there were on the ballot. Voters would have the option of filling this out themselves, or of letting the "electronic ballot box" do it. Although the "electronic ballot box" would accept ballots whose check field was blank, it would reject as spoiled any ballot whose check field was improperly completed.

As each ballot is inserted into the electronic ballot box, it would record some information in printed machine-readable form on the ballot itself and also in internal electronic storage; the details of this information are described below. Additionally, it would check that all votes were cast properly (no overvotes), the check field was either blank or correct (and if blank it would fill it in and then scan to confirm that it had done so correctly), and it would confirm that all marking areas were either completely blank or thoroughly filled. Ballots with excessive marks would be rejected as spoiled; those with ambiguous marks would be rejected for correction.

Ballot information

Each machine would be designed to record a maximum of 50,000 ballots per election (this should not be a limitation, since other factors would limit capacity to a much lower number). These would be subdivided into 1,000 sets of 1-100 ballots, though the actual subdivision would be transparent to voters.

At the start of each election, each machine would be assigned an identifier which would uniquely define the machine and the election; this number is called the "election-machine id". This would be the same for all ballots cast by the machine in the election.

At the start of each "set" of ballots (including at the start of the election) the machine would select a number randomly but uniquely from "00" to "99" as a "set-id"; no number would be reused on a particular machine in a particular election.

As each ballot was cast, the machine would mark it with the election-machine id and the set-id. It would also randomly select and mark for each race a three-digit number called a "ballot-race id" which was unique within that race, within that set of ballots. The machine would then randomly decide whether or not to begin a new set (with a weighted function so that after the first ballot the answer would more likely be 'no' but after the 990th it would more likely be 'yes'). Starting a new set would cause a new set-id to be selected, and would make all ballot-race id's eligible for re-use.

Within each race, any ballot may be globally uniquely identified by the combination of the election-machine id, the set-id, and that ballot-id marked on that ballot for that race. This combined number will referred to as the "race-unique id". As a simple example, suppose there are three races and a ballot is marked 39921-49-501-392-948. The 39921 is the election-machine id, the 49 is the set-id, and the remaining numbers are the ballot-race id's. The "race-unique id's" for this ballot would be 39921-49-501, 39921-49-392, and 39921-49-948.

Post-election reporting

Following the election, a list would be published for each race showing all ballots cast; the list would contain for each ballot the race-unique id and the candidate selection. Anyone wishing to could easily run the list through a perl script or other program to confirm that reported vote totals in fact match the votes on the list, and could easily confirm that the number of ballots in the list matches the number of recorded voters. Note that the lists would not contain any information that would allow any individual person's vote to be ascertained, as the id's would be randomly assigned. Identifying the last people to vote by their membership in a "short" set would not be possible since the sets would be of random length.

If an automated recount is necessary, the ballots could be run through a counting machine, producing a second data file similar in form to the first. Any ballot which reads unclearly would be rejected for hand inspection, but all others would be processed automatically. Doing a cross-check between the two lists would help to catch mechanical problems, and could be useful for that purpose, but would not necessarily catch fraudulent programming. For that, the third step comes in.

To verify accuracy and legitimacy of the actual vote recording, interested parties would be allowed to randomly select ballots from the list to be examined. Any of a number of means could then be used to physically retrieve the paper ballot and inspect it (e.g. even if the ballots were physically shuffled after the original election, during a recount the machine could record the physical order in which they appear). If there is any significant malfeasance or fraud, even a fairly small sampling will likely be enough to catch it. For example, if 1% of the ballots are miscounted, there's a better-than-50% chance of catching one within 100 samples and a better-than-98% chance of catching one within 400 samples. If 0.1% are miscounted, then 1,000 samples will catch one more than 50% of the time, and 4,000 will catch one more than 98% of the time.

While recounts are statistically useless because, in case of discrepancy, there isn't any way to know what's "right", sampling as described will be much more useful and informative. Since ambiguous ballots should be rejected by the electronic ballot box, there shouldn't be even a single ballot that doesn't match the electronic record. If one is found, then something is probably wrong; to allow for the possibility of a statistical fluke, a sample larger than the original one (say twice as large) should be taken. If it comes up clean, then the original anomoly was probably a fluke. Otherwise, machines should be inspected and adjusted as needed; ballots should then be rescanned to determine if any of them read differently after adjusting the machines. If so, particular ballots that read differently should be inspected to determine why. Otherwise another, larger random sample of ballots should be examined to determine whether the previous failures were a statistical fluke.

Key features

Although the vast majority of the tabulating work under my system could be done by machine, saving considerable labor versus a hand-counted election, there would be no need for anybody to 'trust' the machines. If anyone tried to rig machines to produce false results, a random statistical sample of a size appropriate to the election margin would most likely find it. For a 4% race, a sample size of 100 would suffice. And that's not 100 ballots per ward--that's 100 ballots total throughout the entire region where the race is conducted. If the margin were only 0.4%, then 1,000 ballots should probably be sampled. But even that would be a considerable improvement over hand-counting hundreds of thousands or millions.

Perhaps more important than the improved statistcal certainty provided by the use of random statistical sampling is another feature of this system: ballots can be identified for additional scrutiny. With conventional systems, if one recount yields a one result and another recount yields a different result, that may suggest a problem, but it would provide zero guidance toward solving it. By contrast, tracking ballots via random id's would allow particular ballots which read differently on different passes to be identified. If a smudge was causing misreads, the problem could be noted and the counts adjusted appropriately.