Consensus 28/32 or 8/8?

Development
24

I think I have been able to find some formulas to compute the bad nodes percentage needed to control the network.

I started from these:
Total groups = C(Nodes, Size)
Bad groups = ∑ C(BadNodes, p+Quorum-1) * C(Nodes-BadNodes, MinGoodSize-p)
where:

  • C is the binomial coefficient
  • Nodes = Total number of nodes
  • BadNodes = Number of nodes controlled by the attacker
  • Quorum/Size is the consensus
  • MinGoodSize = Size-Quorum+1
  • p = index from 1 to MinGoodSize

For example with a 28/32 consensus:
MinGoodSize = 5
Index = p = {1;2;3;4;5}
Attacker’s nodes = p+Quorum-1 = {28;29;30;31;32} choosen from BadNodes nodes
Honest nodes = MinGoodSize-p = {4;3;2;1;0} choosen from (Nodes - BadNodes) nodes

I get the following result:

601×508 56.5 KB

It seems that to control the majority of groups, the attacker needs to controls 85% of the nodes which is compatible with your simulations. I am not sure of my formulas, but maybe this is an indication that they are not entirely wrong.

Here are the correponding data:

The bad group percentage in red indicates that the attacker controls at least one group. It appears that to take control of one single group the attacker needs to control 65% of nodes. The formula I used is:
BadGroups/Groups*Nodes/Size>=1, meaning the probability of a bad group multiplied by the number of groups (the network nodes partitionned in groups of Size nodes). I am not sure of that one too.

Some other results:

601×508 57.1 KB

(though the ratio is the same, 7/8 is really less secure than 28/32)

601×508 56.1 KB

(and a first bad group and 20% of nodes, it is clear that GROUP_SIZE and QUORUM constants in routing/src/types.rs will have to corrected before final delivery).

Here the link to the source Excel file so that anyone can test other scenarios. Input cells to modify are on a orange background.
Consensus simulation

8 Likes