Byzantine Generals Problem is a common term in the blockchain field as well as a core issue in cryptography.
Byzantine Generals Problem is a distributed peer-to-peer network communication fault tolerance proposed by Leslie Lamport in his paper The Byzantine Generals Problem.
In the dictionary of blockchain, it is described as follows: Byzantine Generals Problem means “it’s impossible to reach an agreement on unreliable channels where certain messages are missing.” Therefore, there are other errors in the system other than message delay or non-delivery failure, including message falsification, the failure of node process according to the protocol, etc., which will potentially cause targeted damage to the system.
It may sound a bit complicated and confusing. Next, we’d like to use the example of Pleasant Goat and Big Big Wolf to explain what is the “Byzantine Generals Problem.”
Byzantine Generals Problem
Suppose one day when the Wolf grabbed Slow Sheep, the chief of the sheep village. For the sake of his security, five lambs in the village demand to attack the Wolf Fort to rescue the chief.
Here we assume that the five lambs have equal combat capabilities. They are stationed in five strategic locations outside the Wolf Fort and can only communicate with each other through messengers. Only the joint action by at least four of them can successfully rescue the chief.
To make the problem simpler, we set only two action strategy: attack or evacuation. For the sake of democracy, they decide to vote to decide whether to attack or to withdraw based on the principle of majority.
During the voting process, each lamb needs the pass its own voting message to other five lambs through messenger, so that each lamb can reach consensus to decide on attack or evacuation based on its own choice as well as the principle of majority.
But the problem is that there may be traitors among them; perhaps one lamb may show obedience to the Wolf.
Assume that the traitor receives two votes for attack and two votes for evacuation, Then, it only needs to pass the attack message to the two lambs who voted for the attack, and pass the evacuation message to the two lambs who voted to retreat. There will be two lambs attacking and two lambs retreating, which will destroy the team synergy and the rescue operation will be doomed to fail.
Moreover, since the lambs need messenger to deliver the message, the traitor is very likely to forge the letter and send the false message in the name of other lambs.
Even if all the lambs are loyal, it’s also probable for the messenger to be replaced or killed by the Wolf.
In the aforesaid cases, if the loyal lambs still follow the principle of majority, the mission of rescuing the chief will still be doomed to fail.
So, due to the existence of risks, each lamb must be very careful and never easily believe the message from other lambs, thus the whole rescue operation will be greatly affected.
That’s the Byzantine Generals Problem.
Appearance of Bitcoin
If we reflect such a story into a computer system and regard the lambs as the computer nodes and the messenger as the communication system: the core of the Byzantine Generals Problem is how to exchange information in the case of unreliable nodes and communication so as to reach consensus.
And according to research on this issue, if the number of traitors is greater than or equal to 1/3, then there will be no solution for the Byzantine Generals Problem.
This problem was raised in 1982, but it was not until 2008 when Satoshi Nakamoto proposed bitcoin that it was resolved to some extent.
As we can see that there are two essential issues of the problem: “consistency” and “correctness”. Why is it so difficult to be solved? There are two important reasons:
- Unencrypted information is easy to be cracked, impersonated and forged;
- Low cost for the malicious behaviors of nodes to affect the consensus;
So, how does the underlying technology of bitcoin solve the Byzantine Generals Problem?
Asymmetric Encryption Technology
First, the bitcoin network can encrypt the information sent by the nodes, that is, to protect the node information with asymmetric encryption technology.
The technology has three features as follows:
- Privacy of message delivery
- Confirmation of identity
- Signature cannot be forged or falsified
Since the blockchain network is decentralized and the information is shared at all nodes, thus the possibility of passing different information to different nodes due to opaque information is greatly reduced.
In addition, the encryption and decryption process of asymmetric encryption algorithm adopt two different keys: the “public key” and the “private key”, which effectively avoids the tampering, leakage and forgery problems during message delivery.
Byzantine Fault Tolerance
In addition, the bitcoin network increases the cost of information delivery. It’s stipulated that only one node can broadcast information within a certain period.
The cost refers to the POW (Proof of Work) mechanism. The so-called message delivery refers to the broadcast on the blocks after the mining of bitcoin. Under such a mechanism, only the first node which completes the POW (bitcoin mined) can broadcast on the block.
The specific implementation of such a program is just based on the algorithm of Byzantine Fault Tolerance.
Byzantine Fault Tolerance is a consensus algorithm in blockchain technology.
The basic concept of Byzantine Fault Tolerance algorithm can be described as follows: anyone in the system is unreliable. Once one person receives message from another person, he needn’t make any immediate judgment, just pass the message he received to another person. Thus, the message is transparent among all the members (for example, A sends attack message to B, B sends his own thoughts together with A’s idea to C, then C can see the information from both A and B). Since most nodes in the system are honest, everyone can make judgement by comparing with the general information, so that the probability of error will be greatly reduced.
According to the research, if there are N nodes in the system, only the number of dishonest nodes F reaches: F=(N-1)/3, then the normal operation of system will be affected.
With more than 30,000 nodes on the bitcoin network, attacking these nodes for the sake of ulterior motives will take a large amount of hashrate and costs. Therefore, even if there are some malicious nodes in the system, so long as the majority is good, it will be fully possible to realize the decentralization consensus.
It also seems to explain why mining is not a waste of resources —- after all, the cost of building trust is not zero.
It can be said that through asymmetric encryption technology and Byzantine fault tolerance algorithm, bitcoin provides a solution to the Byzantine Generals Problem. Such a solution can also be introduced to other fields whose core problems are due to the lack of trust on distributed networks.