Likelihood of malicious nodes in a shard

Question

in his post https://vitalik.ca/general/2021/04/07/sharding.html, V. Buterin said: “Certainly, they can wait until they get lucky and get 51% in a single shard by random chance despite having less than 50% of the total stake, but this gets exponentially harder for attackers that have much less than 51%. If an attacker has less than ~30%, it's virtually impossible.“

Now I tried to calculate the exact likelihood of the event e that in at least one shard more than 50 % the shard’s nodes are malicious depending on:

• the total number of nodes N,
• the number of malicious nodes M,
• the number of shards S.

The nodes are assigned randomly to each shard and each shard contains the same number of nodes.

I discussed this with colleagues, but we couldn’t find a solution, and I hope to find an answer here. Our approach was to calculate the total number of all outcomes / number of e = likelihood. But we got stuck with number of e.

Thank you

Answer 1

The shard committee is designed to have a minimal number of required members so that the chance of getting a majority of malicious nodes in a shard is so small. I happened to write an article before, and Gusti Albrecht summarized it with a formula.

In the formula, we assume global 1/3 malicious nodes(N/M = 1/3 in your notation). We analyze the probability of a committee getting more than 2/3 of malicious nodes.

We can answer your question by reverse engineering this formula. Set n=111, change 1/3 and 2/3 to 1/2, and 2/3n to 56 to analyze the probability of malicious nodes getting 50% in a single shard when they have 50% total stake.