On-chain Liquid Democracy

A healthy internet is decentralised. It is open, inclusive, neutral and safe. However, our entire internet experience as we see today is governed by a few organisations who often have economic incentives to work on closed systems that harm the internet interoperability; and consequently, we’re losing on transparency and participation along with it. The idea that these few organisations make decisions behind closed doors that eventually affect our internet experience sounds totalitarian to me.

On/Off Chain Governance

An excerpt from an essay on blockchain governance by Peter Zeitz, 0xproject.

Blockchain platforms have witnessed an explosion of collaborative innovation, where small independent teams of developers create narrow layers of functionality that interact with one another to create an end user experience. Currently, project teams in our ecosystem align towards a shared goal of building out open infrastructure and persuading a common pool of users to adopt it.

As fancy as working towards shared goals sounds, it brings with itself a completely new set of challenges around decision-making processes for the projects building out this open infrastructure. These decision-making processes are broadly classified under an umbrella term — Governance. I find the discussions around blockchain governance especially fascinating because they bear an uncanny resemblance to how citizens of nation states allow themselves to be governed — playing a part (or none at all) in policy making for the country. It’s fascinating how challenges in the blockchain space map to issues in the real-life — fiscal, monetary, environmental impact, governance and so on.

Liquid Democracy

One such idea that maps out beautifully to both blockchain space and living reality is the idea of liquid democracy. Liquid Democracy creates a truly democratic voting system that empowers voters to either vote on issues directly, or to delegate one’s voting power to a trusted party — to vote on their behalf. What if each of us could pick whoever we wanted — personal representatives — to more closely champion our values? This article aspires to be a technical one so I’ll skip discussing liquid democracy itself — which warrants for several articles of its own and has been discussed concisely in True Democracy for the 21st Century and Democracy 3.0 for the transparent world. Now, I would like to walk you through the solidity implementation of the same and the following assumes the knowledge of ideas behind liquid democracy. It also attempts to be a solution to some of the open challenges for on-chain Liquid Democracy.


Solidity Tutorial

Step 1
The sponsor of the vote will create the contract LiquidDemocracy, add voters and proposals — for the voters to deliberate on. Let’s say the state sponsors the vote to gather public opinion on whether they’d like $403 million to be spent on building the world’s largest statue. For the sake of illustration, we can assume the people can vote on a Yes, No or Maybe.

addVoter and newProposal functions

For this example, we will write a test to add 3 proposals and 9 voters. The test is written using the truffle testing framework. A couple relevant features of the framework:

  1. Before each contract() function is run, contracts are redeployed to the running Ethereum client so the tests within it run with a clean contract state.
  2. The contract() function provides a list of accounts made available by your Ethereum client which you can use to write tests. These accounts are accessible as accounts array in the test.

ganache-cli configures 10 accounts by default. accounts[0] belongs to the sponsor (default account used by truffle to deploy the contracts) and accounts[1], [2]....[9] will be our voters. The test would look like:

add proposals and voters

Step 2
Now the voters can start choosing their delegates for the vote in question. Voter 3 knows that their kin (voter 2) is well versed in state’s economic policies and infrastructural requirements — so they decided to delegate their vote. Similarly, some other voters decide to delegate to people they thought are more insightful about the subject.

Some voters delegate their voting power

Even though voter 7 is acting as a proxy for voter 8, under the constructs of liquid democracy, voter 7 can further delegate their voting power in its entirety to someone else, if they prefer — creating a super proxy.

Voter 7 delegates their combined vote to voter 5

Tasked with the responsibility of making the righteous judgement on behalf of 3 other voters; voter 5 decided it’s best that they let voter 4 (whom they deem to be the subject matter expert in this regard) make the best judgement on behalf of the 4 of them.

Voter 5 delegates their combined voting power to voter 4

The delegates and vanilla voters then exercise their voting rights to vote on proposals — Yes, No and Maybe, denoted as P0, P1 and P2 respectively.

Voting begins

While the voting was in progress, voter 8 saw that their delegate chain had voted for Maybe. Having been following these discussions about the state expenditure, voter 8 started feeling more strongly about the subject and decided that an expense of $403 million can be better utilised to fuel the state’s growth and decided to delegate to voter 2 — who has been constantly lobbying against the statue.

Voter 8 changed their delegate

Solidity code for the same would look like this.

Lines 13–15 in function delegateTo delegates the voter’s (msg.sender) vote to address delegate . The index of the address delegate in validVoters[] is at voters[delegate].index . Also setting the voter’s state to State.Delegated . The runtime heavy function here is delegationCycleExists which checks for delegation cycles i.e. V1 delegates to V2, V2 delegates to V3 and then V3 attempts to delegate to V1.

Delegation cycles have to be avoided

For n voters, the worst case time complexity is O(n), however in a real scenario we are unlikely to see large delegation chains — often the voters would gravitate towards delegating to a handful of representatives or voting directly.

Large delegation chains are unlikely

Also, vote function is simply:

set .vote and .state in the voter object

Then for the test, votes and delegations look like:

Now, the vote comes to an end and it’s time to find out the winning proposal. To find the winning proposal, I have used the depth first search graph traversal.

  1. The idea is to loop through the validVoters array (line 10) and traverse up the delegation chain until we find a voter who has directly voted on a proposal (or not voted/delegated at all) — calling them leaf voters henceforth.
  2. While traversing up the delegation chain, we add the voting power (variable totalVotes) for each voter along the way and mark the voter as visited.
  3. When we reach a leaf voter, add the accumulated votes to the proposal for which the leaf voter voted for.
findWinningProposal

Again, the worst case (large delegation chain) time complexity for the above is O(n²)- because we are traversing all way from a voter up to the leaf voter each time to find the eventual proposal they voted for. To optimise here, we can use a call stack to keep track of the voters being processed as part of a delegation cycle and backtrack to set the proposal number for each voter for which their vote counted towards. This way we can bring down the time complexity to O(n) by using by O(n) space. This approach would be similar to union-find path compression.

The complete test with assertions would look like:

truffle test

Hope you liked the ideas presented here! If you’d like to discuss the ideas behind liquid democracy, implementation, path compression or have a better data structure in mind that could be put to use here, head to the comments section. Thank you for reading this far!

I used the https://ncase.me/crowds/ sandbox mode to create the cute little voter diagrams. Do checkout this really cool game on the wisdom (or madness) of crowds. Also, received help from my sister to edit the illustrations.