Back in early days of business computing, circa 1980, computer scientists began to examine reliability and computers. It was determined that a reliable computer system must be able to cope with the failure of one or more of its components. A failed component may exhibit a type of behavior that is overlooked and problematic, namely, sending conflicting information to different parts of the system. The problem of coping with this type of failure is expressed abstractly as the Byzantine Generals Problem. This abstract problem and the solutions thereof are used in developing highly reliable and trusted blockchain implementations.
The Byzantine Generals Problem Explained: Why Trust Is So Important
The Byzantine Generals Problem (BGP) is one of many in the field of agreement protocols. Lamport framed his paper around a story problem. This was the style of the day as evidenced by the attention received by another computer scientist, Edsger Dijkstra and his dining philosophers problem, based on a classic operating system synchronization problem.
To set the table for this problem—and as the musical Hamilton will be on Broadway long after this book is out of print—we see that the BGP problem was relevant in the American Revolution. At the start of the conflict, the Continental Congress ordered an oath of allegiance to be administered to all army officers. George Washington, the commander-in-chief, administered it to the general officers. When Washington began to read the oath to Major General Charles
Lee, Lee withdrew his hand from the Bible. When Washington demanded a reason for the strange conduct, according to The Writings of George Washington, Lee replied, “As to King George, I am ready enough to absolve myself from all allegiance to him; but I have some scruples about the Prince of Wales.” This odd reply elicited much laughter. Lee was then playing a desperate game of treason, and probably had some problems with his conscience about taking
such an oath which he (and later Major General Benedict Arnold) would violate.
The BGP is built around a similar story line: the commanding general who makes a decision to attack or retreat, and must communicate the decision to his lieutenant generals. A given number of these actors are traitors (possibly including the general). Traitors cannot be relied upon to properly communicate orders; worse yet, they may actively alter messages in an attempt to subvert the process.
In the analogy, the generals are collectively known as processes, the general who initiates the order is the source process, and the orders sent to the other processes are messages.
Traitorous generals and lieutenant generals are faulty processes, and loyal generals and lieutenant generals are correct processes. The order to retreat or attack is a message with a
single bit of information: a one or a zero.
A solution to an agreement problem must pass three tests: termination, agreement, and validity. As applied to the Byzantine Generals Problem, these three tests are:
- A solution has to guarantee that all correct processes eventually reach a decision
regarding the value of the order they have been given. - All correct processes have to decide on the same value of the order they have been given.
- If the source process is a correct process, all processes must decide on the value that
was original given by the source process.
The best way we know to implement blockchain is to use many different processors to compute the same result, and then to perform a majority vote on their outputs to obtain a single value. See the image below, which views the BGP and blockchain issues in a side-by-side analogy.
