The Byzantine General Problem describes a situation where the involved parties must agree on a single strategy to avoid failures. The involved parties need to coordinate their action or behaviour but cannot trust each other to get organized.
It is a made up, historical situation where multiple generals and their individual armies have surrounded a city to attack it. The majority of the generals must somehow coordinate a decision to either attack or retreat at the same time; otherwise, the situation ends up in a major failure.
If a group of Byzantine Generals attack a city, two problems emerge-
- It is difficult to carry out a coordinated attack as the general and armies are far from each other.
- The city might have a large enough army and the only resort is to attack from all sides.
General A on the left sends a messenger to the right with a message “ ATTACK GABRIEL” . If in case the troops on the right are unprepared, they send the messenger back. A potential problem arises as the messenger can be captured, killed or even replaced by another messenger.
In order to resolve this problem the General attaches a nonce (random hexadecimal value) to the original message. The text attached with nonce is further hashed, until a suitable output is obtained. If the conditions are not satisfied, the values keep changing until the desired output is obtained. A major drawback with this method is the consumption of a large amount of computational power.
If in case the messenger is caught and the message is tampered, the hash continuously changes as the message changes. However, no hash function is 100% collision-free. It is also possible that the message is tampered and changed until the desired output is obtained.
The problem was solved by Satoshi Nakamoto’s “ Proof of Work” Protocol.
Henceforth, instead of only a General sending the message, a cumulative message is sent by the General and the Lieutenants. The cumulative message is hashed, a nonce is attached and then the resulting hash is hashed again. In this situation, even if the messenger is caught, the message is tamper-proof.
However, cumulative hashing gives rise to yet another problem. In order to achieve consensus, the General and the Lieutenants must agree on the same decision. There is a steep possibility that a General or a Lieutenant maybe a traitor.
The researchers of the Byzantine General Problem solved the problem in a 1982 publication which stated “ 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.”
Let us examine the a case with a Commander and three Lieutenants involved-
The decision is say ‘V’ while the Lieutenant claims that the decision is X. A majority vote is taken which establishes the fact the correct decision is ‘V’.
There is also a possibility that the Commander is spreading false information. In this case, the Lieutenants form a consensus and prevent a failure.
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 demonstrating General Byzantine Fault Tolerance enabled by Proof of Work. Here is an excerpt from his mail-
“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.”
The examples of Byzantine faults in Bitcoin include consistent censoring of transactions, double spending and any elements which could cause the system to fail. In order for a miner to submit the next block, he finds a solution to the complex mathematical problem. When the problem is solved, the miner is rewarded with the block reward and transaction fees associated with the block. The other nodes in the network check the validity of the mined block and after reaching supermajority the block is added.
Conclusively, the Byzantine General Problem was successfully resolved by proof-of-work, a consensus mechanism used in blockchain technology. New technologies tapping the blockchain prowess are ensuring that their systems are byzantine fault tolerant.
