What is the Byzantine general problem in computer science? Under which condition does the Byzantine Generals Problem Cannot be solved? What is Byzantine agreement problem and its solution?
Source : wikipedia.org
One of the important problems that Satoshi Nakamoto, known as the creator of Bitcoin, had to find a solution with technologies such as distributed ledger and blockchain, on which he bases his work, is the Byzantine Generals Problem, published in 1980, based on the work of Lessie Lamport, Robert Shostak and Marshall Pease. In some sources, this problem (perhaps not by that name) was first mentioned by Prof. Dr. It is said to have been put forward in a research titled “Some constraints in and trade-offs in the design of network communications” written by Eralp Akkoyunlu and his team in 1975.
Cryptocurrencies are made possible by the coordination of nodes scattered in many different locations, thanks to certain consensus algorithms. By reviewing these problems, we can understand the root cause of the difficulties of consensus among them. So what was wrong with the Byzantine generals? Let’s take a closer look; In order to understand this problem, we must first set the scene.
Byzantine armies surrounded the castle from all sides to seize the enemy castle with its strong walls and brave and valiant warriors. Although the soldiers defending the castle are few in number, they are certainly not easy prey, thanks to both their courage and the strong walls of the castle. If the Byzantine armies cannot coordinate their attacks and attack from at least three wings at the same time, they are highly likely to fail. In the Byzantine army, the army on each wing is under the command of a general, and since the armies are not very close to each other, communication between them can only be provided by messengers. In the forests where the messengers use their paths, the enemy soldiers capture the messengers whenever possible. As if this were not enough, there is also intelligence that there is a traitor in the army.
The highest-ranking general, as the commander, needs to command the attack. The general who leads the armies of the north has the highest rank and commands the attack. He sends a messenger to the other three armies, announcing that they will attack at dawn the next day.
Now let’s consider the possibilities…
The first possibility actually overlaps with another problem, also known as the Two Armies Problem.
Did the sent messengers arrive at their destination? Or were they captured on the way? The only way to answer such a question would be for each army to give a feedback on the message received, that is, send a messenger back. In this way, the commander can understand that the message has been delivered to the owners by looking at the feedback he receives.
Although the problem seems to be solved, let’s put ourselves in the shoes of a general sending a messenger to the commander that he has received the message. The commander gave the command to attack and asked him to send a messenger for verification, but what if the messenger sent for verification is caught on the way? In this case, the commander can cancel the attack, as he will not know whether we have received the order, and a coordinated attack is absolutely necessary to win! So now should we attack at dawn tomorrow morning or not?
If you examine the problem carefully, you will realize that we are actually trapped in a closed loop. No matter how many times the commander and general send messengers to each other, they can never reach 100% agreement, but as a result of the mutual exchange of enough messengers, a serious consensus is formed. However, the time it will take for each bride to go will require long periods of time to reach an adequate compromise. One of the alternative solutions that can be applied to avoid this loss of time may be to send 100 messengers at a time. Even if some of the messengers are caught, the probability of a few messengers arriving at their destination will increase so that sufficient agreement can be reached without extending the time. However, even if the time is shortened here, the cost is very high.
If we cut the Two Armies Problem here and go back to our troubled Byzantine generals, they have a serious problem beyond this Two Armies Problem, that they have a traitor in them to deal with.
The Byzantine Emperor and his assistants evaluate and ponder the intelligence that there is a traitor among them. Finally, they prepare a protocol that the generals have to implement and send it to the generals. According to this protocol, each general will share the order he receives with other generals by sending a messenger.
The commander leading the Northern Army sends the order, “We will attack at dawn tomorrow morning” to the other three armies with a messenger. Assuming that we have somehow solved the Two Armies Problem, we now assume that the command has arrived across the street. As per the emperor’s order, each general who receives the commander’s order sends the orders to both the commander and the other generals with a messenger. Thus, each general has his own orders and orders that other generals claim to have received.
If one of the generals is a traitor and he chooses not to attack, the attack of 3 out of 4 armies will be able to bring down the city. For this, the treacherous general should give false information while repeating the order and try to confuse the other generals. However, since only one of the 3 messages sent by the treacherous general to the generals will have come from him, two of the messages will contain the same correct message and the generals will identify the distorted message and implement the real order.
Thus, the solution of the Byzantine Generals Problem reveals the basic feature of decentralized structures. Not just a center, but all points are in mutual communication with each other.
This problem we have described above is called the Byzantine Generals Problem. If any member of the community in blockchain networks sends inconsistent information about transactions to others, the reliability of the blockchain is compromised and there is no central authority that can step in to correct it, the nodes to agree on the transactions made depend on a suitable solution to the Byzantine General Problem on the network.
One of these solutions is known as the Byzantine Fault Tolerance [BFT] system as a reference to the Byzantine General Problem we shared with you above. However, Byzantine Fault Tolerance is only one possible solution to the Byzantine General Problem. PoW [Proof of Work], PoS [Proof of Stake] can be given as examples for other well-known solutions.
