Validation of Ballot Chaining

[keithrfung]

This is to continue the conversation of Ballot Chaining from this issue:

Main Issue
Election-Tech-Initiative/electionguard-python#272

Related Issue

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.
Election-Tech-Initiative/electionguard-python#57

Referencing the relevant members of that convo
@JohnLCaron
@AddressXception
@rc-ms
@danwallach
@benaloh

[JohnLCaron]

Validation of ballot chaining has two aspects that might cause problems:

1. Ballots have to be stored in the same sequence as the hash chain. Right now, ballots are simply written to individual files named by ballot_id, which may not be sequential. The file system has no obligation to keep these in order.
2. Validation of a ballot is no longer independent of other ballots, so cannot be parallelized at the ballot level.

[rc-ms]

Agreed. For end-to-end verifiablie options, we need to implement a ballot-chaining method and will present a proposal in the coming days that addresses your very point. For your second item, we do not need ballot chaining for an audit use case so we want to support a parallelization option as well. @AddressXception proposed a way of handling chaining as per the spec in a modular way so audits can function as they need to as well.

[benaloh]

This might be a good opportunity to explain the rationale behind ballot chaining. It is not critical to E2E-verifiability or anything else that we do, and we could simply eliminate it if it becomes too onerous. The value of ballot chaining is that it mitigates what is sometimes called a "trash attack".

Without chaining, there is nothing to stop malicious insiders from simply discarding ballots they they might suspects will not be checked. One instantiation would be that a poll worker collects the trash outside of a poll site at the end of the day and picks up any tracking codes that have been discarded. Although not impossible, it is very unlikely that anyone will miss any of these codes if they are simply deleted and replaced with fraudulent new ones.

By chaining ballots, and specifically tacking codes, it becomes impossible for rogue insiders to replace ballots after the fact. Any change in the middle of a chain would alter all subsequent tracking codes. Rogue poll workers could potentially still see a voter discard a tracking code and quickly delete the ballot before the next voter arrives, but this is much harder to effect. There is also nothing to stop the end of a chain from being altered, so the ideal would be to ensure that the final tracking code has high visibility by engaging in a process that causes a final tracking code to be produced and shown to everyone present when a poll is closed.

It's presumably simplest to have the chains be per device to minimize communication and dependencies. Although there is a lot of flexibility in how this is implemented. Also, as RC says, there is no point in a chain for the RLA scenario since the attack does not apply in that case.

[danwallach]

I have two modest requests:

• Pay attention to big-O. It would be catastrophic if we had millions of ballots landing in a single, linear, hash chain, which could happen if we encrypted the output of a central scan tabulator. There are numerous tree-shaped things out there, including what I worked on a decade ago (https://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf), which get the costs down.
• Keep the hash-integrity verification machinery out of the definition of a ballot. Think of it as a general-purpose file system or database or log system, but don't think of it as a thing specifically for ballots. You write to it. You read from it. When you read from it, there's a possibility that those reads will fail, because the hashes aren't lining up.

On a BMD which wants to output some sort of hash commitment, it can ask the log machinery for the latest commitment, and output that alongside whatever else it's writing into the voter's receipt.

In that paper that Crosby and I wrote in 2009, we thought a lot about these sorts of issues. I'd hope we can benefit from some of that thinking now. Also, there's some old Python code banging around that we can use as a template, although it's going to be Python2, so no type annotations, etc.

[danwallach]

BTW, if you read that paper, we have a concept of "Merkle aggregation", where you can "add" up anything you want as part of the tree structure, from bottom to top. This would actually jive really nicely with our homomorphically tallies. Probably not necessary, but just a clever thing we could do.

[danwallach]

Ohai, the code that Crosby wrote is actually in Java!
https://github.com/scrosby/fastsig/tree/master/src.lib/edu/rice/historytree

[rc-ms]

I’m all in on Merkle aggregation; it’s now my phrase of the week and maps exactly to how we (“we” meaning people that are not me) were thinking of things

[JohnLCaron]

As an outsider, Im swayed by Josh's argument that chaining is important, and despite his disclaimers, maybe even necessary. I do understand its not useful in RLA. And that a central scanner might output very large chains that deserve big-O attention. The use case I am wondering about is when the election record comes from a single precinct level voting machine (what's a typical ballot count range for those?). But then there are thousands (how many?) of those in a populous election district. What could help prevent bad actors from adding spurious election records?

[vteague]

Is there any chance we could achieve defence against the trash attack, but by adapting the Merkle Tree structure somehow? For example, rather than incorporating a hash of the previous ballot (as in a hash chain) could we incorporate some part of the Merkle Tree with the same effect?

I haven't thought about this hard, but perhaps ballot N could include something like the highest so-far-constructed node that incorporates ballot N-1?
------N1234--------
--N12-----N34-----
1-----2___3----4___5

e.g.
ballot 2 gets N12;
ballot 3 gets N12;
ballot 4 gets N1234;
ballot 5 gets N1234
etc?

(This particular construction could be total rubbish - I'm just suggesting there might be a good O(log n) solution.)

[JohnLCaron]

These are some notes from looking at the latest spec, thought it would be worth consolidating here:

6.A H0 = H(Q̅)

We talked about letting H0 be something else, though I dont see any problem with it being H(Q̅ ).

6.B H_i = H(H_i−1, D, T, B_i )

1. Add D to the definition table. pdf p 19 has "where D consists of the voting device information described above", but I dont see that anywhere, and its currently not implemented.
2. Add T to the definition table. pdf p 19 has "T is the date and time of ballot encryption" which isnt well defined. In implementing, one just uses whatever is in the election record for that ballot, CiphertextAcceptedBallot.timestamp. Currently thats an int64, "tics since the unix epoch", time zone unclear, but UTC is a good choice.
3. Add B_i to the definition table. pdf p 19 has "B_i is an ordered list of the individual encryptions on the ballot – with the ordering as specified by the ballot coding file". Currently the implementation uses CiphertextAcceptedBallot.crypto_hash, which might be this definition? And begs the question as to whether the verifier needs to independently calculate that quantity, rather than use whatever is in the election record.

6.C the closing H(H_last , "CLOSE") is correctly computed from the final tracking code H_last .

Seems like you could just store H_last in the election record, maybe the PublishedCiphertextTally?

[benaloh]

6.A The initial hash H_0 should include the extended base hash Q̅. If desired, it could contain a per-device start code or any other additional date.

6.B Yes. The detailed format of the date, time, etc. can be chosen as convenient for the implementation. But we should make them clear for everyone to see and replicate.

6.C An explicit CLOSE of each hash chain is probably not necessary, but it seems like a useful safety feature. The process expectation would be that when poll workers take the steps to close a precinct that one of these steps will cause a closing hash to be computed and then immediately published to all present along with the cleartext tallies. We could probably just publish the final tracking code at that time, but an explicit closing hash precludes any possibility of subsequent hashes being tacked onto the end.

[eleanor-em]

Hello hello, just wondering if there's any ideas whether a Merkle tree-like structure for efficient inclusion is on the cards for the near future? Or is it more a long-term goal?

[AddressXception]

moving this discussion to the main electionguard repo:

#73