Remove a random subset of validators in net_dynamic_hb

[vkomenda]

Instead of a single validator (a.k.a. pivot node), the test net_dynamic_hb should pick a subset of validators at random for removal. This will better reflect the interface to DynamicHoneyBadger that instead of changing one node in fact changes all nodes by substituting one set of validators for another.

[RicoGit]

Hello! I'm going to fix it and I have a few questions.

1. "should pick a subset of validators at random" - should this subset has N-1 number of validators? In other words, should get removed exactly one validator during the test? And which one validator will be removed should decide a random case. Right?
2. Even if we remove only one validator during the test, this situation may violate N=3f+1 invariant. For example when NetworkDimension(4, 1), NetworkDimension(7, 2) and so on. After removing 1 correct validator cluster should become invalid. Is this a problem for this concrete test?

[vkomenda]

@RicoGit, thanks for taking this issue!

You are right about breaking the correctness invariant. I think that if we remove a subset of validators from a correct network and it becomes incorrect as a result then we can skip checking subsequent assertions because they may not hold with more than a third of validators being malicious.

However, for this test I would suggest always making sure that the network remains correct after removal of a subset of nodes. That is, if there is no such subset that you can remove without making the network incorrect, there is no reason to try readdition because the resulting incorrect network may in general not readd the nodes in that subset.

[RicoGit]

Let me clarify. The test has to remove more than 1 validators, but cluster should remain correct.

For example is we have total N nodes and f malicious node, the test should remove less than N-(3f+1). But in the case of N=4 f=1, the test should remove 0 nodes - in that case, the test will check nothing.
Perhaps, we should improve NetworkDimensionStrategy that allow us to change N/f ratio? We should escape situations like N=4 f=1, N=7, f=2 and so on for the current test.

[vkomenda]

These are all good points. On one hand, we want to remove nodes only if the removal results in a network that preserves the correctness invariant, or the assertions might fail due to the network having become incorrect. On the other hand, we still need to test cases with maximal assumptions on the number of correct and faulty nodes, such as num_nodes = 4, num_faulty = 1. Including the selection of the subset of nodes to be removed in NetworkDimensionStrategy is a good idea, I think. This subset can include faulty nodes as well as correct ones. If the only way to guarantee that more than a third of all nodes are correct after removal is to remove faulty nodes instead or in addition to correct ones, that should be done. Taking the example with num_nodes = 4, num_faulty = 1, the subset of nodes to be atomically removed and readded must include the faulty node.

[afck]

I think we should actually test the most general case and replace one set of validators with a completely different set of validators which may or may not even overlap with the first one.

Of course both sets need to satisfy the condition that less than a third of them are malicious. But note that correctness of the algorithm never depends on the intersection of the sets or anything. During the transition period, the old set is still fully performing the consensus algorithm, while the new set is running the distributed key generation (DKG). After DKG has been completed, the new set takes over the consensus algorithm.

[vkomenda]

I think we should actually test the most general case and replace one set of validators with a completely different set of validators which may or may not even overlap with the first one.

How about making that a new test rather than modifying drop_and_readd? I agree that changing the validator set would be a good test case. This issue is only about what we want to do with drop_and_readd.

[RicoGit]

I agree, let's drop_and_readd removes some nodes from the existing network. Another test case replace_all_validators. will replace the network with a new one. (new set of validator will not overlap with the first one). What do you think?

[vkomenda]

Makes sense. 👍