How to make the consensus faster than the original chain BBFT – a comparison between BBFT and FBFT/HotStuff

Foreword

Recently, the BYTOM technical team released the Bystack blockchain BaaS platform, including the side chain consensus algorithm BBFT (Bystack Byzantine Fault Tolerance). In this article, I will explain the problems that the original chain BBFT tries to solve and analyze the main differences between BBFT and other consensus agreements. BBFT is a variant of PBFT, and its principle is in line with PBFT. If you want to understand the ingenuity of BBFT, you must enter the PBFT context. PBFT existed in the world as a consensus agreement long before the blockchain was dominated by Bitcoin. Invented in 1999 by Castro and Liskov, it is a classic design with a 20-year history. It was invented to solve a classic problem in distributed systems: the Byzantine general. To this day, PBFT still contains a lot of ingenuity worthy of repeated scrutiny, and continues to inspire future generations to invent better agreements.

PBFT basic operational process

PBFT is a three-phase protocol with two rounds of voting. Each view has a specific node as the primary node (Primary/Leader), which is responsible for informing all nodes to enter the voting process. Each node will go through the three stages of Pre-prepare/Prepare/Commit and decide whether to vote/enter the next stage according to the received message. Each node will send the message to all other nodes after the vote is completed. If a node gets a majority consensus after two-stage voting, each node can update the state of the machine and end the round. View-change is performed only when most nodes initiate. When the current leader node does not perform the task normally, this can replace the current leader node and ensure the normal operation of the protocol.

PBFT characteristics

PBFT has quite different characteristics from the Sakamoto consensus (blockchain): PBFT is a licensing, leader-based, communication-based, security-heavy consensus agreement.

• Permissioned: PBFT is not completely open. This is because PBFT needs to enable nodes to verify each other's messages and accurately grasp the number of nodes. The blockchain is a non-licensing system that is open to anyone. .
• Leader-based: First, the leader is decided, and then the leader sends the proposal. The most direct benefit is that you don't need to waste your computing resources to win the opportunity to lead the node. The disadvantage is that the opportunity to become the leader node is unfair and lacks the incentive to join the network only when the viewport changes. The blockchain is the block with the highest difficulty in selecting multiple work proposals. Although this will result in a waste of computing resources, the probability of becoming a blocker is roughly fair, which is directly proportional to the computing power.
• Communication-based: PBFT's security is based on 3-stage voting. Although it doesn't have to consume a lot of computing resources as proof of work, the huge amount of communication also creates a bottleneck for scalability—even the most practical. PBFT cannot be extended to more than 1000 nodes. Not only that, PBFT uses a message authentication code (MAC), which requires each node to verify a message for each round of voting. A large number of signatures/verifications are another potential bottleneck.
• Safety over Liveness: PBFT ensures security regardless of network assumptions (synchronous/asynchronous), and it is almost impossible to have bifurcation, so it has the characteristics of Instant Finality. In contrast, the blockchain is more active than security. Its security depends on the synchronous network. It is quite common to have multiple consensus (and branching). It needs to be confirmed by a certain number of blocks. In order to ensure that it is no longer enough to be separated.

PBFT problem

First, each node in the PBFT needs to communicate nn in each round of voting. Assuming n is 1000, each consensus requires at least 100,000 communications, although PBFT is already the most practical protocol among the BFT family. Such a huge amount of communication demand is still the bottleneck of expansion.

• The 17-year plunge will be repeated? Tens of thousands of BTCs have been transferred to the exchange
• Do DApp with a smartphone, Samsung releases blockchain development kit
• Market analysis: the next kill or unsustainable, the market continues to fluctuate with a high probability

How to improve efficiency?

Aggregate signature

In order to improve efficiency, an intuitive idea is to avoid nn communication. We can specify a node in the network as a coordinator to send/receive votes for each node, so that each node only needs to send a message to the coordinator, thus avoiding the communication of nn. However, in such a situation, the coordinator has the potential to do evil because the coordinator can perform the next round of voting or status updates before actually receiving the specified number of messages. Therefore, we can use the Threshold Signature to ensure the proper behavior of the coordinator. The signature of the threshold can guarantee that the signatures that exceed the number of thresholds (t-of-n) are valid. In other words, we can specify that only when the coordinator gathers 2f+1 thresholds, the coordinator can continue to advance the consensus with a legal signature. Harmony FBFT is a BFT family protocol that uses aggregated signatures to increase efficiency.

Figure 1: FBFT Signature Aggregation

Pipeline design

Each content must go through two rounds of voting / three stages to reach a consensus, if there are m content, you need to perform 2m voting. Pipelining can reduce the number of votes. The basic idea is as follows: Let each node vote in the prepare phase of the i-th round and also the commit phase of its previous content i-1. By doing so, you can save redundancy in repeating the same content and greatly improve efficiency. This idea was first seen in the HotStuff protocol published in 2018.

Figure 2: HotStuff Pipelining

Only let some nodes participate in the consensus: minimum spanning tree

Another way to improve efficiency is to avoid having all nodes participate in the consensus, which is exactly what the original chain BBFT takes. In BBFT, there are three types of nodes: Consensus Node/Gateway Node/Leader Node. These nodes form the structure of the tree. The tree is the minimum spanning tree (Minimal Spanning Tree) of the nodes in the network, which may be derived by distributed algorithms, or It is provided by an external service. The node of the leaf is the Consensus Node; the root of the tree is the Leader Node; the other part is the Gateway Node. Each node has a separate task: the Consensus Node is responsible for voting; the Gateway Node does not need to participate in the voting, but must be responsible for aggregating the signature sent by the Consensus Node; the Leader Node is responsible for exchanging messages with other Leader Nodes. The operation process of BBFT is shown in the figure below. The consensus process of BBFT is the process of the message spreading from the root to the leaf and back to the root.

Figure 3: BBFT: Minimal Spanning Tree

Figure 4: BBFT Process

How to ensure safety and liveness?

While bringing new technologies to PBFT to increase efficiency, it is also necessary to ensure the security and activity of the protocol itself. Let's take a look at how the above agreement is to ensure both.

View-change

FBFT follows the PBFT view change, that is, the leader node is not replaced under normal conditions, and the leader node is changed only when more than 2f+1 nodes initiate the view change. Although the view domain transformation itself is a mechanism that can replace the evil leader node, it also requires the protocol to have three phases to ensure the security of the protocol (ie, no separation).

Rotating Leader

HotStuff, on the other hand, introduces a mechanism for the rotation of the leader nodes, replacing the leader nodes in each round, thus avoiding the high cost of communication costs. Leadership rotation is also common in many BFT family agreements, which is currently the mainstream of security mechanisms.

Hybrid

Compared with the original chain BBFT, each company's director, while applying the visual field transformation and the leadership node rotation, is equivalent to double insurance. It is worth noting, however, that the current BBFT technical white paper has only one round of voting models and does not propose a two-round voting/three-stage consensus model. In addition, the order of the leader node rotation will also be based on the stake of each node. If the node violates the agreement, the node will be punished.

BBFT's challenge

Based on the above analysis and comparison, BBFT currently has several significant challenges. First of all, is the generation of the minimum spanning tree, how to balance decentralization and efficiency? Secondly, BBFT only adopts a single round of voting as a consensus. In the case of introducing a view change, branching may occur, and such a network may also be threatened by eclipse attacks. Finally, under the premise of introducing the signature of the threshold, it is necessary to introduce the distributed key generation (Distributed Key Generation) to jointly generate the private key. This part is not mentioned in the technical white paper, but it is a potential factor that may cause a bottleneck.

Conclusion

This article introduces the characteristics and performance of PBFT, and compares the solutions of FBFT/HotStuff/BBFT for performance problems. Finally, it summarizes the future challenges of the original chain BBFT, hoping to help readers understand the essence of BBFT. .

Reference material

• Than the original chain BBFT
• PBFT
• HotStuff
• Harmony FBFT

Author: Juin Chiu, Unitychain researcher & Taipei Ethereum Meetup co-organizer, the current research interests consensus agreement / slicing / autonomous status.

This article authorizes the launch of Babbitt Information by the author.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!