Re: [Demexp-dev] Thoughts on voting machines

[David MENTRE]

Hello Brian,

Brian Hurt <address@hidden> writes:

> I'm not sure what the scope of this project is, or what the current design 
> is.  So I thought I'd just throw these thoughts at the wall and see what 
> stuck.

The scope of this project is to make an electronic voting system
suitable to the requirements of the democratic experience project.

In short: - votes can be modified at any time;
          - you can delegate your vote to another person;
          - use Condorcet voting algorithm.

You'll find a detailed english description of the project at:
 http://www.demexp.org/article.php3?id_article=1

So the system we are implementing is pretty different from a classical
electronic voting system (with paper trails or not).

That's said, we have an interest in latter systems, which are not
strictly off topic of this list:

 - because at one point in the future, if demexp is ever successful, we
   will have to design physical voting devices;

 - because you stand of shoulder of giants, i.e. keep the good points of
   other designs.


> First off all, the only voting system I'd trust needs paper.  The paper 
> ballot is the legal, official ballot.  And the voter has to hold the peice 
> of paper- and understand what the paper says!

For demexp, the ability to change vote at any time relaxes a lot the
need of using paper trails.

But, as you, I wouldn't trust a classical voting system without paper
trails, for obvious recounting reasons.

> But even given that, there is a lot we can do.  The general idea I had was
> the touch screen system exists simply to print out the ballots.  In
> addition, the computer system can perform a non-binding count.  The voter
> enters the booth, makes his/her selections.  Out comes a peice of paper.  
> On the paper is printed his/her votes- in english.  If the vote is 
> correct, the stick it into the slot and the vote is recorded.  If not, 
> they throw the ballot out and try again.  Repeat until they get a ballot 
> they like.

Another solution would be to display the paper ballot behind a glass. If
the voter likes the ballot, it goes into the voting box, oterwise in the
cancel box (for recount of canceld ballots). 

I think a firm as even made and commercialized such a system.

> Note that the computer should have a precise count of exactly how many 
> votes for Kerry, how many votes for Bush, etc., are in each lockbox.  So 
> after the election is done, while the media is still reporting on the 
> non-binding results, the election officials roll dice, or pick cards from 
> a hat, or in some other way select a random statistically signfigant 
> selection of polling machines to recount by hand.  The pull the box out, 
> and start counting papers.  

I would apply standard voting procedures here. In france, the voting
book of law is about 400 pages long, in tiny characters. I think all is
there. The only point to add: "in case of difference between electronic
and paper count, the paper count should be taken into account".

Beside that, I don't know if a systematic statistical recount sampling
is necessary or not.

> The paper ballots themselves could be made very easy to OCR with an
> obscenely high degree of reliability.  First off, you print on the paper 
> alignment marks, which allow you to figure out the paper's orientation no 
> matter what.  Second, you use an OCR-friendly font, like the one used for 
> the numbers on the bottom of your checks.  Third, there are a limited 
> number of possible strings at any given location.  If we OCR a vote and 
> get back "Albert W. Gere Jr., Democrat", that was much more likely a vote 
> for Gore, and not a vote for Bush.  We have a lot of redundancy.  And, if 
> all else fails, humans can read the ballot.
>
> The goal of the computer is to make creating the ballot as easy, 
> foolproof, and quick as possible.

Or you can recount manually, without OCR. After all, if you don't trust
a computer to count votes, you won't trust a computer to recognized
characters, which is a much more complicated task. 

> There is a known tendency for voters, when picking at random, to pick the 
> first name on the list.  So we want to randomize the order of candidates 
> for every voter, to negate any statistical advantage of position.

Interesting point. I've never seen it elsewhere.

> Another idea I like is help screens.  For candidates, these would be 
> small, one-page explanations of who they are and why you should vote for 
> them, written by the candidates.  For referendums, they should be similiar 
> summaries of why you should vote for/against the referendum, written by 
> parties advocating said position.  This would allow the voter in the booth 
> who suddenly went "I have no idea who these candidates are, or what this 
> referendum is about" to be given some clue.

Well, the strong point of democracy is not the vote itself but the the
vote *and* the debate before the vote. So the information should be made
before the vote and not at vote time.

Interestingly, in demexp, for each response to a question there will be
a link to an external forum, web site, etc. to feed further debate.

> I also like the idea of allowing sample ballots to be programmed in.  Note 
> that the voter would still be able to go back and override the choices, 
> it'd just be a bunch of default choices.  So the voter could go "I want to 
> vote the straight Trotskyist ticket, except I hate who they have running 
> for Dog Catcher, do I want to vote for the other guy."

I don't like this idea. It's too complicated. What is your semantics of
"Trotskyist" ticket. Our French socialists might look communists for
Americans while they are more like American Republicans for us. :)

> Another idea I had: in addition to the ballot, the voter gets an identical 
> "receipt" to take home.  The receipt and the vote is given a 256-bit, 
> cryptographically secure random number as an ID.  After the vote is done, 
> all the votes are published on a website somewhere- no names, just receipt 
> ID and what the vote was.  The advantage here is that I, the voter, can 
> then verify that a) my vote exists and was counted correctly, and b) the 
> tabulation of votes as put up on the web site matches the tabulation of 
> the votes announced as the result.

Yes, interesting point. The debian voting system is using a similar
scheme. 

In a previous attempt to design a secure voting algorithm for demexp, I
used a similar scheme. However, I'm not sure at all I've used it
properly.

  http://lists.gnu.org/archive/html/demexp-dev/2004-03/msg00015.html

And the initial design was lacking important features for us. 

  http://lists.gnu.org/archive/html/demexp-dev/2004-03/msg00031.html


> This could all be done with off the shelf parts.  My back of the envelope 
> approximation would be:
>
>       - a really cheap PC motherboard.  We want a PC because we want 
> on-board video, not something you get with most embedded hardware.  But we 
> need almost no processor power.  VIA would be good, or really cheap 
> Athlons.  K6s would work if we could still get them.  Or Transmeta.  The 
> idea here, however, is cheap as can be.
>
>       - A touch screen monitor
>       - Some sort of cheapo printer (A receipt printer)
>       - Some bent tin

You also need to physically put those parts into a proper design. For
example, you need to add physical devices to ensure that your voting
machine is not tempered during the vote (or at least you can detect a
tempering). You also need to make the machine work even in case of lack
of electric power. Etc.

> We need someway to know when the user has voted, and some way to make sure 
> the voter only votes once.  Those I'm still working on.

I'm a strong proponent of formal verification of the machine code.

The two free software projects I found interesting in that regard:

 ACL2 : http://www.cs.utexas.edu/users/moore/acl2/
  to prove Common Lisp programs. I think it is conceivable to make an
  automatic translator from CL to C.

 Why & Caduceus : http://why.lri.fr/
  to prove properties directly on real C code.

A list of free software formal tools:
 http://gulliver.eu.org/ateliers/fv-tools/fv-tool-list.html


The code of demexp is made in OCaml (you probably know that ;) and it is
theoretically possible to use the Coq proof assistant to produce proven
OCaml code from its proof. So it would be possible to prove part of
demexp code. But it would probably be very complicated (conflict
resolution in Condorcet voting is quite hairy).

Yours,
david
-- 
 David MENTRÉ <address@hidden>