What is the difference between Byzantine Fault Tolerant Protocols and Byzantine Agreement protocol (i.e., BA*)?
Is it just a naming convention or both concept differs fundamentally?
Nathan Aw
1 Answer
There are many problems in the family of "Byzantine" questions with slightly different names and all related to each other in various ways. Generally, the problem concerns a network of nodes all connected with all, some of which are honest and some of which are adversarial, i.e., can behave arbitrarily, even maliciously and send different data to different peers or refuse to send data altogether. Each of these nodes have some "input", potentially different for each, and they want to agree on a common view. The "input" can be the set of new transactions to confirm in the case of bitcoin, for example.
The canonical problems in the space, which are equivalent (if you can solve one, you can solve the other), are formulated as follows:
The Byzantine Agreement Problem. A group of nodes needs to agree on some value. The protocol needs to (a) terminate within finite time, (b) have all honest nodes reach the same result, and (c) the result reached must match the input of one of the nodes.
The Byzantine Generals Problem. A group of nodes has a designated "leader" called a "general". The leader has an input value and the rest of the nodes need to agree on a value. The protocol needs to (a) terminate within finite time, (b) have all honest nodes reach the same result, and (c) if the leader is honest, then the value agreed by everyone should be the leader's value.
These problems were put forth by Lamport in his seminal paper.
These problems can be modified to allow for less connectivity or to allow for failures that are not byzantine (i.e., do not allow for malicious intelligence, just failure that isn't trying to subvert the system actively). You can also add digital signatures to the mix to make the problems easier.
In bitcoin's case, the problem solved is a harder variant; anonymous Byzantine agreement. In this case, the number of parties can change arbitrary and the parties do not know who is sending each message. The solution to this is to use Proof-of-Work.
To answer your original question about Byzantine Agreement versus Byzantine Fault Tolerance. Broadly, these titles refer to the same problem of agreement. However, more specifically, BA is used to refer to the specific problem of reaching consensus about a decision under byzantine settings; while BFT refers to designing any generic protocol (not necessarily requiring agreement), for example the Byzantine Generals protocol, for solving a problem under byzantine faults, i.e., faults that are malicious. The generic problem of BFT and the problem of BA are equivalent - if you have agreement, you can be fault-tolerant; and if you are fault-tolerant you can reach agreement.
