Skip to content

Instantly share code, notes, and snippets.

@gakonst
Last active September 8, 2022 23:57
Show Gist options
  • Save gakonst/f7756debc09a75ce6c54eb526be14e52 to your computer and use it in GitHub Desktop.
Save gakonst/f7756debc09a75ce6c54eb526be14e52 to your computer and use it in GitHub Desktop.
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
Copy link

Shymaa-Arafat commented Jul 21, 2021

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)

@Donabbaskid
Copy link

Screenshot_2021-07-20-22-20-19-75

@Donabbaskid
Copy link

Don

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment