Understanding the Byzantine Generals’ Problem (and how it affects you)
A note from Anthony: If you haven’t already, please read the article ‘Gaining clarity on key terminology: Bitcoin versus blockchain versus distributed ledger technology’ and ‘Consensus Explained’. If you’re new to this space, these articles will provide some useful context.
My son is nearly 10 years old. A few days ago, I shared with him the Byzantine Generals Problem. For nearly an hour into bedtime, he struggled with the problem and how to solve it — unsurprisingly! It is a fictitious problem, but one of the hardest problems of all time. It was first referenced in the paper titled ‘The Byzantine Generals’ Problem’, published in 1982.
What my son does not yet know or understand (aside from the answer(s)!) is the profound impact of the problem and the practical application of the solution, referenced in the paper titled ‘Bitcoin: A Peer-to-Peer Electronic Cash System’, published by Satoshi Nakamoto in 2008.
As Mike Maloney explains in his recent documentary, the Byzantine Generals’ Problem can be summarised as a question: How do you make sure that multiple entities, which are separated by distance, are in absolute full agreement before an action is taken?
In other words, how can individual parties find a way to guarantee full consensus?
Before considering possible solutions to this problem, allow me to outline the problem in more detail, and explain how it relates to you and your business.
Dissecting the Byzantine Generals’ Problem
Imagine divisions of a Byzantine army, attacking a completely encircled city. To proceed, the generals of each division, who are dispersed around the city’s periphery, must agree on a battle plan. However, while some generals want to attack, others may want to retreat.
In the official description of the Byzantine Generals’ Problem (which you’ll find on page three of the aforementioned paper), there is a leader-follower set-up. In order to achieve consensus, the commanding general and every lieutenant must agree on the same decision.
The conditions are described as follows:
Page 3, The Byzantine Generals Problem
To complicate matters, the generals are so far apart from each other that messengers are required in order for the generals to communicate. Also, one or more lieutenants may be a traitor, intending to sabotage the situation.
So, given these conditions and the commander-lieutenant set-up, can the army execute a strategy?
The solution to the problem relies on an algorithm that can guarantee that:
- All loyal lieutenant generals decide upon the same plan of action, and
- A small number of traitors cannot cause the loyal lieutenants to adopt a bad plan.
The loyal lieutenants will all do what the algorithm says they should, but the traitors may do anything they wish. The algorithm must guarantee the first condition regardless of what the traitors do. The loyal lieutenants should not only reach an agreement but should agree upon a reasonable plan.
Why the Byzantine Generals’ Problem could be your problem too
The Byzantine Generals’ Problem is the analogy most often used to illustrate the requirement for consensus for distributed ledger technology (DLT).
The nodes in the distributed system must all agree on a certain set of rules, and be able to move forward by agreeing on a particular assessment of a transaction before it is added to the database.
This is not easy, especially where thousands of nodes exist. In addition to that, each one must agree on the validity of new information to be added, thus preventing bad actors from sabotaging the ledger and rewriting history.
A specific type of consensus algorithm must be adopted to achieve this, enabling the nodes to work together to update the ledger securely.
Understanding Byzantine fault tolerance
A Byzantine fault is any failure in the system that presents different symptoms to different observers. It implies no restrictions, and makes no assumptions about the kind of behaviour a node can have (e.g. a node can generate any kind of arbitrary data while posing as an honest actor).
The actual occurrences and taxonomy of Byzantine faults in different systems is a complex and extended topic. However, it’s defined in such a way that results in a formal definition of Byzantine fault tolerance (BFT).
Note that Byzantine faults are the most severe and difficult to deal with. Byzantine fault tolerance has been needed in airplane engine systems, nuclear power plants, and pretty much any system whose actions depend on the results of a large amount of sensors.
It all comes down to consensus
In this article, we discussed some background information pertaining to the problem of consensus in distributed systems.
In future articles, I will explore the types of consensus and a related comparison. Stay tuned!