Byzantine Generals & How Proof-of-Work Drives Consensus
How resistant are blockchains to malicious actors?
Consensus refers to how miners (nodes) on blockchains agree on the transactions inside each block. It’s essential that agreement can be reached even if some nodes aren’t behaving correctly, since there’s no single source of truth to refer to. This resilience of a system is known as Byzantine Fault Tolerance, and is explained in today’s write-up. Enjoy.
*Thank you to Ziad for proofreading.
Byzantine Generals Problem
Understanding consensus starts with the Byzantine Generals Problem. This is a fictional scenario that illustrates why agreeing on anything in distributed systems is difficult. A distributed system is simply one with many participants performing the same function. In the Byzantine Generals problem, it’s a set of generals that are trying to attack Byzantium.
To launch a successful attack, the generals need to coordinate so that they attack together. If they don’t attack together, there’s a high chance their siege will fail. Each general can send messages to other generals, calling for an attack or a retreat. The question becomes, how can we ensure a successful attack even if some generals are traitors?
The answer is based on two things: the number of generals, and how many of them together are required for a successful attack. Some systems need more than half of the generals to attack together to succeed, others need two thirds, and some may only need one general for a successful attack.
Byzantine Fault Tolerance
Byzantine Fault Tolerance describes the level of faulty or malicious participants a network can have.
The Two Generals Problem
Let’s start small. Imagine a simple system, one with two generals (or nodes, or sensors, etc.) that need to agree, in this case to attack. If one of them sends a message, they cannot be certain the other received it. If the general receiving the order sends an acknowledgement, they also have no way of knowing it was received.
Since there are only 2 participants, there is no way to verify that the same orders were received by someone else. This is a system with no tolerance for faulty generals, and does not work well even when all generals are honest.
Multiple Byzantine Generals
Now lets add more generals to mitigate the problem above. Imagine we double the number of generals to four, and we try to repeat our siege on Byzantium. When one general calls for an attack, the order is received by the other three generals. Each receiving general can verify with the others that the plan is indeed to attack. Acknowledgements are not required, the generals can verify the orders received by other generals are the same.
In this example, we’ve mitigated the issue of coordination. However, a new problem presents itself. What happens if a general attempts to sabotage the attack? To step outside the metaphor for a moment, this need not always be a malicious actor, or someone with bad intent. When a distributed system is a group of sensors monitoring something, and one of them starts feeding in wrong data, how can a system determine which input is correct?
Being Byzantine Fault Tolerant
Back to our treacherous general, who has just issued different orders. Two generals are told to attack, and the third is told to retreat. When the generals check their orders with one another, the majority will report their orders to attack, and the minority will assume their orders were intercepted along the way.
In this scenario with four generals, one of which is a traitor, we need at least two of the other three to be honest. Those two can be used to verify the third, since the majority will win. If the two honest generals have different results, then they’ll follow the third general’s orders, whether to attack or retreat. Either way, the three generals are in consensus, and an uncoordinated attack (or failure) is avoided.
So being Byzantine Fault Tolerant means requiring at least two out of three honest participants in case a fourth one is faulty.
Bitcoin’s Solution
Bitcoin’s solution to the Byzantine Generals Problem was with Proof-of-Work. Within our previous metaphor, Proof-of-Work says that any general can call for an attack, but the attack does not happen immediately. Instead, the generals agree on a time to attack in the future. It does not matter how long they take to attack, only that they attack together.
The rules are that when a general wants to send an order and time to attack, they prepare a message that requires a lot of work (imagine a message with intricate writing, a wax sealed envelope, and so on). The message simply confirms the time for attack, and is broadcast to the other generals. When the other generals receive this message, they know what one of them is doing.
To make the proof-of-work more secure, this process is repeated. The receiving generals craft messages in response to confirm the plan, putting the same work into preparing each. When the second message is sent, it is based on a “chain” of two proofs-of-work. Once the proof-of-work chain has reached several messages in length, it can be taken as a source of truth, as it’s clear to see the effort of all generals was required to create it.
Proof-of-work is far more secure than a simple Byzantine Fault Tolerance. Instead of requiring two thirds as honest actors, only half need to be honest instead. Since the honest half will cooperate, they will have a longer proof-of-work chain which will serve as the source of truth. Their siege will be coordinated and successful.
In Conclusion
Blockchains must have Byzantine Fault Tolerance (BFT), since there is no single source of truth. Nodes must agree with one another on which blocks have been added to the chain. Thanks to Bitcoin’s Proof-of-Work innovation, a network only needs 50% of nodes to be honest. This gave us secure, decentralized money, and allowed for the decade and half of innovation we’ve since.
Thank you for reading, I hope you enjoyed this summary on Byzantine Fault Tolerance, Consensus, and Proof-of-Work!
If you have any questions, please comment them on this post! If you’d like me to cover any topics, feel free to suggest them in the comments also.
Thank You & Additional Reading!
Thanks a lot for reading! Here are some more resources if you'd like to dive deeper.
Email Explanation of Proof-of-Work by Satoshi Nakamoto
An introduction to byzantine fault tolerance and alternative consensus by Alexandra Carrillo
Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance by Georgios Konstantopoulos
Sign up if you haven’t already for more simple write-ups on blockchain concepts.
Share a Summary
Thanks again, please consider sharing this write-up below!
Stay kind. Stay curious.