Byzantine generals problem

Byzantine

The creation of effective peer-to-peer networks as the cryptocurrency basis became possible only thanks to the introduction of the blockchain system as the main architectural element.

The problem was to create certain algorithms that would allow individual users of the network to reach consensus on its general state. Which is quite problematic since there is no trust between most elements. With a centralised system, things are easier: you either trust the regulator and use its services, or not.

The efficient operation of decentralised systems became possible only thanks to the creation of automatic consensus algorithms. It solved the problem of trust in the interaction between the individual nodes but could not completely protect the system from accidental errors and external influences.

The situation is simple — all elements trust each other by default, but what if some of them are mistaken, and others intentionally provide false information? How to make a common “collegial” decision in this situation? This task is called the “Byzantine generals problem”, and its solution lies at the core of P2P networks resilience.

Backbone of the problem

This problem was invented in 1982 as a typical illustration of how strong the problems of finding a collegial solution in large groups consisting of equal right elements can be.

The condition of the problem is as follows. There is a city besieged by several Byzantine armies, each of which has its own commander. A successful siege requires a simultaneous attack from all sides, or a general retreat and a regrouping of forces. The decision that has been made cannot be cancelled. Communication is carried out by couriers, not instantly. The task is to achieve a common solution and execute it simultaneously.

The problem is that messages transmitted between individual generals to coordinate their actions may be lost, delayed or destroyed. And their contents may be falsified by enemy spies, not to mention the fact that individual generals can sabotage a general attack.

Is it possible in such a situation to achieve an effective collegial decision, which will have to be accepted by all participants? As it turned out, yes.

At the moment, the most effective solution to the Byzantine generals problem involves the consent of more than two-thirds of all participants, provided that they act honestly and transmit valid data. However, if most of the members of the distributed network (more than 51 percent) agree to act maliciously, the entire decision-making process will be disrupted.

Byzantine fault tolerance

Essentially, it is an opportunity to make common collegial decisions even when not all nodes are connected to the decision-making process or provide deliberate misinformation.

This can be achieved in several different ways, however, as practice has shown, the consensus algorithms adopted in blockchain networks are one of the best options. They are automatic, not requiring personal trust between the individual nodes, indestructible and complex enough to be imitated by criminals.

Consensus algorithms

Currently, two main consensus algorithms are used — Proof of Work (PoW) and Proof of Stake (PoS). In the first case, reliability is guaranteed by the computational work that any other network participant can double-check. In the second, by a certain financial contribution and a further opportunity for the guarantor to participate in the process. The most popular cryptocurrency at the moment — Bitcoin — uses the Proof of Work (PoW) consensus algorithm.

To imitate the confirmation of the consensus algorithm, significant resource costs are required, as it is necessary to compensate for both cryptographic protection methods and the computing power of a constantly working network. However, even this algorithm does not provide absolute resistance to external influences. The real application experience shows that the consensus algorithm developed by Satoshi Nakamoto is the most optimal solution to the problem at the moment.

Conclusion

The Byzantine generals problem can be used in all situations when you need to make some collegial decision on the basis of many different testimonies. For example, in aviation, nuclear power and space flights, decisions have to be made based on the readings of numerous sensors. Each of which may be spoiled or submit false information.

However, modern methods used in the design of blockchain networks make it possible to achieve significant stability of the entire system in such situations. This is what made it possible to create effective cryptocurrency networks. However, it is possible that soon more effective consensus algorithms will be developed that will help cope even with such complex problems as network scalability.