Deciding on a single state of the network is very important for a distributed network to function. However, what happens when one of the actors decide to break the rules of the network?
A secure consensus protocol needs to be fault tolerant. To understand this very point, we will discuss some very important concepts starting with Two Generals Problem.
Two Generals Problem
First published in 1975, this problem describes a scenario in which two generals are attacking a common enemy. One is the leader general and the other is the follower general. To win this battle, both the generals will have to attack the enemy camp at the same time.
However the camps of both these generals are on either side of the enemy army. So when the first general (in order of rank) has to send a message across to the second general, the messenger has to cross the enemy camp to deliver the message. This creates a risk of getting caught and the message remain being undelivered. So while the first general attacks, the second general would not as he does not have the message.
Now if the messenger does manage to cross the enemy camp and reach the second general, an acknowledgement is necessary from the second general to confirm that the message has been received and the plan looks good. This extends to repeated acknowledgements leading to a scenario where the generals are unable to reach a consensus or agreement.
This problem is unsolvable.
Byzantine Generals Problem
This is a twist to the above problem that we just discussed. This is a problem where commanding general and lieutenant generals are the main actors.
The commanding general must send an order to his n-1 lieutenant generals such that –
- All loyal lieutenants obey the same order
- If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.
In order to reach consensus, it requires majority of the decision a lieutenant observes. This means that as long as 2/3 of the actors are loyal, consensus is reached and the enemy can be defeated.
However, if more than 1/3 of the actors are traitors, then consensus will not be reached and the army will be defeated by the enemy.
In the above diagram, the Commander “C” sends “Attack” message to all the three lieutenants. However L3 acts as a traitor and passes on a wrong message to L2.
L2 employs fault tolerance by selecting the majority among three messages that he has received – Attack, Attack, Retreat.
In the above diagram, the Commander C acts as a traitor and sends three different messages to his three lieutenants. The lieutenants behave loyal and pass on the correct message to each other.
All the three lieutenants have the same set of messages – Attack, Retreat, Defend. Although these are totally different commands, consensus is reached as the consideration is the default option to Retreat.
Byzantine Fault Tolerance (BFT) and Application in Blockchain
Byzantine Fault Tolerance is the feature of a network that helps tolerate the failures arising out of the Byzantine Generals Problem.
These failures are very severe and difficult to deal with as they have no restriction on how a malicious node may behave.
For a blockchain that mostly holds value and data, this is very important. As malicious nodes can inflict serious economic damages to the network. If the network is not BFT, a malicious node can transmit incorrect and fake transactions causing a havoc in the system and rendering it valueless. More so when there is no centralized power to take over and repair the damage.
That is where blockchain consensus protocols come in.