Byzantine Fault Tolerance: Solving Byzantine Generals Problem
- The Byzantine Generals’ Problem describes a scenario where a system may fail if its components cannot agree on a concerted strategy. The problem assumes that some fraction of the system is corrupt and will act against the system. A Byzantine Fault Tolerant (BFT) system should be capable of achieving finality regardless.
- Bitcoin is Byzantine fault-tolerant. Defending against Byzantine faults is one of the most important aspects of maintaining a decentralized network’s functionality, stability, and security and was imperative to the design of Bitcoin. When network consensus is what prevents double-spending, a Byzantine fault is crippling.
When it comes to making decisions, centralized systems are incredibly efficient. An order from the top trickles down through the ranks until it gets executed. There are no conflicting opinions when all of the power lies with a trusted third-party, but with great power comes great incentive for attackers.
A centralized system has a single point of failure – its center. Financial systems are the foundation of a burgeoning economy, and where there’s money involved, crime is never too far behind. Blockchain technology is making economic systems more secure than ever before using decentralized networks and programmable money, but there have been (and still are) numerous challenges in its way.
Blockchains are, by nature, decentralized, and getting everyone on the network to agree on certain decisions can be challenging. For blockchains to process any information, the network needs to reach a state of agreement or ‘consensus.’ This is when all participants draw the same conclusion about the state of the network’s data.
Consensus is one of the foundational concepts behind blockchain architecture. Still, due to how these systems work, individuals are more likely to act based on the information available and what incentivizes them. This creates issues because the decisions that motivate one group of users don’t always affect others the same way.
To ensure a blockchain’s smooth functioning, there needs to be a system to ensure the network can achieve consensus consistently. This requires solving a question initially posed in the 1980s known as the Byzantine Generals’ Problem.
The Byzantine Generals’ Problem Explained
The problem defines a Byzantine army split into groups surrounding a city. Each group is led by a general, and they can only communicate via messenger. The army needs to agree on a common strategy – attack or retreat. However, if one of the Byzantine generals decides to go against the official decision, the army will not collectively act.
This is known as a Byzantine Fault. In computing, the Byzantine Generals’ Problem describes a scenario where a system may fail if its components cannot agree on a concerted strategy. The problem assumes that some fraction of the system is corrupt and will act against the system. A Byzantine Fault Tolerant (BFT) system should be capable of achieving finality regardless.
Is Bitcoin Byzantine Fault Tolerant?
On blockchain networks, each node is considered a Byzantine general that contributes to the network’s consensus. Defending against Byzantine faults is one of the most important aspects of maintaining a decentralized network’s functionality, stability, and security and was imperative to the design of the first-ever cryptocurrency – Bitcoin. When network consensus is what prevents double-spending, a Byzantine fault is crippling.
If Bitcoin was not Byzantine fault-tolerant, a malicious user could create false transactions, spending money that doesn’t exist and devaluing the entire system. To prevent this, miners must agree on a single version of the blockchain. Once one finds a solution to the proof-of-work problem, it is broadcast to the network to be verified by other nodes, and the rewards go to the miner who solved it first.
This provides the network with a verifiable method of observing how much work the chain has put in. Still, it uses an incredible amount of energy and computation power that scales with network participation. Bitcoin is one of the first realized, sustainable models of a decentralized BFT system, but it’s far from perfect, and while the risk of malicious nodes acting against the network in BFT systems is low, it isn’t zero.
Secure to a Fault
The problem of obtaining Byzantine consensus in these systems was originally conceived during a SIFT project sponsored by NASA in the Computer Science Lab at SRI International in 1978. SIFT, or Software Implemented Fault Tolerance, was based on using multiple computers to communicate to reach consensus even with faulty actors through pairwise messaging.
Dubbed the Interactive Consensus Problem, it wasn’t immediately apparent just how many computers were needed to guarantee that conspirators couldn’t overwhelm the correctly acting nodes. The study showed that a BFT network would need 3n+1 nodes, which led to them creating a generalized algorithm for n > 0.
Before Bitcoin’s Proof-of-Work implementation of a proper BFT consensus mechanism, experts worldwide had already proposed multiple solutions. Some only worked if the number of malicious actors remained below a certain threshold fraction of the network; others included the use of unforgeable signatures to ensure the network verified messages. Of the many algorithms that spawned between the 80s and the new millennium, Miguel Castro and Barbara Liskov’s Practical BFT algorithm proposed in 1999 was highly influential, inspiring a whole new wave of improved BFT algorithms.
BFT mechanisms use components to repeat an incoming message to other recipients, but these mechanisms assume that the simple act of repeating a message blocks the development of Byzantine symptoms. For better security, these assumptions must be provably true to an acceptable degree of fault coverage. The problem with providing this kind of proof is the need for a sufficiently wide range of signals exhibiting Byzantine behavior, and this testing can often require specialized fault injections.
Blockchain technology wouldn’t work unless it solved the Byzantine Generals’ Problem. Double spending is a fatal flaw in decentralized payment systems because unless the nodes maintaining the global ledger can agree on a list of legitimate transactions, the system is meaningless. Consensus is a dynamic process and can be achieved in many different ways, but these methods or ‘consensus mechanisms’ are all built on some core principles.
Ideally, consensus algorithms should produce as much agreement from the group as possible, with every participant’s vote carrying an equal amount of weight. Further, all participants should collaborate to create the best solutions for the majority, making the mechanism more useful as more people participate, allowing it to address a more accurate majority.
The Evolution of Consensus
Bitcoin may have been the world’s first practical cryptocurrency, but many attempts were made to create a decentralized digital currency before Satoshi Nakamoto. David Chaum’s DigiCash, Nick Szabo’s Bit Gold, and Wei Dai’s B-Money are great examples of pre-Bitcoin cryptocurrencies that failed because of their inability to implement Byzantine fault tolerance. Nakamoto solved this problem by integrating ‘Nakamoto Consensus,’ a special class of consensus mechanisms, into the protocol.
Nakamoto Consensus requires that nodes have something to lose, which incentivizes them to agree with the rest of the network. When miners compete to solve Bitcoin’s Proof-of-Work algorithm, they spend computation power in the hope of receiving a reward, and this ‘work’ gives them skin in the game.
Through this economic incentivization, Bitcoin cleverly does away with most of the traditional challenges of creating decentralized systems, assuring its protocol is as secure as possible. A report from Bitcoin mining software company Braiins shows that the cost to take control of the majority of the Bitcoin network’s hash rate runs upward of $5.5 billion.
Bitcoin is undoubtedly secure, and its creation has had game-changing effects on the world of financial services, introducing humanity to an entire decentralized economy. However, as mentioned earlier, Bitcoin’s Proof-of-Work algorithm is particularly power-hungry, consuming electricity at the same rate as some whole countries. This has sparked the invention of many more BFT consensus mechanisms that aren’t as wasteful, such as Proof-of-Stake, and the more intricate Delegated Proof-of-Stake.
Proof-of-Stake, and Delegated Proof-of-Stake
In a Proof-of-Stake (PoS) system, instead of miners competing to solve a mathematical problem, block creators are chosen based on how much stake they have in the network. For example, if an individual owned 1% of the total supply, that person has a 1% chance of being entrusted with creating the next block. Different PoS systems have different rules for how a user’s stake impacts their ability to create blocks, but this heavily disincentivizes acting against the network in fear of losing their stake.
This dramatically reduces the energy consumption of a decentralized network, with only a few nodes working to verify transactions at any given point in time. It is arguably just as secure as a Proof-of-Work chain, but concerns surrounding how attackers could manipulate PoS networks into becoming more centralized using a sufficient amount of capital is still heavily debated.
Delegated Proof-of-Stake does away with most of these concerns by allowing participants to choose ‘delegates’ to validate transactions. Users can form groups to vote, allowing for the implementation of a BFT protocol. Since the number of nodes in a group is limited and well-defined, a DPoS system also guarantees much higher scalability and efficiency levels.
Delegates are also expected to define a leader rotation, giving each delegate a turn within the rotation to produce blocks. The rewards are then distributed among the group, but if the delegate is not available to produce a block, they have to wait for their next turn.
Each participant’s voting power is allocated in proportion to their participation. This involves a relationship with another consensus protocol called Proof of Participation and is a characteristic part of the model. To favor decentralization, DPoS blockchains typically vote on governance-related decisions as well, including topics like rewards, number of delegates, network forks, and more. This also includes penalizing delegates that do not behave in accordance with the network.
A Byzantine fault can be defined as any system failure that presents itself with different symptoms to different observers, and a node’s behavior is never assumed to abide by certain restrictions or act in a certain way. Byzantine faults can lead to some of the most severe breaches in network security, but solving this problem was a challenge faced by people in all kinds of industries. From airplane engines to nuclear power plants, any system that depends on multiple sensors needs to be tolerant to Byzantine faults.
In fact, some aircraft systems, like the Boeing 777’s information management and flight systems, have implemented Byzantine fault tolerance. As real-time systems, their solutions must be extremely low-latency, with the ability to detect a Byzantine fault within microseconds of added lag. Even some spacecraft designs, such as the SpaceX Dragon, account for Byzantine fault tolerance.
The reason BFT systems aren’t entirely devoid of vulnerabilities from malicious nodes is because Byzantine fault tolerance only observes broadcast correctness. This is the property of a system component to broadcast a single, consistent value to other parts that all receive the same value.
In cases where the broadcaster is inconsistent, the other components must be able to agree on the final value. This allows for attacks involving adversarial components that deliberately and consistently send incorrect values to other components – a weakness that not all BFT systems can defend against.
As blockchain technology continues to evolve, the mechanisms used to achieve finality will improve with it. From East Roman armies to digital gold, humans have a track record of solving problems they ponder upon for a long time. Blockchain is just over a decade old, and the term ‘Byzantine Generals’ Problem’ is only a few decades older, but as decentralized networks and their consensus algorithms become increasingly sophisticated, blockchain is solving a problem that’s been pondered for millennia – trustless money.