The Byzantine Generals’ Problem (shortened to BGP for the rest of the post) is a fundamental problem in a distributed computer network. BGP is a derivation of the unsolvable Two General's Problem, in which, two generals sitting on two opposite sides of an enemy's camp need to send coordinated attack information to each other through (not around) the enemy's camp. Therein lies the problem. How do you trust that the information has not been compromised along the way? How do you know the messenger has not been corrupted by the enemy? The BGP, described in more detail below, expands this problem to a Generals-to-Lieutenants configuration.
Blockchain technologies have their own varying solutions to solving this issue. Bitcoin, Ethereum, and their inspired, kindred blockchain protocols are all decentralized peer-to-peer networks. Trust is paramount. No one party owns the ongoings nor decides the actions of the network, so how to ensure the network is running smoothly and honestly. In other articles we will explore how different blockchains solve BGP. Before formally defining BGP, I suggest you read my previous post about system architecture.
Queue the danger music since some of the generals may be traitors. The loyal generals are trying to reach agreement on what to do next. They devise a plan (or in computer science, an algorithm) guarantee two things: 1) all loyal generals agree on the same plan (consensus), and 2) the loyal generals act upon that plan regardless of what the traitor generals do. There are a few constraints we need to place on this plan. The consensus plan should be reasonable. The number of traitor generals should be small enough that they do not corrupt the loyal generals plan(s). All the generals or commanders have to agree upon one of two possible actions: 1) exact time to attack or 2) exact time to retreat. This is high risk because if only one of the armies attacks, the entire army will be defeated.
Diagram from the original Byzantine General's Problem paper
In the figure above, traitors are filled in with black lines. In Figure 1, a loyal General sends a message to Lieutenant 1 and 2. L2 is a traitor and sends a conflicting message to his peer. L1 does not know who the traitor is: is the General a traitor or is his peer a traitor? In Figure 2, the General is a traitor and sends conflicting messages to L1 and L2. Since both Lieutenants are loyal, L2 sends L1 the message he received from the General. From L1's point of view, he again does not know who is the traitor: the General or Lieutenant 2? In both scenarios, the army attacks with less than full strength.
Now let's get closer to finding a solution. We create two new Figures (3 and 4) to expand the BGP above to include an additional Lieutenant (L3) and one more message type. In Figure 1 and 2 we had two message types: "Attack" and "Retreat". In Figure 3 and 4 we add "Uncertain", denoted as Z in the figures above. These additions increase the problem's complexity. It gets even more complicated once we add more Generals, Lieutenants, and message types.
Byzantine Fault Tolerance (BFT) is a trait of a system that can withstand failures (attacking at less than full strength) defined by BGP. BFT is one solution to the infamous BGP. Yet Byzantine Faults are the most severe issues in a variety of network applications. High stakes systems such as nuclear arsenal commands or complex vehicles such as commercial airliners require solutions to BGP. In blockchain technology this is even more pervasive. Bitcoin for example does not have a single authority or central server to issue commands to the rest of the network. This distributed computing environment requires a sophisticated BFT solution.
In Bitcoin, a traitorous General is the same as a node sending unreliable or inconsistent information to the rest of the network. There is no IT department or central authority to correct issues. Absolute trust is needed by every general, or node, on the network. Bitcoin's attempt to solve BFT through its PoW algorithm has been battle tested since inception. Is it a final solution to the problem? What Bitcoin lacks in speed, it makes up for in security. Blockchains that optimize for speed such as EOS decrease their levels of decentralization to achieve their goals. EOS has yet to be battle tested but passing muster on BFT will be one criteria to judge its success.
Hopefully you learned something new. In a future post we will delve into the concept of Tragedy of the Commons.
Sources:
Thank you for coming to the site. Quantalysus publishes blockchain research and analysis for the crypto community. Please follow on Twitter, Steem (please follow and upvote if you can – thanks!), Telegram channel (New!), and Medium to stay up to date.
If you want to earn Aelf (ELF) tokens for just using Twitter and Reddit, sign up for their candy / bounty program.
If you learned something:
