Raj.
Github

Byzantine Generals Problem

Rishab Raj

Published on

Introduction

The Byzantine Generals Problem(BGP) is a classic thought experiment which illustrates the challenge of how reaching a consensus in a distributed network In any distributed systemfew nodes can be malicious or unreliable or compromised. Solving this problem is essential for maintaining the integrity of a such a system.

Byzantines Generals Problem

The Scenario

lets assume 4 generals encamped around a city and they are planning to capture a city. To succeed they should agree on a single plan: attack or retreat.

  1. If they attack simultaneously they will win

  2. If they attack in fragment they will lose

One General will act as a Commander and sends the message to other Generals to attack, and all the other Generals will reiterate the Commanders message to all other Generals so that they can decide from majority.

The Problem

The core problem is Trust. In distributed system we cannot assume that all of the nodes are reliable. An unreliable or compromised node can send conflicting messages to different nodes to prevent a consensus. The goal of this experiment is to come up with a solution where honest Generals can come up to a conclusion even when we have few traitors.

Example 1

Now let us try to understand this with an example.

Suppose there are 4 Generals - A(Commander), B(Traitor), C and D.

General A thought that it is a good time to attack the city, so he sent three messengers to General B, General C and General D respectively and asked them to attack!, but General B is having malicous intention and he in order to confuse the General C and General D again send a messenger with messenge retreat! to General D and general A, and attack to general C. Other 2 Generals who are honest reiterate the correct message to other Generals. In this case we have following

  1. General A -> [attack to General B, attack to geenral C, attack to general D ]

  2. General B -> [retreat to General A, attack to general C, retreat to general D ]

  3. General C -> [attack to General A, attack to geenral B, attack to general D ]

  4. General D -> [attack to General A, attack to geenral B, attack to general C ]

Individual conclusions of each Generals

  1. General A -> 1 retreat and 2 attack hence attack

  2. General B -> 3 attack does not matter as TRAITOR

  3. General C -> 3 attack hence attack

  4. General D -> 2 attack and 1 retreat hence attack

Final Consensus : Attack!

So Even if we have 1 Traitor among 4 Generals, honest generals can come to a consensus.

Example 2

Now I have chosen 4 generals with 1 traitor because in distributed system with m traitors we need to have atleast total of 3m + 1 generals for consensus it is called Byzantine Fault Tolerance(BFT).

We can verify this by performing the same experiement with 3 Generals with 1 traitor in that case suppose if General A acting a Commander sends attack to other 2 generals B and C, but B being traitor sends retreat to C and attack to A and General C being honest reiterates the correct message, we have following

  1. General A -> [attack to General B, attack to general C]

  2. General B -> [attack to General A, retreat to general C]

  3. General C -> [attack to General A, attack to general B]

Individual conclusions of each Generals

  1. General A -> 2 attack hence attack

  2. General B -> 2 attack does not matter as traitor

  3. General C -> 1 attack and 1 retreat cannot decide

hence here we have 2 honest generals who cannot come to a consensus.

Conclusion

By understanding Byzantine Generals Problem(BGP) and Byzantine Fault Tolerance(BFT), we can understand the trustlessness in any type of distributed system and how a system with few unreliable participants can ensure that final data is secure and correct using BFT.