a gas-efficent, ranked-choice voting system

gas-efficient ranked choice voting.md

here i describe a design of a gas-efficent, ranked-choice voting system.

the problem

the most common form of ranked choice voting, instant run off, works like this:

1. voters submit a list of candidates sorted by their preference.
2. if there is an option with the majority of first-preference votes, that option is the winner.
3. otherwise, remove the option with the fewest first-preference votes from all preference lists and repeat.

this algorithm presents a problem: the compute cost for tallying an election result increases with the number of votes cast; a proposal can be DOSed by an adversary casting many votes.

complexity management

when encountering problems like this, you've basically got two options:

1. invent or discover a different algorithm for doing the same thing.
2. move the complexity somewhere running out of gas isn't a security risk.

for an example of the second point, consider the problem of counting the number of elements in a linked list. at first glance, this is O(N), but one can trivially modify the linked list datastructure to put the length in storage and then it can be accessed instantly so long as it is updated when new elements are added. the complexity is moved from getting the length, to the extra storage read / write every time an element is added or removed.

our approach uses both techniques. at a high level, our algorithm has:

1. constant gas voting as the number of votes cast increases.
2. higher gas costs for casting a vote than tallying the result of votes.

in essence, we move complexity into the act of voting, out of the act of tallying. we ensure that the highest cost operation is the act of casting a vote, and that if one vote can be cast, all votes can be cast.

deriving an implementation

we change our ranked choice voting system from instant run off, to the Condorcet Method. which works as follows:

1. voters submit a list of candidates sorted by their preference.
2. if there is a candidate who is perfered over every other candidate by the majority of voters, that candidate wins.
3. otherwise, there is no winner.

it is possible for this algorithm to produce no winner, yet these cases, practically speaking, appear to be rare (see the section titled "A Condorcet winner always exists" here).

let $C$ be the set of candidates and $V$ be the set of voters and their vote weights such that $\forall v \in V$ $v[c]$ is the weight given to candidate $c$ by voter $v$. we can then say that $c_i$ is a Condorcet winner if:

$$\forall c \in C, c \neq c_i \implies 2 * \vert\vert \{ v \mid v \in V, v[c_i] > v[c] \}\vert\vert > \vert\vert V \vert\vert$$

from here, we set our sights on pre-computing this value whenever a vote is cast. to do so, we define a new matrix $M$:

$$M[i][j] := \vert\vert \{ (a, b) \mid a \in V,b \in V, a \neq b, a[i] > a[j] \} \vert\vert - \vert\vert \{ (a, b) \mid a \in V,b \in V, a \neq b, a[j] > a[i] \} \vert\vert$$

the math notation here is unplesant, so in psudocode:

M[i][j] = number_of_times_i_has_beaten_j - number_of_times_j_has_beaten_i

given such a matrix, a candidate $c_i$ is a winner if:

$$\forall p \in M[c_i], p \gt 0$$

in english: a candidate wins if the number of times they were perfered over every other candidate by the majority of voters.

implementing this in Rust is quite straightforward.

pub struct Condorcet {
    m: Vec<Vec<i32>>,
}

impl Condorcet {
    pub fn new(candidates: usize) -> Self {
        Self {
            m: vec![vec![0; candidates]; candidates],
        }
    }

    pub fn vote(&mut self, preferences: Vec<usize>) {
        for (index, preference) in preferences.iter().enumerate() {
            // increment every value in self.m[preference] which
            // appears in preferences[index + 1..] as preference is
            // ranked higher.
            for victory in (index + 1)..preferences.len() {
                self.m[*preference][preferences[victory]] += 1
            }
            // decrement every value in self.m[preference] which
            // appears in preferences[0..index] as perference is
            // ranked lower.
            for defeat in 0..index {
                self.m[*preference][preferences[defeat]] -= 1
            }
        }
    }

    pub fn winner(&self) -> Option<usize> {
        // a winner is someone who wins a majority runoff with all of
        // the other candidates.
        self.m
            .iter()
            .enumerate()
            .find(|(index, row)| row.iter().skip_nth(*index).all(|&p| p > 0))
            .map(|(index, _)| index)
    }
}

the complete crate is here.

future work

additional analysis is still needed to determine if there is a strategy an attacker could use while voting that would produce elections with no winner. if such a strategy does exist, what percentage of voting power must collude to DOS a proposal?

@larry0x It'd be helpful if you can compare the time and storage complexity of 1) voting, 2) tallying of the "common method" and your method

thanks for the feedback. i considered this for a while and it's pretty hard to prove an upper bound on the runtime efficiency of instant-run-off. i tried one version where i wrote out an example and analyzed it, but that felt a little too much of a detour from the main point to go into the writeup, and because of the earlier point i wasn't sure if it was useful.

in the "polished version" of this i ended up just saying:

We weren't able to find a way to do instant run off tallying in constant time over the number of ballots, though that doesn't make it impossible or mean it hasn't been done.