microsoft/electionguard-python

A python module implementing the ElectionGuard specification. This implementation can be used to conduct End-to-End Verifiable Elections as well as privacy-enhanced risk-limiting audits.

🗳 ElectionGuard Python

This repository is a "reference implementation" of ElectionGuard written in Python 3. This implementation can be used to conduct End-to-End Verifiable Elections as well as privacy-enhanced risk-limiting audits. Components of this library can also be used to construct "Verifiers" to validate the results of an ElectionGuard election.

📁 In This Repository

File/folder	Description
docs	Documentation for using the library.
src/electionguard	ElectionGuard library.
src/electionguard_tools	Tools for testing and sample data.
src/electionguard_verifier	Verifier to validate the validity of a ballot.
stubs	Type annotations for external libraries.
tests	Tests to exercise this codebase.
CONTRIBUTING.md	Guidelines for contributing.
README.md	This README file.
LICENSE	The license for ElectionGuard-Python.
data	Sample election data.

❓ What Is ElectionGuard?

ElectionGuard is an open source software development kit (SDK) that makes voting more secure, transparent and accessible. The ElectionGuard SDK leverages homomorphic encryption to ensure that votes recorded by electronic systems of any type remain encrypted, secure, and secret. Meanwhile, ElectionGuard also allows verifiable and accurate tallying of ballots by any 3rd party organization without compromising secrecy or security.

Learn More in the ElectionGuard Repository

🦸 How Can I use ElectionGuard?

ElectionGuard supports a variety of use cases. The Primary use case is to generate verifiable end-to-end (E2E) encrypted elections. The ElectionGuard process can also be used for other use cases such as privacy enhanced risk-limiting audits (RLAs).

💻 Requirements

• Python 3.9+ is required to develop this SDK. If developer uses multiple versions of python, pyenv is suggested to assist version management.
• GNU Make is used to simplify the commands and GitHub Actions. This approach is recommended to simplify the command line experience. This is built in for MacOS and Linux. For Windows, setup is simpler with Chocolatey and installing the provided make package. The other Windows option is manually installing make.
• Gmpy2 is used for Arbitrary-precision arithmetic which has its own installation requirements (native C libraries) on Linux and MacOS. ⚠️ Note: This is not required for Windows since the gmpy2 precompiled libraries are provided.
• poetry 1.1.13 is used to configure the python environment. Installation instructions can be found here.

🚀 Quick Start

Using make, the entire GitHub Action workflow can be run with one command:

make

The unit and integration tests can also be run with make:

make test

A complete end-to-end election example can be run independently by executing:

make test-example

For more detailed build and run options, see the documentation.

📄 Documentation

Overviews:

• GitHub Pages
• Read the Docs

Sections:

• Design and Architecture
• Build and Run
• Project Workflow
• Election Manifest

Step-by-Step Process:

0. Configure Election
1. Key Ceremony
2. Encrypt Ballots
3. Cast and Spoil
4. Decrypt Tally
5. Publish and Verify

Contributing

This project encourages community contributions for development, testing, documentation, code review, and performance analysis, etc. For more information on how to contribute, see the contribution guidelines

Code of Conduct

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

Reporting Issues

Please report any bugs, feature requests, or enhancements using the GitHub Issue Tracker. Please do not report any security vulnerabilities using the Issue Tracker. Instead, please report them to the Microsoft Security Response Center (MSRC) at https://msrc.microsoft.com/create-report. See the Security Documentation for more information.

Have Questions?

Electionguard would love for you to ask questions out in the open using GitHub Issues. If you really want to email the ElectionGuard team, reach out at [email protected].

License

This repository is licensed under the MIT License

Thanks! 🎉

A huge thank you to those who helped to contribute to this project so far, including:

Josh Benaloh (Microsoft)

Keith Fung (InfernoRed Technology)

Matt Wilhelm (InfernoRed Technology)

Dan S. Wallach (Rice University)

electionguard-python's Issues

Establish Windows Workflow and Action

A working windows workflow and accompanying GitHub action need to be created to help users identify how to use this project.

End to End Election Integration Test

Create a integration test that runs through end to end election

Revisit handling errors and the impact on Optional

Current as defined in the Architecture and Design document, we return Optional to allow returning none and failing quietly. There are numerous sections where this creates convoluted and not clear code. This needs to be revisited and discussed.

One such issue is the use of int_to_q_unchecked and similar functions. These are used frequently and push the issue around of when to return None due to a failure. These would be much clearer with a throw of an Error with a message.

One possible solution is that all global stateless functional methods do not return Optional and stateful classes always return Optional. This would allow for throwing errors at those levels.

Output Data Representation

Determine the proper format for representing output data from the system.

This was brought up as part of this: #1 (comment)

One consideration is the representation of ElementModP and ElementModQ which will require some custom parsing to properly represent these values

Create dependency graph step in CI

Utilize pydeps to display a dependency graph as a visible artifact in the CI process

https://pydeps.readthedocs.io/en/latest/

https://pypi.org/project/graphviz/

Command should be something like:

• pipenv run pydeps . --show-dep

Create make commands
make install-graph-tools
make install-graph-tools-mac
make install-graph-tools-windows
make install-graph-tools-linux

make dependency-graph

Define placeholders for contests at election instantiation

When creating an election, we should instantiate the placeholders for each contest once at startup so that we can minimize redundant compute cycles and reduce code complexity in the encrypt/decrypt loops

Implement Master Ballot Nonce Encryption

there are several cases where we need to use a free-form encryption in the application.

1. when sharing keys between guardians
2. when storing or sharing nonce values
3. when encrypting/decrypting value in the extended_data field on a ballot

we will implement an "ordinary elgamal" encryption that will give us up to 3840 bits fo fidelity.

we will choose a prime p for ordinary ElGamal such that p mod 4 = 3, option 3 becomes easier in this case because it ensures that (-1) is a non-square mod p.

say we have a message m:

1. append SHA-256(m) to get M=(m|SHA-256(m))
2. Check if M is a square mod p by computing z = M^((p-1)/2) mod p
3. If z=1, compute an ElGamal encryption of M. If z=-1, compute an ElGamal encryption of (-M) instead.

After decrypting, check if the final 256 bits is the SHA-256 hash of the first 3840 bits. If it is, take the first 3840 bits as m. If not, negate the result and then take the first 3840 bits as m (the remainder should match the SHA-256 hash of m).

Design Considerations

sensitive values should be created and immediately encrypted in the same function where they are generated. They should only be long-lived in memory in the encrypted form.

open question: Should A guardian's election key pair should also be encrypted with the free-form encryption?

We must designate a fixed-length of the data that is going to be encrypt-able by the free-form encryption. Given that secret keys are in the space [1,Q) it is likely we should choose 256 bits

Guardian keys:

1. election public/private key pair (for exponential elgamal)
2. election free-form public/private key pair (for ordinary elgamal, encrypting nonces, extended data, etc.)
3. secret-sharing public/private key pair (for any encryption scheme, our implementation is ordinary elgamal)

Election Keys:

1. election joint public key (exponential)
2. election joint free-form public key (ordinary)

Generating the joint free-form key

The joint free form key is generated using the exact same secret sharing process as is used for the primary election key.

Sharing keys between guardians

When sharing keys between guardians, the free-form encryption is used to encrypt the election private key shares and the election free-form private key shares. The function used to do this is pluggable to support an external system choosing to use a different form of encryption, such as RSA. A stub for this already exists. Our default implementation will re-use the same ordinary elgamal encryption mechanism we are using for the joint free-form key. This means we will be using an ordinary elgamal key pair in the context of a guardian secret-sharing to encrypt another ordinary elgamal key pair used in the context of encrypting free-form values in the election

Storing or sharing nonce values

Once the guardians have shared and verified the keys, a secondary election free-form joint public key is associated with the CiphertextElectionContext and used to encrypt the random master nonce values that are generated for each ballot. The encrypted representation of the random master nonce replaces the current unencrypted nonce on the CiphertextBallot.

To support key flexibility, we must also support the use case that a specific consumer may not be using the guardian key ceremony artifacts and therefore we must allow a single public/private key pair to serve as the election joint free-form key. This should work in a similar format to encrypting/decrypting ballots by using a single key that bypasses the key ceremony entirely.

This supports several use cases, specifically:

1. using the key ceremony for both encrypting ballots and nonce values, but separating the contexts with the 2 separate keys described above
2. using the key ceremony for encrypting ballot selections, but disallowing the guardians from decrypting or knowing the nonce values used for the ballots
3. similarly, using a single key pair for the ballots, but using the key ceremony for the nonces
4. using single values for the ballots and using single values for the nonces

Encrypting/decrypting the value in ExtendedData

On a ballot, the extended data field is also encrypted with the election joint free-form public key. In order to make the ballots homogenous, extendedData values are padded to max length. if no data is passed in the extended data field, then random data is generated to fill the field. There is more info in #35

In the default workflow for an end-to-end election, the key ceremony guardians are used to generate both the joint public key and the free-form public key; and the free-form key is used to encrypt both nonces and extended data.

In our implementation, if the key ceremony guardians are used for all keys, we only support reusing the free-form key for both extended data and nonces. The option also exists to use a different free-form key for either the nonce values or the extended data fields by providing a single key-pair for either case. It is up to the consumer to implement this if desired.

Implement Ballot Encryption and Define Data Structures

Encrypt the ballot with python infrastructure

• Define initial ballot data structures
• Execute ballot encryption
• Ensure tests cover edge cases

Add crypto "test parameters" to speed up unit tests

The problem: Big unit tests suites run slowly, bottlenecking on the cryptographic computations.

The current workaround: Reducing the number of tests or the size of the tests that run. Particularly for the Hypothesis tests, this reduces their ability to find bugs.

The better solution: Have smaller values for P, Q, and G, such that everything fits in 32 bits or even 16 bits.

The challenge: How do we introduce "test parameters" without them ever, ever finding their way into production code? What's the minimal set of changes to add a "test mode"?

Two broad options:

1. "Monkey patching" or otherwise having test code, from outside of the electionguard package, reach into the package and make changes. Editing the values of P, Q, and G is easy. Similarly, it looks like all you have to do is change Q_MINUS_ONE and you'll fix hash_elems.
2. Having a "test mode switch" wired directly into the electionguard package. It sets a globally visible boolean flag and overwrites the values of P, Q, G, etc. It would also nuke the dlog cache state.

I'm slightly in favor of the "test mode", since it can generate suitably loud warnings if it's ever used in a real election, or could even disable specific features, like writing persistent data to a file. Another way to ensure mistakes aren't made is to just write out the parameters as part of any election file, so if we see any election with "test parameters", that will be an instant read flag. Like, trying to load up some persistent data, the first thing you do is check the parameters, and if they're not equal to what you expect, you raise an error.

How do you pick the right parameters? Says our resident cryptographer: "All we need is any small prime q that is larger than the number of voters and a larger prime p such that p-1 is a multiple of q. We don’t have to go to all of the trouble I did to select primes to optimize other characteristics and to do so in a publicly-justifiable way."

I already had a Sieve of Eratosthenes program hanging around, so I searched for the smallest Q greater than 32767 (2^15 - 1) and came up with:

P = 65543
Q = 32771

Implement Trustee Key Ceremony

Support regenerating and reverifying tracking codes

Tracking codes are generated based on a specific ballot marking device. In order to verify that the tracking codes are constructed correctly, each ballot has to be associated with the device that encrypted it.

in encrypt.py add the device hash to the encrypt_ballot function interface so it can be propagated with the ballot. Also propagate the seed hash so that the ballot tracking id's can be regenerated by traversing the collection of ballots encrypted by a specific device.

`PlaintextBallotSelection` `plaintext` field should be an `int`

Since we added the extended_data field to capture text, the plaintext field can be replaced with an integer.

As a string, this filed is flexible and supports an extended range of use cases without having to modify the data structure, but at the expense of added parsing complexity. Since this field really is just a value that is encrypted, it could be an integer and imply to the consumer that this is an encodable value and that the extended_data field should be used for any string representations. One other consideration is that this decreases the human readability of a plaintext ballot expressed in json (unless we further add parsing complexity).

in such an implementation, for n-of-m type contests; the value 0 should always resolve to False whereas any other value should resolve to True

Consistent Multiprocessing for Tally

multiprocessing is used in a few places to speed up computation of some large values. When using the library in the recommended way, it behaves as expected, however it is possible to deadlock by calling internal functions. This is illustrated by Pool objects existing in multiple scopes.

Proposed solution:

Implement a consistent queuing strategy for scheduling work on multiple processors so that the library cannot be deadlocked intentionally or unintentionally.

The focus on this card is going to be moved to displaying an example of paralleling for Tallies specifically.

Refactor CiphertextBallot and CiphertextAcceptedBallot relationship

In the current implementation, the CiphertextAcceptedBallot inherits directly from the CiphertextBallot however this relationship is not correct since the CiphertextAcceptedBallot should not have a nonce field for itself or any contest or selection and it should also require that the proof field is required for each contest and selection.

Proposed solution:

create a CiphertextBallotBase which other elements can derive from. Similarly, refacotrs will need to be completed for CiphertextBallotContest and CiphertextBallotSelection.

children:

• CiphertextSecretBallot - (the current CiphertextBallot) which includes a required nonce and an optional proof
• CiphertextVerifiableBallot - no nonce and proof is required
• CiphertextAcceptedBallot - inherits CiphertextVerifiableBallot and includes the state field.

Explain project workflow and github workflows

Explain how the project will be managed and how the workflow works going forward for future maintainers. Also, explain the Github workflows and their purposes.

Expected to be in markdown file in the docs folder.

Implement Guardian Decryption (All Present)

Decrypt with all guardians present

decrypt spoiled ballots

• spoiled ballots also publish their nonce values, which is a shortcut to decrypting with the guardians

Automated Document Generation

Create automated documentation such as doxygen for python code.

Expectations are this exports to

1. readthedocs
2. GitHub pages

in our documentation we need to include defining the various ways to interact with the system, for instance, we need ot call out that an encryption device can choose to discard the encryptions and proofs, and only keep an encrypted representation of the master ballot nonce and the tracking code as a secondary workflow

Handling scalability of Output Data with directory structure

If we have a million or more encrypted ballots, and we want "random access" to them (e.g., a web server that you give the ID of a ballot and it returns the ciphertext). This suggests that we cannot simply write out a single, enormous JSON file with a list of the ballots. However, we could definitely write out one file per ballot.

1. If you have a million files in a single directory, things get chunky. Just getting a directory listing can be painful. The usual workaround is to use subdirectories. So, if the files were named with six base-10 digits (e.g., 123456.json), you could store them as 12/34/123456.json.

2. If we stick with JSON for the on-disk representation, which is perfectly reasonable, we probably want to compress it. Python has support for several different compression algorithms (https://docs.python.org/3/library/archiving.html). Security issues could crop up here if the compression code is written in C, so some advance auditing would be relevant. On the other hand, if we go with a binary format (msgpack, protobufs, etc.), then this issue goes away.

3. So those JSON files have individual encrypted ballots. We still need all the metadata. That probably goes in a "main" JSON file of some sort, which then includes SHA256 hashes of the individual encrypted ballot files. The main JSON file could itself then be digitally signed with conventional tools, or maybe the hash of the main file is published by the election officials and we're done. No need for digital signatures at all? As described, this is a cheesy two-level Merkle tree. If we were worried about the main file getting too big, then we could add another level. It's at best unclear whether we want/need a general-purpose Merkle tree implementation.

resolution of this issue should be paired with #96 to provide a lookup recordset

Establish Mac Workflow and Action

A mac workflow test and action need to be established to ensure users know how to use the system.

Add Pull Request Template

Add pull request template that lines up with standard electionguard pull request template across other repositories.

Ballot Accumulation

Cast/spoil

Implement Ballot Tracking Codes

Update Architecture & Design Notes

Notes on Architecture on Design in python should be updated from engineering notes for future coders to line up correctly.

Contribution Section

Add contribution section to detail major contributors across releases and highlight particular contributions going forward.

Distribute as Package

distribute electionguard as a package that can be consumed, such as via pypi

• Add release or package workflow
• Add badges to repo
• Add distributable package on pypi and github packages
• Update Microsoft Banner Image

Create Key Ceremony Hypothesis generators

The tests that cover the key ceremony, guardian, and key ceremony mediator, and election polynomial are sufficient unit tests for development, however we should also provide hypothesis tests similar to those used for the election, encrypt, and decrypt functions that exercise a broad spectrum of valid and invalid input data.

object_ids should have internal structure

Right now, these object_id strings are tricky. Since they’ve all got the same type (string), it’s easy to mix them up.

Proposal: all object_id strings should have a “type prefix” (think: “Hungarian notation”), which is enforced by all the constructors for ElectionGuard core types. So, for example, all Candidate object_ids must start with the prefix “candidate” and then can be anything after that, so candidate1, candidate2, or candidate-0195-ab3f-129b, doesn’t matter, so long as you’ve got the right prefix.

Then, when you’ve got cross-references, where one thing names another, you can “type check” the object_ids to make sure they’ve got the proper prefix.

Example: a BallotStyle has a list of GeopoliticalUnit object_ids in it. If the BallotStyle constructor required every string in that list to have the prefix gpunit, that would catch bugs and be useful during debugging.

consistent logging

currently logs.py uses global functions but should instead be scoped to a specific instance or process, possibly by using an object.

additionally, a consistent log format should be specified and the public logging api should automatically take object scope into account.

Hash cleanup

the hashing mechanism api surface could be modified to better support optionals and nulls. This will reduce code complexity by removing the need for the generic type, and the flatten method.

additionally the CryptoHashable and CryptoHashcheckable protocols should be cleaned up to better express that these two concepts are different. There is the concept of a hash over metadata, and there is the concept of a crypto hash, which may be a combination of the hash of the metadata along with some other external seed.

one consideration is support for this in the hash_elems method, which likely cannot handle a method parameter that gets passed to the protocol implementation that requires the seed parameter.

see this: #1 (comment)

Support multiple `VoteVariationType` values

currently electionguard only supports n-of-m style vote variations. Add support for other types of contests.

Accept Ballot force validation

the accept_ballot function should automatically regenerate proofs if they are missing. if it cannot, it should reject a ballot that is missing proofs.

encrypt ballot async

currently ballot encryption occurs synchronously, but we should support both pooling on mutliple core machines and have asynchronous versions of the methods.

in ballot.py add a multiprocessing pool to encrypt the selections of a contest using all available cores.

also, add encrypt_ballot_async and corresponding asynchronous loops to support cases where a consumer may not want to wait for the process to finish.

Add master branch CI rules

master should have CI rules ensuring that all cross platform builds pass

Improve metadata validation

The current implementation of input validation for an ElectionDescription skips a few details:

• there is no verification on ElectionType. for instance, for party primaries, then all candidates should have the same party?
• there is currently no validation done for ballot styles connected to party id's and verifying the contests are correct for that style
• we should require that every candidate has a party specified, and that there is a special party for non-partisan
• we should verify that the contest sequence order set is in the proper order for the election
• document and validate the candidate_id in SelectionDescription

Streamline Python Workflow

• Debate use of tox
• Ensure feature parity including use of mypy as static type checker, unit tests using hypothesis, and code coverage
• Add linting / formatting check
• Speed up speed of unit testing or allow to isolate a test locally
• Investigate best case for running locally
• Publish pyp package for pip install

GeopoliticalUnit vs. BallotStyle, and what to do if the former is absent

Consider the case of ElectionGuard being used to encrypted a manifest of ballots from a list of CVRs, where we know (or can infer) the ballot styles, but where we have no information about the geopolitical units.

At that point, any attempt to infer GeopoliticalUnits will need to wing it. The choices seem to be:

• GeopoliticalUnits map one-to-one with contests
• GeopoliticalUnits map one-to-one with ballot styles
• You have one singular GeopolitcalUnit and use that everywhere

What's a GeopoliticalUnit supposed to be? That's a bit unclear, but a useful way to think about it is a polygon on a map.

The singular GeopoliticalUnit seems like the preferable solution, as opposed to just making things up. Consider some problems with the other options:

• A Contest, by definition, has a singular electoral_district_id, which is meant to be a GeopoliticalUnit. Since a Contest can appear across multiple ballot styles, this means the "one-to-one with ballot styles" option doesn't work.
• So what about one-to-one with contests? This could work, and makes the GeopoliticalUnit data into a shadow copy of the Contest data. At that point, it's reasonable to ask why we're tracking GeopoliticalUnits at all.

Performance implications

(Need to double check this, but...) Right now, when ElectionGuard encrypts ballots, the work it does is apparently based on the GeopoliticalUnits rather than on the BallotStyles, in terms of not bothering to encrypt choices that a voter wasn't presented on any given ballot. This means that a singular GeopoliticalUnit would have slower encryption performance than a GeopoliticalUnit one-to-one with Contests.

Arguably, the BallotStyle data should be definitive in what Contests are and are not encrypted on any given ballot.

Create a Flask Api

Implement an API, probably with ReST, using Flask (https://flask.palletsprojects.com/en/1.1.x/) to display the possible uses of electionguard.

improve input validation when encrypting ballots

encrypt_ballot

• validate that contest object_ids provided match valid contests for the ballot style
• validate that there are no duplicate contests provided

encrypt_contest

• validate that selection object_ids provided match valid selections for the contest description
• validate that there are no duplicate selections provided

additionally, the current use of is_valid on the ballot may be insufficient to capture this information in a clear way. Instead, validation may need to be handled in a separate class in order to concisely validate ballots against their expected descriptions without breaking the object graph.

Add bit-packed serialization mechanism

currently the Serializable interface supports to_json and from_json

as a consuming application i would like to serialize and deserialize using a binary serialization mechanism so that i can conserve space for objects in transit and on disk.

both message pack and protobuf are reasonable options.

Additionally, as a consuming application i would like to have strong confidence that the serialization parsers behave consistently so i do not have to worry about malformed data issues.

consider using EverParse

Implement Ballot Decryption

Create Command Line Interface

Implement a command line interface so a user can start electionguard in the command line and run commands for a way to interface with electionguard.

installation-steps for beginners

Hi, I would like to suggest to put more detailed steps about howto install and start using everything in the readme file. Executing make or sudo make isn't working for me. Could be something todo with different versions of python on my system and me not having basic knowledge about this. (I'm on Linux mint) but I guess I wont be the only beginner who will bump onto this.

Add CodeQL GitHub Action Check

Github Action:
https://github.com/github/codeql-action

This is rebranded version of LGTM

Update Decryption Documentation

The language and flow of the decryption documentation needs to be updated to better reflect the process.

Create make files for workflow

to reduce the complexity of the GitHub actions and simple runs from command line

Create Remote Procedure Interface

For users that may wish to have a remote procedure interface for certain interactions with electionguard.

Encrypt `extended_data`

The PlaintextBallotSelection includes an extended_data field that should be encrypted and decrypted.

Question: The encryption method should be able to support string lengths up to 256? or 256 bits?

In order to make the ballots homogenous, extendedData values are wrapped in an internal data structure and padded to max length. The first 4 characters are reserved for the length, and then the string follows.
if no data is passed in the extended data field, then random data is generated to fill the field and it is keyed specifically to be identified as random data.

For instance, something like this:

1. extendedData in: some write in candidate name, extended data out: 028:some write in candidate name_gj8749hg8g55h98... where 028 is the character count of the real data
2. extendedData In: (an empty string), extendedData out: 000:_jh7453h7egnu9...

as an alternative we could use ore reuse some binary serialization mechanism and then encrypt the serialized value?

suggestions welcome

error handling for words.py

src/electionguard/words.py: the methods here don't handle bad input, and will instead implicitly raise errors or have undesirable behavior. Perhaps these should return Optional results, and require error checking.

Implement Trustee Threshold Decryption

Remove BallotStore

The ballot store is deprecated in favor of using the generic DataStore. this ticket is to remove the ballot store and replace all usages with a generic data store