TrustyVote - A better voting system for groups on the ROBLOX platform.
IntegerUnderflow, 2017.
Abstract
Current ROBLOX voting systems are either black box private message based ones (where a user must trust an election account to accurately count the votes, for example in the UK group) or are fully exposed voting systems (where everyone can see how everyone has voted, for example in the NUSA group). These systems both massively sacrifice between vote confidentiality and proof that votes were counted. I propose a new system, TrustyVote, that combines the best features of both of these systems for a better voting system.
An example election
Suppose we have a group where we want to conduct an election. The following facts are given for this example:
There are 200 voters, starting with Voter 1, then Voter 2, up to Voter 200.
There are 5 candidates, starting with Candidate A, then Candidate B, up to Candidate E
The voter process
To vote, voters must join a voting place where a game server collects votes to publish them. The game server contains the following features;
- A pool of votes that need to be published (the “memory pool”)
- An interface for voters to send their votes to the server
- The published votes so far
The memory pool is composed of two distinct parts:
- Votes for candidates (The “vote pool”)
- The users who the votes in the vote pool correspond to (the “user pool”)
A voter who wants to vote joins the given voting place, when they join, the game server verifies that they do NOT appear in the published votes OR the memory pool, if they do, the game server should prevent them from voting and kick them. Otherwise, the voter is presented with the list of candidates. The voter then selects the candidate they wish to vote for and generates a random string (the “verify secret”). The voter then creates their “voter identity” as follows:
Voter Identity = sha256(userid + verify secret)
The voter then sends to the server the following:
- Their voter identity
- Who they want to vote for
The voter is then shown their verify secret on their screen as a receipt.
The game server then takes the voter identity and vote and adds it to the vote pool, at the same time it gets the voters userid and adds it to the user pool.
An example of a Memory Pool, in this example the voter secret is always “example”
Publishing votes
When a threshold of votes in the memory pool is reached, n, the game server should publish the votes. It does this as follows:
- It gets the hash of the last published block of votes. (The “previous block hash”)
- It works out what number sequentially of published blocks of votes it is, such that if 2 blocks have come before it is block 3 (the “block height”)
The game server then constructs a block of votes, the block is composed of four parts:
- The previous block hash.
- The block height
- The vote pool for the published block
- The user pool for the published block
The game server then widely publishes the block before clearing its memory pool, this can be done through many ways, such as a group wall post, group shout, bulletin board post on the devforums, discord message or etc.
Because each block includes the previous block hash, each block reinforces the previous block.
Everyone can verify voter eligibility and vote integrity
Say we wish to verify that each voter is eligible and voted only once. This is trivial in this system. For each block we perform two tasks:
- We verify that there is only one vote in the Vote Pool for each vote in the User Pool.
- We verify that everyone in the User Pool is eligible to vote.
Since there is 1 vote per user between the Vote Pool and User Pool, and each user in the User Pool is eligible we can then conclude that the block is genuine or not genuine.
Everyone can verify that their vote has been included
Say we are a voter and wish to verify that our vote has been included, we search the blocks for a user pool that includes our userid, as long as this block is valid, we can conclude that as there is 1 vote per user in the user pool that our vote was included.
Only the voter can verify who their vote went to, preserving ballot secrecy
Say we are a voter and wish to verify that our vote has been counted correctly, that is, the vote was made for the candidate we chose, we first find the block containing our id in the user pool as described above, we can then reconstruct our identity by taking our receipt (“voter secret”) and combining it with our userid to recreate our voter identity, we then need to verify that this voter identity is in the vote pool and that the vote is for who we voted for.
Say we are not the voter and wish to find out how a voter voted, spoiling their ballot’s secrecy, the problem we face is that without the voter secret, recovering the voter identity requires a brute force attack. The attempts needed for a 50% chance of recovering the votes vote can be expressed as:
- p = (c^l) / 2
Where:
p = The probability for a 50% chance of a break
c = The size of the character set for voter secrets
l = The length of voter secret strings
We can see that as the size of the character set increases or the length of the voter secret string increases, the amount of attempts needed for a break increases exponentially.
Some example numbers are reproduced below, where the character set is all letters in the English alphabet and the numbers 0 to 9, that being, 36 characters in total.
