"Validation of Ballot Chaining" in spec is wrong or not implemented correctly

[JohnLCaron]

In part 5 of https://github.com/microsoft/electionguard/files/5278086/EG.Verifier.Construction.docx:

5 Validation of Ballot Chaining

An election verifier must confirm that each of the values in the running hash is correctly computed.  
Specifically, an election verifier must confirm each of the following.

1. The equation H0=H(Q) is satisfied.
2. For each ballot Bi, Hi=H(Hi-1,D,T,Bi) is satisfied.
3. The closing hash H=H(Hl,"CLOSE") is correctly computed from the final tracking code Hl.

Numbers 1 and 3 are not implemented in current python library. Number 2 is correct.

1. in EncryptionMediator in encrypt.py. line 71:

        self._seed_hash = encryption_device.get_hash()

To follow the spec, one should use the extended base hash.

3. The closing hash is not computed. It appears that you would have to add a bogus CiphertextAcceptedBallot to do so?

I thought it better to add an issue rather than a PR, since Im not sure of the status of the "validation spec".

[danwallach]

To make matters more complicated, I pretty much ignored all of these specs while building the verifier used by arlo-e2e, in part because there's a need for partial / out of order / parallel encryption and verification.

It would be lots of fun to think carefully about how to reconcile the arlo-e2e design and the ElectionGuard design.

[JohnLCaron]

Does arlo-e2e use the same json serialization as electionGuard?

[danwallach]

I changed the bignum serialization to base64, to save space, and I used my own structures for everything above the ballot abstraction, since each ballot is written to it's own file. I also had to add a Chaum-Pedersen decryption proof that wasn't part of the ElectionGuard-Python implementation. All of that's sitting in the VotingWorks fork of ElectionGuard-Python, until they take my PR.

[keithrfung]

@JohnLCaron The Verifier instruction were done by Josh Benaloh as he is writing and editing the newest specification. It's not contained within the specification. If you look at the implementation done by his students referenced in that issue, you'll notice they had similar problems.

Election-Tech-Initiative/electionguard#32

This is a good thing to reach out to @rc-ms about. We'll try to paint a better picture of the direction and adherence to the specification going forward.

[rc-ms]

This is a great thread and gets to the different use cases ElectionGuard can be applied against. @danwallach is using EG for arlo-e2e in an audit, not end-to-end verifiability, context; as such, the notion of a ballot chain can be punted in service of performance and scalability.

in addition, as @keithrfung suggests we want to make the specification more "present" in the code itself rather than a separate document. Per @danwallach 's suggestion, look for a call to discuss further how we handle these divergent use cases clearly and cleanly.

[benaloh]

The details here are clearly underspecified, and the spec would benefit from greater detail.

The purpose of these hashes is external to the core of ElectionGuard. The sole value of this hash chain is to make it more difficult for rogue election officials to (after the fact) discard ballots and/or add new ones. There is no value to this hash chain for the RLA use case. If this were to be entirely dropped from the E2E-V use case, nothing would be lost beyond this added layer of external protection. In many ways, it would be cleaner to just eliminate this hash chain.

While other details of the spec are critical, the details matter little here. Pretty much any way to chain the ballots is as good as any other. Thus, it is OK to just use the details from the code and then incorporate these details into the next iteration of the spec.

[JohnLCaron]

If I understand the work flow, when ballots are cast, they are immediately encrypted so that the voter can be given a verification code. A ballot's verification code depends on the previous ballot's verification code, creating a chain of ballot verification codes, aka ballot chain. Each device has its own ballot chain. At the end of the election, the ballot chain is closed.

Each device is running its own software stack, and is responsible for creating its own ballot chain. So theres no master process that would constitute a single point of failure.

Assuming Ive got that right:

1. Given that its a device specific chain, it does make sense to start the chain with a device specific value. So perhaps we just need to change the spec to that?

2. Theres no obvious place to put the closing hash. Perhaps we need a ballot chain object that records that and possibly other info?

3. What to do in the case of a machine that needs to be rebooted? Does it need to recover its chain, or can it start a new one? Does electionguard need to provide API support in some way for that?

[benaloh]

This is a good summary and the points are all valid.

1. Yes. It would be possible to augment the base hash to include device information. The spec instead adds device information (including a device identifier) to the hash chain along with the time that each new ballot is added to the chain. This seems to achieve the same thing -- although the details are clearly underspecified.
2. Exactly where to put the close of each hash chain is a good question. They should be included in the public election record.
3. It is fine to start a new chain if a device reboots. Old chains should be closed in the election record, but there is no private information in the chains, so the chain closing data could be produced externally.

[danwallach]

If/when we're opening Pandora's box about how exactly to build a hash chain, I might suggest that we can use something fancier than just a linear hash chain. One design that I worked on a decade ago used a tree-like append-only structure, allowing membership proofs to be logarithmic rather than linear (https://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf). I'm sure the blockchain crypto people have newer structures as well.

Also, there's an argument that we made in a voting system paper around the same time that you really want to have a "launch code" at the start of the election -- a random nonce that the election officials announce at the start of the day. This defeats a peculiar attack where an attacker tries to substitute a completely alternative history of votes. A launch code makes it impossible to precompute such a thing before election starts.

[rc-ms]

so speaketh Pandora. I'm all about a launch code since the ballot manifest itself has to be registered to generate the security keys for the election (as well as inform the input structure for tally calculation on submitted data). I'll let @AddressXception weigh in on hash chains and whatnot, since i recall him muttering similar things recently.

[benaloh]

I'm not sure that I see much benefit to more elaborate chaining structures here. Voters may want to check that their individual tracking codes are part of the published election record, but this is independent of the hash chain. The only place where the contents of the chain are likely to be verified is when verifying the integrity of the full election record; and when doing this, the entire chain is verified -- so a linear structure is as good as any and is simpler than the alternatives.

I'm also not sure that I see the utility of launch codes, although please feel free to educate me on what I may be missing. Perhaps if we were using short tracking codes or weak digital signatures, there might be value to an (insider) adversary in having time to create collisions. But we're using strong crypto, so I don't see much benefit to shortening the time available to adversaries. That said, I see no harm to integrity that would be caused by adding launch codes. My principal concern is not so much the additional step in the code but instead the additional procedural step for election administration.

[danwallach]

Right now, my main goal is to put all of this stuff on the table. Launch codes help with a very specific attack. Do we care about it? Sub-linear hash structures are valuable if you want to validate less than every single ballot. Is that a use case?

We've got over a decade of literature to mine on these topics. I'd encourage us to take some time to consider these issues.

[keithrfung]

This discourse is certainly lively. I'm gonna try and get some clarity.

Keep the issue open?
Do we consider this a deficiency to solve immediately in python or do we need to revisit the specification and clarify this first and then implement accordingly? I'm assuming the latter based on the current conversation.

Future Discussion
Particularly @danwallach 's and @benaloh 's discussion about how to implement the chaining should likely be moved to a larger discussion on the specification itself. I think this is probably gonna be a much larger conversation.

• Discussions of electionguard and the specification
• Discussions of how to implement in electionguard-python

[AddressXception]

I have been stewing this over the past several weeks, and I keep coming back to the ballot chaining mechanism being very implementation specific. My current thinking is that this should actually be sufficiently vague in the spec to support multiple use cases, but we may want to clearly define a minimum subset of "recommended" approaches that demonstrate how integrators can choose to take advantage of this feature.

In my opinion launch code/init vector likely falls into this category of a specific use case and our internal object model should be flexible & minimal enough to support bringing that feature if desired.

On the point regarding formalizing the code implementation to support the open/close components to the spec, we should absolutely do that. An interface accepting an arbitrary string parameter should solve both the open/close problem and allow the external system to specify an init vector if it desires. (For instance, we can formalize this by modifying EncryptionDevice to include an open(initializationVector: str = None) type method.

Regarding the hash chaining, this may also be outside of the scope of the base protocol & spec. I believe only a subset of use cases care about this feature, and it is likely also implementation specific. Additionally, there are a number of existing commercial and open-source solutions that verify the integrity of a dataset and solve for these cases.

Here are a couple of things we could do with the hash chain:

• leave it alone: the current implementation is naive and provides a simple (but perhaps inefficient) solution. Consumers can choose to discard this data and use an external mode instead. In this case some compute cycles are wasted and it is unclear to new developers that this data is considered optional sometimes.
• just get rid of it: remove the previous_tracking_hash from the struct, disassociate the ballots from the device, and define this concern as completely external. It will simplify the core code and protocol slightly, but we lose the formality of forcing consumers to consider this case.
• formalize the merkle tree structure - our current encrypt_ballot has a nonce seed attribute used to generate nonce's on a ballot from top to bottom (ballots -> contests -> selections). We could instead invert this to seed nonces from the bottom up (selections -> contests -> ballots) by default, decoupling the ballot object and the contest object from the selection objects, which gives more flexibility to do things like normalize the object hierarchy.
• • This tree structure is sort-of captured already in the crypto hashes found in the rich objects.
• • Adding an optional device_hash string field to _ciphertext_ballot_selection_crypto_hash_with would effectively allow a consumer to define their own graph structure.
• • In this case, as a useful default, we can keep our rich object in code for convenience, but provide a test or sample that shows how to represent a ballot's selections differently for external processing.
• • In this model, the encryption device seeds its arbitrary metadata into each selection's device_hash field & the device tracks the root state. Consumers can then choose to link each record together in novel ways such as by including the previous state root in each incremental selection encryption's crypto hash function, effectively recreating our current simple linked-list structure, or doing something more complicated.

I'm sure Im missing some nuance here and there are definitely other use cases, but I thought some practical suggestions might help. Interested to get your thoughts.