Software Design Document
From Scantegrity Wiki
Scantegrity is a security enhancement for any optical scan voting system. It lets each voter verify that her ballot was correctly recorded and counted, but doesn’t change how the voter marks her ballot or reveal how she voted.
Scantegrity achieves this increased election integrity through confirmation codes that are printed on the ballot in invisible ink and a verifiable commitment-based end-to-end integrity mechanism. These tools allow anyone to verify the election tally independently of the physical chain-of-custody.
The polling place procedures and equipment remain the same. The optical scanner and paper ballots can still create independent tallies. These features mean that the system couples significant gains with minimal impact on its users.
This specification is not complete. It is still in need of significant review and thought. Component design documents are also in need of a lot of work.
The purpose of this document is to formalize the design and implementation of the Scantegrity voting system. It should be useful to many types of people:
- Anyone, including interested members of the Public (our customer) and Election Officials, will better understand the system and it's properties.
- Programmers will be able to use this document to understand and work on the System.
- Independent Testing Authorities will be able to test the system using the claims in this document.
- Researchers can study the system through this document.
The target audiences are evaluators and implementers, but this document should be useful to anyone who wishes to understand the overall structure and general responsibilities of each component.
This document is a High Level Design Document (HLDD) of a system composed of several independent systems. It is a basic overview of the implementation, putting all the components of the system into context.
The ultimate goal of this document is a technical and functional specification that humans outside of the project can read and understand. We want to minimize barriers to entry for the interested novice open source developer. Where possible, we want to be accessible to the casual reader. To that end, we strive to be:
- Complete — Everything here should reflect the latest information. If an implementation changes something, come back here and change the spec. We do not want readers to be several versions behind by the time they are ready to dive into the code.
- Clear — Avoiding ambiguity as much as possible. Citing relevant references, giving example use cases (if applicable), and noting all known unknowns.
- Entertaining — We want people to be able to read it without falling asleep. This means concise, simple, professional language mixed with a little humor. Stilted, verbose formal language in the passive tense is forbidden.
This document should give some background, specify system architecture, and detail data exchange formats. It will also provide a brief description of components, pointing the reader to larger and more detailed design documents for each one.
This section is a reference for what a new reader may need to know to understand parts of Scantegrity. It is not intended to provide comprehensive explanation, but to point the reader to the correct resources.
Readers should be familiar with terminology common to the voting community and industry. The terminology is sometimes disputed, controversial, redundant, and confusing. For our part, we try to avoid these problems when writing, choosing the most common term where possible and being specific about what each term means. We recommend the following resources:
The most current, up-to-date technical resources are always available on the Learn More page under "Selected Technical Papers." It is not necessary to read them to understand everything in this document, but it is helpful for understanding how the system works and why it does what it claims to do.
Election authorities use a workstation to create confirmation codes and add them to the ballots. After voting, they use the workstation again, reading the electronic ballot images (EBIs) to interpret marks on each ballot and post the chosen letters. They use the workstation a final time to respond to audit challenges, and everyone can check the responses to be sure the results tallied properly. The next sections talk more about who does what and details the experiences of various types of players in a Scantegrity Election.
The central trusted election authorities (EAs) are typically a small group of professional, paid, election administration officials. They could be non-partisan, made up of a group of people from opposing parties, representatives of the candidates, etc. The key property is a common election property---that the election officials mutually distrust each other enough to provide effective oversight. If enough EAs collude with an outsider who is also running a tracking scheme at the polling place then there is a voter privacy concern.
Most of what the EAs do revolves around the central workstation running the Scantegrity Election Manager (SEM) software. They create the commitments, post them online, and subsequently post responses to audits and the results of the election. This has been characterized in publications as a set of 4 meetings where specific tasks are carried out, but there are things that need to happen before, between, and after these key meetings. In order, a description of the tasks are as follows:
- Create a Ballot. After contests are set and a candidate list is determined, one of the EAs or a secretary creates a Ballot in their favorite software. Afterward, it can be loaded into the Ballot Creator software to add Voice, serial numbers, and other programmatic details necessary for the election software.
- Meeting 1: Election Initialization. Using SEM, the officials generate commitments for the election and post them online. This creates a "Digital Audit Trail" of sorts.
- Meeting 2: Pre-Election Audit. Using SEM, the officials respond to challenges provided by the election auditors.
- Ballot Printing. The EAs take the printing data to the printer for printing. This might require work from SEM, or some other way. It's assumed this usually happens right after the Pre-Election Audit.
- Print Audit. Auditors choose a random subset of printed ballots, they are fully marked, audited as in Meeting 2, and posted online.
- Meeting 3: Tally. The results are tallied and posted online. This involves taking the plain text EBIs from the scanners and processing them to determine results and generate an input file to reveal the codes chosen by voters.
- Spoiled Ballots. Ballots spoiled during the election are audited as in Meeting 2.
- Meeting 4: Post-Election Audits. Responses to the challenges posted by auditors for the results are answered and the election is certified.
- Dispute Resolution. If there are problems, they are resolved sometime after meeting 3. Valid complaints are fed back into the tally phase and a subsequent post-election audit is held with leftover data. If there are no challenges, leftover data for which it is possible to reveal is revealed.
Election Judges (or Poll Workers)
Election Judges (EJs) are members of the volunteer workforce that conduct every election. They are typically paid some amount of money to run the election---in Maryland they make about $150 per election. These groups are split into equal numbers by party affiliation or some other method to achieve effective oversight. Usually there are 2 chief judges that undergo additional training and sign off on various actions that happen at the polling site.
An EJ's experience and duties are as follows:
- Poll Site Setup. EJs unpack tables and equipment, placing it in appropriate locations at the polling site. EJs perform various procedures to verify Poll Books and the Scanner haven't been tampered with by checking seals. When starting the scanner, EJs will print and sign off on the scanner's identity in addition to posting a standard zero-tape on the polling site bulletin board. This identity printout contains a digital signature that can be used during audits.
- Running the Election. EJs sign voters into the Poll Books, give them ballots, handle voter assistance issues, and handle spoiled ballots. During most of the (infrequent) actions both chief judges sign off using standard forms included with other election equipment. The only common action is sign in and scanning, which regular judges are assigned to (usually a card is signed at check-in, and given to the scanner before scanning).
- Ending the Election. EJs print the scanner results tape and post it to the local poll site bulletin board. This also contains a digital signature of the results that can be used during audits. Memory units from the scanner are removed and sent back (along with other equipment, spoiled/used/unused ballots, etc) with the chief judges to the election HQ, and are fed into SEM for Meeting 3.
Anyone can audit the election. The official auditor just picks the unpredictable numbers that election officials use to reveal commitments. These choices could be based on a transparent process, such as the least significant digits of the closing value of stocks the day after the data is posted online, or by letting the candidates in each race provide the numbers.
Auditors make their choices in 3 situations:
- Pre-Election commitments. Before the election and before printing, the auditors choose which ballots will have all of their commitments revealed and will not be used in the election. This is typically half or more of the digitally generated ballots (as it costs an insignificant amount of time to create that many).
- Print Audit. This happens twice, once right after printing, and once during the election when anyone (even a voter) can spoil a printed ballot. The same things happen as in the Pre-Election commitments audit, and everyone can verify that what was printed on the paper is what was represented in the commitments posted online.
- Post-Election Audit. This is the partial reveal to verify that the election officials counted the ballots correctly.
The final job of the auditor is to download all the election data as it is posted, and to verify that what was revealed matched the commitment data.
Voters could be anyone. All they have to do is vote. Optionally, they record their codes and check them online.
A voting systems is really a system of systems. Scantegrity is not much different, you could (in theory) do a lot of the work through manual processes and there would be only one component that requires a software implementation; the others only serve to facilitate the rest of the election.
That one necessary component is the Scantegrity Election Manager (SEM). Observe the following: It could print directly to a printer. The web server only posts information, which is what web servers do, and you could substitute it for your standard bulletin board. The scanner is not considered part of Scantegrity, but part of the underlying optical scan system. The verification software is not part of the election system, but something someone else should probably write.
While the engine makes the system go, having everything else makes it a much more pleasant and less error-prone experience. The bushidō of Scantegrity is not limited to "Do not verify the software, verify the election." There is one more tenet:
- "Make sure the software is of the highest quality, and that it meets any and all user needs."
Scantegrity's components are as follows:
- Ballot Creator — This is a ballot creation tool that allows users to take PDF images of their ballot and prepare them for use during the election. It allows users to identify each contest and how it should be counted and to add audio clips for instructions, each contest, and each candidate. The output of this tool is posted online so that everyone can check that the ballot used in the election was properly formed.
- Scantegrity Election Manager — This component, used exclusively by the central Election Authorities, creates commitments and responds to audit challenges. The output from this component is posted to the Web Bulletin Board.
- Web Bulletin Board — A web server that anyone can use to audit the election. Commitments are posted by the Election Authorities, Auditors post challenges, and Election Authorities post responses to those challenges using this component. This could be a simple website, but it is ideally an integrated web application that facilitates multiple elections.
- Printer — Used to print ballots. Must support the revealing ink used by Scantegrity.
- Optical Scanner — Scans ballots and stores the EBIs. The EBIs are then fed into the Scantegrity Election Manager and results are tabulated.
- Election Verifier — Allows auditors to verify the posted ballots and data posted to the Web Bulletin Board.
This list is not a comprehensive set, but rather a set of the basic elements necessary for a standalone system with reasonable features. There are a number of possible standalone auxiliary systems that may be desirable:
- Electronic Poll book — A networked Poll Book that allows Election Judges to easily sign in voters.
- Accessibility Workstation — An Electronic Ballot Printer that marks a ballot for voters with disabilities, but could be used by anyone.
- Absentee/Provisional Ballot Manager — A scanner application that facilitates high speed scanning and alerts the user to problem ballots.
- Receipt Generator — A scanner/printer combo that takes a marked ballot and prints out the marked areas on a receipt form.
The workstation engine and printer are trusted, meaning that they have some access to the system's secrets (i.e. the correlation between ballot number and codes, the hash functions for creating tables, etc...) To ensure this trust, the implementation must use Trusted Platform Modules or another similar mechanism.
The designers of Scantegrity have proposed to remove trust from both of these components using an independent trustee model. A majority of trustees would then be necessary to get the secrets. The implementation would need to use a back end based on visual cryptography and a mix net. This option has not yet been explored because election officials are not accustomed to a trustee model. There are also other (much less important) reasons:
- Integrity of these components is always guaranteed due to the built-in external auditing, no matter how broken things might get.
- Election officials are already trusted with making sure the polling sites provide a private environment.
- Mix nets are slow.
For each step of the election, the Scantegrity Election Manager (SEM) software creates output data in an XML format. This data is used in various ways and includes data necessary to independently verify the correctness of the tally generation.