search

initc3 / HoneyBadgerBFT-Python

The Honey Badger of BFT Protocols
Other
134 stars 65 forks source link

Subprotocol tests #34

Open sbellem opened 6 years ago

sbellem commented 6 years ago

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 commented 6 years ago

From @amiller on May 30, 2017 3:41

Partially addressed by refactoring and tests:

sbellem commented 6 years ago

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

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.