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 ↔ relayer interaction
The user-relayer interaction in both VRP and SVRP is the following:
-
(Only in VRP) Voter creates and signs a pre-vote message and broadcasts it in the relayer discovery network.
-
(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.
- 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
- 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:
-
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)
-
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.
-
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