Subprotocol tests

[sbellem]

From @amiller on May 26, 2017 4:46

Need tests for individual subprotocols, like reliable broadcast, binary agreement, etc.

Copied from original issue: amiller/HoneyBadgerBFT#10

[sbellem]

From @amiller on May 30, 2017 3:41

Partially addressed by refactoring and tests:

• Reliable Broadcast amiller/HoneyBadgerBFT@80f09d1
• Common Coin amiller/HoneyBadgerBFT@aa63120
• Binary Agreement amiller/HoneyBadgerBFT@9f7803b
• Asynchronous Common Subset amiller/HoneyBadgerBFT@5ac8a66

[sbellem]

The current code base (under the dev branch at the moment of this writing) has ~98% of code coverage. This means that the most of the code of the subprotocols does get executed when the tests are run.

So, what would make sense to tackle as part of this issue, is to verify/test whether the implementations are accurate.

We may perhaps consider the following:

Verify the lemmas & costs of the algorithms

• Design and implement tests that verify that the various lemmas supporting the algorithms are not violated.
• Also test that the implementation respects the expected costs.

As a concrete example, lemma 1 for the binary agreement [MMR14_]:

LEMMA 1. Let n > 3t. Consider the situation where, at the beginning of a round r, all the non-faulty processes have the same estimate value v. These processes will never change their estimates, thereafter.

So here the idea is that there would be a test that checks the above lemma.

As a an example of checking the cost, from Mostéfaoui et al._ again:

As far as the cost of the algorithm is concerned, we have the following, where c ≥ n − t denotes the number of correct processes.

If the correct processes propose the same value, each round requires two communication steps (one in the BV-broadcast and one broadcast), and the expected number of rounds to decide is two. Hence, the total number of messages sent by correct processes is 2cn.

So to help ensure that the implementation is correct, the above would be verified by one or more tests.