Simplified Byzantine Fault Tolerance (SBFT) For Blockchain Applications
By Poya Rahmati on ALTCOIN MAGAZINE
One of the biggest areas of contention is the consensus algorithm that each blockchain employs. The consensus algorithm is what determines the speed, reliability, and scalability of the blockchain. In this article, I’d like to propose a new consensus algorithm called Simplified Byzantine Fault Tolerance (sBFT) as an improvement on the current standard, PBFT (Practical Byzantine Fault Tolerance) introduced by Miguel Castro and Barbara Liskov (link) that is currently used by projects such as Ripple.
It is no secret that blockchain technology has proven to be extremely useful in applications where immutability and trust of data are paramount. From fintech (i.e. cryptocurrencies) to healthcare, production, research, and other industries and applications. For this reason, there’s a huge demand for improvement in the blockchain capabilities.
Practical Byzantine Fault Tolerance (PBFT)
To learn about how PBFT works, you can read these great articles:
- https://medium.com/coinmonks/pbft-understanding-the-algorithm-b7a7869650ae
- https://medium.com/coinmonks/implementing-pbft-in-blockchain-12368c6c9548
To summarize, PBFT is a great solution to reaching consensus however it is not scalable due to the number of messages that need to be sent which will increase exponentially as the network grows. The max number of messages is calculated as follows:
M = 1 + 3f + 3f² + (3f)(3f+1) + 3f+1
where f is the number of allowable faulty nodes given network size N and calculated as:
f = (N-1)/3
So for a network of 7 nodes that would allow for 2 faulty/bad nodes, PBFT requires a min of 92 messages. For 10 nodes 191 messages and for 40 nodes 3,161 messages. And this needs to be repeated for every block that is created.
Why Simplified Byzantine Fault Tolerance (SBFT)?
SBFT requires about a 3rd of messages to be sent compared to PBFT and achieves consensus much faster. In most cases within 0.2s. Message count for SBFT is calculated by:
M = (3f+1)(2f+1) + 1
So for a network of 7 nodes, we require 36 messages. For 10 nodes 71 and for 40 nodes 1,081.
How Does SBFT Work?
SBFT is specifically designed for blockchain applications and works by introducing three new mechanisms:
- Nodes are grouped in delegations in increasing authority. 1st node is considered lead, 2nd node is considered second in charge and so on.
- Each new block is maintained by a specific delegation with pre-determined “Open” and “Close” timestamps and this information is shared with every other node in the delegation.
- Each node will use it’s internal time to decide when to take certain action and has specific instructions on how to act.
Basic Timeline
Imagine a delegation with 4 nodes (N=4) which allow for 1 faulty/bad node (f=1) and lets define t=0s as the “closing” time for a new block which is known by all nodes. Furthermore, every node contains all the pending transactions to be included in the new block.
At t=0s all nodes automatically begin the consensus process. They each generate a hash of their block and it’s transactions and send that information to every other node in the delegation. At the same time, each node starts listening for block hashes coming from other nodes.
Consensus Process
Lets look at the process from point of view of Node-1 (N1) which has the highest priority within the delegation. A(n) and B(n) are hashes coming in from all other nodes. In this case, N3 is a faulty node with a disagreeing hash (B3). For a 4 node system, we need agreement from at least 3 nodes.
As shown below, as soon as a third agreeing hash comes in, N1 considers the consensus to be achieved. In this case, since N1 is also the lead within the pool of agreeing with nodes, it is responsible for announcing the new block.
Other Cases
Let’s look at the case above from point of view of N2. In this case, N2 also achieves consensus but does nothing since it is not the lead node. This case study also illustrates that the order of incoming messages does not matter.
Timing Issue
Another benefit of an SBFT consensus is that the system does not need to wait for all responses and is robust even if lead nodes are faulty or late.
In the case below, lets consider N=5 which requires at least 3 agreeing nodes. Looking at the case from point of view of N2, we can see that if consensus is achieved with the missing response from N1, then N2 is promoted to lead and is tasked with announcing its block to the network. The delegation is also able to handle late messages from would-be lead nodes. This is acceptable because we can be sure that any node that is announcing a block has achieved consensus within the delegation so N1’s response doesn’t matter after consensus.
Conclusion
Each node in an SBFT consensus is capable of acting autonomously without the need to communicate back and forth with other nodes. The entire consensus is achieved with only one burst of outgoing messages.
