Towards better Ethereum voting protocols

“Would the honourable members please cast their votes, ‘Aye’ or ‘Nay’ …”

From the Roman Senate to present day Westminster, unambiguous collective decisions have been taken by members physically separating into distinct groups in a process called ‘Division of the Assembly’. When called, members of parliament exit through separate doors representing a vote of ‘aye’ or ‘nay’. This procedure might seem quaint and antiquated, but it has the benefit of being transparent, explicit and easy to do.

Collective decision making in general, and voting in particular represent a core value proposition for the Ethereum blockchain. From DAOs to liquid democracy, from Schelling games to futarchy; many projects are contingent on carefully calibrated voting mechanisms.

This article discusses some of the challenges of Ethereum voting mechanism, and how they may be made fair and secure.

Please vote ‘0xAye6StFySl5lFHC’ or ‘0xNay4xFTtiS7p5e416jCY’

Let’s start with a simple example: the ‘Division of the Assembly’. Can that be done on the blockchain?

Imagine we create a voting token and assign one token to each member of parliament. We call a vote and each member of parliament is required to send their token to one of two doors addresses representing ‘aye’ or ‘nay’. Whichever address holds the most tokens at the end of the vote wins.

Sounds simple, but as ever, the devil is in the detail.

One Human one Vote?

The first difficulty we encounter is that on the blockchain we have no notion of “an individual”.

When voting in parliament, we know exactly who our MPs are. For general elections, the situation is less clear and a lot of effort is expended on maintaining electoral rolls. On the blockchain the task becomes impossible (outside of very specific circumstances). Who has the right to vote? Which addresses get a voting token?

The blockchain does not know about individual people; it only knows about individual addresses. It is impractical to call for one-address-one-vote: I alone may generate thousands of Ethereum addresses and send messages signed by each of them in turn. This is indistinguishable from thousands of people sending one message each. This is known as a ‘Sybil attack’.

Therefore, in order to mitigate Sybil attacks, we must have either a closed assembly which actively manages its membership, or a voting method that does not count addresses.

One Token one Vote?

Who votes? Is it the member of parliament who votes by sending the token from their address? Is the token the vote no matter where it comes from? If a member of parliament sends me their token and I send it to the ‘aye’ address, that would be like me, showing up at Westminster and impersonating an MP!

Instead of trying to ‘fix’ this problem through token address whitelisting, let’s extend the concept by allowing even fractions of tokens to be transferred. Voting tokens as described above represent something indivisible — e.g. membership in a parliament, or a ballot paper. Addresses are indivisible in ethereum, but tokens generally are not. What if voting tokens may be freely transferred between addresses and also divided up among them?

Half a token half a vote?

If a token is split over one thousand addresses casting one vote each, the total voting weight weight would still be 1. This compelling property makes token-weighted voting attractive, as it eliminates the Sybil attack vector.

Because we lack a proof-of-individuality, it is more common to find token-weighted voting schemes [e.g. in TheDAO]. These tokens do not represent an individual’s membership in an assembly; instead they represent some form of stake and their distribution is handled by the market.

Suppose tokens represent shares in a company. Shareholders commonly conduct share-weighted votes. A large shareholder’s vote counts proportionally more than that of a small shareholder. It makes no difference if I cast a vote from one account holding all of my shares or split my shares into thousands of accounts and cast thousands of votes; the total weight remains the same and the vote is not vulnerable to Sybil attack.

May I have a ballot paper?

Tokens now play a dual role. On one hand they represent my ownership in a company; on the other, they represent my voting weight. We must separate these roles when implementing our voting mechanism.

It is impractical for shareholders to vote by sending their shares to a voting contract because:

1. We need a way to return them afterwards
2. Users are limited to one vote at a time
3. Voting incentives are skewed by the opportunity costs imposed by reduced liquidity.

The obvious thing to do is to accept voting transactions from any address that holds share-tokens and to weigh that vote by that address’ token balance without the tokens being transferred anywhere. After all, this is exactly how shareholders at an annual general meeting would vote. Alas, things are not so simple.

The double vote attack

While shareholders at an AGM all cast their votes simultaneously, on the blockchain this is impossible.

Polls need to remain open for long enough to allow anyone to vote irrespective of timezone. Moreover, “everyone voting at the same time” requires all votes be part of the same transaction — a technical impossibility.

Having established that polls must be open for some time, imagine the following scenario:

1. Alice has 100 tokens and she casts a vote (with a weight of 100).
2. Alice transfers her tokens to her friend Bob.
3. Bob, with his newly acquired 100 tokens casts another vote (weight 100) before transferring the tokens to Charlie, who also votes.

It doesn’t matter whether Alice, Bob and Charlie are the same person or even if they all vote the same way; as long as users can transfer tokens between votes, double voting is a problem.

Token Locking

Instead of requiring Alice to send her tokens to the voting contract, we could just prevent Alice from transferring her tokens after she’s voted, and only allow them to be moved again after the polls close and the result is in. This is the approach taken by theDAO and is worth examining in detail.

This vote relies on the interplay of two components: the vote contract and the token contract.

When a vote is called, any address with a non-zero token balance may cast a vote consisting of a specially formatted transaction sent to the vote contract. When a vote is received, the following events are triggered (sketch):

1. The vote contract retrieves the current token balance of the voter.
2. The vote contract reads the vote (say ‘aye’ or ‘nay’) and adds the relevant number of votes to the total.
3. The token contract marks the voter’s address as locked and prevents any further transfer of tokens from this address until the vote is over.

This scheme allows us to hold multiple token-weighted votes simultaneously and it is resistant to Sybil attack.

Unfortunately neither votes nor running tallies are secret. Everyone observing the blockchain can tell which address voted, which way it voted and what the current total votes are, and most importantly, voting incentives are skewed.

Liquidity costs

Locking tokens can have unintended side effects. If people cannot move their tokens around then they cannot sell them either. In a fast moving market the ability to sell at short notice is valuable and may incentivise people to vote either only very late in the voting period or not at all.

It is important to be mindful of such effects, as it is easy to inadvertently introduce skewed incentives into a voting mechanism. In the case of the voting contract holding the tokens, liquidity cost affects the ‘aye’ and ‘nay’ votes equally, but in theDAO it was discovered post launch that the voting procedure specifically disincentivised voting ‘nay’.

Collect all votes and count at the end

If we do not lock tokens, we can still record the votes even if we cannot determine their correct weight.

After a vote is opened, we may proceed as follows:

1. Any address may send a vote ‘aye’ or ‘nay’ to the vote contract.
2. The vote contract records the address and the vote.

At the end ‘someone’ sends an ‘evaluating transaction’ which closes the vote and triggers the vote contract to:

3. read a previously recorded vote.

4. retrieve the address’ token balance from the token contract.

5. add the relevant number of votes ‘aye’ or ‘nay’.

6. delete the vote from the list.

7. repeat steps 3–6 until no votes are left.

For voting to work without token-locking therefore, we do not need everyone to cast their vote simultaneously as long as we evaluate en bloc.

Alas, this is impossible.

Gas limits

Every action in the Ethereum Virtual Machine costs ‘gas’ — an Ether denominated fee for processing the transaction. There is a limit to how many actions we can take in one go because we are allowed to use only a fixed amount of gas in each transaction and in each block.

This means that while we can add up ten votes, or one hundred votes, we cannot add up a million votes. The evaluating transaction — the one that is meant to add up all votes with the correct token-weighting — would exceed the gas limit. (A variant of this scheme was suggested in relation to The DAO and an investigation revealed that it would not work past 6000 votes)

Splitting the evaluation into two or more transactions is also not feasible as that reintroduces the double voting problem.

All aboard

Another undesirable feature of the voting presented so far is not technical, but social. During the voting period, running tallies are public.

Voting mechanisms are generally intended to harness the ‘wisdom of crowds’. To do so effectively, there are three main conditions which must be met:

1. Diversity of opinion: Each person should have private information even if it’s just an eccentric interpretation of the known facts.
2. Independence: People’s opinions aren’t determined by the opinions of those around them.
3. Decentralization: People are able to specialize and draw on local knowledge.

Where these conditions are not met, many cognitive biases negatively impact its efficacy, and lead to undesirable consequences such as bandwagoning and groupthink. (See also: here, here, and here.)

It is important therefore that a successful voting mechanism should defend these conditions by hiding the outcome of the vote, until the vote has concluded.

Commit / Reveal

Step 1: Put your ballot in a sealed envelope.

During the voting period masked votes are submitted. Instead of submitting a vote directly, voters generate a signed voting transaction and only submit its hash. This is the ‘commit’ phase. The vote has been submitted to the blockchain, but the vote is private and sealed by this “hash-lock”.

Step 2: Unseal your own envelope and count your own vote.

After the polls close, voters send a second transaction: the ‘reveal’. The voter submits the original signed vote to which they had previously committed. The vote is only accepted as valid if its hash matches the commit. A valid reveal transaction adds its vote to the total tally.

This procedure obviates bandwagoning and allows votes to be tallied without hitting the gas limit. The downside is every voter must submit two transactions for every vote. (Note also this is not a secret ballot — after the reveal step everyone’s votes are public knowledge.)

Partial-lock voting in Colony

When a proposal is made to a Colony, any token holder may vote. Votes must be sealed by a hash-lock as described above (“commit”). Accounts are not locked during the voting period, so tokens may be transferred back and forth between accounts throughout.

However, when the vote closes, all accounts with committed votes are locked. They cannot make any outgoing transactions until they reveal, and all incoming tokens are withheld by the token contract and not added to their accounts until after the reveal. The reveal transaction adds the relevant number of tokens to the vote totals, adds all withheld incoming tokens to the account and removes the lock.

Importantly, even though this method uses a form of account locking, there is no liquidity cost to the user as accounts can always be unlocked immediately when they are needed. This voting mechanism scales to arbitrarily large numbers of votes because each voter’s own reveal transaction adds their vote to the total. There is no need for one global add-the-votes transaction and thus we don’t hit the gas-limit.

Partial-lock voting in detail

When a user submits a hash-locked vote, the time the vote closes is recorded. The account is locked from that time onward and all transfers withheld until the user submits the reveal transaction to have their vote counted and their account unlocked.

The colony contract maintains a data structure consisting of all votes an address has committed but not revealed. It takes the form of a double linked list ordered by time the votes close and a list of unrevealed secrets for every closing time.

We declare Timestamp 0 as the first and the last element. This double linked list of closing times can be seen therefore, as forming a closed loop starting and ending at 0.

Suppose a user casts a new vote with closing time 127. Looking at our diagram we can see the record should be inserted between timestamp 123 and 456. Within the smart contract however all we could do is start at timestamp 0 and traverse the entries until we encounter the first whose timestamp is greater than 127 (or we hit zero again). Such a stepwise procedure would run into the gas limit: we can imagine proceeding to the 5th entry in the list but not the millionth. Yet, this failure to determine where in the list some timestamp belongs is only constrained to smart contracts themselves. From the outside, any of us can read the entire state and reason about it — the user who is sending a new voting transaction has no problems determining where in this list it ought to be inserted.

We cannot expect the smart contract to ‘find the first entry whose timestamp is greater than 127’, but a transaction can tell the contract to ‘insert a new record after timestamp 123’. Thus, while the contract cannot iterate over the list, the transaction can specify a position in the list where the vote belongs.

Submitting a new vote:

In order to submit a vote, the user must submit a voting transaction consisting of the following data:

1. Vote ID: what are we voting on
2. Secret: the commitment
3. Position in the list where it is to be inserted

The contract can check if the data supplied in 3. is correct (i.e. if the list remains sorted after the insertion) by comparing the corresponding previous and next timestamps. Either a new timestamp is added to the list, or if it already existed, the vote is added to the corresponding list of secrets.

Revealing a vote:

To reveal a vote, a user must submit a reveal transaction consisting of:

1. The vote ID: what vote we are revealing

2. The vote itself — the one whose hash is the commit.

From the vote ID, the contract determines the closing time of the vote and calls up the corresponding entry in the list and retrieves the committed secret. It compares the hash of the submitted vote to the committed secret. If they match, it updates the vote tally and deletes the secret. If there are no more secrets at this timestamp, it removes the timestamp’s entry from the list entirely, modifying the neighbouring next/previous links accordingly.

Finally, if the account is now in an unlocked state, any held funds are added to the account.

Determining if an account is locked

When a user wishes to transfer tokens, the token contract retrieves the first timestamp in the list — the ‘next’ entry from 0. We then have the following possibilities:

1. The timestamp is 0. In this case the list was empty, there are no unrevealed or pending votes and the account is unlocked.
2. The timestamp is old enough that the reveal period has expired for this vote. In this case the account is locked and the user must first delete this entry from the list. (The user can do this by issuing a standard reveal transaction even though the vote will no longer be counted).
3. The timestamp shows the voting period has ended and is currently in the reveal period. The account is locked and the user must first issue a reveal transaction.
4. The timestamp shows the voting period has not yet ended. In this case the account is unlocked.

Conversely, whenever there is an incoming transaction to an address, the token contract must determine if the receiving account is locked. If locked, incoming tokens are not added to the account directly but instead added to a ‘pending’ balance which will credit the actual account when it is unlocked.

What’s still missing:

Missing from this sketch is how we deal with the situation in which multiple votes close at the same time [Hint: Each timestamp entry maintains a double linked list of unrevealed secrets, a count for number of unrevealed secrets as well as a pointer to one of the secrets in the list].

Our full implementation will be explained in the upcoming Colony Whitepaper.

Where does that leave us?

The partial-lock vote mechanism has many benefits. It scales indefinitely, does not suffer from the double voting problem nor the bandwagon effect, and it does not impose a liquidity cost on voters. While it does require two actions per vote, that inconvenience can be substantially mitigated by thoughtful interface design.

The mechanism represents the basis on which Colony’s day-to-day decision making infrastructure is built. Beyond a yes/no vote it can support virtually any voting methodology: multiple choice, range voting, borda count, ranked voting, et cetera.

It also allows votes to be weighted by more than just token balance: Colony will facilitate meritocratic governance. The eventual implementation will take into account a person’s contributions to a project, not just their token wealth.

Furthermore, the usefulness of the locking mechanism extends beyond voting and decision making: it can also enable disbursement of rewards to token holders without a loss of true fungibility — an issue which would have become apparent in ‘theDAO’ in time.

And yet…

There is still a case to be made for token locking. Longer term/larger governance and budgetary decisions benefit from a token-locking vote that forces voters to “put their tokens where their mouse is”. The context is important, and unlike theDAO the consequences of locking should not be asymmetrical and should be explicitly understood as features of the contract, not unintended consequences.

The hierarchy of decision making in Colony, delineating at which level we intend to use which mechanism, will be explored further in another blog post.

Join Colony's mailing list to stay up to date with conversations on the future of work and organizations.

About the Author

Aron Fischer received his PhD in mathematics from the City University of New York in 2015. His specialization was in Algebraic Topology and Homotopy theory. Since his graduation he has been studying homotopy type theory in his free time and is interested in how (higher) type theory can help us write safer smart contracts.

He is working for Colony in R&D, developing the governance protocols, and for the Ethereum Foundation's Swarm team where he is working on state and payment channels for the swarm incentive structure. He regularly participates in the Casper research hangout and can be found in the ethereum research gitter channel under the handle 'homotopycolimit'.