Better Security via Intentional Over-representation and Under-representation

1. Committee Selection in Distributed Systems

In distributed systems, it’s often needed to select a committee — a small set of nodes that can represent the entire system. This small set of nodes can help to make decisions efficiently, on behalf of a much larger network. The scheme used for committee selection underpins many critical distributed system applications, such as distributed system governance, blockchain consensus protocols, etc.

2. Proportionality: A Key Principle for Committee Selection

Take Proof-of-Stake (PoS) blockchain as an example, where each node may hold different stake. Here stake refers to the amount of cryptocurrency a node holds. Security of the blockchain is achieved by first selecting a committee, and then letting the committee run a consensus protocol. For each empty seat in the committee, when we select a node for that seat, a node holding s stake is usually selected with probability s/T, where T is the total stake in the system. In this way, the selection process ensures perfect representation: A node with 2s stake will have twice the probability of being selected, compared to a node with s stake. There is neither over-representation nor under-representation.

All existing committee selection schemes follow the above principle, which we call proportionality. This principle is important, not just because it makes intuitive sense. It has a deeper mathematical foundation: Typically in PoS blockchains, it is assumed that an attacker can control any set of nodes as long as their total stake is bounded (since it is trivial for the attacker to create many malicious nodes, each with rather small amount of stake). With proportionality, regardless of which nodes the attacker controls, the "impact" of the attacker is proportionally limited.

On the other hand, if a node with 2s stake has 10 times the probability of being selected, compared to a node with s stake, then the 2s stake of that node is over-represented. In such a case, the attacker can target such a node, to get a disproportionally large influence (i.e., 10) while paying a cost of only 2s. Putting it another way, over-representation will always introduce a vulnerability for the attacker to exploit.

3. Surprise: Over-representation Actually Improves Security

As a highly surprising discovery, we find that deviating from the proportionality principle actually improves security! Specifically, we discover that over-representation and under-representation, surprisingly, help to improve the security of the blockchain. We call these committee selection schemes, which allow over-representation and under-representation, as non-proportional schemes. The following figure shows a committee selection scheme that follows proportionality, and one that does not.

Here in the proportional scheme, when choosing a committee member, a node with stake 0.3 is chosen with probability exactly 0.3. In the non-proportional scheme, in contrast, this probability is 0.33.

Results under various real-world stake distributions (including Ethereum, Solana, Cardano, Dogecoin, Bitcoin, and Bitcoin-Cash) show that non-proportional committee selection schemes reduces the failure probability of the committee by many orders of magnitude.

4. Deeper Mathematical Insights

A careful reader might remember that previously, we said that over-representation would always introduce a vulnerability for the attacker to exploit. On the surface, this contradicts with our discovery, which says that over-representation helps to improve security.

It turns out that there is no contradiction, if one looks at this carefully: Non-proportional schemes indeed increase the expected number of malicious committee members. But they also impact other statistical behavior of the number of malicious committee members. One such statistical behavior is variance: With smaller variance, even though the expectation becomes larger, it can still be harder for the malicious nodes to dominate the committee. Such phenomenon is bad for the adversary, and hence beneficial to security.

This work has been submitted for publication, stay tuned for the paper.