Possible for Verification # collisions

[dsernst]

Issue:

There is a very small chance of two voters randomly generating identical Verification #s.

Per the math from https://github.com/dsernst/siv/blob/e6c27d87d10b8da5cc8f4dafebe33546e7db4871/src/vote/tracking-num.ts#L24 for an election w/ n voters, the chance is:

• 500 voters => approx 1 in 10 billion
• 50,000 voters => approx 1 in 100 million

(This math might be incorrect though, we might need to square the exponent, and then it only takes an election with 1 million votes to get 1 collision. See https://en.wikipedia.org/wiki/Birthday_problem#Probability_of_a_shared_birthday_(collision))

And every election rerolls the dice again, so eventually we would run into it.

---

In any case, whatever the chance, we do want to make sure SIV gracefully handles this situation.

I believe right now, when reconstructed shuffled and unlocked votes, the SIV API admin/unlock code will randomly override half of the vote columns that collide. This is definitely bad, not only bc it breaks those voters' verification — it would show a random mix of their ballot selections — but it would actually lose one of the votes and screw up the final count.

Solution:

Instead of overriding the collision, the unlocking code should check if there is already a decrypted & reassembled vote there, and push it into an array. So the updated type for reconstructed votes becomes

-Record<column_key, vote_selection>
+Record<column_key, vote_selection[]>

This is a pretty obscure case, and almost certainly wouldn't change any election outcomes, (the collided vote lost would have to be in a race with a margin of 1) but nonetheless it would be good to make sure SIV can handle it.

Luckily if this comes up before we fix it, no critical vote data would have been lost or anything, and it can still be fixed after the fact.

Anyone who looked into the Universal Verification proofs might notice there was a vote missing. The election admin's message after hitting unlock would say (n-1) of n votes unlocked. The voters whose vote collided would see half their selections from the other voter.

[dsernst]

Written about here: https://docs.siv.org/technical-specifications#aside-on-verification--collisions

Aside on Verification # Collisions

Because the Verification # is generated privately and independently by each voter's device, there is a small risk of collisions. Since they are made of 12 decimal digits, there are $10^{12}$ (approximately $2^{40}$) distinct Verification #'s possible. Per the Birthday Problem, we can expect a collision after around $2^{40/2}$ votes, approximately one million.

A collision is not a critical issue, but only a slight inconvenience for the voters whose Verification #'s collide. Individual voter verification is still fully possible. Furthermore, Verification #'s are specific to a single election. Since many jurisdictions report vote-totals precinct-by-precinct, there is no adverse impact on privacy to segment Verification #'s to precincts as well. Even the largest cities rarely have precincts above 10,000 voters, so we expect Verification # collisions to be quite rare, and of low-impact.