WHAT IS BYZANTINE FAULT TOLERANCE (BFT)?

• What happens when nodes decide to not follow the rules and to tamper with the state of his ledger?
• What happens when denial nodes are a large part of the network, but not the majority?

Byzantine General’s Problem

To understand Byzantine General’s problem (Leslie Lamport, Robert Shostak and Marshall Pease 1982) here is a scenario. Imagine there is a Byzantine army divided into sections and each section is commanded by their own generals. Each general has only two options, whether to conquer or retreat from attacking the enemy’s army. Every general may have different choices in this circumstance, a coordinated attack or retreat decision by every general will be better for the entire army than a half-hearted attack/retreat by a few generals. The sensitivity in this scenario is once a decision is taken by a general, the decision can’t be changed and a synchronized attack by the majority of the generals will be required to defeat the opponent army.

The original research paper published by the 3 authors mentioned above defines the condition as follows:

To synchronize the attack, the generals need to communicate with messages about their state of decisions. The primary challenge in the Byzantine Generals’ Problem is that the messages can get somehow delayed, destroyed, or lost. Adding to this, even if a message is successfully delivered, one or more generals may choose (for whatever reason) to act maliciously and send a fraudulent message to confuse the other generals, leading to a total failure. These malicious or traitor generals (lesser in number than loyal generals) may attempt to prevent the loyal generals from reaching an agreement. This will result in a definite defeat of the army because of the false communications done by the traitor generals. To avoid this condition, there has to be an algorithm that makes sure that all loyal generals reach a common decision so that the small number of traitors will be unsuccessful in preventing the agreement. Consider there are 9 generals out of which 4 agree to retreat and 4 agree to conquer (the worst case), and the decision depends upon the decision of the 9th general. The message is transferred with the help of a messenger.

1st case is where the 9th general (the commanding general) can be the traitor. He will tell send attack messages to attacking generals and `retreat message to retreating generals which will cause only half of the army to attack. The other case can be that the messenger is a traitor and he may forge false waits to influence the decisions of the agreement. 

Byzantine Fault Tolerance

To solve this, we need an algorithm that needs to make sure that out of 3m total generals, at most m can be traitors. To simplify the purpose of this algorithm, it means the algorithm can reach consensus as long as 2/3 of the generals are honest. If the traitors are more than 1/3, the consensus is not reached, the armies do not coordinate their attack and the enemy wins. Let ‘v’ be the value sent by the commander to the general.

Steps:

• Commander sends v to all Lieutenants
• L1 sends v to L2 | L3 sends x to L2
• L2 ← majority(v,v,x) == v
  The final decision is the majority vote from L1, L2, L3 and as a result consensus has been achieved

Let’s examine the case of the commander being a traitor:

Steps:

• Commander sends x, y, z to L1, L2, L3 respectively
• L1 sends x to L2, L3 | L2 sends y to L1, L3 | L3 sends z to L1, L2
• L1 ← majority(x,y,z) | L2 ← majority(x,y,z) | L3 ← majority(x,y,z)

They all have the same value and thus consensus is reached. We need to check here that even if x, y, z are all different values, the value of majority(x, y, z) is the same for all 3 Lieutenants.

Hence, any system or algorithm which solves or prevents Byzantine General’s problem is a part of Byzantine Fault Tolerance. Consider the system where the nodes/computer systems are the generals and the messengers are our digital communication systems. Imagine a system where the general (computer system) encrypts the message using asymmetrical cryptography or digitally signs the decision (making it unforgeable) and the decision is transmitted to all the generals simultaneously.  This way, the general can’t send different messages, the generals receiving can verify the message by seeing what other generals have received preventing both general and the messenger to act like a traitor. This characteristic of a system that prevents the Byzantine General’s problem is called Byzantine Fault Tolerance. The method of asymmetrical cryptography, digital signatures, broadcasting the data to all the nodes, and agreeing to the state which the majority agrees defines what BFTs in a blockchain.

Consider the generals as different nodes of a blockchain. All the participants of the cryptocurrency network need to agree or give consensus regularly about the current state of the blockchain. Blockchains use different consensus mechanisms to bring the nodes to the agreement. If more than half of the nodes act maliciously, then the system has to face the 51% attack. Even in the case of Bitcoin’s consensus mechanism, i.e. Proof of Work, if 51% of the users act fraudulently, they will succeed in executing a fraudulent transaction on the Bitcoin’s blockchain.

You can read the original research paper here: