Cheap, secure and fully decentralized voting system on Ethereum

Voting system is a core component of any Decentralized Autonomous Organization (DAO) regardless of its complexity and number of participants. Despite of massive interest in this area, fully decentralized and secure (therefore trustworthy) on-chain votings are still hard to implement.

There are two key problems:

1. Sybil attack resilience — it is hard to keep track of valid voters.
2. Cost-effectiveness (if we manage to fix problem #1) — not all voters are interested to pay high fees in order to declare their opinion.

In this article I want to present my solution to this case. This solution provides a level of security that is enough to automate critical decision making in any DAO such as automatic protocol modification or even automatic smart-contract upgrade done in completely decentralized manner.

Task definition

Let’s assume we need to implement a voting system that have to satisfy these requirements:

• voters can only ACCEPT or REJECT a voting topic;
• voters vote by their voting power (weight) based on amount of tokens they possess;
• voting can be “executed“ — that will lead to some critical change in another part of our dapp (imaginary, in this article);
• voting can only be “executed” after it expire and only if the majority of voters ACCEPT-ed it;
• no token lock during votings.

Also, this voting system should be completely decentralized:

• there is no admin;
• any token holder is able to start a voting;
• any token holder is able to vote;
• any token holder is able to “execute” a voting.

The Problem

If we naively implement this like “check the caller’s token balance and if they did not voted yet — add the balance to ACCEPTED or REJECTED counters” that just won’t work.

We see that a malicious token holder would easily overcome such a voting system. All they need to do is to simply vote once, transfer token to an another address and then vote again. They can repeat this process until they reach a desired voting outcome. Our votings lost their trustworthiness and we no longer able to perform critical on-chain actions autonomously — this will lead to inevitable death of our dapp.

This situation when an actor uses unlimited identities to gain an advantage over a system is called a Sybil attack. It looks very simple at a first glance, but the more we think of a solution, the more we get confused.

“Omg, just provide a list of every token holder’s address and balance when you create a voting, this is easy!” — we think

This looks like a valid idea — if we should somehow prevent users from making many identities, we could restrict them to stick with a single identity during a voting. There are two questions:

1. This list can theoretically become huge, how do we handle this?
2. Who should supply the list into our voting system?

Analysis

Now when we know what questions exactly we have to answer in order to proceed, let’s do a little of software architecture analysis.

1. The list can become huge

EVM is pricy (especially with 1200 USD per 1 ETH exchange rate), this means our code should be very compact and performant if we want someone to even touch our dapp. We also can’t operate large datasets (like our potential list), because this can lead into complete DoS of the voting system (if there is more computation to perform over that list, that a single block can handle).

Let’s imagine this solidity function

function startVoting(
    address[] calldata voters, 
    uint duration, 
    string calldata description
) external {
    for (uint i = 0; i < voters.length; i++) {
        require(token.balanceOf(voters[i]) > 0); 
    }
    createVotingObj(voters, duration, description);
}

It takes a set (technically, a list — we have to manually check if there are any repetitions) of voters, checks that all of them have something in their wallets and creates a state entry with these addresses and their corresponding balances. It is obvious that this function doesn’t scale and could require huge amount of gas if there are many voters.

Looks like a “list” won’t work here — we need something else.

2. Someone should supply this information into our voting system

This can’t be done by us — this would mean that our dapp is centralized.

This also can’t be done by someone else, because we have no way (and we shouldn’t, actually) validate this data. Look at the function above once again — nothing stops a malicious user of making an “exclusive” voting, where only a little subset of token holder would be able to vote.

This information also can’t be retrieved from the token itself. Balances in ERC tokens are stored inside a mapping

mapping(address => uint256) balances;

and mappings in EVM are implemented in a way that doesn’t let us to iterate over it’s keys. So there is no way to know addresses that have non-zero balance.

Looks like this information should come from somewhere else.

3. Conclusion

A key to the solution lies in obtaining a method to “freeze” balances at some point in time and then use this snapshot to validate any voter. This method should be cheap and autonomous (so voters couldn’t take any advantage of it). We need to have on-chain access to balance history of any account holding the token. That way there is no need for users to stick to some identity — it will work out of the box.

The solution

To make it cheap we should write our solidity code in gradual fashion — when no bulk reads/writes are performed and only a little portion of data is modified per transaction. So, it looks like our only way is to update balance history on-chain every time token moves. Let’s do this.

Let’s assume that we’ve chosen OpenZeppelin’s ERC777 implementation as a base for our token.

This implementation of ERC777 provides a hook-function that makes it easier to explain and present the idea, but if our goal is cost-effectiveness we might want to keep it minimal and implement this logic on top of ERC20. This is a little harder (we’ll have to alter original ERC20 methods) but still pretty trivial.

Now we want to take advantage of ERC777 _beforeTokenTransfer hook, like this

/**
 * Using openzeppelins hook to update history on every change
*/
function _beforeTokenTransfer(
    address operator, 
    address from, 
    address to, 
    uint256 amount
) 
    internal 
    override 
    virtual 
{
    if (from != Utils.EMPTY_ADDRESS) {
        updateAccountHistory(from, balanceOf(from).sub(amount));
    }
    if (to != Utils.EMPTY_ADDRESS) {
        updateAccountHistory(to, balanceOf(to).add(amount));
    }
    super._beforeTokenTransfer(operator, from, to, amount);
}

This hook is automatically executed every time tokens move: on transfer(), send(), mint() and burn(). That is exactly what we need, so we just update balance history each time it fires. An account history is just a an array of records

// notice, we can optimize it to only use a single slot
struct BalanceSnapshot {        
    uint256 timestamp;        
    uint256 balance;    
}

which we store for each account of this token

mapping(address => BalanceSnapshot[]) balanceSnapshots;

But how exactly do we update it? We just check if the last snapshot was done in the same block or not. If it is, we override it with a new balance value (to only store a most recent snapshot per one block), otherwise we just make a new snapshot and add it to the end of the history.

Now, when we have a balance history of each account accessible on-chain, we can implement the main function of this contract — balanceAt(). This function returns us a balance of any account at any moment in time. Inside this function we take advantage of linear nature of the balance history (it is sorted by timestamp by default) and use a binary search to find a snapshot that we need.

But what if the balance history of a particular token holder becomes too big? In this case the token holder can call clearAccountHistory() function, that will remove their complete balance history except for the last snapshot, if there is one. This is still secure for our voting system — soon we’ll see why.

Here is the complete gist of our fancy token.

Let’s continue on our quest for beauty, gentlemen. Next we need to implement our voting system smart-contract itself.

The idea is simple: every time we need a voter to prove their token possession we use token.balanceAt() instead of token.balanceOf(). For each existing voting the contract should store some timestamp that represents a moment in time from when it is legitimate to put votes. This exact timestamp we would use to check balanceAt. If at this timestamp a voter was holding some tokens ( balanceAt returns non-zero), they are allowed to vote.

There is also a little caveat here. Our token works perfectly fine with past events, but is bad when it comes to present or future events. Never rely on balanceAt in future and in a current block — this action can be manipulated by an attacker.

Our voting system smart-contract stores votings in structs

enum VoteStatus {        
    NONE, ACCEPT, REJECT    
}
// notice, this can also be optimized
struct VotingDetails {
    // we need this field to implement a voting threshold
    uint256 myTokenTotalSupplySnapshot;
    uint256 createdAt;        
    uint256 duration;        
    uint256 totalAccepted;        
    uint256 totalRejected;        
    bool executed;        
    string description;        
    mapping(address => VoteStatus) voteByAccount;    
}

In this article we keep it simple, but in a real-world example in order to change some protocol parameters we might want to also add them to this struct and store on-chain transparently.

The smart-contract also has 3 next functions:

• startVoting() that just stores a new struct in the state;
• vote() that checks voters balanceAt and applies it to the result;
• executeVoting() that can be invoked only after duration pass.

Here’s the complete gist of our smart-contract.

This complete code might seem big, but if we think carefully we can clearly see that almost all of it is the actual voting protocol, not permission checking. If we consider our voting contract as a client code for the token contract, it becomes obvious that we’re only using a single function from it and all this good stuff comes for free.

And that’s all we need to reach our goal. These two contracts completely satisfy our requirements. Our voting system is completely decentralized — any DAO can make decisions even if there is no maintainer. This vote() function is super-cheap — it takes less than 0.01 ETH to vote (with 100 GWEI gas price). Basically, we spread it’s cost and complexity over the entire lifecycle of the dapp, without compromising security.

How can we possibly break it? I don’t know. If an attacker would try the old trick “vote -> transfer -> vote again” it just won’t work, because the voting system doesn’t care about future — it only operates with a snapshot of the balance history. Any scheme with clearAccountHistory() is also a failure, because the voting system will interpret a clean history as zero-balance and won’t let this voter to participate current voting anymore. Just don’t forget to check for current block and everything should be fine.

Current block check is important because during a current block an attacker can still perform “vote -> transfer -> vote again” technique.
Imagine we started a voting, but forget to check current block timestamp in the vote() function. This means that if someone immediately votes (in the same block), our voting contract will use the most recent balance history snapshot for it’s computations. But this snapshot is not finished yet! It can still change during this block and we can’t be confident about it.

It is easy to see that this voting system can be modified to implement 1 account = 1 vote scheme or to implement an ability to re-vote.

This pattern (token with on-chain history) can be also used in any other protocol with similar requirements — for example, dividends distribution based on token shares.

Here is a link to a github repo that contains this exact voting system covered with tests, so you could play with it for better understanding.

seniorjoinu/solidity-cheap-voting

I believe, this technique can be used in any other blockchain platform and I hope it was useful and interesting for you.