The Voting system is a core component of any (DAO) regardless of its complexity and number of participants. Despite massive interest in this area, fully decentralized and secure (therefore trustworthy) on-chain votings are still hard to implement. Decentralized Autonomous Organization There are two key problems: Sybil attack resilience — it is hard to keep track of valid voters. 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 a completely decentralized manner. Task definition Let’s assume we need to implement a voting system that has to satisfy these requirements: voters can only or a voting topic; ACCEPT REJECT voters vote by their voting power (weight) based on the number 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 expires and only if the majority of voters -ed it; ACCEPT 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 vote yet — add the balance to or counters” that just won’t work. ACCEPTED REJECTED We see that a malicious token holder would easily overcome such a voting system. All they need to do is simply vote once, transfer the token to another address and then vote again. They can repeat this process until they reach the desired voting outcome. Our votings lost their trustworthiness and we no longer able to perform critical on-chain actions autonomously — this will lead to the inevitable death of our dapp. This situation when an actor uses unlimited identities to gain an advantage over a system is called a . It looks very simple at a first glance, but the more we think of a solution, the more we get confused. Sybil attack “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 event. There are two questions: This list can theoretically become huge, how do we handle this? 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 to complete of the voting system (if there is more computation to perform over that list, that a single block can handle). DoS Let’s imagine this solidity function (uint = ; < voters. ; ++) {
        require(token.balanceOf(voters[ ]) > ); 
    }
    createVotingObj(voters, duration, description);
} { function startVoting (
    address[] calldata voters, 
    uint duration, 
    string calldata description
) external for i 0 i length i i 0 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 a 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 to (and we shouldn’t), validate this data. Look at the function above once again — nothing stops a malicious user from making an “exclusive” voting play, where only a little subset of token holders 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( uint256) balances; => address and mappings in EVM are implemented in a way that doesn’t let us . So there is no way to know addresses that have a non-zero balance. iterate over its keys 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). That way there is no need for users to stick to some identity — it will work out of the box. We need to have on-chain access to the balance history of any account holding the token. The solution To make it cheap we should write our solidity code in a 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 the balance history on-chain every time the token moves. Let’s do this. Let’s assume that we’ve chosen implementation as a base for our token. OpenZeppelin’s ERC777 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 hook, like this _beforeTokenTransfer() _beforeTokenTransfer(
    address , 
    address , 
    address , 
    uint256 amount
) override 
    virtual 
{ ( != Utils.EMPTY_ADDRESS) {
        updateAccountHistory( , balanceOf( ).sub(amount));
    } ( != Utils.EMPTY_ADDRESS) {
        updateAccountHistory( , balanceOf( ). (amount));
    }
    super._beforeTokenTransfer( , , , amount);
} /**
 * Using openzeppelins hook to update history on every change
*/ function operator from to internal if from from from if to to to add operator from to 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 the balance history each time it fires. Account history is just an array of records {        
    uint256 timestamp;        
    uint256 balance;    
} // notice, we can optimize it to only use a single slot struct BalanceSnapshot which we store for each account of this token mapping( BalanceSnapshot[]) balanceSnapshots; => address 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 — . This function returns us a balance of any account at any moment in time. Inside this function, we take advantage of the 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. balanceAt() But what if the balance history of a particular token holder becomes too big? In this case, the token holder can call , 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. clearAccountHistory() 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 instead of . 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 . If at this timestamp a voter was holding some tokens ( returns non-zero), they are allowed to vote. token.balanceAt() token.balanceOf() balanceAt balanceAt 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 NONE, ACCEPT, REJECT    
} uint256 myTokenTotalSupplySnapshot;
    uint256 createdAt;        
    uint256 duration;        
    uint256 totalAccepted;        
    uint256 totalRejected;        
    bool executed;        
    string description;        
    mapping(address => VoteStatus) voteByAccount;    
} { enum VoteStatus { struct VotingDetails 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 them on-chain transparently. The smart-contract also has 3 next functions: that just stores a new struct in the state; startVoting() that checks voters and applies it to the result; vote() balanceAt that can be invoked only after duration pass. executeVoting() 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 function is super-cheap — it takes less than to vote (with gas price). Basically, we spread it’s cost and complexity over the entire lifecycle of the dapp, without compromising security. vote() 0.01 ETH 100 GWEI 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 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. clearAccountHistory() 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 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. vote() It is easy to see that this voting system can be modified to implement scheme or to implement an ability to . 1 account = 1 vote 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. https://github.com/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.

Chain

Dapp

fees

Super

2022 - HackerNoon Contributor of the Year - Smart Contracts

Read My Stories

Nominated for 2022 - HackerNoon Contributor of the Year - Smart Contracts

Too Long; Didn't Read

Discover Saakuru: Web3 Mass-Adoption with 0-FEES

I Built An Ethereum-based Fully Decentralized Voting System

Too Long; Didn't Read

Companies Mentioned

Coin Mentioned

Alexander Vtyurin

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

I Built An Ethereum-based Fully Decentralized Voting System

Too Long; Didn't Read

Companies Mentioned

Coin Mentioned

Alexander Vtyurin

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES