Practical byzantine fault tolerance
The practical byzantine fault tolerance algorithm is based on the story of the Byzantine army, known as Byzantine Generals' Problem, and was designed as a solution to the problem that the story presents (reference: https://www.usenix.org/legacy/events/nsdi09/tech/full_papers/clement/clement.pdf). The story goes that several divisions of the army are camping outside an enemy city. Each division is commanded by its own general. The generals can't communicate directly with each other—they can only communicate by messenger. They observe the enemy and need to decide on a common plan. However, not all of the generals are loyal and some may try to prevent the group from reaching an agreement. If the generals decide to attack the city, they need the majority of the entire Byzantine army to attack at the same time. To accomplish this goal, the generals need an algorithm or scheme that ensures that:
- All generals who are loyal can reach a consensus on the same plan of attack
- A small group of traitors are prevented from causing the loyal generals to adopt a bad plan
The loyal generals will do what the scheme tells them to do; whereas the traitors will do whatever they like. The scheme must guarantee this condition, regardless of the actions of the betrayers. Besides reaching an agreement, it should also be a rational plan. This problem can be complicated when there are a few traitorous generals who always cast a vote for a sub optimal plan, or may do so selectively, for example, when you have an uneven number of generals where two decide to attack and another two decide to retreat. The fifth general can then decide to send a message to the first group to attack and for the other group to retreat. The first group might not be so lucky attacking the enemy. The following diagram shows two of these scenarios:
Now let's alter this story so it represents our situation. The generals are the participating entities that run the blockchain, and the messengers are the means of communication across the network. The generals need to decide collectively whether the information submitted or a piece of the plan is valid or not. In our story, a valid piece of information would decide when and where to attack. Loyal generals are participants in the blockchain who ensure the integrity of the blockchain and that only valid information is accepted. The group of traitors are the entities who try to falsify information by submitting incorrect data and send assets that they don't own to other entities on the blockchain.
The PBFT scheme works as follows: Every participant (or general) maintains an internal state that is the specific status of the action plan. When a participant receives a message, or transaction, it is used in conjunction with their internal state to perform a computation. Based on the result of the computation, that participant can then decide what they think about the message and share that decision with the other participants. A consensus is reached based on the total of the decisions submitted by all participants. The consensus does not work by the majority of participants agreeing on only one decision submitted by a general, but that every decision that is sent from one participant to another is broadcast to all other participants in the network. So, if participant A sends a positive vote to participant B and a negative vote to participant C, then participant C would send their negative vote to participant B and conclude that participant A has sent two different votes. Participant B would also send a positive vote to participant C, also resulting in that same conclusion. This type of consensus requires less effort; that is, computing power and energy, but, in turn, it comes at the cost of anonymity because the system knows which decision each participant has sent. This type of consensus is used by blockchains, such as Hyperledger Fabric and Ripple. The following diagram shows the voting process where the Commander sends A to all Lieutenants, L1 sends A to L2, but L3 sends B to L2. From the point of view of Lieutenant 2, the majority of the votes is A:
