Preface

Bytom blockchain has recently released BaaS (Blockchain as a Service) platform Bystack, which includes the sidechain consensus algorithm BBFT (Bystack Byzantine Fault Tolerance). This article will elaborate on the problems that BBFT addresses and analyze the major differences between BBFT and other consensus protocols. BBFT, whose principle is consistent with that of PBFT, is a variant of PBFT (Practical Byzantine Fault Tolerance). Before going deeper into BBFT, we must first get clear what PBFT is. Long before blockchain became popular thanks to bitcoin, PBFT had been around as a consensus protocol. Invented by Castro and Liskov in 1999, it is a 20-year-old classic design to solve a classic problem in distributed systems: the Byzantine Generals Problem. To this day, PBFT still contains many clever ideas that continue to inspire future generations to create better protocols.

Basic operating process of PBFT

PBFT is a three-stage protocol with two rounds of voting. Each View has a specific node as the Primary/Leader, which is responsible for broadcasting all nodes to vote. Each node will go through the three stages of Pre-prepare/Prepare/ Commit and decide whether to vote/go to the next stage based on the received message. After each node votes, it will send the message to all the other nodes. If the majority of nodes reach a consensus after a two-stage vote, each node can update the state machine and end the round. View-change is only executed when most nodes initiate it, when the current Leader does not execute the task normally, this can replace the current leader and ensure the normal operation of the protocol.

Features of PBFT

PBFT differs from Nakamoto consensus (blockchain) in features: PBFT is permissioned, leader-based, communication-based, safety-over-liveness.

• Permissioned: PBFT is not completely open, due to PBFT’s need for nodes to verify each other’s message and to accurately count the number of nodes; while blockchain features permissionless, which is open to all.
• Leader-based: In PBFT, one node is first elected as the “leader”, and the leader broadcasts its proposal to all other nodes. The most direct advantage of doing so is that it does not need to waste its own computing resources to fight for the opportunity to be a leader node. While the disadvantage is that only when the View changes would the leader node rotate, the opportunity to become the leader is not fair and there lacks incentive to join the network; while in blockchain, it chooses the block with the most difficult proof-of-work as the consensus among multiple proposals. Although this will cause waste of computing resources, the probability of becoming a block producer is roughly fair and proportional to the computing power.
• Communication-based: the security of PBFT is based on a three-stage vote, though it doesn’t have to consume a lot of computing power like proof of work, the communication complexity causes bottleneck in scalability – even though known as the most practical protocol, PBFT can’t scale to more than 1,000 nodes. But even more than that, PBFT uses the message authentication code (MAC), which requires each node to validate the message in per round of voting, as thus, the large number of signatures/verifications is another potential bottleneck.
• Safety over Liveness: PBFT can ensure safety under any network assumption (synchronous/asynchronous), which is almost impossible to lead to forks. Therefore, it is featured by Instant Finality. Blockchain, on the other hand, weighs liveness over safety. Its safety counts on a synchronous network and it is also quite common to have multiple consensuses (and fork), in this context, a certain number of blocks need to be “confirmed” to ensure that it’s secure and unlikely to fork the blockchain.

Problem of PBFT

Each node in the PBFT needs to do n-n communication in each round of voting. Let’s say n = 1000, then each consensus requires at least 100,000 communications. Although PBFT is considered the most practical protocol in the BFT family, this huge amount of communication requirements is still a bottleneck

How to improve efficiency?

• Signature aggregation

To improve efficiency, an intuitive thought is to avoid n-n communication. We can designate a node in the network as the coordinator to send/receive votes from each node, so that each node only needs to send messages to the coordinator, thus avoiding n-n communication. In such situations, however, the coordinator may act maliciously, because the coordinator can go to the next round of voting or update the status without actually receiving a specified number of messages. In such a context, we can use Threshold Signature to ensure the legitimate behavior of the coordinator. Threshold Signature can guarantee that only signatures that exceed the Threshold number (t-of-n) would be valid. That is, we can specify that only after the coordinator has collected 2f+1 threshold signatures can the coordinator proceed with the legitimate signature to push the consensus. Harmony FBFT (Fast Byzantine Fault Tolerance) is a BFT protocol that adopts signature aggregation for efficiency.

Figure 1: FBFT Signature Aggregation

• Pipelining design

Each content must go through two rounds of voting/three stages to reach a consensus. If there are m content, 2m votes need to be carried out. Pipelining reduces the number of votes. The basic idea behind Pipelining is: while each node is voting in the prepare stage of the i round, they are also voting in the commit stage on the previous i-1 content. In this way, redundant votes on the same content can be saved and efficiency is greatly improved. The idea was first seen in the HotStuff protocol published in 2018.

Figure 2: HotStuff Pipelining

• Minimal spanning tree

Another way to improve efficiency is to avoid having all the nodes participate in the consensus, which is exactly what Bytom’s BBFT adopts. In BBFT, nodes are classified into three types: Consensus Node/Gateway Node/Leader Node, which form a tree – Minimal Spanning tree of nodes in the network, possibly generated by distributed algorithms or supplied by external services. The leaf is Consensus Node, the root is Leader Node, and the rest is Gateway Node. Each node has a separate task: Consensus Node is responsible for voting; Gateway Node doesn’t have to vote, but had to aggregate the signatures sent by Consensus Node; Leader Node is responsible for exchanging messages with other Leader nodes. The operation flow in BBFT is as follows, the consensus process is the process message travels from tree root to leaves and back to the root.

Figure 3: BBFT: Minimal Spanning Tree

Figure 4: BBFT Process

How to ensure safety and liveness?

While introducing new technologies into PBFT to improve efficiency, it is also required to ensure the safety and liveness of the protocol itself. Let’s check how the protocol above ensures both.

• View-change

FBFT follows the View Change of PBFT, that is, it does not change the leader node in normal circumstances, unless there’re more than 2f+1 nodes initiate View Change. Although View Change itself is a mechanism that can replace a malicious leader node, it requires that the protocol must go through three stages to ensure the security of the protocol.

• Rotating leader

HotStuff, on the other hand, brings in the mechanism of rotating leader, which changes the leader node in every round, so as to avoid the high communication cost of View Change. Leader rotation is also common in many BFT family protocols, which is the mainstream security mechanism at present.

• Hybrid

Bytom’s BBFT takes the advantages from each BFT family by adopting the View Change and Rotating Leader, which offers a double safety. However, the current BBFT technical white paper has not proposed a two-round/three-stage consensus model, but only presents a one-round voting model and does not propose. In addition, the order of leader rotation is based on the Stake of each node which will be punished for violating the agreement.

Challenges BBFT faces

Taken together, BBFT has several noteworthy challenges. First of all, how to generate the Minimum Spanning Tree, how to balance decentralization and efficiency? Secondly, BBFT only adopts single round voting as the consensus, a fork may occur under the circumstance of bringing in View Change, and such network will also be susceptible to solar eclipse attacks. Last, after adopting Threshold Signature, Distributed Key Generation protocol must be introduced to jointly generate private keys, which will a potential factor that may cause bottlenecks, but has not been mentioned in its technical white paper.

Conclusion

This article provides a brief introduction about the features of PBFT and its problems in terms of efficiency, and compares the solutions of FBFT/HotStuff/BBFT protocols to the problem, finally summarizes the future challenges Bytom BBFT may face. Hope this could help readers better understand the BBFT protocol.

References

[1] Bytom Team. BBFT Whitepaper https://github.com/bystackcom/BBFT-Whitepaper/blob/master/whitepaper.pdf

[2] Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance http://pmg.csail.mit.edu/papers/osdi99.pdf

[3] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, Ittai Abraham. HotStuff: BFT Consensus in the Lens of Blockchain https://arxiv.org/abs/1803.05069

[4] Harmony Team. Harmony Technical Whitepaper https://harmony.one/whitepaper.pdf

This article is translated from “比原链BBFT如何让共识更快——兼论BBFT与FBFT/HotStuff的比较” written by Juin Chiu, a researcher with Unitychain, co-organizer of Taipei Ethereum Meetup, interested in consensus protocol/Sharding…