My formulas need effectively some more explanations. Let me try to do so:
C(Nodes, Size) is the number of ways to choose Size elements from a set of Nodes elements. As there are Size nodes in a group and Nodes nodes in the network, this is the total number of all combinations of nodes to constitute a group. So this is total number of all possible groups. Let’s call it Groups.
This was the easy part. The hard part is to compute the total number of all possible bad groups. We’ll take a 28/32 consensus as an example.
Let’s begin with a group of 28 bad nodes. There are C(BadNodes,28) ways to choose 28 bad nodes from a set of BadNodes nodes. For each of these partial groups there are C(Nodes-BadNodes,4) ways to choose the remaining (honest) nodes in the group. Thus there are C(BadNodes,28)*C(Nodes-BadNodes,4) possible groups with exactly 28 bad nodes.
Similarly there are C(BadNodes,29)*C(Nodes-BadNodes,3) possible groups with exactly 29 bad nodes … and C(BadNodes,32)*C(Nodes-BadNodes,0) (= C(BadNodes,32)) possible groups with exactly 32 bad nodes.
When we sum all of them we get all the possible groups with 28, 29 … and 32 bad nodes. That is the total numbers of groups having a quorum of bad nodes. Let’s call it BadGroups. Formally It is equal to ∑C(BadNodes,27+p)*C(Nodes-BadNodes,5-p)
where p = 1 … 5 (because 27+p = 28 … 32 and 5-p = 4 … 0).
- 5 is equal to Size-Quorum+1 (in my previous post I called it MinGoodSize but now I think that BlockingMinority is a better name)
- 27 is equal to Quorum – 1
Which leads to the general formula:
*BadGroups=∑C(BadNodes,Quorum-1+p)C(Nodes-BadNodes,BlockingMinority-p) where BlockingMinority=Size-Quorum+1 and p = 1 … BlockingMinority
The ratio BadGroups/Groups is the probability of a group to be a bad one. This is then the portion of the network that the attacker controls.
One last thing: The number of groups in the network is roughly Nodes/Size. If we multiply it by the ratio of bad groups we get the number of bad groups. So the attacker will gain control of his first group when BadGroups/Groups*Nodes/Size >=1
This is a purely static analysis where the bad nodes doesn’t try to disrupt the network (as I said earlier) and that doesn’t take into account dynamic reactions of the network. But I think it gives a rough idea of the order of magnitude of the number of nodes needed to control the network.