The Byzantine Generals’ Problem
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.
The Byzantine's General Problem
If you need a refresher on history, the Byzantine Empire was the successor to the Roman Empire. The Romans split their empire in half between the East and West. The Eastern half became the Byzantine Empire. Following in the footstep of their forebears, the Byzantine army has launched a military campaign against a walled city. It's strategy is to surround the defenders before launching its attacks. The army is comprised of several legions, or divisions, each led by a general and their reporting lieutenants. The lieutenants and generals only communicate via messengers, and legion generals also communicate between each other via messengers. Do you already see the analogy of this structure with the computer network structures up above? If not, don't worry, we'll break that analogy down for you later.
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.
Without going over the math in too much detail, consensus can be reached as long as 2/3 of actors are loyal. In the figures above, each Lieutenant all have the same orders and consensus is met. Each Lieutenant has X, Y, and Z as their orders. Let's also plan for a solution where if messages are missing or the message is Uncertain the default strategy is to retreat. Even if X, Y, and Z are different combinations of retreat, attack, and uncertain then the Lieutenants take on the default action: retreat. Live on to fight to another day.
Byzantine Fault Tolerance
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:
- Byzantine General's Problem, 1982 Leslie Lamport, Robert Shostak, Marshall Pease
- Byzantine Fault Tolerance, Wikipedia
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:
- Please consider donating. My blog’s ethereum address: 0x1ea7ab9acd4294d32bb0c790dd08a66640342680
- Earn Aelf tokens by following them on Twitter (my referral link)
- Follow me on Steem (@quantalysus). I appreciate upvotes!
- Follow me on Twitter (@CryptoQuantalys)
- Getting Started: Airdrops
- Getting Started: Byzantine General's Problem
- ICO Review: Holochain
- ICO Review: Edenchain
- ICO Review: Quarkchain
- ICO Review: DAOStack
- ICO Review: Alchemint
- ICO Review: Loki Network
- Coin Review: Ontology
- Coin Review: Aelf
- Coin Review: Mithril: a social network app on the blockchain
- Coin Review: Qtum
- Coin Review: Waves
- Coin Review: Banyan Network (BBN)
- Opinion: Why we need regulation
- Opinion: Token economics
- Opinion: ICO paradox
- Opinion: Why we love Steem
Wow, great write up man, your explanation skill is incredible and I really enjoyed reading and understanding what use to be complicated to me.
Would you mind discussing our upcoming project with you and seeing what great input you can offer? We are building a blockchain on the EOSIO software that connect Smart Cities to Blockchain And Help Create A Crypto-Economy For Free Society.
I will appreciate your feedback on how we can further our talk
Hey @bania I'm always game to get in touch with projects. Feel free to email me at [email protected].
Congratulations! This post has been upvoted from the communal account, @minnowsupport, by quantalysus from the Minnow Support Project. It's a witness project run by aggroed, ausbitbank, teamsteem, theprophet0, someguy123, neoxian, followbtcnews, and netuoso. The goal is to help Steemit grow by supporting Minnows. Please find us at the Peace, Abundance, and Liberty Network (PALnet) Discord Channel. It's a completely public and open space to all members of the Steemit community who voluntarily choose to be there.
If you would like to delegate to the Minnow Support Project you can do so by clicking on the following links: 50SP, 100SP, 250SP, 500SP, 1000SP, 5000SP.
Be sure to leave at least 50SP undelegated on your account.
wao! what a nice and beautiful write up!!.i love that
wow great up
Resteemed by @resteembot! Good Luck!
Curious? Read @resteembot's introduction post
Check out the great posts I already resteemed.
ResteemBot's Maker is Looking for Work
You got a 59.23% upvote from @upmewhale courtesy of @quantalysus!
Earn 100% earning payout by delegating SP to @upmewhale. Visit http://www.upmewhale.com for details!
Great article, in my humble opinion no one that invests into crypto should use it without understanding this problem and principle - its a cornerstone to the entire movement.
Agreed. I'm putting together a curriculum for a few hour workshop. Planning to help build the house of understanding brick by brick for those who want to learn about this space.
Awesome, I'm thinking about doing a project similar - just need to find the time.
let's visit each other's blog @ zuhrafriska
I soon as there is Byzantine somewhere in a title or sentence, I have to read on, as a history buff I am! ^^ And in that case, even if it has little about history, I don't regret! Really interesting!
@quantalysus! It was a pleasure to read through this whole article. History+blockchain combined! Something very innovative I would say!