Financially Guaranteeing Vote Integrity

Imagine that once your election administrator confirmed your vote was successfully received, you have the confidence that it will be in the final tally, and their claim is backed by significant financial guarantees.

This means if you vote on Day 1 of a 7 day voting period, you can have strong confidence that once your vote has been confirmed on Day 1, you don't need to return back again a week later when the voting period ends on Day 7.

Proposed Design

After you cast your vote, you receive an unforgeably-signed receipt of your Encrypted Vote Submission. This is stored in the browser LocalStorage on your voting device, and also emailed to your address on file as an additional backup. If, for any reason, your vote does not make it into the final tally, you can use this signed receipt to claim a large financial payoff.

Protocol Coverage

This mechanism specifically protects SIV Protocol Step 3: Submitting Encrypted Votes. It can serve as an additional layer of a strong Defense-in-Depth strategy.

Other steps of the SIV Protocol continue to be protected by their own specialized defenses.

Impact

Initially, at small amounts, this acts as a bounty incentive to identify and strengthen SIV.

As it grows, it can create a stronger incentive for voters to report issues.

Because it includes a cash reward, voters who require assistance to use this feature can use the reward to fund that assistance, by splitting some of the earnings.

Many people wonder if other voters will take the time to verify their vote. Even without this, they should if they're upset about the election outcome. But if they truly think there was an issue, especially regarding their own vote, this mechanism serves as a strong incentive for them to provide evidence. Likewise, it helps to dispel any potentially false claims. "If your vote was truly lost, you can claim your large $ reward. Why aren't you?"

As the pot grows larger and is well-advertised, the lack of any valid reports serves as further indication that voters did not have trouble finding their vote in the final tally.

Supporting Multiple Claimers

The simplest implementation is for the first person to successfully claim to get the entire bounty amount. But it is useful to get more information on whether there was just a single issue, or a handful, or a large number. To encourage this, rather than paying out 100% of the pot to the first successful claim, they could receive a smaller % between 0 and 100. The 2nd would receive that smaller % of the remainder, and so on.

Legally-Backed Enforcement

Such a financial guarantee can be offered with the backing of the traditional legal system.

This is familiar, easy to understand, and relatively easy to get started with.

Automatic Enforcement Using Smart Contract Escrows

Because these are cryptographic claims, paying out rewards can be upgraded into automatic enforcement, executed publicly, by Smart Contract escrows.

Benefits:

1. The guarantee funds are publicly set aside upfront.
2. It's much harder for the guarantor to fail to uphold their promise. If the smart contract system unexpectedly fails, legal remedy is still available as a backup.
3. The per-election transaction costs, whether a successful claim is made or not, can be vastly lower.
4. Successfully claiming the funds can quickly be done at home, rather than involving any sort of lengthy court process.
5. Everyone is able to transparently see if and when funds are ever successfully claimed.

High-level Summary

This system can be implemented by:

1. Using a smart contract to put bounty money in escrow.
2. Posting the full Merkle Tree of all submitted votes.
3. Voters can send their signed submission receipt to the smart contract.
4. If the submission receipt is validly signed, and the vote doesn't appear in the final Merkle Tree, the bounty reward is automatically paid out to them.
5. If no one claims the bounty in X days after the votes were posted, the bounty is returned to the original guarantor.

Technical details:

The main transactions:

#1. At the start of the election, SIV puts bounty funds into escrow

An initial transaction with:

a) the committed bounty amount (in a USD stablecoin like USDC)
b) the election_id
c) the public key that will sign submission receipts of accepted votes

#2. At the end of the election, SIV posts hashes of all the submitted votes

a) a Merkle Tree of all the accepted votes
b) election_id (should match 1b)

Size estimate:
(256 bits for each hash) * (num of votes) * (2 for Merkle Tree height)
So an election with 100k votes => ~51 megabits or 6MB.

#3. Anyone can then post a "bounty claim transaction"

This requires their signed vote confirmation receipt.

In response to Transaction 3, the smart contract checks:

1. Does the election_id match 1b?
2. Does this confirmation receipt have a valid signature, from the key in 1c?
3. Is the hash of the vote in the confirmation receipt truly missing from the Merkle tree posted in 2a?

If all 3 checks pass, send the bounty from 1a to the address that posted transaction 3.

Other Design Considerations:

MEV Defense

To prevent front-running, transaction #3 should be separated into two separate blocks: commit then reveal.

3a: Submit hash of the signed receipt + claimer's address.
3b: Reveal the full valid signed receipt, matching the 3a hash.

This is important to ensure the bounty isn't stolen by block validators.

Expirations

If it's been x days (e.g. 45) since Transaction 2 (Merkle tree) was posted without any successful claims, remaining funds are returned back to the address who posted Transaction 1.

To make sure Transaction 2 is posted without delay: If it's been y days (e.g. 45) since Transaction 1 was posted (funds put into escrow) without a matching Transaction 2 (Merkle tree), anyone can claim the reward, without needing a signed submission receipt.

v2: More efficient way to prove non-inclusion in the Merkle tree

Transaction 3, check #3 says "Is the hash of the vote in the confirmation receipt truly missing from the Merkle tree posted in 2a?". We could post the entire tree, as described above, and check over each leaf, but that's going to be expensive onchain. A lot of data to post, and a non-trivial amount of work to loop through it all.

Instead, we can optimize this by breaking the non-inclusion check into two parts, claim then dispute:

First, as before, the claimer still submits their signed receipt and vote they believe wasn't included. This can still be split up into two transaction for MEV Defense as described above. Now though, they also need to provide a small financial deposit, as DOS protection. $5 should be fine to start.

Then, it's up to the smart contract owner (SIV) to either:

• de facto accept the claim, by doing nothing for some pre-defined DISPUTE_DURATION
• Or, they can dispute it, by providing a valid Merkle path from the provided vote hash up to the root hash.

Efficiency gain: This means transaction #2 (at the end of the election) only requires the single root hash for the tree, rather than all of the votes. The dispute transaction would include the path, which is only log(n) hashes, rather than n hashes. For a 100k vote election, this requires only ~17 hashes, rather than the 200k of the full tree. This is also far less computation for the smart contract, only needing to check the hashes along the path (e.g. 17), rather than looping through all of them (100k).

If the smart contract confirms the dispute path is valid, the claimer loses their small deposit.

The bounty remains in escrow until the expiration period is over, or until a successful claim is made.

• One noteworthy consideration of this optimization is that the full tree is no longer posted onchain. There is also no financial guarantee anymore that directly forces the smart contract owner to post the full tree off-chain either. But if SIV fails to do, that absence is directly observable by everyone, all voters & independent observers too.
  • In this optimized construction, the smart contract is more directly focused on the job of providing just the financial guarantee for losing signed votes, no longer responsible for posting the full tree.
  • The root-hash links the smart contract posting to the off-chain full tree, which anyone can directly verify themselves is a valid merkle tree.

v3: Even more efficient way to prove non-inclusion:

Rather than the Claim-then-Dispute method described above (v2), we can simplify these back into a single Non-Inclusion Proof, as long as the tree is sorted:

Sorted Merkle Tree Non-Inclusion Proof

Setup:

• A Merkle tree is built over a strictly sorted list of values.
• Only the Merkle root is posted on-chain.
• The full list is available off-chain.

To prove that a value x is not in the tree:

Submit:

1. Two adjacent leaf values L1 and L2 such that L1 < x < L2
2. Merkle inclusion proofs for both L1 and L2 up to the root

Verifier checks:

1. That L1 < x < L2
2. That L1 and L2 are adjacent in the sorted list (proven by their relative positions in the Merkle tree)
3. That the Merkle proofs for L1 and L2 both lead to the known root hash

If all pass, it proves x is not in the original sorted list.

Anyone can verify the off-chain data is sorted.

Individual voters can prove their vote is missing.

Improvements over v2:

• Successful claims get paid immediately.
• Claimants no longer need to submit a deposit.
• No need to pick a DISPUTE_DURATION.
• One less transaction to post on-chain.
• No need for SIV to dispute invalid claims, & thus less need to monitor.

Same log(n) efficiency gain as v2 — still only need to post the original root hash.

Based on preliminary research and feedback, this seems a promising upgrade.

However, this model is currently under further study. We are open to feedback and collaboration: team@siv.org