A paper review: The BedRock of BFT: A Unified Platform for BFT Protocol Design and Implementation
In this article, I will summarize the preprint paper called BedRock. The BedRock was written by Mohammed Javad and other researchers like Mohammed Sadoghi.
In this post, I explain BedRock, a new tool that explores many BFT protocol design choices and generates a best fit protocol based on the developers' input. BedRock provides an API that takes the user’s design choices as input and maps it to the BFT design space to generate a preferable protocol that could match an existing or discover a new protocol. Of course, there is a restriction when BedRock maps the design choices to the design space because of the consensus properties.
BedRock characterizes BFT protocols based on different dimensions: environmental setting, a protocol structure, QoS features, and performance optimizations. Then, BedRock generates protocol implementations that can be used for experimentation and deployment.
To understand what is the design dimension, Figure 1 presents only two dimensions(the number of replicas and the number of commitment phases) on both design space and design choices in BedRock. Figure 3 provides an overview of how an application developer interacts with BedRock.
BedRcok design dimensions are classified into four categories: environmental settings and protocol structure that present the core dimensions of BFT protocols and are shared among all BFT protocols, a set of optional QoS features including order fairness and load balancing that a BFT protocol might support, and a set of performance optimizations for tuning BFT protocols.
To understand these classifications, let us start with environmental settings(ES). ES includes the number of replicas, communication topology, authentication, timers, responsiveness, and synchronization. The design choices in this category are adjusting the number of replicas from 3F+1 to 5F+1, changing topology from star to clique topology, etc.
Second, the protocol structure includes commitment strategy, the number of commitment phases, view-change, checkpointing, recovery, and client participation. Third, quality of service includes order fairness and load balancing. Fourth, the performance optimization includes out-of-order processing, request pipelining, parallel ordering, parallel execution, read-only requests processing, separating ordering and execution, trusted hardware, and request/reply dissemination.
PBFT is the base of all BFT protocols. For that, the paper expands PBFT by using the following design choices: linearization(message complexity of the protocol), phase reduction with increasing the number of replicas(redundancy), leader rotation, Non-responsive leader rotation, optimistic replica reduction, optimistic phase reduction, speculative phase reduction, speculative execution, optimistic conflict-free, resilience, authentication, robust, fair, and load balancer. All of the above are design choices where each one(or combination of more than one) results in a new variant of the PBFT. Table 1 shows how these categories represent in the design space of the BedRock.
Figure 6 shows how BedRock derives a wide range of BFT protocols using its design choices from PBFT. For example, let us start with PBFT towards Kauri. While PBFT has quadratic message complexity, three phases, and a stable leader, HotStuff has linear complexity, rotated leader, and 7 phases. Kauri improves the load balancing in HotStuff.
Figure 5 provides the communication complexity in each BFT protocol corresponding to PBFT.
That was all about how BedRock retrieves existing BFT based on design space and design choices. BedRock also discovers new BFT protocols called:
- Fast Linear BFT(FLB). It commits transactions in two phases with linear communication messages.
- Fast Tree-Based balanced BFT(FTB). instead of 7h in Kauri, FTB has only 3h phases by using different design choices like a rotated leader and phase reduction.
BedRock consists of the constraint checker that receives queries from end-users and finds all plausible points in the design space that satisfy the input query, the BFT protocol generator that generates a chosen protocol by an end-user, and the execution engine that enables end-users to experiment with generated BFT protocols.
Now, I will look for some of the interesting figures that show BedRock’s evaluation. BedRock uses batching with the batch size of 400 and a workload with client request/reply payload sizes of 128∕128 bytes.
PBFT should not be an issue because it deals with a stable leader! In HotStuff, I guess the reason is that the backup nodes failed which might be the candidate leaders.
Figure 26 shows the results of three batch sizes of 200, 400, and 800. Some protocols benefit from batching, while others are either saturated or degraded.
To sum up, this BedRock is a good tool that unifies many protocols and shows many cool things about BFT. The user should be familiar with the area in order to choose the right protocol based on suggested protocols. It will be nice if the paper shows proof of system correctness. I am worried about some design choices that might lead to a violation of the system properties.
