[EM] Why We Shouldn't Count Votes with Machines

[Kristofer Munsterhjelm]

  > As I say above, we are in trouble.  Until we both fix the machines and
> demonstrate success of the repairs, such use of paper backups makes sense.
> 
> Complicating all this, paper ballots have their own problems.

Hopefully the paper ballot problems won't be the same as the machine 
problems, so that fraud is complicated rather than made easier.

>> Let's look at this again. What does a voting machine do? It registers 
>> votes. Surely, that can't be a difficult task, so why use a computer? 
>> Why not (for Approval or Plurality) just have a simple chip connected 
>> to a PROM, with the chip in turn connected to a bunch of switches, one 
>> for each candidate, with a matrix display next to each switch, and a 
>> final switch to commit the ballot? Such a machine would be provably 
>> correct: as long as you have a PROM that hasn't been preprogrammed 
>> (this can be checked at the beginning), and the machine hasn't been 
>> compromised (rewired switches, backdoor chips), then it'll work as 
>> promised.
> 
> I will use "zillion", a stretchable value, below:
> 
> A zillion precincts each set up for a few of the zillion races voted on 
> in the US.
> 
> A zillion personnel who must do all the manual labor and guidance of 
> voters.  This is a sideline, thus hard to justify learning complex 
> skills, rather than a full-time career for these.
> 
> A zillion voters, who BETTER be provided a simple interface for voting.
> 
> At end of election the counts for the zillion races better get attended to.
> 
> I really see it easier to do well effectively if you take advantage of 
> what computers can do (and have them do better than the failures we have 
> experienced).

So you're saying that computers are better than specialized machines? 
I'm not sure that's what you say (rather than that machines are better 
than paper ballots), but I'll assume that.

Because the specialized machines are simpler than computers, once mass 
production gets into action, they should be cheaper. The best here would 
probably be to have some sort of independent organization or open-source 
analog draw up the plans, and then have various companies produce the 
components to spec.

The simplicity of voting could also count against general-purpose 
computers as far as manual labor is concerned. If the machine has been 
proved to work, you don't need to know what Access (yes, Diebold used 
Access) is to count the votes, and you don't need a sysadmin present in 
case the system goes to a blue screen.

You could also do these kind of proofs on general purpose computers, but 
then you'd have to design the complete software system from the bottom 
up, which includes what one'd traditionally consider the OS; and if it's 
general purpose, you also have to ensure that the vendors don't patch 
the systems after they've been deployed.
Having the kind of programmable ROM infrastructure with a limiter on 
per-voter might be good in the general-purpose computer case as well, in 
which case the computer just act as a GUI. Then it can't mass vote - the 
worst (which is pretty bad) it can do is alter the ballot as the voter 
votes.

> For Condorcet you must recognize, for A vs B, how many ranked A>B and 
> how many B>A.  Must do this for every pair of candidates.  If write-ins 
> are permitted (better be), they are more candidates to attend to.

That's true, but it's still fairly simple. Assume the ranked ballot is 
in the form of rank[candidate] = position, so that if candidate X was 
ranked first, rank[X] = 0. (Or 1 for that matter, I just count from zero 
because I know programming)

Then the simple nested loop goes like this:

for (outer = 0; outer < num_candidates; ++outer) {
  for (inner = 0; inner < num_candidates; ++inner) {
   if (rank[outer] < rank[inner]) {      // if outer has higher rank
    condorcet_matrix[outer][inner] += 1; // increment
   }
  }
}

It's less than instead of greater than because lower rank number means 
the rank is closer to the top.

Write-ins could be a problem with the scheme I mentioned, and with 
transmitting Condorcet matrices. One possible option would be to prepend 
the transmission with a lookup list, something similar to:

Candidate 0 is Bush
Candidate 1 is Gore
Candidate 2 is Nader
Candidate 3 is Joe Write-In
Candidate 4 is Robert Write-In, etc

and if the central gets two condorcet matrices that have the same 
candidates in different order (or share some candidates), it flips the 
rows and columns to make the numbers the same before adding up.

"Writing in" with the switches-and-display GUI would still be very 
difficult, however; I recognize that problem.

> We know that failing is possible with defective computer systems.
> 
> I claim that those willing should be allowed to demonstrate, and deliver 
> if they demonstrate ability, good computer systems.
> 
> Agreed the average voter cannot demonstrate quality of systems, though a 
> few have failed so miserably that even they should notice.

I don't really like computerized voting, since I think it solves a 
problem that isn't there while complicating things a lot. But if voters 
insist upon computerized/machine voting, then we might as well do the 
best of it, and in my opinion, it would be better to prove positively 
(that everything it's supposed to do, it'll do correctly no matter what 
happens) than negatively (that it won't err), because there's so much 
more potential for something to fall between the cracks in the latter 
case than in the former.

The specialized conclusion follows from this, because in the general 
purpose computer case (without your own OS or something with a security 
microkernel or similar to ensure the validity of the proofs) you have to 
prove that the display driver doesn't mess with memory it shouldn't, 
that the keyboard driver doesn't, and that basically the entire OS works 
as specified.

> Some talk of printing copies of the ballot:
>      Certainly voter should have aid in verifying the ballot.
>      But I do not see need for printing such.

One idea that came to mind when considering this and Kathy Dopp's 
statement that voters don't check their ballots, is this: have the 
machine print the ballot (underneath glass) on a transparency. The 
system is set up so that the screen is monochrome in one color and the 
printer is monochrome in another. Then overlay, very precisely, the 
printed ballot on top of the monitor. If there are any discrepancies, 
then those will stand out because there'll be a color mismatch. The 
printed ballot is what counts - no in-memory count is kept.

It would require very precise alignment and wouldn't do anything for 
colorblind voters, and the GUI would have to look (if not act) just like 
the paper ballot so that the confirmation isn't on a separate screen 
(which would defeat the purpose). Those requirements may be too strict 
for the method to work, but I mention it anyway in case it isn't.

The point of using the printed ballots as what counts is that as long as 
the voter checks the result, there's no way for the computer to "keep 
two books" - to tell the voter the ballot registered was for X while 
secretly registering one for Y instead.

>      I am for a record on disk of each ballot, but done in a maner to 
> not destroy secrecy.

You have to be very careful when doing so, because there are many 
channels to secure. A vote-buyer might tell you to vote exactly at noon 
so that the disk record timestamp identifies you, or he might, in the 
case of Approval and ranked ballots, tell you to vote for not just his 
preferred candidate, but both the low-support communist and the 
low-support right extremist as well, so that he can tell which ballot 
was yours and that you voted correctly.

Perhaps one could have a compromise by repeatedly record the Condorcet 
matrix so far (or Approval counts, in the case of Approval) once they've 
changed sufficiently. That idea may have more subtle flaws, but those 
may also be fixable; I don't know if either is the case.

Finally, the disk record won't help if the machine is compromised. If 
pre-election polls show the incumbent at 47% and the challenger at 53%, 
and the machine changes challenger ballots to incumbent ballots at a 
rate of 7%, prior to those ballots being written to disk, nobody will be 
any wiser. Even an individual ballot record would just show that 7% of 
those that in reality voted for the challenger, voted for the incumbent 
instead, as if having changed their minds just before the election.

(If you go further in this vein, trying to fix that attack, you 
eventually end up at cryptographic zero-knowledge proofs, which aren't 
really "disk records", but more than that.)

> Disk records should also report what, of a 
> suspicious nature, may have been done to the system.

That's a good idea, but it should probably be network based instead of 
disk based so that the virus (if one is introduced) can't just wipe its 
tracks afterwards. Or use some non-erasable medium like aforementioned 
PROMs (or a CD-R for that matter).