{{ message }}

Instantly share code, notes, and snippets.

# gakonst/prob.py

Last active Jul 30, 2021
Probability of a malicious validator controlling majority of a 6125-size committee
 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))

### Shymaa-Arafat commented Jul 21, 2021 • edited

 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)¹²[ 5³121110987/(6543*2) 35² 12111098/(546) 3²5121110*9/24 3³121110/6] =3⁶5³/8¹² 1110[ 5² 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)729125110/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)