Description

▪ Follow the instructions very carefully. Answers that do not conform to the instructions will not be given credit.
▪ Understand thoroughly all the code given to you in this lab. Search for documentation online if there is a primitive or API you have not encountered before.
In this project, you will implement the basic, unauthenticated Byzantine fault tolerant consensus algorithm described by Lamport, Shostak, and Pease in their seminal paper titled The Byzantine General’s Problem [1].
The project code provides you with a simple consensus protocol testing framework that you will use to test the correctness of your implementation. Read and thoroughly understand all the project code before beginning.
The Java class named hw4.BasicTests gives several tests that demonstrate how to use the consensus testing framework. Your submission should make all the tests pass. For example, test0 test case is reproduced below and configures a small network running the FollowLeader consensus protocol described in class that fails to solve the BFT consensus problem for any number of malicious nodes.

The test case creates a Network object which represents a network of four FollowLeader nodes whose communication links form a complete graph. The first node is marked as the leader. The set of possible values over which consensus will be conducted is specified as the constant VALUE_SET, and the default value is specified as the constant VALUE_0. The initial value of the leader is set as VALUE_1. The SynchronousExecutor class runs the network for a series of five rounds. Each round gives each node the opportunity to send messages to its adjacent nodes and then to receive messages sent to them for processing. Then the test case checks whether agreement and validity are satisfied.
The project code provides a full implementation of the FollowLeader consensus protocol to help you understand how the testing framework works. The FollowLeader consensus protocol is in the hw4.consensus.follow package and consists of three files: FollowLeaderNode, FollowLeaderPayload, and FollowLeaderMaliciousNode. The
FollowLeaderNode class is a compliant implementation of the FollowLeader protocol. The FollowLeaderPayload class represent the structure of the messages that are passed between nodes in the protocol. The
FollowLeaderMaliciousNode class simulates an attacker that attempts to subvert the FollowLeader protocol.
The project code also gives incomplete implementations of the MajorityVoting and UnauthBFT consensus protocols. Your task is to complete them by making all the tests in hw4.BasicTests pass. You will very likely need to write your own tests to validate your work. The tests provided in the project are only given to you to clarify how the code should be written.

Part 1: Attacking the Majority Voting Protocol

Part 2: Unauthenticated Byzantine Fault Tolerance

Frequently Asked Questions
1: For the malicious nodes in majority voting, is there an expected strategy we should use?
A strategy was briefly outlined during class, however you are free to devise your own strategy, as long as it breaks consensus consistently.
2. Can we use randomness, or do we need to think of a strategy for the malicious nodes so that they can try their best to break the consensus.
3. My understanding is that the malicious node/leader can send anything regardless of what’s actually initialized/sent to it. Is this correct?
Correct.
4. Is it guaranteed that the leader is malicious? Because if the leader is not malicious, there is no guarantee that the consensus can be break based on the number of malicious nodes.
5. What will be the grading criteria for HW4? Except the 3 sample tests for regular majority voting, I see only 4 tests there and they are only checking two conditions (agreement and validity).
Part 1 will be graded based on whether the malicious node is able to break consensus when the leader is malicious and has access to at least two Sybil nodes. Consensus is broken when either agreement or validity is not reached.
Part 2 will be graded based on whether the compliant node is able to reach consensus consistently when at most a third of the nodes are malicious. Reaching consensus means that both agreement and validity are satisfied.

6. The project code has a lot of inline console outputs in the code. Will processing factor into grading?
Processing won’t factor into the grading. Grading will be based on solely on whether the end result is breaking (Part 1) or reaching (Part 2) consensus properly.

References