Secret Voting and the Double Linked List
This is the second of a 3-part article which presents the Solidity-based implementation of the Token weighted voting protocol.
Here, we continue to define the double linked list used to manage vote secrets and we dive into the voting implementation itself as well as the logic behind determining if an address is locked.
Vote secrets data structure — the double linked list
Vote secrets are stored in a double linked list. Each entry consists of the poll id, vote secret and is ordered by poll close time. The list contains only the unrevealed vote secrets for a user, i.e. when a vote is revealed, it is removed from this list.
Zero-entry item
The list implementation uses a helper zero-entry item where the previousItemlink points to the last item in the list and the nextItem link points to the first item in the list, thus closing the list structure.
This design gives us less edge cases as we don’t need to track variables such as the first item in the list, the item count or cater for special cases where we’re inserting at the start or at the end of the list.
Design for poll votes that close at the same time
Additionally, we need to design support for cases where two or more polls close at the same time, thus having conflicting pollCloseTime in the ordered list. We solve this by having a second inner double linked list. We move the pollId and vote secret into this inner list, leaving the outer list to just holding pollCloseTime information.
Example design for this above, models a user having voted 5 times in polls with Ids: 1, 5, 8, 12 and 14. Polls 1 and 5 close at the same time at timestamp 10, while the other polls (8, 12 and 14) close at unique times, respectively 52, 123 and 456 and thus have just a single vote secret entry against them in the inner list.
The storage data model of the key/value pairs for two linked lists can therefore be modelled as follows
//Doubly linked list holding polls closeTimes
sha3("Voting", userAddress, pollCloseTime, "prevTimestamp") => uint256 prevTimestampsha3("Voting", userAddress, pollCloseTime, "nextTimestamp") => uint256 nextTimestamp
//Doubly linked list holding vote secrets
sha3("Voting", userAddress, pollCloseTime, "secrets", pollId, "secret") => bytes32 secretsha3("Voting", userAddress, pollCloseTime, "secrets", pollId, "prevPollId") => uint256 pollIdsha3("Voting", userAddress, pollCloseTime, "secrets", pollId, "nextPollId") => uint256 pollId
Sorting double linked lists
In the case where the smart contract is responsible for finding the position in the list for a new vote, it’s possible that in the transaction inserting the vote runs out of gas, as we iterate through items to find the right order.
We solve this by delegating to the user the job of providing us the position where their vote needs to be inserted. We validate the position info they give us and do the insert.
In addition to lower gas costs, as we don’t sort on the blockchain, this approach has the added benefit of a fixed and predictable transaction cost for adding a vote secret to the list, as storage cost is fixed.
Secret voting
Whenever a user makes a vote, first they must establish what their precommitted vote secret is to be. They do this by finding the Keccak hash of a salt value and the chosen poll option Id. This is the equivalent of calling sha3(salt, pollOptionId); in Solidity.
The salt is required so that the user’s vote cannot be discerned pre-reveal. The salt is revealed during the reveal phase, and so should not be sensitive, but it should be unique for every vote and not have to be remembered or chosen by the user. The voteID signed with the user’s private key, for example, would meet these requirements, as would the brief signed with the user’s private key, which would have the additional benefit of allowing the user to prove what they voted on, as well as the direction they voted.
The user then calls the vote function,
function submitVote(
uint256 pollId,
bytes32 secret,
uint256 prevTimestamp,
uint256 prevPollId)which has four arguments:
uint256 pollId — Id of the poll which they’re voting on
bytes32 secret — The secret string described above
uint256 prevTimestamp — The timestamp that the secret should be inserted after for the outer list (of poll closing times) to remain correctly sorted. If this is 0, then the current element is the first element in the linked list that comes after the zero-entry item.
uint256 prevPollId — The poll Id that the secret should be inserted after for the inner list (of poll ids and vote secrets) to remain correctly sorted.
A number of validations then take place before the secret is added, to ensure the poll is open and its closingTime hasn’t past as well as the position in the outer and inner lists is correct.
isAddressLocked function
The purpose of the double linked lists are two fold: firstly as described above, to store unrevealed votes and secondly, to determine if an address is locked.
An address is defined as locked, if there is at least 1 vote a user has to reveal, i.e. at least one vote for poll which has closed.
This check is implemented in a function, namely isAddressLocked(address) which looks at the outer list of pollCloseTimes, takes the first item in the list (after the zero-entry item) and compares the now block timestamp against it. Since the list is ordered by pollCloseTimes, we guarantee that if the first item in the list is less than the now timestamp, i.e. the poll close time for that first item has passed, there is at least one vote secret which needs to be revealed and therefore the user address is locked.
This model can be implemented as follows
In the third and final article we’ll examine how the isAddressLocked function above is used to extend the token implementation. We also look at the mechanics of revealing a vote.
Colony makes it easy for people all over the world to build organisations together, online.
Join the conversation on Discord, follow us on Twitter, sign up for (occasional and awesome) email updates, or if you’re feeling old-skool, drop us an email.
