The Byzantine question was a classical problem in cryptography which dealt with how a digital currency can be prevented from being spent twice. In other words whether a cryptocurrency transaction is genuine or not.
Therefore it is also known as the Double Spending Problem.
The aim of the problem is to reach a consensus on whether a transaction is genuine or not. This is analogous to whether a message sent by a traitor (malicious node) is genuine or not.
The Byzantine Problem
The name Byzantine Fault Tolerance came from a story where a Byzantine General and his commanders must attack or retreat at the same time. Whatever they do, they must do with consensus. Otherwise, they will be killed.
Suppose there is 1 General (G) and 3 Commanders (C1, C2, C3).
If they decide to attack or retreat, how do they reach a consensus?
Scenario 1: General Asks Them to Attack, C1 is a Traitor
In this scenario, the general (G) orders all six commanders (C1 to C6) to attack. C1 is a traitor and will attempt to disrupt the consensus by sending “Retreat” messages, while all loyal commanders will faithfully follow the general’s order to attack.
Messages from the General:
- G > C1: Attack
- G > C2: Attack
- G > C3: Attack
- G > C4: Attack
- G > C5: Attack
- G > C6: Attack
Each commander (C2 to C6) receives the “Attack” order directly from the general. However, C1, being a traitor, will attempt to disrupt the process by sending conflicting “Retreat” messages to the other commanders.
Subsequent Messages:
- C1 (traitor) > C2: Retreat
- C1 (traitor) > C3: Retreat
- C1 (traitor) > C4: Retreat
- C1 (traitor) > C5: Retreat
- C1 (traitor) > C6: Retreat
- C2 (loyal) > C1: Attack
- C2 (loyal) > C3: Attack
- C2 (loyal) > C4: Attack
- C2 (loyal) > C5: Attack
- C2 (loyal) > C6: Attack
- C3 (loyal) > C1: Attack
- C3 (loyal) > C2: Attack
- C3 (loyal) > C4: Attack
- C3 (loyal) > C5: Attack
- C3 (loyal) > C6: Attack
- C4 (loyal) > C1: Attack
- C4 (loyal) > C2: Attack
- C4 (loyal) > C3: Attack
- C4 (loyal) > C5: Attack
- C4 (loyal) > C6: Attack
- C5 (loyal) > C1: Attack
- C5 (loyal) > C2: Attack
- C5 (loyal) > C3: Attack
- C5 (loyal) > C4: Attack
- C5 (loyal) > C6: Attack
- C6 (loyal) > C1: Attack
- C6 (loyal) > C2: Attack
- C6 (loyal) > C3: Attack
- C6 (loyal) > C4: Attack
- C6 (loyal) > C5: Attack
Results:
- C1 (traitor): Sends “Retreat” messages to all other commanders, but they will be outnumbered and identified as the traitor.
- C2, C3, C4, C5, C6 (loyal): Each loyal commander receives 5 messages: 1 “Retreat” from C1 and 4 “Attack” messages from the general and other loyal commanders.
Since the majority of messages received by C2, C3, C4, C5, and C6 are “Attack,” they will all agree to attack.
Conclusion:
The attack proceeds successfully, and the traitor C1 is exposed.
The loyal commanders (C2 to C6) will reach a consensus to attack, and they will know that C1 is the traitor due to the conflicting “Retreat” messages.
Scenario 2: General Asks Them to Attack, C1 and C2 are Traitors
In this scenario, both C1 and C2 are traitors, trying to disrupt the plan.
Messages from the General:
- G > C1: Attack
- G > C2: Attack
- G > C3: Attack
- G > C4: Attack
- G > C5: Attack
- G > C6: Attack
Subsequent Messages:
- C1 > C2, C3, C4, C5, C6: Retreat
- C2 > C1, C3, C4, C5, C6: Retreat
- C3 > C1, C2, C4, C5, C6: Attack
- C4 > C1, C2, C3, C5, C6: Attack
- C5 > C1, C2, C3, C4, C6: Attack
- C6 > C1, C2, C3, C4, C5: Attack
Results:
- C3, C4, C5, C6: These loyal commanders will receive 4 “Attack” messages from each other and 2 “Retreat” messages from C1 and C2. The majority is still “Attack,” so they will agree to attack.
- C1 and C2: As traitors, they will send and receive “Retreat” messages between themselves but will be outnumbered by the loyal commanders.
Conclusion:
- The majority (C3 to C6) will still agree to attack, and the traitors C1 and C2 will be exposed.
- The attack will proceed despite the two traitors.
Scenario 3: General Asks Them to Attack, C1, C2, and C3 are Traitors
In this scenario, three commanders (C1, C2, and C3) are traitors, creating a more difficult situation for consensus.
Messages from the General:
- G > C1: Attack
- G > C2: Attack
- G > C3: Attack
- G > C4: Attack
- G > C5: Attack
- G > C6: Attack
Subsequent Messages:
- C1 > C2, C3, C4, C5, C6: Retreat
- C2 > C1, C3, C4, C5, C6: Retreat
- C3 > C1, C2, C4, C5, C6: Retreat
- C4 > C1, C2, C3, C5, C6: Attack
- C5 > C1, C2, C3, C4, C6: Attack
- C6 > C1, C2, C3, C4, C5: Attack
Results:
- C4, C5, C6: Each loyal commander will receive 3 “Attack” messages from other loyal commanders and 3 “Retreat” messages from traitors. In this case, they cannot reach a majority agreement because half of the messages are conflicting.
- C1, C2, C3: The traitors will continue sending “Retreat” messages, causing confusion.
Conclusion:
- No Consensus: The loyal commanders (C4, C5, C6) cannot reach a majority decision due to the increased number of traitors. As a result, the group will fail to act decisively, leading to indecision or retreat.
- With 3 traitors (50%), the system can no longer reach a reliable consensus.
Comparison with Blockchain Nodes (Miners in Bitcoin and Validators in Ethereum, Cardano, Solana)
In a blockchain network, nodes function similarly to the general and commanders in the Byzantine Generals’ Problem. The nodes (like commanders) must agree on the validity of transactions (attack or retreat) to maintain the integrity of the system, even if some nodes are compromised (traitors).
Comparison:
- General as the Leader:
- In the original problem, the general sends an order to the commanders, and the commanders communicate among themselves.
- In blockchain, there is no single general. Instead, each node (like a commander) independently validates transactions or blocks and broadcasts them to others.
- Traitorous Nodes (Malicious Nodes):
- Just like the traitor commander (C1) sends conflicting messages (retreat), a malicious node may send false or manipulated data (invalid transactions or blocks).
- Other honest nodes need to identify these malicious nodes and reach a consensus, ensuring that the majority agrees on the correct information (valid transactions).
- Consensus Algorithms:
- In the general-commander analogy, the loyal commanders use majority voting to decide whether to attack or retreat, even with conflicting information.
- Similarly, in a blockchain, consensus algorithms like Proof of Work (PoW), Proof of Stake (PoS), and Practical Byzantine Fault Tolerance (PBFT) help honest nodes reach consensus, even if some nodes are compromised. The blockchain can function as long as the majority of nodes are loyal (honest).
Conclusion
Both systems rely on achieving consensus despite potential failures or malicious actors. In the blockchain, consensus mechanisms ensure the integrity of the system, just as the loyal commanders ensure the army follows the right strategy.
