2

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

1
  • If you translate this into a function, people at the Mathematics stack Exchange could help you. – Undead8 Apr 17 at 1:51
2

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.

enter image description here

2
  • 1
    Thank you for this quick reply! If I see it correctly, this formula uses the binomial distribution. But the binomial distribution is for experiments with replacement. When selecting the nodes from a pool, nodes should only used once. That is an experiment without replacement. Maybe I understood something wrong here: I would be glad, if you could expand on that, please. – Mario HSMW Apr 20 at 5:01
  • @MarioHSMW Yes, you're right the committee size problem should be the "with replacement" one. The formula is an approximation so that we can get the insight fast. I've seen people doing a more rigorous one. – user2754799 Apr 21 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.