The Byzantine Generals Problem, conceptualised by Leslie Lamport, Robert Shostak and Marshall Pease in 1982, is a puzzle in the field of distributed computing. This metaphor represents generals encircling an enemy city and wishing to coordinate an attack. This problem regained interest after the creation of Bitcoin in 2008 by Satoshi Nakamoto, who proposed an innovative solution to this dilemma.
Distributed computing is a field of computer science in which systems made up of several independent computers communicate and coordinate their actions by exchanging messages to achieve a common goal. These systems are often geographically distributed, enabling tasks to be handled more efficiently and resiliently.
A well-known example of distributed computing is Google's system, which uses a distributed architecture to manage Internet search queries. This system distributes data and processing across many servers and data centres around the world, enabling billions of queries a day to be processed quickly and efficiently.
The problem faced by the Byzantine generals is relatively simple to describe. A number of Byzantine army generals are stationed around an enemy town, each commanding his own troops, and are planning a coordinated attack. Their communication is limited to oral messengers, and they must agree on a common plan of attack, aimed at launching the assault simultaneously at an agreed time, for example at dawn, failing which defeat will be inevitable. They communicate their intentions using the messages "attack" to confirm the action or "retreat" to cancel it.
However, some of these generals may be traitors and seek to sow disorder. These traitors may send retreat messages to persuade loyal generals to withdraw at the crucial moment, thereby risking defeat.
The challenge is to develop a strategy or algorithm that ensures that all the loyal generals agree on a unified plan of action, despite the presence of traitors who will seek to thwart their plans.
The difficulty is compounded if a commander, whom subordinate generals must obey, is himself a traitor.
The importance of Byzantine failures in modern computer synchronisation systems is crucial, particularly in areas where security and reliability are paramount. The challenge of Byzantine generals, illustrated by the coordination required between various computer systems, is particularly pronounced in the aviation industry. For example, in the case of aeronautics, and specifically for complex aircraft such as the Boeing 777, the robustness and reliability of IT systems are essential for flight safety.
These systems must be designed to process information from different sources and to make correct decisions even if some of this information is erroneous or maliciously altered. The architecture of the Boeing 777, for example, uses the principles of redundancy and cross-checking to prevent failures and ensure reliable operation, which is in a way an application of Byzantine fault tolerance.
However, this synchronisation problem is most apparent in decentralised networks, such as those used by crypto-currencies. Bitcoin, for example, is based on a distributed network where each participant maintains a copy of a transaction register, the blockchain, which requires a reliable consensus despite the potential presence of malicious participants.
These systems must resist Byzantine breakdowns, where certain nodes can act as traitors, disrupting the general agreement. The challenge is therefore to develop algorithms that ensure consensus even in the presence of these "Byzantine" nodes. This type of algorithm has what is known as Byzantine fault tolerance (BFT).
In the context of Bitcoin, which facilitates the transfer of value, the challenge is to reach agreement on the ownership of assets in a distributed way, without depending on a central authority such as banks, while preventing malicious actors from compromising the consensus.
Solving the problem of the Byzantine generals requires more than two-thirds of the generals to be loyal, limiting the proportion of traitors to less than one-third. Before the advent of technologies such as Bitcoin, this problem was tackled by so-called "traditional" consensus algorithms, including PBFT (Practical Byzantine Fault Tolerance). This algorithm enables a network to process thousands of requests per second with a latency of less than one millisecond.
However, these traditional systems present a significant vulnerability: they require prior selection of the nodes authorised to participate in the consensus. This selection can be made via a proof of authority, a whitelist of nodes, or a delegated proof of stake. This closed approach makes the system vulnerable to external attacks, as the validating nodes are explicitly identified and therefore more exposed to threats.
The introduction of Bitcoin in 2008 marked a turning point with the introduction of Nakamoto's consensus algorithm, based on proof of work. This mechanism uses blocks of transactions that are added to a blockchain. In this system, the validity of a chain is determined by its accumulation of energy, often referred to as "the longest chain". Although there may be temporary divergences in consensus, the economic incentives inherent in the protocol encourage compliance. Miners, who are responsible for validating transactions, are incentivised to deploy their computing capacity in exchange for bitcoins, which motivates them to maintain the integrity of the network.
The invention of Bitcoin represents a significant advance in solving the so-called Byzantine Generals problem, not through absolute finality, but through a probabilistic approach. Unlike traditional algorithms that guarantee a definitive conclusion, the Bitcoin system accepts that, although a transaction is never totally irreversible, its permanence can be reliably estimated after several blocks have been added to the chain. Nakamoto's protocol, at the heart of Bitcoin, is based on a less restrictive principle than most traditional systems, requiring only 50% of computing power to be honest, rather than the usual 67%.
This feature allows Bitcoin to operate efficiently with a large number of nodes participating in an open manner, which is crucial for an application as delicate as currency. Indeed, most economic functions are regulated by a state monopoly and any competition is generally sanctioned. This is why Bitcoin has had to operate outside the established laws in order to survive.
