Minimum Committee Size Explained
Thanks to Vitalik Buterin and Yahsin Huang for the review and feedback
Trigger warning: High school math
In eth2.0 sharding, validators are randomly assigned into committees to produce crosslinks. Each committee must have at least a minimum number of members called “minimum committee size”. In the Eth2.0 Specification, a side note says the recommended number is 111 validators. A constant `TARGET_COMMITTEE_SIZE` of 128 is chosen as an approximate number of 111 because every constant in the specification is defined as a power of 2. Power of 2 is easier to memorize and calculate using only the human brain.
This article walks you through the reasoning of how this 111 magic number affects the security of the whole system.
Here’s how the safety of a committee is defined. Suppose the protocol barely has the honest majority of total validators, i.e., 2/3 of honest validators 😇 and 1/3 of malicious validators 😈, we want each of the committees still has an honest majority when the protocol randomly shuffled those validators into the committees.
To give a concrete example, suppose we have 300K of total validators, with 100K of them are attackers. The protocol has 1024(1K) committees, each is assigned with 300 validators. If a committee unfortunately has 200 attackers, then this committee is not safe.
The situation is analogous to drawing balls from a bin. Say, there is a huge bin that contains millions of balls, you happen to know 2/3 of the balls are yellow 😇 , and 1/3 of them are purple 😈. We want to draw 3 balls and requires no more than 1 ball is purple.
We can whip out some formula to analyze the probability of the event of “2 or 3 purple balls drawn.”
- For the “3 purple” case, the probability is (1/3) * (1/3) * (1/3) =0.037
- For the “2 purple and 1 yellow” case, don’t forget the 3 possible combinations (😈😈😇, 😈😇😈, 😇😈😈). (1/3) * (1/3) * (2/3) * choose(3, 1) = 0.222.
Wrapping up the above steps into some Python functions, we can derive a mapping from the number of balls drawn to the probability of undesired outcomes.
The `prob` gives the probability of getting 2 purples 😈from a 3 balls draw, while `probgte` gives the probability of getting 2 purples 😈 or more (i.e. 2 and 3). This is passing k=2 and n=3 as the function parameters.
As the below figure shows, the probability decreases as the number of balls drawn increases. The zigzags happen when the k is exactly 2/3 of n.
Note: At some data points, I incorrectly include the probability of not passing 2/3 into the calculation. For example, in the case of 4 balls drawn, the probability of 2 purple should not be added. I mistakenly use int instead of ceil to convert fractions into integers in Python.
>>> list(range(int(4*2/3), 4+1 )) # incorrect
[2, 3, 4]
>>> list(range(ceil(4*2/3), 4+1 )) # correct
[3, 4]Thanks to Gusti Albrecht for pointing out the error in the chart!
If you are not convinced, the trend is more significant when the number is large.
Translating the above fact to the committee problem, this means we can increase the committee size in order to reduce the probability of having 2/3 of attackers in it. By specifying a tiny probability that we are comfortable with, we can determine the desired minimal committee size.
Suppose the probability is 2**-40, a committee needs at least 111 members.
Some other factors might affect this committee size.
- If the attacker manipulates a random number generator, it is better to choose an even smaller probability and thus a larger committee size. 40 bits of manipulation means the attacker can sample 2**40 times, so in this case, we parameterize the probability to 2**-80 to target a 2**-40 safety failure rate. The committee size is 231 now.
- To be conservative, one can target 2/5 of malicious validators not taking over 3/5 in a committee. The committee size to keep that probability under 2**-40 is now 315.
Summary for math savvy readers
References
- Eth2.0 Specification
- Slides of Vitalik’s talk in Ithaca, July 2018 page 9–11
- Serenity Design Rationale Crosslink-committees section
- See how shuffling works in Proto’s diagram
