Dev Diary I: A Walkthrough of PLCR Voting in Solidity
This is the first entry in a series of regular dev diaries members of the adChain Registry dev team will be publishing over the coming months. This first entry is about the adChain Registry’s partial-lock commit/reveal voting system, and was written by Mike Goldin of ConsenSys.
Voting on whether to admit domains to the adChain Registry is the heart of adChain’s incentive game. To support this we have developed and open-sourced a generic, Apache-2 licensed implementation of partial-lock commit/reveal (PLCR) voting, written in Solidity. PLCR voting is an efficient system for token-weighted voting which enables a user to participate in multiple polls simultaneously with their tokens while preventing the double-voting of tokens within polls. Importantly, it allows users to withdraw at any time the maximum number of tokens not being actively used for voting.
PLCR voting was originally described in a blog post by Aron Fischer writing for the Colony project. Elena Dimitrova’s blog posts on the topic were referenced heavily in building this implementation. We are grateful to them for their original work!
Why PLCR Voting?
Implementing PLCR voting in Solidity is not trivial, so why bother? In addition to obscuring vote tallies prior to poll completion using commit/reveal (which is desirable to prevent the voting process itself from influencing vote results) PLCR voting enables two things:
- It enables a user to participate in multiple polls simultaneously while preventing the double-voting of tokens within polls.
- It allows users to withdraw at any time the maximum number of tokens not being actively used for voting.
As an illustration: a user loads 10 tokens into the PLCR Voting contract. The user then commits 10 tokens in poll A and six tokens in poll B. After revealing in poll A, six tokens remain locked in poll B but the user can withdraw four tokens.
In a naive non-PLCR polling system, a user might lock tokens in a smart contract describing a single poll. This is not an ideal solution because it prevents the user from participating in multiple polls simultaneously with the same tokens. If the user’s tokens are locked in some smart contract, another smart contract cannot `transferFrom` the user to lock them itself.
Remediating this and using one smart contract to manage multiple polls need not be super complex if the contract can lock all user tokens while the user has tokens committed in any polls. However, if the user has approved such a contract to lock 10 tokens and less than 10 are actually committed to polls at any point, the user has to wait for all the polls to conclude before withdrawing any of their tokens. This could actually discourage users from participating in voting, as it ties their hands should they have tokens committed to polls while market events are occurring they might like to respond to. Polling systems should maximize token liquidity to the extent possible.
Maximizing token liquidity as such requires the developer take on a fair bit of complexity, at least in Solidity. Using MiniMe tokens is one approach. PLCR voting supports tokens which are not MiniMe tokens.
PLCRVoting.sol
A deployed instance of PLCRVoting.sol specifies a token for which voting rights may be apportioned. Any token-weighted votes needing to be made using that token can be made using the same deployed PLCR voting contract, and these polls will not interfere with one another. The token to be used is specified as the only argument to the constructor.
Creating a poll
The startPoll function is used for creating new polls. It takes three arguments and returns a uint. The arguments are:
voteQuorum: the necessary percentage of votes “for” necessary for a poll to be considered passing. Some poll topics may require a supermajority to pass, for example.
commitDuration: the duration of the commit period, in seconds.
revealDuration: the duration of the reveal period, in seconds.
In the function body, the first thing we do is increment the contract’s pollNonce, a storage variable. By incrementing it every time a poll is started, we create a unique ID for each poll. Because we always increment the pollNonce first, note that there will never be a poll with ID zero.
Next we instantiate a Poll struct and add it to the pollMap using the pollNonce as the key. The Poll struct stores the poll parameters which were passed in as arguments and initializes counts of votes for and against to zero.
Finally we fire a PollCreated event with the pollNonce, and return the pollNonce to be used later as this poll’s pollID. Pretty simple!
The next logical thing which might happen after a poll is created, is that someone might like to vote in that poll. There are a few steps to this process, which begin with requestVotingRights.
Requesting voting rights
To prevent tokens double-voting within a poll, the PLCR contract needs to manage user tokens from the time they are committed to when they are revealed. Managed tokens can be used to vote in multiple polls concurrently, but not multiple times in the same poll. requestVotingRights function bestows voting rights to the user equal to the weight of the tokens put under management.
In the first line of the function body we check that the actual token balance of the message sender is sufficient relative to the numTokens argument provided. The following line calls transferFrom, moving numTokens from the balance of the message sender to the balance of the PLCR contract. The first line is a redundant check: the second require statement would throw an error in any case where the first did. This is just defensive programming, since people may use this contract with buggy ERC-20 implementations (though there is no excuse for doing so when good implementations exist).
Notice also that transferFrom will fail if the user did not approve the PLCR contract to transfer numTokens prior to calling requestVotingRights. This is sad and there are proposals to improve upon the “approve and call” pattern, but they are not yet widely implemented.
Finally, if the first two lines succeed, we increment the voteTokenBalance of the message sender by numTokens. Whew. We can vote now. We could also withdraw everything now, as none of the tokens managed have yet been locked in a poll.
Committing a vote
Commit-reveal is a pattern used in ENS to conceal bids, and can be used for secret balloting as well. A committed vote is a salted hash of the user’s vote, meaning the user’s preference (yes or no) is concatenated with some randomness (the salt) before being hashed and committed. commitVote takes the following arguments:
pollID: The ID of the poll being voted in (originally returned in some invocation of startPoll)
secretHash: The keccak256 hash of the voter’s choice and salt (tightly packed and in-order)
numTokens: the number of tokens to commit to the poll for this vote
prevPollID: the ID of the poll for which the user currently has the greatest number of tokens less than or equal to numTokens committed (we’ll talk about this one later).
Okay, lets look at the function body. The first thing we’re going to do are a few checks. We’ll call a helper function to make sure the commit period for the provided pollID is active, that the voteTokenBalance of the message sender is at least the numTokens value passed in, and that the provided pollID is not zero.
Digression: why do we treat the poll for pollID zero specially? We noted earlier that in startPoll there will never be a pollID for pollNonce zero, and here we specifically check that votes are not being committed to the poll at pollID zero. In the EVM, all data is initialized to zero. If you declare a uint x and don’t initialize it, (x == 0 && x == false) will be true. For smart contracts that interface with the PLCR voting contract, it may be useful to reference the poll at ID zero as a sort of null value. In the adChain Registry, for example, pollIDs are stored with listings which have been challenged. By default these will be initialized to zero. It is efficient if we can know that a listing with pollID zero has no active challenge rather than having to store a separate boolean. For this reason we want to keep the poll at index 0 unused.
Okay, so we finished our checks. Now we’re going to do something funky and introduce our doubly linked list.
The Doubly Linked-List
The PLCRVoting contract uses doubly-linked lists to keep track of which polls users have tokens committed in. Implementing a doubly-linked list is a freshman year homework assignment for computer science majors, but implementing one in Solidity is rather more challenging than doing so in, say, Python, because Solidity is such a low-level language. The doubly-linked list is what lets us efficiently release the maximum number of tokens possible to users who wish to withdraw their voting rights and have tokens committed in multiple polls less than the total tokens they have voting rights for.
First, a meditation on a core concept: mappings can be used to address memory directly in Solidity, like pointers in C. This is the key to building complex data structures in Solidity.
In PLCR voting there is one doubly-linked list per user, addressed using the msg.sender address of the user. A node in a user DLL corresponds to a pollID. The DLLs are always sorted by the number of tokens committed by the user for the polls corresponding to the nodes. Data is stored separately from the nodes themselves and is addressed using the hashed concatenation of a user address and a node ID to index into a string-keyed mapping of integers called an AttributeStore.
To clarify: a user address addresses a specific DLL. A nodeID addresses a specific node in a DLL, but because nodeIDs correspond to pollIDs, multiple DLLs can have nodes with identical nodeIDs. By concatenating a user address with a nodeID and hashing, we get a unique location in memory where we can look to find data. The reason we store the data separately from the nodes is so we only need to store one mapping for all nodes, as opposed to one mapping per node. The declaration of a mapping, even if the mapping is empty, uses storage.
That’s the basic overview of how the DLL works. Lets get back to how commitVote works and see how we use the DLL in practice.
Committing a vote, continued
On line 102 we set a uint called nextPollID to the result of a method getNext, which is a method of msg.sender’s DLL, that takes an argument prevPollID. prevPollID is the ID of the node which will be the previous node of the new node we are inserting. nextPollID then will be the next node of the new node we are inserting, since it’ll go after prevPollID and therefore before nextPollID.
Why do we make the user provide the prevPollID value? We could search through the list to find the correct prevPollID, but in very long lists we might bust the gas limit doing so. Better to let the user do that off-chain in a call and then provide it so the transaction can run in constant time.
Line 104 checks, in constant time, whether the provided prevPollID was valid given the number of tokens being committed in the new poll. It should not be possible for the list to become unsorted. If the check passes, on line 105 we insert the new node!
We’ve inserted a node, but notice we haven’t actually added the data yet. On line 107 we’ll use a helper function attrUUID to create a new universally unique ID which is the sha3 hash of the user address and the nodeID. Finally we store the number of tokens committed for the poll and the secretHash of our vote.
Wow, that was hard!
Revealing a vote
Now that we know how committing works, revealing will actually be relatively easy. We’ve learned all the hard stuff at this point, so let’s take a gander at revealVote! revealVote takes three arguments:
pollID: the pollID of the poll being revealed for.
voteOption: the user’s choice in the poll. 1 is a vote for, 0 is a vote against.
salt: the random number concatenated to voteOption to produce the secretHash from commitVote.
You’ve been around the block at this point, so you know what we’ll do first: checks. We’ll check that the reveal period for the provided pollID is active, that the user has not already revealed for this poll, and we’ll make sure the provided vote option and salt actually match the secretHash which was committed by computing the sha3 hash of the two items and comparing the result to the secretHash stored in the user’s DLL.
On line 140 we’ll get the number of tokens the user committed for this poll. Then depending on what the user’s choice in the poll was, we’ll update the poll’s global votesFor or votesAgainst tally.
Finally on line 147 we’ll remove the node for this poll in the user’s DLL.
Wow, that was easy!
Who won?
Okay, so a poll’s reveal period has concluded and we want to know how it went. This one’s pretty simple. The isPassed function takes a pollID as an argument and returns true if the number of votes for satisfied the quorum requirement relative to the votes against. In a tie the poll is not passed. Note that the quorum requirement is not a quorum of total tokens which must vote, it is only a quorum of the tokens which did vote.
Taking our tokens out
This is the part we’ve worked so hard for. Lets say we have voting rights for 10 tokens, but only seven of them are currently committed in polls. Using withdrawVotingRights we should be able to get three out. withdrawVotingRights takes as an argument the number of tokens we wish to withdraw.
The magic happens on line 69. We calculate the tokens available to withdraw by subtracting from the user’s voteTokenBalance the result of a helper function getLockedTokens taking the user address as an argument. This wraps another helper function getNumTokens which takes as arguments our user address and result of yet another helper function getLastNode.
Now think about this: our DLL is always sorted by the number of tokens committed to a poll. getLastNode indexes to node zero (the root node) for the DLL of the user and gets the previous node, which should be the poll for which the user has the greatest number of tokens locked. Just by subtracting that number from the total number of tokens the user has loaded in the PLCR contract, we know how many they can withdraw.
All of the hard work we did with the DLL, we did for that.
Back in withdrawVotingRights, it’s all bookkeeping: we send the tokens back to the user and decrement their voteTokenBalance.
And that’s it!
Hopefully this walkthrough has been helpful for your understanding of how our PLCR voting contract works! Feel free to use it yourself for all your token-voting needs!
Massive props to ConsenSys 2017 interns Yorke Rhodes, Cem Ozer and Aspyn Palatnick for working so hard this summer to make the PLCR voting dream a reality.
