Continuous Export

The VVSG 2.0 Test Assertions state that:

TA1.2-H 1: The voting system MUST prevent the loss of voting data in the event of a data input failure without relying on re-casting ballots. TA1.2-H 2: The voting system MUST prevent the loss of voting data in the event of a storage device failure without relying on re-casting ballots.

To meet these assertions, our precinct scanners export cast vote records (CVRs) to USB drive continuously, as ballots are cast. Continuous export also allows for a speedy polls close, as cast vote records need not be exported all at once on polls close.

Merkle Tree Structure

To perform continuous export while also keeping signatures, i.e. authenticity information, up-to-date, we have to be able to write both CVRs and authenticity information incrementally. (It isn’t enough to just hash and sign new data. We need an up-to-date root hash/signature.) We can use a Merkle tree structure to accomplish this efficiently.

Assuming every CVR has a random UUID, e.g. 4d6a9dad-e6d6-4a29-89bc-9ab915012b73, we can specifically use the following structure:

<cvr-directory-name>.vxsig ← Signature on root-hash.txt
<cvr-directory-name>/
  root-hash.txt ← hash( concatenation of all * hashes )
  4/
    4-hash.txt ← hash( concatenation of all 4* hashes )
    4d/
      4d-hash.txt ← hash( concatenation of all 4d****... hashes )
      4d6a9dad-e6d6-4a29-89bc-9ab915012b73/
        4d6a9dad-e6d6-4a29-89bc-9ab915012b73-hash.txt
        cast-vote-record-report.json
        Images

In Practice

We don’t actually have to 1) use a nested directory structure on the USB or 2) store all intermediate hashes on the USB. We can store the structure and intermediate hashes on the machine in a database table, e.g.

Then on the USB, we can use a flat structure that’s much easier to reason about and iterate over:

<cvr-directory-name>.vxsig ← Signature on root-hash.txt
<cvr-directory-name>/
  root-hash.txt
  4d6a9dad-e6d6-4a29-89bc-9ab915012b73/
    cast-vote-record-report.json
    Images

The database table makes recomputing hashes easy, as retrieval of all hashes for a given ID prefix becomes a simple SQL query. This approach also decreases the chance that we accidentally depend on data written to USB when computing hashes, protecting against compromised or faulty USBs.

In the above examples, we’ve listed a root-hash.txt file and have signed that. In practice, we use a JSON file capable of storing other metadata and sign that:

<cvr-directory-name>.vxsig ← Signature on metadata.json
<cvr-directory-name>/
  metadata.json
  4d6a9dad-e6d6-4a29-89bc-9ab915012b73/
    cast-vote-record-report.json
    Images

Sample metadata.json:

{
  "arePollsClosed": false,
  "castVoteRecordRootHash": "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
  ...
}

Import

Whenever a machine imports a CVR directory, it authenticates the CVRs by 1) verifying the signature on the metadata.json file and 2) recomputing the “castVoteRecordRootHash” in metadata.json from scratch to ensure that it’s correct.

Code Links

Refer to the following codebase links for more detail on CVR hashing:

• https://github.com/votingworks/vxsuite/blob/main/libs/auth/src/cast_vote_record_hashes.ts — CVR hashing logic, including the Merkle tree implementation

There is a tension between the requirement that (a) voter privacy should be strongly protected, and (b) Cast Vote Records should be continuously exported in order to ensure that they can be immediately available in the case of hardware failure. For example, if each scanned ballot naively results in the creation of a new CVR file on the USB stick with a timestamp, the order of CVRs is obviously preserved on the USB stick, as the file creation and modification timestamps reveal the order in which those CVRs were stored.

To meet both requirements, VxScan performs some amount of "shuffling" every time a CVR is saved to the USB drive. Every time a ballot is cast and its CVR is saved to the disk, VxScan picks one or two CVRs already stored on the USB drive, and updates their creation and modification time on the USB drive. This is the digital equivalent of taking one or two random ballots from a pile, and bringing them to the top of the pile. Thus, if an attacker were to view the CVRs on the USB drive, they would not be able to determine the order in which those ballots were cast, because of this constant shuffling.

The exact procedure used by VxScan, rather than just a mv operation, is three steps. This is done to ensure that all metadata for a given CVR is updated, including file creation time. Recall from that a single CVR is structured, on disk, as a directory that contains the JSON data of the CVR and the ballot images for that CVR. Thus, the operations VxScan performs to move a single CVR "up to the top of the pile" is made up of three parts:

• first, rename the directory corresponding to the CVR to a new name that indicates it is being copied, specifically by appending -old:

mv 4d6a9dad-e6d6-4a29-89bc-9ab915012b73/ 4d6a9dad-e6d6-4a29-89bc-9ab915012b73-old/

• then, copy this renamed directory back to the original name:

cp -r 4d6a9dad-e6d6-4a29-89bc-9ab915012b73-old/ 4d6a9dad-e6d6-4a29-89bc-9ab915012b73/

• finally, delete the -old directory:

rm -r 4d6a9dad-e6d6-4a29-89bc-9ab915012b73-old/

This three-step operation ensures that

• all metadata for that CVR is updated, leaving no trace as to when that CVR was first saved to disk

• if a failure occurs at any point, it is possible to recover completely without losing any data.

When a VxSuite machine exports data to a USB for another VxSuite machine to import, the first machine digitally signs that data so that the second machine can verify its authenticity. We use this mechanism in two places in particular:

1. To authenticate “ballot packages” — These configuration bundles are exported by VxAdmin and used to configure VxCentralScan and VxScan.

2. To authenticate cast vote records — These are exported by VxCentralScan and VxScan and imported by VxAdmin for tabulation.

The exporting machine digitally signs the following message using its TPM private key (as configured in Access Control):

MESSAGE_FORMAT_VERSION + “//” + ARTIFACT_TYPE + “//” + ARTIFACT_CONTENTS

It then outputs the following to a .vxsig file:

SIGNATURE_LENGTH + SIGNATURE + SIGNING_MACHINE_CERTIFICATE

The importing machine parses the above, extracts the exporting/signing machine’s public key from its certificate as provided in the .vxsig file, reconstructs the message, and then verifies the signature. The importing machine also importantly verifies that the signing machine certificate in the .vxsig file is a valid certificate that is 1) signed by VotingWorks and 2) for the expected machine given the artifact type, e.g. VxAdmin if the artifact is a ballot package. We verify 1 using the VotingWorks CA certificate installed on every machine.

If signature verification fails on the importing machine, the importing machine will refuse to import the artifact. This provides protection against data tampering and/or corruption as data is transferred from one machine to another via USB.

Code Links

Refer to the following codebase links for more detail on VxSuite artfiact authentication:

• https://github.com/votingworks/vxsuite/tree/main/libs/auth — VxSuite authentication lib, a good starting point for all things authentication

• https://github.com/votingworks/vxsuite/blob/main/libs/auth/src/artifact_authenticator.ts — Artifact authentication logic

• https://github.com/votingworks/vxsuite/blob/main/libs/auth/src/cryptography.ts — OpenSSL commands underlying various authentication and signing operations