The Byzantine Generals problem and Bitcoin’s solution
Bitcoin

The Byzantine Generals problem and Bitcoin’s solution

By Matteo Gatti - 4 Aug 2019

Chevron down

The Byzantine Generals Problem is a computer-related problem consisting in finding an agreement by communicating through messages between the different components of the network. But Bitcoin solved it.

This is a problem that was theorised by the mathematicians Leslie Lamport, Marshall Pease and Robert Shostak in 1982, who created the metaphor of the generals. The case study of the Byzantine Generals is well known in the field of distributed systems.

The Bitcoin blockchain was created with the aim of eliminating trust in third parties during a transaction. The objective is to ensure that everyone agrees on the chronological order of transactions and therefore it is essential to introduce a consensus algorithm, which allows the various players in the network to agree.

The metaphor

Several generals are on the verge of attacking an enemy city during a siege. They are located in different strategic areas and can only communicate via messengers in order to coordinate the decisive attack.

However, among these messengers, it is highly probable, or even certain, that there are traitors. The traitors carry messages that contradict the army’s strategy. The problem, therefore, lies in the ability to carry out the attack effectively despite the risk of treason. This is known as decentralised consensus.

In the best case scenario, the message that will arrive will be coordinated: attack or retreat.

Or, as is more logical, the message will not be coordinated, so both orders will arrive: attack and retreat.

The problem faced by the Byzantine generals is the same as that faced by distributed computing systems. How to reach a consensus on a distributed network where some nodes may be faulty or voluntarily corrupted?

The Byzantine Generals problem in the case of Bitcoin

In the specific case of Bitcoin, the system must be able to maintain its reliability in the event that a minority of components send incorrect or harmful information to evade double-spending.

This problem is very difficult to solve. However, Satoshi Nakamoto, with the Bitcoin blockchain, offered a practical and functional solution by combining asymmetric encryption, peer-to-peer systems and Proof of Work, ensuring that all network participants can quickly and securely agree and share each transmitted message.

Nakamoto’s solution

In his emails, Nakamoto explains how the Proof of Work chain offers a solution to the Byzantine Generals problem and shows how a number of generals who are ready to attack must coordinate on the moment the attack is launched. It is not important which time to choose in particular, but it is crucial that the attack takes place in a synchronised manner.

The decision has been made that once the time of the attack has been decided by one of the generals, it will be considered valid for all. But since the network is not instantaneous, it is possible that two generals announce two different times for the attack simultaneously. With the result that some will receive the first time and others the second.

This is solved by using the Proof of Work chain. When a general receives a message he has to solve an extremely difficult problem. The first one who solves it communicates it to the other participants. If someone was at work on a different attack time, they will have to replace it with the one they just received, because this chain is the longest and therefore considered valid.

The blockchain

The blockchain, therefore, ensures that a set of nodes belonging to the same network, work together, managing the network in sync and effectively. Nakamoto’s solution is innovative but to be so, it requires a certain amount of energy to be consumed and introduces a necessary delay between the generation of two blocks.

A consequence of a functional and secure trustless system, which is being remedied by developing new types of consensus algorithms.

 

We use cookies to make sure you can have the best experience on our site. If you continue to use this site we will assume that you are happy with it.