Byzantium, the capital of the ancient Eastern Roman Empire, was once one of the world’s most powerful and wealthy cities. However, due to its vast territory, Byzantium often faced external invasions and internal rebellions. To defend its borders, Byzantium dispatched multiple armies, each commanded by different generals. Achieving consensus among these generals became a significant challenge.
The Byzantine Generals Problem has a close relationship with blockchain. A blockchain network is a distributed network where nodes, like Byzantine generals, must achieve consensus on transactions and data in an unreliable network environment.

Two Generals Problem

The Two Generals Problem is a special case of the Byzantine Generals Problem. The problem and its proof of unsolvability were first proposed by E.A. Akkoyunlu, K.Ekanadham, and R.V. Huber in their 1975 paper “Some Constraints and Trade-offs In The Design of Network Communications.” In 1978, Jim Gray formally named this problem the “Two Generals Problem” in his book “Notes on Data Base Operating Systems.” Originally, it was used to analyze the issues of achieving consensus through communication over an unreliable communication link. It is now commonly used to illustrate consistency and consensus issues in distributed systems.

Problem Definition:
Two armies of country A, each led by a general, are preparing to attack an army of country B. The army of country B is surrounded in a valley, with A’s two armies stationed on the hills on either side of the valley. However, the only path between the two armies of A goes through the valley. B’s army is stronger than either of A’s armies individually, but if both A’s armies attack together, they can defeat B’s army.
Problem: Can an algorithm be devised that allows the two generals of A’s armies to agree on a simultaneous attack? The algorithm may include sending and receiving messages.
Solution: The classic Two Generals Problem is unsolvable. There is no protocol that can guarantee the two armies of A will successfully coordinate their attack. However, in practical systems, issues can be addressed relatively reliably, such as with the “three-way handshake” mechanism in the TCP protocol.

Byzantine Generals Problem

The Byzantine Generals Problem was first proposed by Leslie Lamport, a 2013 Turing Award winner, in his 1982 paper “The Byzantine Generals Problem.” The problem describes how to achieve consistency in distributed systems in the presence of malicious behavior, such as message tampering.
Several armies of the Byzantine Empire surround an enemy city, each led by a general. The Byzantine armies could only communicate through messengers. After observing the enemy’s forces, the Byzantine generals must reach the same conclusion: only if more than half of the Byzantine armies attack together can they capture the city and achieve victory.

Solution: If the number of generals (nodes) in a Byzantine system is Z and the number of unreliable (traitorous) generals is X, then only when Z ≥ 3X + 1 can a Byzantine Fault Tolerance (BFT) protocol guarantee system consistency.
In practical systems, failures causing nodes to be unresponsive are classified as “Crash Faults,” while nodes that forge or tamper with messages are classified as “Byzantine Faults.”

Consensus Algorithm Classification

Blockchain systems are a type of distributed system, especially public chains like Bitcoin and Ethereum, which consist of numerous highly decentralized and mutually untrusting network nodes. The blockchain consensus mechanism ensures that the blockchain system consistently achieves data consistency without forks.
Based on the fault tolerance type, consensus algorithms can be classified into non-Byzantine Fault Tolerance (CFT) algorithms and Byzantine Fault Tolerance (BFT) algorithms.

Non-Byzantine Fault Tolerance Algorithms

In distributed systems, non-Byzantine Fault Tolerance algorithms ensure the reliability of the entire distributed system when nodes experience system failures or unplanned outages (non-Byzantine faults). However, when malicious nodes forge or tamper with data, non-Byzantine Fault Tolerance algorithms cannot ensure system reliability. These algorithms are primarily used in closed, controlled enterprise distributed systems. The most representative non-Byzantine Fault Tolerance algorithms include the Paxos algorithm and the Raft algorithm.

Byzantine Fault Tolerance Algorithms

Byzantine Fault Tolerance algorithms allow a distributed system to ensure reliability even if nodes experience any type of fault, as long as the number of faulty nodes does not exceed a certain proportion. Simply put, as long as the number of faulty nodes (due to non-Byzantine or Byzantine faults) is less than a certain proportion of the total nodes, Byzantine Fault Tolerance algorithms can ensure system reliability. Due to the presence of many untrusting network nodes in blockchain systems like Bitcoin and Ethereum, Byzantine Fault Tolerance algorithms are primarily used in blockchain consensus mechanisms. The most representative Byzantine Fault Tolerance algorithms include PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work), and PoS (Proof of Stake).