# Shuffling node memberships of subnets: an exploratory conversation

Of course! Let me start with a quick recap: So replicas in our consensus protocol create notarization shares to indicate valid blocks. They might create notarization shares for different blocks at one height. When they see a full notarization (which consists of 2f+1 notarization shares), they move on to the next round. If there exists only 1 notarization in a round, that means we have agreement (because chains must consist of fully notarized blocks at every height). To help identify this, notaries also create a finalization share on a block b at the end of the round if they did not create a notarization share on any block at that height other b. If a block b collects 2f+1 finalization shares, we consider it finalized, and replicas trust that this is the agreed-upon blockchain.

This is safe on a subnet of size n = 3f+1 when at most f nodes are corrupt, meaning that a finalization on block b means that no other notarized block b’ at that height can exist. That is because if we have 2f+1 finalization shares, that means those nodes say they did not notary-sign any other block at that height. f of those may be corrupt, so they might have lied, but it means at least f+1 nodes are honest and really did not create notarization shares for other blocks at that height. Since we only have 3f+1 replicas, and we know that f+1 did not create notarization shares for any other block b’ at that height, it only leaves 2f nodes that could have possibly created notarization shares on b’, but this is less than the threshold 2f+1, concluding the proof.

Now the attack: suppose the attacker controls more than f (say f+1) corrupt replicas, and additionally has full control over the network. For simplicity, let’s look at a 4 node subnet consisting of nodes A, B, C, and D, and the adversary controls 2 nodes (which is f+1, more than 1/3rd). The notarization/finalization threshold is 3 for a 4 node subnet. Let’s say A and B are the corrupt nodes. The attacker can make sure there are two valid blocks at height h, b1 and b2. It makes sure that replica C only receives block b1, and replica D only receives block b2 (using the fact that it fully controls the network). C will create a notarization share for b1, and D for b2. Using its control over replicas A and B, the attacker can complete both notarizations for b1 and b2, and show the full notarization on b1 to C and the full notarization on b2 to D. C will now create a finalization share on b1 (since it only created a notarization share on that block), and similarly D will create a finalization share on b2. Now again using A and B, the attacker can complete two finalizations on b1 and b2. This completes the attack: C thinks that block b1 is final, while D thinks b2 is final, and they are conflicting blocks.

So this shows that an attacker having more controlling more than f out of 3f+1 nodes is problematic. You cannot just sign arbitrary blocks, but we cannot guarantee agreement anymore.

As demonstrated by the attack above, if f+1 nodes are actively malicious and the adversary can control the network, then we immediately have a problem. If f+1 nodes are faulty in the sense that they are offline but not actively malicious, then the subnet would be stuck, but the NNS can replace nodes in the subnet.

8 Likes