Minimum Committee Size Explained

  • 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.
>>> list(range(int(4*2/3), 4+1 )) # incorrect
[2, 3, 4]
>>> list(range(ceil(4*2/3), 4+1 )) # correct
[3, 4]
Note that the y-axis is in log scale
  • 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

Thanks again for Gusti Albrecht’s contribution to this summary.

References

Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store