Before we can really dive into some of the newer Byzantine Fault Tolerance Protocols. We need to really examine and understand the Byzantine Generals Problem with regard to Fault Tolerance protocols. In this article, we will be speaking specifically about Proof of Work, as it relates to solving the Byzantine Generals Problem.

Byzantine Generals Problem 2 General explanation Bitcoin blockchain cryptocurrency

2 Generals from Byzantine with a Problem

In this article, we will first examine The 2 Generals Problem. We will look at how the 2 Generals Problem leads us to the Byzantine Generals Problem. And finally, how Proof of Work, serves as the source of consensus for the Bitcoin blockchain solving the Byzantine Generals Problem.


If you can’t Trust a General, who can you Trust?

The 2 Generals Problem is an experiment that represents an issue of computer networking over an unreliable link. In this problem, we’ll call these 2 connected ‘nodes’, Generals. In this situation, both Generals and their armies have come upon a city they wish to attack. Each General’s army on its own is not enough to defeat the enemies army successfully, thus they need to cooperate and attack in a coordinated effort. The problem in coordinating this effort is that the Generals are separated by a significant distance (you can think of this as 1 on either side of a massive castle, with a moat). In this example, General 1 is considered to be the Leader, and General 2 is 2nd in command. In order for them to coordinate the time of the attack, General 1 has to send a messenger across enemy territory, to deliver a message to General 2. Using this method, there are many possible points of failure. The messenger could get captured by the enemy while en route to deliver the message, this would result in General 2 not receiving the message and General 1 attacking while General and his army hold their ground. If the message is successfully delivered by the messenger, General 2 still needs to acknowledge that he received the message. You guessed it, this is done the same way, General 2 now sending the message with the messenger back to General 1. Obviously, the same problem exists on the 2nd message and any subsequent message. Thus, creating a loop where each General is just sending messages without knowing if they have been or will be received by the other General. The essence of the 2 generals problem is if General 1 sends a message, how can General 2 confirm receipt without sending an additional confirmation message? If this sounds confusing to you? Don’t worry, you are not alone, as there is currently no solution to this problem. The reason I provide you the background on the 2 Generals Problem, is a newer problem has been iterated off of this problem, and its stuck its roots into the Blockchain space.

What to do when there are more than 2…

The Byzantine Generals Problem is much more than a fancy buzzword that bounces around Reddit threads on the internet. It is an important distributed computing problem that was first introduced in 1982, in a paper published by LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE. The trio was a group of researchers working under a nonprofit research company in California, known as SRI. Similar to the 2 Generals Problem, the Byzantine Generals Problem deals with, reliable computing systems handling malfunctioning components that give conflicting information to different parts of the system which prevents consensus in the distributed computing system. The main difference with the Byzantine Generals problem and the 2 Generals problem is that with the Byzantine Generals problem more than 2 Generals are involved in the decision making process. Whereas, in the 2 Generals problem, we had the scenario of Lead General and Follower General. In the Byzantine General scenario, you have a Commander and Lieutenant hierarchy. In order to achieve consensus in the Byzantine Generals Problem, the Commander and ALL Lieutenants must agree on the same decision. This scenario opens up for the possibility that one or more Generals maybe a traitor, and could agree with consensus but then go about doing their own thing.

 
Here is how the problem is described and solved by the authors of the 1982 publication, The Byzantine Generals Problem.
Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach an agreement. It is shown that using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed
Pictures Help…
To further explain, let’s examine the illustrations below:
Byzantine Generals Problem 2 General explanation Bitcoin blockchain cryptocurrency
In the diagram above we can see that Lieutenant 3 is ‘Malicious Actor’. When we look at the interactions between the ‘honest’ counterparts, we can see that the Decision is V, while Lieutenant 3 is trying to tell Lieutenant 2 that the Decision is X. The final decision is a majority vote between the Lieutenants, with 2 of 3 Lieutenants reaching the Decision V, an honest majority has been met and the Decision is in fact V.
Byzantine Generals Problem 2 General explanation Bitcoin blockchain cryptocurrency
In the 2nd diagram, we explore the possibility of a Malicious Commander. The commander in this scenario has sent 3 different inputs to the 3 Lieutenants, so there is no possible way they would come out with the same answer, right? Actually, that is not exactly correct. Remember, there are 2 outputs: Attack & Retreat; the inputs are different times of attack. Using the majority vote, we find that all Lieutenants in diagram 2 find the same input (x,y,z). You may be asking yourself, how does this even form a consensus if they all receive different inputs? What we can see is that the Lieutenants have come up with the same majority of inputs (which is x,y,z), and because they have realized that the commander is sending out conflicting information, they can reach consensus on retreat because it is clear that the commander is pedaling malicious information with regard to the time of the attack. The Byzantine Generals Problem leads us to the notion of Byzantine Fault Tolerance. Byzantine Fault Tolerance is the characteristic of a system that tolerates the Byzantine failures brought about in the Byzantine Generals Problem that we just described. A Byzantine Failure is an inherently difficult class of failures where there are no restrictions or assumptions based on the behavior of a node in the system.

How does this apply to Blockchain?

So, how does this apply to blockchain? A blockchain is a distributed ledger that is not in control of any one party. It’s no secret, that a lot of these distributed ledgers hold massive value. Because these ledgers are essentially ‘honeypots’ of wealth, it makes sense that a malicious actor would love to cause faults in the system in order to try and gain access to that wealth. In that case, the Byzantine fault tolerance is necessary for a blockchain to operate effectively. What about the concept of trustless nodes in a public blockchain? Take Bitcoin for example, in the absence of Byzantine fault tolerance, a malicious actor could execute things like double spend, or alter transactions, which would effectively eliminate the Bitcoin blockchains reliability which would make it worthless.

An Email from Satoshi…

Proof of Work (PoW) on the Bitcoin blockchain became the first demonstration of Byzantine Fault Tolerance on a blockchain. In an email from Satoshi Nakamoto in November of 2008, he explained the concept in a simple way, demonstrating General Byzantine Fault Tolerance enabled by Proof of Work, he provided an example of Byzantine Generals ‘brute forcing’ a wifi password. Below is part of the email from Satoshi, explaining the Proof of Work as it relates to cracking a Wifi Password:

They [the Generals] only have enough CPU power to crack it [in this example the wifi password] fast enough if a majority of them attack at the same time.
They don’t particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.
They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it’s expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they’re working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.
After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.
So that is a lot to digest, and that’s not even the whole email, but Satoshi does a great job explaining a difficult concept in a clear way. What Satoshi’s idea enabled was guaranteeing a way for an honest majority to come to a consensus on anything. Remember in the email he stated, they don’t particularly care when the attack will be, just that they all agree on it. What he means by that is, by being able to calculate the expended CPU that it takes to find the Proof of Work, it can be seen whether or not the majority are coming to a consensus on any given transaction. On the Bitcoin blockchain, examples of Byzantine faults would include a double spend, consistent censoring of transactions, or any other element that could cause the system to fail in the current state. Proof of Work in Bitcoin is used as a means of processing transactions. In order for an actor to submit the next block to be added to the chain they must find the solution to a particular mathematical problem, these people are actually called miners. And the miner that is most likely to solve the mathematical problem first, is the one that has the most computing power (or in mining terms ‘Hashing Power’). When the problem is solved, the block is mined, and the miner is rewarded with Bitcoin for the Block Reward and any Transaction fees associated with the block. Other nodes in the network will be alerted and will check the validity of the mined block. Below is an easy to understand illustration which demonstrates at a high level why you cannot cheat the Bitcoin blockchain.
Byzantine Generals Problem 2 General explanation Bitcoin blockchain cryptocurrency

I hope you have enjoyed this deep dive into Proof of Work and how it is used within the Bitcoin blockchain. We will look to follow up this article with additional articles on Proof of Stake (PoS), and Delegated Byzantine Fault Tolerance, as well as others.


References
:

Article on the Byzantine Generals Problem
Article on Proof of Work & Proof of Stake
Satoshi Nakamoto’s Email

Leave a comment

Share
Reddit
Tweet
Share
Email