Byzantine Generals Problem and their Application in Blockchain
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) so that both of us can know with certainty: “We both agreed and will attack at the same time. XX: YY day ZZ “
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 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 generals have signalled want to attack, 2 generals have signalled to withdraw, and 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 they attack (and 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:
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: 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 v option, 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 (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.
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 also 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 Protocol. 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 — Proof of Stock) 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.
Published at Wed, 05 Feb 2020 13:45:24 +0000
{flickr|100|campaign}
