The Byzantine Generals’ Problem
I had just mentioned the term “The Byzantine Generals’ Problem” in my previous post. The Byzantine Generals’ Problem (henceforth mentioned as BGP) is a classic problem faced by any distributed computer system network. We have already discussed that Bitcoin is a decentralized, peer to peer distributed system. Decentralization is the core principle of Bitcoin and this is achieved only through distributed system. Let us understand high-level difference between the different types of distributed networks
Centralized Vs Decentralized Vs Distributed networks
The diagram is self-explanatory.
- In Centralized Systems there is one central authority or server and all the other nodes act like clients or entities who accept message and enact accordingly
- In Decentralized Systems there are multiple servers who receive messages from one central server. The individual nodes are connected to the secondary servers. However, in some systems, all servers can be of equal in hierarchy with no central server as well.
- In Distributed systems there is no central authority. Each node is connected to every other node and has the exact same authority. Of course, in terms of computing distributed systems the processing power of each node might vary to a huge extent.
BGP — Explained as a fictitious historic incident
Imagine that the grand Eastern Roman empire aka Byzantine empire has decided to capture a city. Alas, there is fierce resistance from within the city. The Byzantine army has completely encircled the city. The army has many divisions and each division has a general. The generals communicate between each as well as between all lieutenants within their division only through messengers.
All the generals or commanders have to agree upon one of the two plans of action. Exact time to attack all at once or if faced by fierce resistance then the time to retreat all at once. The army cannot hold on forever. If the attack or retreat is without full strength then it means only one thing — Unacceptable brutal defeat.
If all generals and/or messengers were trustworthy then it is a very simple solution. However, some of the messengers and even a few generals/commanders are traitors. They are spies or even enemy soldiers. There is a very high chance that they will not follow orders or pass on the incorrect message. The level of trust in the army is very less
Consider just a case of 1 commander and 2 Lieutenants and just 2 types of messages- ‘Attack’ and ‘Retreat’.
In Figure 1 — The Lieutenant 2 is a traitor who purposely changes the message that is to be passed to Lieutenant 1. Now Lieutenant 1 has received 2 messages and does not know which one to follow. Assuming Lieutenant 1 follows the Commander because of strict hierarchy in the army. Still, 1/3rd of the army is weaker by force as Lieutenant 2 is a traitor and this creates a lot of confusion.
However what if the Commander is a traitor (as explained in Figure 2). Now 2/3rd of the total army has followed the incorrect order and failure is certain.
In Figure 3 and Figure 4, we have just added 1 more Lieutenant and 1 more type of message (Let’s say the 3rd message is ‘Not sure’). Immediately the complexity of finding a consensus between all the Lieutenants and the Commander is increased. Now imagine the exponential increase when there are hundreds of Lieutenants.
This is BGP. It is applicable to every distributed network. In fact, in the Bitcoin network, it is even more complex as there is no true ‘General’ or server. All participants or nodes (‘Lieutenant’) are exactly of equal hierarchy.
All participating nodes have to agree upon every message that is transmitted between the nodes. If a group of nodes is corrupt or the message that they transmit is corrupt then still the network as a whole should not be affected by it and should resist this ‘Attack’. In short, the network in its entirety has to agree upon every message transmitted in the network. This agreement is called as consensus.
In future reading, we will see how Bitcoin algorithm gives a probabilistic solution to BGP.
— -
If you are an enthusiast in Bitcoin, Distributed Ledgers/ Blockchain and similar crypto-technologies then do join my Signal group, where we as a community, will answer all your questions. Join by clicking here
— -
I will definitely reply to your comments and clarifications. Do share your thoughts :)
Follow me on Linkedin and Twitter
Header stock image from Wiki and figures of Byzantine army is from the original whitepaper
