A verifiably secure and proportional committee election rule
Authors: Alfonso Cevallos and Alistair Stewart
Abstract. The property of proportional representation in approval-based committee elections, which has appeared in the social choice literature for over a century, is typically understood as avoiding the underrepresentation of minorities. However, we argue that the security of some distributed systems depends on the opposite goal of preventing the overrepresentation of any minority, a goal not previously formalized which leads us to an optimization objective known as maximin support. We provide a thorough analysis of its approximability, and propose a new efficient election rule inspired in Phragmén's methods that achieves a) a constant-factor approximation guarantee for the objective, and b) the property of proportional justified representation (PJR). However, the most striking feature of the new rule is that one can verify in linear time that the winning committee satisfies the two aforementioned properties, even when the algorithm is executed by an untrusted party who only communicates the output. Finally, we present an efficient post-computation that, when paired with any approximation algorithm for maximin support, returns a new solution that a) preserves the approximation guarantee and b) can be efficiently verified to satisfy PJR.
Our work is motivated by an application on blockchains that implement Nominated Proof-of-Stake, where the community elects a committee of validators to participate in the consensus protocol, and where preventing overrepresentation protects the network against attacks by an adversarial minority. Our election rule gives rise to a validator election protocol with formal guarantees on security and proportionality, in which the ability to efficiently verify these guarantees on the winning committee proves to be key in adapting the protocol to the trustless and resource-limited nature of blockchains. We provide details of such an implementation in the Polkadot network, launched in 2020.