Lamport-Shostak-Pease BFT Algorithm

Practical Byzantine Fault Tolerance (pBFT) is a consensus algorithm introduced in the late 90s by Barbara Liskov and Miguel Castro. pBFT was designed to work efficiently in asynchronous (no upper bound on when the response to the request will be received) systems. It is optimized for low overhead time. Its goal was to solve many problems associated with already available Byzantine Fault Tolerance solutions. Application areas include distributed computing and blockchain.

What is Byzantine Fault Tolerance?

Byzantine Fault Tolerance (BFT) is the feature of a distributed network to reach consensus (agreement on the same value) even when some of the nodes in the network fail to respond or respond with incorrect information. The objective of a BFT mechanism is to safeguard against the system failures by employing collective decision making (both – correct and faulty nodes) which aims to reduce to influence of the faulty nodes. BFT is derived from Byzantine Generals’ Problem.

Byzantine Generals’ Problem

The problem was explained aptly in a paper by LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE at Microsoft Research in 1982:

Imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching an agreement. The generals must decide on when to attack the city, but they need a strong majority of their army to attack at the same time. The generals must have an algorithm to guarantee that (a) all loyal generals decide upon the same plan of action, and (b) a small number of traitors cannot cause the loyal generals to adopt a bad plan. The loyal generals will all do what the algorithm says they should, but the traitors may do anything they wish. The algorithm must guarantee condition (a) regardless of what the traitors do. The loyal generals should not only reach agreement, but should agree upon a reasonable plan.

Byzantine fault tolerance can be achieved if the correctly working nodes in the network reach an agreement on their values. There can be a default vote value given to missing messages i.e., we can assume that the message from a particular node is ‘faulty’ if the message is not received within a certain time limit. Furthermore, we can also assign a default response if the majority of nodes respond with a correct value.

Leslie Lamport proved that if we have 3m+1 correctly working processors, a consensus (agreement on same state) can be reached if atmost m processors are faulty which means that strictly more than two-thirds of the total number of processors should be honest.

Types of Byzantine Failures:

There are two categories of failures that are considered. One is fail-stop (in which the node fails and stops operating) and other is arbitrary-node failure. Some of the arbitrary node failures are given below :

· Failure to return a result.

· Respond with an incorrect result.

· Respond with a deliberately misleading result.

· Respond with a different result to different parts of the system.

Advantages of pbft:

· Energy efficiency :

• pBFT can achieve distributed consensus without carrying out complex mathematical computations (like in PoW). Zilliqa employs pBFT in combination with PoW-like complex computations round for every 100th block.

· Transaction finality :

• The transactions do not require multiple confirmations (like in case of PoW mechanism in Bitcoin where every node individually verifies all the transactions before adding the new block to the blockchain; confirmations can take between 10-60 minutes depending upon how many entities confirm the new block) after they have been finalized and agreed upon.

· Low reward variance :

• Every node in the network takes part in responding to the request by the client and hence every node can be incentivized leading to low variance in rewarding the nodes that help in decision making.

How pBFT works?

pBFT tries to provide a practical Byzantine state machine replication that can work even when malicious nodes are operating in the system.
Nodes in a pBFT enabled distributed system are sequentially ordered with one node being the primary (or the leader node) and others referred to as secondary (or the backup nodes). Note here that any eligible node in the system can become the primary by transitioning from secondary to primary (typically, in the case of a primary node failure). The goal is that all honest nodes help in reaching a consensus regarding the state of the system using the majority rule.

A practical Byzantine Fault Tolerant system can function on the condition that the maximum number of malicious nodes must not be greater than or equal to one-third of all the nodes in the system. As the number of nodes increase, the system becomes more secure.

pBFT consensus rounds are broken into 4 phases (refer with the image below):

· The client sends a request to the primary(leader) node.

· The primary(leader) node broadcasts the request to the all the secondary(backup) nodes.

· The nodes(primary and secondaries) perform the service requested and then send back a reply to the client.

· The request is served successfully when the client receives ‘m+1’ replies from different nodes in the network with the same result, where m is the maximum number of faulty nodes allowed.

The primary(leader) node is changed during every view(pBFT consensus rounds) and can be substituted by a view change protocol if a predefined quantity of time has passed without the leading node broadcasting a request to the backups(secondary). If needed, a majority of the honest nodes can vote on the legitimacy of the current leading node and replace it with the next leading node in line.

Limitations of pBFT:

The pBFT consensus model works efficiently only when the number of nodes in the distributed network is small due to the high communication overhead that increases exponentially with every extra node in the network.

· Sybil attacks : The pBFT mechanisms are susceptible to Sybil attacks, where one entity(party) controls many identities. As the number of nodes in the network increase, sybil attacks become increasingly difficult to carry out. But as pBFT mechanisms have scalability issues too, the pBFT mechanism is used in combination with other mechanism(s).

· Scaling : pBFT does not scale well because of its communication(with all the other nodes at every step) overhead. As the number of nodes in the network increase(increases as O(n^k), where n is the messages and k is the number of nodes), so does the time taken to respond to the request.

Platforms using pBFT variants:

· Zilliqa – pBFT in combination with PoW consensus

· Hyperledger Fabric – permissioned version of pBFT

· Tendermint – pBFT + DPoS(Delegated Proof-of-Stake)

Variations of pBFT:

To enhance the quality and performance of pBFT for specific use cases and conditions, many variations were proposed and employed. Some of them are:

· RBFT – Redundant BFT

· ABsTRACTs

· Q/U

· HQ – Hybrid Quorum Protocol for BFT

· Adapt

· Zyzzyva – Speculative Byzantine Fault Tolerance

· Aardvark

BFT over Asynchronous systems

What’s “asynchronous” Byzantine fault tolerance (ABFT)?

When a decentralized network is Byzantine fault tolerant, it means that the honest members, or nodes, of a network can be guaranteed to agree on the timing and order (consensus) of a set of transactions. Regardless as to whether there are some nodes maliciously trying to prevent that consensus — even if as many as 1/3 of nodes are trying to negatively affect consensus by delaying transactions or otherwise corrupting things. This is the ‘fault tolerance’ of the network, meaning how many nodes can the network tolerate acting maliciously, but still come to an honest consensus.

The ‘asynchronous’ property of Byzantine fault tolerance overcomes a challenge of fault tolerance, which is that of timing. Many forms of Byzantine fault tolerance assume there is a maximum threshold of message latency when coming to a consensus. An asynchronous byzantine fault tolerant (ABFT) network eliminates this assumption and allows for some messages to be lost or indefinitely delayed.

An ABFT network allows for messages to be lost or indefinitely delayed and assumes only that at some point an honest node’s messages will eventually get through. It is much more challenging for an honest node to assess whether another node is not following the rules, if that node’s messages can be indeterminately delayed, but this scenario much better reflects that network reliability in the real world.