Open challenges for on-chain Liquid Democracy

voting

#1

The features we want:

  • Ability for any token holder to delegate their voting power to another address. Someone who is delegated some voting power can delegate those further to another delegate.
  • Holders and delegates have the ability to cast their own vote and override whatever their final delegate voted (can also vote before the delegate, and then the delegate won’t be voting on their behalf).

Implementation approach

When a delegation happens, the total voting power the delegator has (staked tokens + amount delegated to them) is recursively added to the delegate balanced of all the accounts above in the delegation chain. Thanks to this, it is really fast to compute the total voting power of an account, which makes the cost of delegates casting a vote constant regardless of how many holders have delegated their voting power to them.

This approach requires storing quite a fair amount of data when a delegation happens, alternative implementations could store less data on delegation and rely on doing more complex reads for calculating the total delegated amount. This would open the door to potential griefing attacks to popular delegates, making their vote casting transactions more costly.

Challenges

The main unsolved challenges that we have encountered while prototyping on-chain liquid democracy are:

1. Undelegation cost is proportional to delegation chain depth

Because the delegated voting power is added to all the delegates above in the delegation chain, undelegating requires recursively subtracting the previously delegated voting power from all delegates above. Therefore the cost of undelegating grows linearly with the depth of the delegation chain above one’s delegate.

This can be used by delegates to disincentivize undelegations by making them very expensive. By artificially delegating their voting power to other accounts they control, delegates can create a very deep delegation chain that is expensive to undelegate from.

If there are no bounds to the depth of delegation chains, delegates could make it impossible (gas limit attack) for someone to undelegate from them, which could even make tokens stuck forever. This issue can be solved by setting an upper limit (MAX_CHAIN_DEPTH) to how deep delegation chains can be.

2. Properly easuring delegation chain depth requires a lot of storage

As shown in 1, keeping track of delegation chain depth is required to avoid major griefing attacks. A naive approach is just storing at every step of the chain the current depth (every time a delegation is made, it is set to the new chain depth is if it is higher than the previous one). This however presents some challenges when an undelegation happens, as it isn’t possible to know if there were actually more chains of that depth or what the new depth after undelegating is.

Two (bad) solutions to this are:

  • Just keep the historic maximum chain depth for a delegate and not modify on undelegations.
  • Keep track of the sizes of all delegation chains below a delegate, so whenever an undelegation happens the current delegation chain depth can be calculated. This would require a ridiculous amount of storage.

3. Delegators can block holders and delegates from delegating

A delegation chain can be created below a certain delegate or holder by delegating a chain of depth MAX_CHAIN_DEPTH - currentDepth. This would prevent them from delegating further because their delegation chain would be at the maximum.

A solution would be to allow delegates to choose a custom maximum delegation chain depth that their delegators can have if they in order to delegate to them, so they couldn’t be pushed to the chain depth limit by someone delegating to them. A sane default could be MAX_CHAIN_DEPTH / 2 and popular delegates could increase it if needed (if someone will never delegate, it can safely be set to the upper bound). Once increased, it couldn’t be lowered unless forcing all an undelegation of all the deeper delegation chains.

4. The cost of overriding a vote is proportional to delegation chain depth

If anyone in the chain can override the vote of their delegate (In chain A -> B -> C, B could override C’s vote for voting power A + B and A could override the vote too), the cost for overriding a vote is proportionally to the chain depth above.

The griefing attack explained in challenge 1 can be used by delegates to disincentivize vote overriding, making them expensive by creating artificially deep delegation chains.

Conclusion

The impact of these challenges could be reduced by choosing better data structures than this initial naive approach. Implementing complex data structures in the EVM is usually suboptimal given the high costs of storage.

We are actively trying to workaround them and try to have an implementation that diminishes the potential griefing attack vectors. Implementing LD on-chain may end up being too expensive and offloading the calculation of delegation chains and tallying to an off-chain computation oracle may could be the way to go.


#2

Could problem 1 (cost of undelegation) be reduced by requiring each delegation action to vest the assumed cost to unwind the action in a smart contract? Anyone in the chain of delegation would be able to use the funds in the smart contract if they chose to undelegate. This means the original voter (and earlier delegates) would not have to pay for 1 million transactions if a later delegate created a giant delegation chain that they controlled. Thanks for considering.


#3

I agree with AdamOpen that incentives may be the only way to tackle this without moving to a plasma chain or off chain. I don’t see a way around the tradeoff between speed of delegation/undelegation vs voting. I think the challenge is we don’t want casual users to be disincentivized from participating. It’s so hard to get people to vote, and if we charge them to delegate their vote they won’t do it. Maybe one way to approach this would be to require a bond like AdamOpen suggested, but to scale the size of the bond based on the depth of the chain. Delegating one vote could be free, but delegating anything beyond a depth of one could require a bond to be posted that increases in proportion to the depth of the delegation chain.


#4

I think the approach @AdamOpen suggests could potentially be used to ensure that the cost of un-delegating is paid at the time of delegation. However, it is my understanding that it would still be necessary to provide a solution that limits MAX_CHAIN_DEPTH otherwise the un-delegate action could be blocked by hitting the max gas limit for transaction.

If you have to solve the issue of tracking MAX_CHAIN_DEPTH anyways, it can be set to a reasonable chain depth such that the un-delegate action is never too outrageous.


#6

We have the same problem at Kleros to implement Liquid Voting (I prefer this term to liquid democracy as votes are weighted by token holding which is fine but cannot qualify as “democratic”).

My thoughts on the topic:

(I originally tried to post it on this discourse but it was blocked due to link and image restrictions, so if a moderator could remove those, it would make collaboration easier).


#8

Interesting ideas @AdamOpen @TonyWald, thanks for the feedback!

The issue with that approach is that the deposit for delegating would need to also depend on the number of delegations and not only the chain depth, as whoever delegates would need to cover the increased gas cost for undelegating an extra hop in the chain.

A simple user story where this could be a problem: If someone who has been delegated to by many holders with varying chain depths decides that for a period of time when they won’t be paying attention, and they wish to delegate to someone else. Now this delegate would need to deposit a high amount in order to perform a beneficial action. Adding a delegation fee depending on chain depth creates a disincentive for re-delegating.

For clarification, someone undelegating would only need to send one transaction. MAX_CHAIN_DEPTH should be calculated so that the gas needed for undelegating a chain of that size is YEARLY_AVG_BLOCK_GAS_LIMIT / k (k being a number between 4 and 7 to be conservative).

As @lkngtn says, we need to calculate the chain depth at all times and MAX_CHAIN_DEPTH needs to be enforced regardless as it prevents other griefing attacks. I think if the griefing potential is low, delegation chains will tend to be fairly short.


#9

@clesaege that is is a really good analysis, thanks for sharing!

We have had some discussions about creating a game where anyone can submit the result of the vote (along with a deposit and in exchange for some bounty) and if it was not contested then the result would be taken as correct, without any need to do the tabulation on-chain. In the event of a dispute the chain could be tabulated in batches (but would be expensive). The thinking being that the submitters deposit could be used to compensate people for calling the tabulation batches if the result was overturned.

However, it doesn’t seem like there is a way to know upfront how much the deposit needs to be to ensure that it is sufficiently large to cover the costs of manually tabulation. I think your suggested approach of having multiple submissions and assuming the submission with the largest deposit backing it is correct could potentially resolve that issue. Will think on it a bit more!


#10

Hi @lkngtn.
Yeah, think the game with a deposit is the way to go and it can be combined with another approach.
Now we need to determine which approach we want to use for on-chain computational dispute resolution.


#11

Liquid democracy newbie here! Excuse me if something sounds wrong. Thank you.
2 and 3 discuss the implementation of MAX_CHAIN_DEPTH - which is introduced in 1. 4 is a special case of 1. So, solving 1 should suffice. I would like to propose a simple solution.

Let’s say there are n voters V0, V1, .... Vn-1. A particular voter may vote, delegate their vote to another voter or not vote at all.

An array balances[n] - where balances[i] denotes the voting power of Vi.
An array delegatedTo[n] - where delegatedTo[i] == k denotes that Vi has delegated their vote to Vk; -1 otherwise
A mapping(uint => uint) voted - where voted[i] == p denotes Vi voted for proposal p.

    const NUM_VOTERS = n;

    functions:
    vote(uint p) {
    	voter = msg.sender;
    	if (delegatedTo[voter] > -1) delegatedTo[voter] = -1;
    	voted[voter] = p;
    }

    delegate(uint v) {
    	voter = msg.sender;
    	delete voted[voter];
    	delegatedTo[voter] = v;
    }
    // Both the above state changing operations are O(1).

    countVotesOnProposals() public view {
    	mapping(uint => uint) votes; // votes[p] == k denotes k votes on proposal p;
    	// iterate through delegatedTo
    	bool[] memory visited = new bool[](NUM_VOTERS);
    	for (uint i = 0; i < NUM_VOTERS; i++) {
    		if(visited[i]) continue;
    		voter = i;
    		netVotingPower = 0;
    		while(1) {
    			if(!visited[voter]) {
    				netVotingPower += balances[voter];
    				visited[voter] = true;
    			}
                if(delegatedTo[voter] == -1) break;
    			voter = delegatedTo[voter];
    		}
    		votes[voted[voter]] += netVotingPower;
    	}
    }
// The above read operation is O(n)

delegate function would require an additional O(n) read to check (and revert) if a delegate cycle is forming


#12

Hello everyone! I’m new in the Aragon community but I have spent a bit of time in the past researching efficient data structures for on-chain liquid democracy as I’m also interested in the topic.

To the best of my knowledge, Link/cut Trees (introduced by Sleator and Tarjan in this paper) are probably the best data structure to be used when implementing the voting protocol. They have amortized O(log n) worst case performance for all the operations (where n is the number of participants), which is pretty good (it will probably become possible for communities of 1M+ members to do on-chain liquid voting).

Here’s a very brief description of how this works:

  • x votes or delegates the vote to y becomes a link(x,y) operation
  • x changes the vote to z becomes a cut(x) followed by a link(x,z) (the entire subtree of x gets implicitly reassigned as well)
  • one can efficiently (logarithmic time) determine at any point the representative of x by querying find_root(x)

Natively there are no node weights in the link/cut trees (to model the differences in each participant’s stake) but I believe it’s relatively easy to adapt the technique to handle weighted voting as well.

Let me know if you find this line of research worth pursuing, I’m interested to contribute.


#13

Interesting @meronym. I’m not sure this solves the biggest bottleneck for the implementation which relies on calculating the total weight delegated to a delegate when they cast a vote, in a way that doesn’t linearly increase with the number of delegations. The challenges detailed in this post are related to our naive implementation in which we ‘cache’ the weight everyone has given the delegations they received.

More research on how we could use this data structure so we can efficiently get the weight of every node would be super welcome!


Exploring alternatives to Liquid Democracy
#14

This post was referenced on medium in an article walking through some possible approaches to implementing LD on-chain, figured it would be worthwhile to cross reference here: https://medium.com/@atvanguard/on-chain-liquid-democracy-c08ed8c07f6e