Simple Voting Relay Protocol: Optimistic Vote Tallying

voting
#1

Definitions

Voting Relay Protocol (VRP)

VRP is a layer 2 protocol built on Ethereum designed to maximize on-chain voting scalability (by a factor of 2-3 orders of magnitude compared to naïve voting implementations) by using the Optimist primitive and vote aggregation by relayers. Thanks to the use of optimistic EVM Storage Proofs almost all ERC20s can be virtually snapshotted and used for voting using VRP.

In full VRP anyone who wishes to be a relayer can do it by bonding a minimum amount of tokens in a Staking contract. It is likely that relayers would be able to relay votes only proportionally to their relative stake to other staked relayers (such restriction could be applied by providing time windows for relayers to relay).

VRP also specifies an incentive mechanism to earn fees for relaying votes. If a relayer commits to submitting a vote by aggregating it to a batch and they don’t do it, a signed receipt from the relayer can get them partially slashed.

Simple Voting Relay Protocol (SVRP)

SVRP is a simpler implementation of VRP that imposes a restriction in the relayer set size, which is limited to 1. This relayer can be unilaterally appointed by the organization wishing to use the protocol for elections or it can be the entity wishing to be a relayer that has the largest token stake (there may be challenges related to relayer transitions).

Even if the relayer is centrally chosen, it is important that the relayer has a token stake that the stakeholders of the organization are comfortable with slashing in case they try to commit fraud.

SVRP vs VRP

SVRP downsides

  • Censorship resistance: even if users can always submit their vote on chain themselves, a unique centrally operated relayer could decide not to respond to their voting inclusion requests, opening the door to discriminating for any reason.

  • Uptime: if the relayer goes down, SVRP stops working.

SVRP benefits

  • No need for relayer discovery: communication between the voters and relayers can be anything the relayer is willing to provide (a REST API, a WS connection, WebRTC…)

  • Lower complexity for fraud proofs: the complicated fraud proofs in VRP come from interactions between relayers trying to grief each other, specially when taking into account that a relayer may be a mining pool. Some of these fraud proofs are also non-attributable, requiring the protocol to penalize completely honest actors that are attacked. By only having just one relayer, this entire family of fraud proofs don’t need to be be implemented, as they are impossible to happen.

  • A trusted relayer is less likely to commit intentional fraud: specially if centrally appointed by the organization and reputation risk is taken into account. However, this is a double-edged sword, as it decreases the potential ROI of monitoring the system (more on this on future work).

In general, SVRP has much less implementation risk as the hardest parts of VRP (unattributable faults, relayer discovery protocol, etc) don’t need to be taken into account.

Voter :left_right_arrow: relayer interaction

The user-relayer interaction in both VRP and SVRP is the following:

  1. (Only in VRP) Voter creates and signs a pre-vote message and broadcasts it in the relayer discovery network.

  2. (Only in VRP) Relayer makes a non-binding relay pre-offer to the voter.

Voter adds the relayer address and relayer reward amount to the vote message, signs the vote message hash with their private key and sends it over to the relayer.

  1. The relayer checks that the vote message is correct (and according to the pre-offer they made), they produce a valid storage proof that results in the claimed balance for the account that can be recovered from the signature.
  • If something is invalid, the relayer should communicate to the voter that they won’t be including their vote in a batch.

  • If everything checks out, the relayer will produce a relay receipt message, sign it and send that over to the user

  1. Is there a need for the user to sign a receipt ACK message that the relayer must include with the votes? Otherwise there is really no incentive for the relayer to produce the receipt, if they will be paid anyway and with no risk

VRP messages

All messages must be RLP-encoded before sending them over any transport protocol or submitting them on-chain.

Pre-vote message (full message for SVRP)

Components:

  • Voting app address identifier (4 bytes: bytes4(hash(address)))

  • Proposal id (3 bytes: 16,777,216 proposals per Voting app)

  • Casted vote (1 byte: 256 options)

  • Voter balance (16 bytes, claimed user balance in the voting app’s token at the snapshot block of vote id)

  • Voter ECDSA signature for message hash (64 bytes, with the trailing bit trick)

Total batch size: 88 bytes

Vote message (VRP only)

Inherits all the fields from the pre-vote message**.** Components:

  • …(Pre-vote message components)

  • Relayer address (20 bytes)

  • Relayer reward (32 or 32 + 20 bytes, depending on whether the token in which the reward is paid is globally specified)

Relay receipt message

  • Vote message hash (32 bytes)

  • Block number inclusion commitment (8 bytes, won’t break for the first ~1.84*10^19 Ethereum blocks)

  • Relayer ECDSA signature for relay receipt message hash (65 bytes)

Relayer aggregation

Before aggregating a vote into a batch the relayer is expected to verify all voter balance proofs and voter signatures. Voters cannot get slashed for getting an invalid proof included in a batch, only the relayer will be. Relayers may decide to blacklist voters that submit several invalid votes to penalize spam. In any case, checking a voting message should take less than 1 second in a reasonably fast computer with a good connection to an archive node.

The aggregation process for a relayer is as follows:

  1. Aggregate in a batch all the votes that need to be relayed in the same transaction, be careful that the size of the batch is not over the limit TBD (needed to avoid fraud proofs to go OOG)

  2. For all the involved proposal ids in the aggregated votes, perform the sum of the total amount of votes for each option. We will call this the relayer summary.

  3. Submit an RLP-encoded array of the aggregated votes in one transaction (optimist commit concept)

Optimistic tally

On relayer submission, the Voting contract (or an election manager contract that has power over individual Voting contracts) won’t verify anything about the data blob with the vote data submitted. The voting contract will generate the hash of the entire blob and put it in storage, and then log the entire data blob in order to prevent data availability issues. It will just take the summary provided by the relayer as true, unless someone challenges it proving the fact that the relayer committed fraud, and triggering a slash.

This has implications for vote tallying, as at any moment the tally that the contract has may be incorrect (as the relayer can claim they are submitting something completely different than their summary). Therefore, a cool down period needs to be established before the voting result can be taken as valid and proceed with the execution. Some analysis would need to be done to choose the period.

Fraud proofs, slashing conditions

It is important to note that on both VRP and SVRP, voters cannot be penalized for providing an invalid or fraudulent vote to a relayer, in order to avoid all voters from having to stake to use the protocol to get a vote included.

Relayers are responsible for verifying whether a vote is valid before signing an inclusion commitment receipt and sending it to the voter. If a relayer submits an invalid vote, they will be slashed.

Any observer will be able to get the full blob from EVM logs and verify locally whether the result the relayer claims is valid, and all voter balances are correct. In case an observer detects fraud, they can challenge it on-chain in a non-interactive way and get immediately rewarded.

Invalid Aggregation Blob: Submit full votes array blob and perform all checks

If a relayer submits an invalid aggregation blob it can be proven by submitting the invalid blob (only the hash of the blob is stored on-chain so it needs to be inputted) and performing the following checks:

  • Blob is well formed and can be decoded

  • Blob contains fewer than the maximum vote limit

  • All votes must be unique within blob

  • Tally of all votes adds up

  • The reward sum of all relayed votes adds up

If any of these checks fail the entire submitted batch is reverted and the relayer is slashed.

Invalid Vote: Submit blob and vote index

If a relayer includes an invalid vote, it can be proven by submitting the blob and the vote index and, if required (see below), a storage proof of the invalid vote, and performing the following checks:

  • Validate voter signature

  • Validate relayer address is correct

  • Validate balance (requires also submitting a storage proof for the voter at the snapshot block)

If either of these checks fail the invalid vote is reverted and the relayer is slashed.

Double voting (relayer): Submit two blobs and vote indices

A single vote (same voter, and nonce) could have been included in two different blobs by a relayer. The two blobs and vote indices where the duplicated vote can be found must be provided.

If both votes have the same voter address and nonce, the relayer is slashed.

Vote Exclusion: Submit receipt to create a dispute

If a relayer provides a voter with a receipt but fails to include the vote in a batch another relayer (could also be the voter but they must have a deposit) can submit the receipt as proof that a vote should have been included. The relayer which issued the receipt must then submit a proof that the vote was included, if they fail to submit the proof within a grace period they will be slashed. If they successfully submit the proof then the relayer who submitted the receipt is slashed.

Gas analysis

Future work

  • Full VRP

  • Injected faults to prevent the verifier’s dilemma

  • Move data availability guarantees off-chain (currently the bottleneck preventing it scaling just by 10x instead of two or three orders of magnitude more)

Known issues

  • Archive nodes required for generating balance proofs. Only relayers need a connection to an archive node.

  • Relayer over-leveraging (the potentially slasheable tokens the relayer has staked are lower than their potential token liabilities due to relaying many votes). If there are no tokens to slash and reward the challenger, there may be no incentive to challenge rogue relayers

3 Likes

Preparing for Polkadot
#2

Hello, I have two questios:

  1. What is the benefit of including voter balance in pre-vote message (it adds extra 68 * 16 gas to each vote)
  2. How should the slashing be executed? If blob is not stored on-chain, does it mean that all voters that should have been included in the blob should collaborate and submit their receipts?

Thank you!

0 Likes

#3

Do you mean in the message that gets relayed on-chain? If the balances aren’t specified in the message performing a tally fraud proof would require checking all of the storage proofs for all the voters, which cost ~400k gas per proof, so we would have to support multi-block fraud proofs.

Even if it is not stored on chain, the full blob is sent to the chain, hashed and logged in the EVM, so it is available for all voters and watchers who can independently verify and submit a challenge. See how the submit function looks like from the POC (we are making this open source very very soon, weird circumstances require us to have this closed source for 3 weeks :sweat_smile:):

We are also researching ways of not sending the entire proof blob to the chain as it is the scaling bottleneck

1 Like

#4

Hi guys! You said on Aracon that code for this will be released in 2 weeks, wanted to check the status. I want to take a look and propose doing stuff around it…

0 Likes

#5

Due to something outside of my control, we will have to wait until very early March to open source it :slight_smile:

0 Likes

#6

Where do we look for it? Also, if you don’t see it happening this week or next, can we get take an early look (under NDA or whatever needed)?

0 Likes

#7

It has just been open sourced today and I will be talking about it in EthCC in an hour

EDIT:

Recording of my talk on Voting v2:

1 Like

#8

Fantastic, diving in!

0 Likes

#9

Pretty interesting talk by Vitalik proposing using Eth 2.0 to guarantee data availability to systems running in Eth 1.0: https://www.youtube.com/watch?v=mOm47gBMfg8

Ensuring availability of voting proofs with EVM logs is currently the bottleneck for SVRP scalability (the real bottleneck being the cost per byte of calldata). We have been researching how to work around with a more complicated scheme as explained in Optimistic off-chain data availability.

Using Eth 2.0 to guarantee voting proof availability would allow us to keep the protocol as simple as it is right now while being able to save the calldata cost (which Vitalik says that could be reduced in the next hard fork anyway). The great thing is that this could be possible in the earliest stages of Eth 2.0 (although I am still not really sure about how one would pay to get data included for attestation).

2 Likes

#10

Jorge, we looked at the code, and I’d like to discuss. As I mentioned, we’re very interested in this topic and would like to work on further implementation. Before making a formal proposal, there are a few things we would need to clarify with you. I’ll be in Berlin next week, would love to meet and discuss, if possible, or do it remotely if that works better. Here are initial topics:

  • Browser/wallet interaction for signing
  • Off-chain storage: Aragon IPFS server (https://hack.aragon.org/docs/guides-faq)
  • Oracles (as client independent autonomous background code) - Determine the need to create new or use existing Aragon infrastructure.
    Please let me know if it’s possible to meet. Thanks!
0 Likes

#11

@amitrovich, what do you mean by formal proposal?

0 Likes

#12

@jorge For Nest.

0 Likes

#13

You might want to know who’s “we”: We met and briefly spoke about this during Aracon (you mentioned you need all the oracles for the smart contract), and you may have seen a few “good first issues” closed by my colleague Greg. As for the Relay voting, here’s a sample of what we’re playing with : https://github.com/usetech-llc/votingrelay. It’s a bit different approach to the gas optimization/trustless implementation approach. This one has 2 differences: 1. We verify signatures and aggregate votes on-chain, so we only record voter address and their choice in logs instead of full proof 2. We have 256 maximum voting options (not only yes or no). This code is just a first shot at it, nothing finished (far from it).

0 Likes