Ballot Proof of Inclusion

[AddressXception]

We recently discussed several practical implementations of proving that a ballot is included in a record set. It appears that there are multiple use cases where a voter may want to prove a ballot's inclusion in a dataset that are related to a verifiable lookup so that the voter does not have to process the entire election result set.

Questions

❓ How can the voter can trust the integrity of the data?
❓ How can a 3rd party verify the lookup is correct?
❓ What known attacks are present to constrain the design of this feature?
❓ Is there a single best-case implementation that can address the known use cases?

User Stories

• As a Voter I would like to verify that my ballot is included in a recordset after the election results have been published so that I can test the integrity of the election system.
• As a Voter i would like to verify that my ballot will be included in a tally prior to the tally being completed so that I can have confidence in the election system while relying on a trusted intermediary or third party to complete the verification.
• As a 3rd party verifier I would like to validate the entire record set is complete so that I can prove an election system did not exclude any results

Implementation Details

Here are a some examples:

• Some 3rd parties could build a verifiable lookup from the official published record set of an election and publish the lookup for public query
• a vote administration authority could intermittently publish a verifiable lookup (either associated with a tally or not) and the lookup could then be verified by some 3rd parties after the official tally is published
• a 3rd party could "request" or initiate a tally process in some way, thereby compelling a vote administrator to make a commitment to a verifiable lookup given some constraint (at a specific time or threshold)

Proposed solutions

A few methods of generating a verifiable lookup have been proposed including:

• A tree-like data structure such as the Tamper Evident Logging method proposed in the previous discussion
• Using Digital Signatures
• A one-way accumulator

Previous Discussion

Previous relevant discussion in the python repo available here:
https://github.com/microsoft/electionguard-python/discussions/282

[danwallach]

A couple thoughts on implementation details:

• Whatever the data structure ends up looking like, it should generically operate on arrays of bytes written out to individual files. Since an encrypted ballot can easily become a megabyte of ciphertext, imagining them written separately to files is a reasonable approach.
• For the general-purpose verification case, where we might be using a cluster to tally millions of ballots, it's essential that we have sub-linear membership proofs.
• For arlo-e2e, where the encryption process also occurs in parallel on a cluster, we need to imagine concurrent writes to the data structure, although that's specialized enough that it doesn't necessarily need to be a core function of the ElectionGuard library. The solution that arlo-e2e is moving towards is to have a "manifest" in each subdirectory which has hashes of all the file contents, except for subdirectories, which will have the (recursive!) hash of the inner manifest.