-blue){kind=icon}
last update 06/03/2024
Implementation of a mixnet using the ElectionGuard Kotlin Elliptical Curve library, and the Verificatum library. The mixnet uses the Terelius / Wikström (TW) mixnet algorithm, see egk mixnet maths for details. Note that paper's timings use the older integer group; the elliptic curve group is much faster.
This is part of VotingWork's cacvote project. It is not part of the ElectionGuard specification per se, but follows the ElectionGuard 2.0 specification wherever possible.
The implementation for Elliptical Curves (EC) is derived from the Verificatum library, including the option to use the Verificatum C library. See VCR License for the license for this part of the library.
Note that the EC implementation is not stable and may change in the future. However, other than different build instructions, this should not affect the API.
Also see: Workflow Notes
- Egk Elliptic Curves Mixnet
Encrypting a ballot with 12 contests and 4 selections each (total of 60 encryptions) takes about 6 ms per ballot, using pre-computed tables for "fixed base acceleration". This does not appear to be using Montgomery forms for fast mod operation.
Mixing 1000 ballots of width 34 takes ~ 17 secs single threaded with good parallelization. Verification is 30-50% slower than the shuffle and proof, see plot.
We use "point compression" on the elliptic curve ElementModP, so we only serialize the x and "sign of y" coordinates, giving a storage reduction of O(64/33) compared to serializing both coordinates, and O(512/33) compared to the integer group. To estimate the computational cost of storing just x and recomputing y: BallotReader reads 1000 ballots (width 34) in 235 msecs. If one computes y instead of reading it, it takes 1274 msecs. So, cost is ~ 1 sec for 34000 texts everytime you have to read the mixed ballots.
Currently we store the ballots in binary and the proofs in json in base64. For very large mixnets, you might want to store proofs as efficiently as possible, which argues for a protobuf option.
readMixnetBallots from working/public/mix1/Shuffled.bin nrows = 1000 width=34
BallotReader took 2352 msecs = .006917 msecs/text (340000 texts) = 235.2 msecs/trial for 10 trials
BallotReaderAlt took 12744 msecs = .03748 msecs/text (340000 texts) = 1274 msecs/trial for 10 trials
cd <install-dir>
git clone https://github.com/JohnLCaron/egk-ec-mixnet.git
cd egk-mixnet
Prerequisites: Java 21
To build the code:
./gradlew clean assemble
./gradlew uberJar
If the library has changed and you need to update it:
cd ~/dev/github/egk-ec-mixnet:
git fetch origin
git rebase origin/main
Then rebuild the code:
./gradlew clean assemble
./gradlew uberJar
Follow the instructions in Egk-ec Getting Started
This is needed for good performance.
~/dev/github/egk-ec-mixnet:$ ./scripts/completeWorkflow.sh working
Runs a complete test of the workflow and writes the output to whatever you set working to.
After running, examine the log file at egkMixnet.log.
The components of this workflow are:
- Uses src/test/data/mixnetInput/manifest.json for the egk manifest. (Change in election-initialize.sh if you want)
- Creates an egk configuration file with default election parameters. (Change in election-initialize.sh if you want)
- Runs the egk keyceremony to create private egk directory.
- Copies the public egk files to the public mixnet directory.
- Generates random plaintext ballots from the given manifest, and writes their encryptions to the public mixnet directory.
- This is the main functionality that needs to be implemented by the election voting system. Likely the voting system will write the plaintext ballot to disk and call RunEncryptBallot.main() with appropriate parameters.
- Homomorphically accumulates digital ballots into an encrypted tally.
- Uses trustee keys to decrypt the tally.
- Runs the egk verifier to do electionguard verification.
- Shuffles the ballots using two shuffling phases, writes to the public mixnet directory.
- Runs the verifier on the mixnet proofs.
- From the last mix's ShuffledBallots, generate table of decrypted (K^sn) serial numbers and proofs.
- This table is written to working/public/decrypted_sns.json.
- Simulate a table of paper ballot serial numbers and their physical locations.
- Pass in "--missingPct percent" to simulate some percent of paper ballots were not received.
- This table is written to working/public/pballot_table.json.
- From a paper ballot's serial number (psn), find the corresponding shuffled ballot and decrypt it.
- Place decrypted ballot into private/decrypted_ballots/ directory.
- Use psn as the decrypted ballot id, and the filename is dballlot-psn.json.
- Verify the proofs in the decrypted serial numbers (decrypted_sns.json).
- Verify the decrypted ballot proofs.
- If digital copies of the paper ballots are available, compare the ballot decryptions to the originals.
working/public
encrypted_ballots/
device1/
eballot-id1.json
eballot-id2.json
device2/
eballot-id1.json
eballot-id2.json
...
mix1/
mix_config.json
proof_of_shuffle.json
ShuffledBallots.json
mix2/
mix_config.json
proof_of_shuffle.json
ShuffledBallots.json
mixN/
...
constants.json
election_config.json
election_initialized.json
encrypted_tally.json
manifest.json
tally.json
decrypted_sns.json
pballot-table.json
working/private
input_ballots/
pballot-id1.json
pballot-id2.json
...
trustees/
decrypting_trustee-name1
decrypting_trustee-name2
...
decrypted_ballots/
dballot-sn1.json
dballot-sn2.json
...