  The property of proportional representation in approval-based committee
elections has appeared in the social choice literature for over a century, and
is typically understood as avoiding the underrepresentation of minorities.
However, we argue that the security of some distributed systems is directly
linked to the opposite goal of avoiding the overrepresentation of any minority,
a goal not previously formalized that leads us to an optimization objective
known as maximin support. After providing a thorough analysis of the
computational complexity of this objective, we propose a new efficient election
rule that simultaneously achieves a) a constant-factor approximation guarantee
for it, and b) the property of proportional justified representation (PJR) -
one of the strongest forms of proportional representation. 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 guarantees, even when the
algorithm is executed by an untrusted party who only communicates the output.
As a result, the rule can be adapted into a verifiable computing scheme.
Moreover, its verification procedure easily admits parallel processing for
further efficiency.
  Our work is motivated by an application on blockchain networks 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 enables a validator selection protocol with formal
guarantees on security and proportionality, and its adaptation as a verifiable
computing scheme with a parallelized verification proves to be key for its
successful implementation given the computationally limited nature of the
blockchain architecture.
