Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove a random subset of validators in net_dynamic_hb #374

Open
vkomenda opened this issue Jan 3, 2019 · 8 comments
Open

Remove a random subset of validators in net_dynamic_hb #374

vkomenda opened this issue Jan 3, 2019 · 8 comments
Labels
good first issue Good for newcomers

Comments

@vkomenda
Copy link
Contributor

vkomenda commented Jan 3, 2019

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
Copy link
Contributor

RicoGit commented Feb 25, 2019

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
Copy link
Contributor Author

@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
Copy link
Contributor

RicoGit commented Feb 25, 2019

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
Copy link
Contributor Author

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
Copy link
Collaborator

afck commented Feb 25, 2019

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
Copy link
Contributor Author

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
Copy link
Contributor

RicoGit commented Feb 25, 2019

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
Copy link
Contributor Author

Makes sense. 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
good first issue Good for newcomers
Projects
None yet
Development

No branches or pull requests

3 participants