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.
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.
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
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.
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.