Byzantine Generals problem
The Byzantine Generals Problem is a computer science problem that presents a challenge in designing distributed systems. It is based on a thought experiment in which multiple generals of the Byzantine army, each commanding their own division, must coordinate to attack or defend a city successfully. The challenge lies in the fact that the generals need to be sure that the others will carry out their orders, as they may be traitors, and so must find a way to reach a consensus without being able to communicate directly with one another.
Byzantine Generals have to decide whether to attack or retreat. The decision must be unanimous, but communication between the generals is unreliable. Some generals may be traitors who will try to prevent the other generals from making the correct decision. The problem can be solved in several ways, one is the Byzantine Fault Tolerance algorithm.
Do you see the analogy to the blockchain already? In the blockchain networks, we face the same problem - we have to undoubtedly confirm the same transaction without being able to communicate between all nodes, which “takes decisions”
Byzantine Fault Tolerance
Byzantine Fault Tolerance (BFT) is a fault-tolerance system that ensures the reliability of distributed systems in the presence of unreliable services. It is a form of distributed consensus that requires multiple system replicas to agree on a single result. BFT is an important tool for distributed computing systems, as it allows them to continue operating, even when individual components within the system experience errors, fail or return malformed results.
BFT is based on the assumption that not all processes or computers within a distributed system may be trusted and that some could potentially be malicious. To achieve fault tolerance, the system must incorporate redundancy and allow for different system replicas to communicate and agree on a single result. This is accomplished through a series of Byzantine agreements, where each replica sends a message to all other replicas, providing evidence that it has reached the same result as the others.
The Byzantine Fault Tolerance system can be applied to various distributed systems, including blockchain networks. In a blockchain context, BFT ensures that all transactions are properly validated and agreed upon by the network before being added to the ledger. This is important for maintaining the integrity of the blockchain and preventing double-spending.
pBFT: the algorithm that powers blockchains
Practical Byzantine Fault Tolerance algorithm (pBFT) was introduced in late 90’s by Barbara Liskov and Biguel Castro. pBTF is an efficient solution for asynchronous systems to solve problems related to Byzantine Fault Tolerance.
pBTF consensus mechanisms try to ensure a practical Byzantine state machine for tolerating Byzantine nodes or failed nodes. The algorithm works by having each node in the network verify its own data, as well as the data of other nodes. The nodes then agree on the correct data; if they don’t agree, they will check the data again. This process is repeated until all nodes agree on the same data. In this way, the algorithm ensures that all nodes in the network are working together to reach a consensus and that the data is correct and up-to-date.
All nodes are assembled in sequence, and one of the nodes acts as a leader. The leader receives requests from clients, his role is to mediate between the client and the rest of the nodes in a network called backup nodes. Leader nodes can be selected round-robin from honest backup nodes when there is suspicion that an old leader is unavailable. Selecting an honest node is based on the ability to communicate between each node in the network and verifying its own data. One of the most important assumptions of the pBTF algorithm is that the number of invalid nodes in the network cannot equal 1/3 of all nodes.
How does it work?
pBTF consists of 3 main parts:
- Pre-prepare phase: the primary node broadcasts a message containing the proposed transaction to all other nodes in the system. The primary node also signs the message with its secret key.
- Prepare phase: the other nodes in the system verify the message using the primary node's signature and then sign the message with their own secret keys. This ensures that all nodes in the system have agreed on the proposed transaction. Node is considered as prepared only if received a pre-prepared message from the leader and also 2f+1 number of commit messages from other nodes (f is number of possible faulty nodes)
- Commit phase: all nodes in the system broadcast the signed message to all other nodes. This ensures that all nodes in the system have agreed on the proposed transaction and that the transaction can be considered valid.
<img>
Benefits
Compared to other consensus mechanisms, pBFT does not require high mathematical computations like PoW, so it is highly efficient in terms of energy consumption. pBFT-based consensus algorithms can be used for time-critical systems since it does not need to follow multiple confirmed by each node. Also the reward model is equitable because all nodes participate in verification.
Limitations
For more extensive networks, pBTF may cause scalability issues, also increasing the number of nodes may be problematic from a communication perspective.
Practical use cases of the pBFT algorithm
Well, pBFT it is not something that you can simply port to your smart contract and use it, but understanding how a particular blockchain works may become crucial when you try to pick the right one for your needs. pBFT guarantees high performance at a low cost. It’s widely used in private blockchains. The most popular private blockchain - hyper ledger - is powered exactly by this algorithm. Cosmos is also using this algorithm. As well as Neo, Quorum, and others.
Summary
PBFT is a powerful but complicated consensus algorithm. Fortunately, you don’t have to understand the details of the implementations to be able to use it :) It’s used by Hyperledger Fabric, Zilliqa and Tendermint in distributed consensus and voting to ensure that malicious actors cannot manipulate the data, while its improved efficiency ensures that the network can reach consensus quickly and efficiently.
Personally, I would love to use it in the voting systems
