Byzantine Generals Problem and their Application in Blockchain
Two Generals Problem, The Byzantine Generals Problem and Byzantine Fault Tolerance
2 Generals Problem
The 2 generals problem is a computer science problem, presented as a challenge to solve, in order to reach an agreement through the exchange of information in a reliable environment. It is often given in introductory lessons on Computer Networking, which explains why the TCP protocol cannot guarantee consistency between connection points.
In general, the two generals problem said that in an environment where communication problems can occur, it is impossible to guarantee the agreement between the two sides.
The content of the problem 2 generals can be described as follows:
- 2 armies are led by generals A1 and A2, attack a city B in the middle.
- The generals A1 and A2 can only exchange through sending letters to each other, but there is a problem that the postman needs to go through City B, which makes it possible for the postman to be captured. The message could not be delivered to the destination or was sent to the destination but the content was modified
- The generals A1 and A2 need to agree on the assault on city B, and the time they both go together. Because both can only win if and only if they attack at the same time. In other words, they need to reach a consensus on the time of the attack
It seems that the problem can be solved simply by electing a commander between two people, and it will be the one who gives the attack timelines to send to the other person and that’s it. But the problem is how (only by sending the message and processing the received message) generals can know with certainty: “We both agreed and will attack at the same time. XX: YY day ZZ “
Let’s take a moment to elaborate on the issue here
- The general A1 will probably start by sending a message to the general A2, with the content “Let’s attack at 12:00 on August 19”. However, after sending the letter, A1 had absolutely no idea whether the postman could deliver the safe message to A2.
- To be sure, A2 will need to send a confirmation to A1 with the content: “I have received your message, and will attack together at 12:00 on August 19”. However, once again, the postman could be arrested, and the general A2 will again be in a state of anxiety whether or not A1 will receive his confirmation
- To be more certain, the general A1 may continue to send a message with the text “I have received your confirmation of the attack plan at 12:00 on August 19”. However, this postman may be arrested, too
Just like that, we will clearly see that, no matter how many rounds of confirmation, there will be no way for each general to make sure that the other has agreed to the attack plan. Both were always in a state of wonder, wondering if the last message they had sent would reach the destination.
The 2 generals problem is the first computer communication problem that proved to be no solution.
The Byzantine Generals Problem
The Byzantine generals problem was posed by three computer scientists Leslie Lamport, Robert Shostak and Marshall Pease in a scientific report called “The Byzantine Generals Problem” in 1982. This is a generalized problem of 2 generals problem.
The Byzantine generals’ problem describes a group of generals in the Byzantine army (Eastern Roman Empire army), which besieges a city. The generals need to exchange to reach an agreement on the plan to attack that city. In the simplest case, they agreed on whether to attack or retreat. Some may want to attack, but some may want to retreat, and the problem is that if there is only a single attack department, then they will fail. That is a worse plan than to attack together or retreat together.
Things get complicated when a general will be able to send messages to other generals. For example, in the case of 5 generals, 2 of them have signaled want to attack, 2 generals have signaled to withdraw. The 5th general is a double agent, texting 2 of generals want to attack that he wants to attack too, also message with 2 generals who want to withdraw that he will withdraw. Then the attackers think that attacking is the majority choice and attack (will fail), the withdrawing side thinks that retreat is the majority choice and they withdraw. They failed to reach a consensus (about having the same opinion).
Everything will be even more complicated when we put in the case that they still have to send a message through a postman, so it is quite possible that the postman … get caught, the mail cannot be sent to the destination or the message content is modified.
There are many solutions mentioned in scientific reports of Lamport, Shostak and Pease. They begin by noting that the problem of the Byzantine generals can be solved by referring to the “Commander and Lieutenants” problem (commander & lieutenant).
The problem is as follows:
- The commander will send orders to the remaining lieutenants
- The lieutenant can send messages to each other
- How can loyal people reach a consensus on a decision (such as attacking or withdrawing)?
Note that even if the commander is a traitor, all (loyal generals) still need to reach a consensus.
Three computer scientists, Lamport, Shostak and Pease have developed an Oral Messages (OM) algorithm to solve this problem. In order for all to reach a consensus, we need to rely on the choice of the majority.
However, it is necessary first to assume that:
- Every message, when sent, will be delivered to the correct destination
- The recipient of the message will know exactly who they receive from
- Can detect the absence of a message (such as someone not sending)
Theorem: With each value m being the number of traitors, the algorithm OM (m) can reach a consensus if there are more than 3m total generals.
In other words, if there are all n commanders, the OM algorithm will reach a consensus when two-thirds are loyal (or no more than 1/3 are betrayed). You can see more details about the OM algorithm here or here
To make it easy to imagine, let’s take a look at the simple case, with 4 generals (including C, L1, L2, L3), and 1 traitor, as follows:
- Case 1: The traitor is L3. C will broadcast the message with content v for L1, L2, L3. L3 betrayed so he modified it, and sent x to L2. However, L2 will get v from L1 and C, will see that the majority has chosen v. From there, loyal generals, including C, L1, and L2, will reach consensus as option v, even though L3 has broadcast messages x.
- Case 2, the traitor is C. C can send x to L1, send y to L2 and send z to L3. L1, L2, L3 are loyal, so they will broadcast the message they receive to others. Thus L1 will receive all 3 commands: x (from C), y (from L2) and z (from L3). It seems impossible to decide, but actually, the decisions of all 3 people will be the same, because the majority is the majority (x, y, z). If x, y, z carry completely different content, and we can’t calculate the weight, all will follow the default option, which could be a draw for example.
Byzantine Fault Tolerance
Byzantine Fault Tolerance (BFT) is a system that solves the problem of the Byzantine generals problem.
Building a Byzantine fault-tolerant system is a necessity, but also extremely difficult in a distributed system.
In 1999, computer scientists Miguel Castro and Barbara Liskov introduced the “Practical Byzantine Fault Tolerance” (PBFT) algorithm that can manage Byzantine states with a high performance that can handle thousands of requests per second with extremely low latency.
After the introduction of PBFT, a variety of other BFT protocols were introduced with many improvements in performance and were more widely applied.
Byzantine Fault Tolerance exists in the engine systems of aircraft, missiles, nuclear plants … things that need to make a decision based on information received from many different sensors.
Byzantine Generals Problem, Blockchain & Consensus
Explain for a while about the 2 generals problem, the Byzantine Generals Problem and the Byzantine Fault Tolerance, many of you might be wondering if it has anything to do with Blockchain 😂
Blockchain is a ledger shared for all members in a decentralized network. There is no trusted third party to manage its operation, but the members of the system must interact with each other to come to a consensus. In other words, a Blockchain system needs a way to withstand the Byzantine fault.
When Bitcoin, the first blockchain was born. Its father, Nakamoto Satoshi also introduced a method to solve the problem of the generals, known as the Proof-of-Work (PoW).
Nakamoto Satoshi explained directly how Bitcoin uses PoW to solve the Byzantine generals problem in an email sent on November 14, 2008, you can check it here.
It should also be mentioned that the Byzantine problem on the Blockchain network has been simpler, thanks to the use of Digital Signatures. With the features that it brings as:
- Authentication: A digital signature can be used to verify who sent a message. Only the owner of the private key can create an electronic signature for a message.
- Integrity: messages cannot be modified during transmission. If that happens, the digital signature will become invalid.
- Non-repudiation: a message with a digital signature has been sent, the person who signed it cannot deny that he created and signed the message
Besides PoW, today’s blockchains also use many other Consensus Protocols. For example, Neo uses Delegated Byzantine Fault Tolerance, or the Linux Foundation’s Hyperledge Fabric platform uses Practical Byzantine Fault Tolerance (PBFT), similar to the consensus solution that Tendermint provides.
In particular, the world’s largest Blockchain platform today, Ethereum has also announced plans to move from Proof of Work to Proof of Stake (PoS) in the near future. PoS on the Ethereum platform, codenamed Casper, will appear with the first version of Casper: Friendly Finality Gadget (Casper FFG), or Vitalik Casper (since this is the version made by a team led by Vitalik Buterin head). This will be the Byzantine Fault Tolerance-style proof of stake, which will have similarities with traditional BFT algorithms.
In the following articles, I will talk more about PoS, as well as Ethereum Casper FFG, please pay attention.