Byzantine Generals Problem

Definition

The Byzantine Generals Problem was first proposed by Leslie Lambert in his paper on the problem of the fault tolerance of communication in a distributed peer-to-peer network, in 1982. During the communication of a distributed , problems occurred in certain parts of the network can cause the computer to send faulty messages, damaging the consistency of the entire . Essentially, The Byzantine Generals Problem is the problem of consensus in peer-to-peer communication.

Origin

The Byzantine Generals Problem originated from the middle ages. The Byzantine Empire had a vast territory; therefore, messengers were the only way for communications between armies. If the traitorous generals or compromised messengers deliver the wrong message, the armies could not reach an agreement on a common plan of action. There are two ways to solve this problem. One is to send messengers using oral messages to reach an agreement where the minority should obey the majority. However, it is very difficult to distinguish the traitors with this method. The other is to send messengers using written messages with exclusive signatures, each general should attach their signatures to the written message, but this could take too much time and a higher amount of resources.

The Byzantine Generals Problem on the Internet

The Byzantine Generals Problem on the Internet refers to the problem where malicious or compromised nodes affect information communication, resulting in data inconsistency in the network. In 1999, Miguel Castro and Barbara Liskov proposed the Byzantine Fault Tolerance Algorithm. They believed if two-thirds of the nodes operate normally, the consistency and correctness of the network can be assured. Later, Nakamoto Satoshi proposed Proof of Work and Asymmetrical Encryption algorithm, providing new solutions to the Byzantine Generals Problem.

Byzantine Fault Tolerance
Suppose the number of generals is n, the number of traitors is t. When n=3, t=1, there is one traitor among general A, B, C. If A sends out the command of “attack,” but traitor B tells C to “retreat,” A, B, and C cannot reach an agreement. Therefore, when the number of traitors is equal to or bigger than the one-third of the total number of generals, the Byzantine Generals Problem cannot be solved.
Similarly, suppose the number of nodes in the network is n, the number of malicious nodes is t, only when N>=3T+1, meaning that the normal nodes constitute two-thirds of N, the network can reach consensus.

Proof of Work

Suppose general A sends out the message of “attack” and attaches his signature to it; if other generals receive the message and agree to attack, they will attach their signature to the message too. If general A sends out the message of “attack” but does not attack, general A can be distinguished as a traitor. This is a way to tell the wrong information from the correct ones.
Similarly, multiple nodes in the network can conclude a “result” – a transaction record, by doing some “work.” The first node which works out the “result” can propagate the transaction record to the entire network. If the transaction record is correct, other nodes will add it to their ledger, preparing themselves for solving the proof of work problem.

With the PoW mechanism, a hacker has to have no less than 51% of the computing power of the entire network to release a false block or damage the network security. In such a case, the cost of such behavior is much greater than the benefit. Therefore, the possibility of false information appearance becomes much lower; the network can reach a consensus in a pretty short time.

Asymmetric Encryption Algorithm

In Asymmetric Encryption Algorithm, one needs to have a pair of keys – a public key and private key, to encrypt or decrypt information. If A wants to send a message to B, then A needs to use B’s public key to encrypt the message, and B needs to use his or her own private keys to decrypt the message. If B wants to prove his or her identity, he or she can sign a message with the private key and broadcast it to the network so that others can verify B’s identity by using B’s public key.
Since the identity and the signature are unforgeable, the Asymmetric Encryption Algorithm has solved the problem of privacy during information transmission and the problem of signature credibility.