Instantly share code, notes, and snippets.

# gakonst/prob.py

Last active September 8, 2022 23:57
Show Gist options
• Save gakonst/f7756debc09a75ce6c54eb526be14e52 to your computer and use it in GitHub Desktop.
Probability of a malicious validator controlling majority of a 6125-size committee
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import math def choose(n, k): return math.factorial(n) // math.factorial(k) // math.factorial(n-k) def prob(n, k, p): return math.exp(math.log(p) * k + math.log(1-p) * (n-k) + math.log(choose(n, k))) def probge(n, k, p): return sum([prob(n, i, p) for i in range(k, n+1)]) committee = 6125 half = committee / 2 for p in [0.45, 0.46, 0.47, 0.48, 0.49, 0.5, 0.51]: print(probge(committee, half, p))

I believe the binomial distribution is not the right one to describe this probabilities, more details in here
https://ethresear.ch/t/is-this-really-a-binomial-distribution-i-believe-the-formula-is-not-accurate/10134

I should also add a recalculation of ur simple example 9 malicious out of 24 with 2 committees:
-Total # of ways malicious can fall in groups is 2⁹=512
( each is indep, and have 2 options)
-The case 4,5 u r describing (no malicious majority threat) can be reached by:
1-choosing 4 out of 9
9876/4! = 9876/24 = 376=126
2-The 4&5 can be arranged in 2 ways (which in group1 & which in group2)
»»»total # of ways for(4,5) = 126*2=252
This is less than half (512/2=256), exactly 0.49
.
-u can re-check the answer by calculating the remaining probabilities for
(9,0),(8,1),(7,2),(6,3) where a malicious majority does exist in one of the 2 groups
They're in the same order
2+18+72+168=260 ≥ 0.5
»»»
Only u may say it's still safe because one of the 2 groups is chosen at random, ie divide by more 2 ~0.253 but it's still a considerable probability
.
I checked here if u r running a Simulation/random number generator code to calculate the probability, but the code is only substituting the formula
....
Ps.
Substituting in ur formula gets the following probability
P=3/8, 1-P=5/8, N=12, K =6,7,8,9 (max possible malicious)

Prob =
(3/8)⁶(5/8)⁶C(12,6)
+(3/8)⁷(5/8)⁵
C(12,7)
+(3/8)⁸(5/8)⁴C(12,8)
+(3/8)⁹(5/8)³
C(12,9)
=3⁶ * 5³ (1/8)¹²[
121110987/(6543*2)

• 3 12111098/(546)
• 5121110*9/24
• 121110/6]
=3⁶
5³/8¹² 1110[
327 + 3594 + 3²59/2 +3³2]
=3⁶
5³/8¹² 110
[2567+ 2720 + 815/2 + 54]
=3⁶5³/8¹² 110
[1050+540+405/2+54]
=(3693/2)729125
110/2³⁶
=3693729125*55/2³⁶
=0.269339
Or could be viewed as
(3/8)⁶(5/8)³ (369355/512)
=(3/8)⁶(5/8)³ * 396.70898
.
Anyways, that's not the same probability calculated the other way round
If they're relatively close, it is because M=2,
I understand true M=32
(but not ♾️ either)

Don