What Is The Byzantine Generals Problem

Introduction

The Byzantine Generals Problem, also known as the Two Generals’ Problem, was proposed in Leslie Lambert’s paper on the fault tolerance of distributed peer-to-peer network communication in 1982. In the communication of the distributed system, some local problems may cause the computer to send error messages and destroy the system’s consistency. Therefore, the Byzantine Generals Problem is essentially a problem of consensus in point-to-point communication.

Origin

The Byzantine Generals Problem originated in the middle ages. Due to the vast territory of Byzantium, the communication between armies can only rely on messengers. If there is a traitor deliberately misrepresenting the information of the army leaders, it will lead to inconsistent operational plans, resulting in the “Byzantine failures”.

In order to solve this problem, there are two solutions: one is to send messengers to each other by oral agreement, and reach a consensus by simple majority, but it is difficult to distinguish potential traitors; the second is to send messengers in the form of written agreements to deliver written messages with exclusive signatures, which should be seconded by each army, but if the transmission is too slow, the signatures may be lost. As both solutions can only solve part of the problem, and it takes too much time and resources to reach a consensus, they are not useful.

Byzantine Generals Problem in the Internet

The Byzantine Generals Problem in the Internet means that in the process of channel transmission, it may be difficult for some nodes to achieve information synchronization due to excessive workload or some malicious attacks. In 1999, Miguel Castro and Barbara Liskov proposed the Byzantine Fault Tolerance (BFT). They believed that if two-thirds of the nodes in the system worked normally, the consistency and correctness of the system could be guaranteed. Later, Satoshi Nakamoto proposed the proof of work (PoW) mechanism and asymmetric cryptographic algorithm of Bitcoin, which provided a new solution to the Byzantine Generals Problem.

Byzantine Fault Tolerance

Suppose there are n generals and t traitors. Say n=3, t=1, so one of A, B and C is a traitor. If A issues the [attack] command, but traitor B tells C to [retreat], then C cannot make a judgment; If traitor B sends [attack] command to A and [retreat] command to C, then A and C cannot reach an agreement. Therefore, when the number of traitors is greater than or equal to 1/3, the Byzantine Generals Problem cannot be solved.

Similarly, assuming that the total number of network nodes is N and the number of malicious nodes is T, the problem can be solved only when N>=3T+1, that is, the number of normal nodes in the network is at least (2/3) N, so as to ensure the consistency of information. In reliable network communication, Byzantine Fault Tolerance can solve the problem of node failure to a certain extent, so that the system can reach a consensus.

Proof of Work (PoW) Mechanism

Suppose general A first issues the [attack] command and attaches his signature. After receiving it, if other generals also plan to attack, they will follow the [attack] command and his signature after general A’s command. If A does not execute the [attack] command after A sends it, other generals can judge A as a traitor and use it to distinguish the right information.

Similarly, multiple participating nodes will get a result through a series of work, and the first node that gets the result will broadcast it to the whole network. If the result is correct, other nodes will add the result to their own ledgers to prepare for calculation in order to win the right to record transactions on the blockchain.

A Hacker must have more than 51% computing power to destroy network security or publish fake blocks. The cost is far greater than the return. Therefore, this mechanism can reduce the possibility of false information and make the system reach a consensus faster.

Asymmetric-key Algorithms

The encryption and decryption of the asymmetric-key algorithms need two separate secret keys - public key and private key, which usually appear in pairs. If A wants to send a message to B, A needs B’s public key to encrypt the information, and B needs his/her own private key to decrypt the information. If B wants to show his/her identity, he/she can sign the private key, write a “signature text” and broadcast it. Others can verify his/her identity according to B’s public key.

Because the identity and signature can not be forged, the asymmetric-key algorithms ensure the privacy of the transmission and the trusted signature.