Exploring Scalability of BFT Blockchain Protocols through Network Simulations

Asserting that these novel BFT protocols can provide sufficient performance in realistic, large-scale systems requires careful evaluation of their runtime behavior. For this purpose, research papers describing these protocols contain evaluations with large-scale deployments that are conducted on cloud infrastructures like AWS, where experiments deploy up to several hundred replicas (for examples see References [13, 16, 36, 40, 59] and many more) to demonstrate a BFT protocol’s performance at large-scale, thus justifying its practicability in a blockchain setting.

Evaluations using real protocol deployments usually offer the best realism but can be costly and time-consuming, especially when testing multiple configurations. The high costs associated with benchmarking a system that runs hundreds of virtual machines on AWS hinder the rapid validation of prototype implementations during their development stage, including testing these implementations in failure scenarios. Thus, an interesting alternative for cheap and rapid validation of novel BFT protocol implementations can be to predict the system performance using simulations.

BFTSim [48] is the first simulator that was developed for an eye-to-eye comparison of BFT protocols, but it lacks the necessary scalability to be useful for the newer “blockchain generation” of BFT protocols (and apparently only up to \(n=32\) PBFT replicas can be successfully simulated [56]). Moreover, BFTSim demands a BFT protocol to be modeled in the P2 language [37], which is somewhat error-prone considering the complexity of BFT protocols and also time-consuming. A more recent tool [56] allows for scalable simulation of BFT protocols, but it unfortunately also requires a complete re-implementation of the BFT protocol in JavaScript. Further, this tool cannot make predictions on the system throughput and thus its performance evaluation is limited to observing latency.

In our approach, we address a critical gap in the state-of-the-art by introducing a simulation method for predicting BFT system performance that is highly scalable, without necessitating any re-implementation of the protocol. This key feature distinguishes our approach from conventional methods and represents a significant advancement for predicting BFT system performance in a practical way.

Emulation tries to duplicate the exact behavior of what is being emulated. Emulators like Kollaps can be used to reproduce AWS-deployed experiments with BFT protocols on a local server farm [25]. A clear advantage of emulation is how it preserves realism: BFT protocols still operate in real time and use real kernel and network protocols. In contrast to simulation, emulation is not similarly resource-friendly, as it executes the real application code in real time, thus requiring many physical machines at hand to conduct large-scale experiments.

Simulation decouples simulated time from real time and employs abstractions that help accelerate executions: Aspects of interest are captured through a model, which means the simulation only mimics the protocol’s environment (or also its actual protocol behavior if the application model is re-implemented). This has the advantage of easier experimental control, excellent reproducibility (i.e., deterministic protocol runs), and increased scalability when compared to emulation.

These benefits of emulation come at some cost: As a potential drawback remains the question of the validity of results, since the model may not fairly enough reflect reality. Furthermore, another existing limitation of all current BFT simulators is the need to modify or (usually) re-implement the BFT protocol to use it within a simulation engine.

In our approach, we address these limitations and aim at making simulation a useful approach for large-scale BFT protocol performance prediction:

This journal article is the extended version of a previously published conference paper [10]. In this version, we extend our research scope towards asynchronous BFT protocols, thus featuring insights derived from our simulations with Narwhal & Tusk and BullShark (the last listed contribution). Apart from novel experimentation and added discussions, this journal article also serves additional elaborations in the methodology section that were omitted due to space reasons in the previous conference version.

This article is structured as follows:

BFTSim. The first simulator specifically designed for traditional BFT protocols such as PBFT [14] or Zyzzyva [33] is BFTSim [48]. It is tailored for small replica groups, and its limited scalability renders BFTSim impractical for newer larger-scale BFT protocols. BFTSim requires modeling BFT protocols in the P2 language, which introduces error-proneness given the complexity of protocols, such as PBFT’s view change mechanism and Zyzzyva’s numerous corner cases. While capable of simulating faults, it only considers non-malicious behavior, lacking functionality to tackle sophisticated Byzantine attacks. BFTSim uses ns-2 for realistic networking and is resource-friendly, running on a single machine.

In contrast to BFTSim, our method allows us to experiment with real protocol implementations. We believe this has two main benefits: First, in some sense, it strengthens the validity of simulation results, because no error-prone re-implementation or modeling of a (very complex) BFT protocol is needed. Instead, the source code of the implementation serves as the single reference point (i.e., following the principle of code is law). This advantage also means that we can save a lot of time and evaluate a larger number of BFT protocols without much effort. It is easy for the developer of a new BFT protocol to adapt our method, because it only requires writing a new protocol connector and subsequently, the developer can compare his implementation against several already-supported BFT protocols in pre-defined benchmarking scenarios. Second, the presented methodology improves on the scalability aspect, because it can run with hundreds of replicas, which seems to be impossible for BFTSim (according to the experimentation of Reference [56], only up to 32 PBFT replicas and a limited number of clients is supported in BFTSim).

Scalable BFT Simulation. Recently, Wang et al. [56] introduced a BFT simulator that exhibits resource-friendliness, high scalability, and includes an “attacker module” with predefined attacks such as partitioning, adaptive, and rushing attacks. Similar to BFTSim, it requires the re-implementation of a BFT protocol (in JavaScript). One limitation to consider is that this simulator cannot yet measure throughput. Additionally, instead of emulating real network protocols, it assumes a high-level model to capture network characteristics. In this model, message delays are represented by a variable sampled from Gaussian or Poisson distributions, which must be defined in advance. Latencies are not derived from a real-world statistical latency map (thus, not reflecting heterogeneous latencies as they occur in real WANs).

In contrast to the simulator of Wang et al., the simulation method presented in this work does not require a re-implementation of the protocol in JavaScript and can also measure throughput, which is an important performance metric for blockchains. It should be also noted that the goals of the tool of Wang et al. and our tool were somewhat different: The authors of Reference [56] were interested in analyzing the potential impact of problematic network conditions (such as misconfigured timeouts) and attacks on BFT protocol latency, which makes it suitable for a validation purpose. Our method focuses on mimicking realistic deployment scenarios (such as planetary-scale deployments) with authentic latency maps to reason about the system performance (both latency and throughput) in real-world blockchain deployments.

Further Approaches. Furthermore, related work in behavior prediction includes stochastic modeling of BFT protocols [41] and a prior high-level simulation model that examined the impact of various message exchange patterns in BFT protocols, yet it falls short in terms of its suitability for analyzing real-world system metrics [47]. Moreover, validation capabilities of BFT protocols have been improved through the generation of unit tests using the Twins methodology [5].

To the best of our knowledge, the methodology for evaluating BFT protocols as presented in this work is the only one featuring a plug-and-play capability, which not only alleviates the evaluation of a broad variety of BFT protocols but also helps strengthen the validity of results, because no error-prone re-implementation is involved. We present a comparison of our approach with the two main competing methods in terms of features in Table 1.

Additionally, there are tools available for emulating or simulating a wide range of generic distributed systems. These tools can substantiate powerful building blocks for evaluating BFT protocols.

Emulators. Emulators such as Mininet [30, 35] and Kollaps [25] create realistic networks that run actual Internet protocols and application code with time synchronized with wall clock. Both approaches offer a high level of realism but are less resource-friendly. Mininet, although not scalable, had this issue addressed with the introduction of MaxiNet [57], enabling distributed emulation using multiple physical machines. Kollaps [25] is a scalable emulator but requires a significant number of physical machines for conducting large-scale experiments.

Simulators. Furthermore, ns-3 [43] is a resource-friendly and scalable network simulator, but it necessitates the development of an application model, thus impeding application layer realism (and preventing plug-and-play utility). Phantom [32] uses a hybrid emulation/simulation architecture: It executes real applications as native OS processes, co-opting the processes into a high-performance network and kernel simulation and thus can scale to large system sizes. The methodology presented in this work utilizes Phantom [32] to conduct the simulations, because its hybrid design allows for high-performance network simulations. We address open challenges that remain when using Phantom for BFT protocols and large-scale systems (see Section 4.2.1).

Several simulators have been developed for blockchain research, including Shadow-Bitcoin [38], the Bitcoin blockchain simulator [24], BlockSim [22], SimBlock [2], and ChainSim [54]. However, these simulators primarily focus on constructing models that accurately represent the features of Proof-of-Work (PoW) consensus mechanisms. As a result, as of the time of writing, they are less suitable for adoption when conducting BFT protocol research. Our proposed methodology is explicitly designed for BFT protocol research and is efficient in conducting large-scale simulations. Recent research also investigated how to faithfully simulate any BFT protocol that uses public coins and shared objects, like common coins as used in Block DAGs [4].

Vulnerability Detection. A few tools have been developed that aim to spot vulnerabilities in BFT protocols. Twins [5] is a unit test case generator designed to simulate Byzantine behavior through the replication of cryptographic IDs of replicas, thus producing protocol runs that feature equivocations or forgotten replica states. We plan to explore the integration of Twins within our simulation methodology in future work. Related work also investigates checking the liveness of streamlined BFT protocols [19]: The authors introduced the concepts of partial state and hot state to represent relevant information about protocol executions. It then employs temperature checking and lasso detection to identify recurring states, thus identifying possible liveness issues in an automated way. ByzFuzz [58] is a fuzzing technique designed to automatically detect bugs in implementations of BFT SMR protocols. BFTDiagnosis [55] is a security testing framework that can inject pre-defined “dishonest behavior” in specific replicas.

Performance Evaluation. Further, there are tools dedicated to the performance evaluation of BFT protocols. HyPerf [29] is a hybrid methodology based on model checking and simulation techniques for evaluating the performance of BFT protocols. BFT-Bench [27] is a benchmarking framework for evaluating and comparing BFT protocols in practice by scheduling experiments with BFT protocols on a local cluster of available machines. Diabolo [26] is a benchmarking suite to evaluate blockchain performance under various workload scenarios. Recently, a BFT testing framework was proposed for the Flow blockchain [31].

BFT protocols rely on synchrony models to capture temporal behavior and timing assumptions, which are important for the concrete protocol designs: In the asynchronous system model, no assumptions are made about upper bounds for the network transmission time or the time needed to perform local computations. These are said to complete eventually, i.e., they happen after an unknown (but finite) amount of time. In contrast, the synchronous system model assumes the existence of known upper bounds. A sweet spot is captured by the partially synchronous system model [21], which assumes a system may start in asynchrony but bounds exist that only hold eventually, i.e., after some unknown time span that is modeled by the global stabilization time (GST). Partial synchrony is employed in PBFT and many BFT protocols that followed. PBFT guarantees liveness only under partial synchrony but always remains safe even when the system is asynchronous.

Replicas repeatedly agree on a block of operations. To complete a single agreement instance, replicas usually go through multiple phases. In our approach, we model each of the phases such that it consists of several components:

Figure 2(a) illustrates these phases for the well-known PBFT protocol. The first phase, prepare, encompasses both dissemination (pre-prepare messages) and confirmation (pprepare messages). Quorum certificates contain votes from sufficient replicas to guarantee that no two different blocks can receive a certificate, thus committing the block. After an agreement completes, replicas execute the operations. An operation completes at the client if the client can verify that it was committed in some block and the execution result is correct.

In many BFT protocols, replicas operate in views, which behave orthogonal to the agreement instances (see Figure 2(a)). A view defines a composition of replicas, select leader(s), and in some cases establish the dissemination pattern. Some protocols re-use a single view under a stable leader (as long as agreement instances finish), as shown in Figure 2(a), but others may change the view for each stage or instance. In leader-driven BFT protocols, a dedicated view change phase synchronizes replicas, replaces the leader, and eventually ensures liveness by electing a new leader under whose regency, agreement instances succeed.

In 1999, Castro and Liskov proposed the Practical Byzantine Fault Tolerance (PBFT) protocol, which became known as the first practical approach for tolerating Byzantine faults [14]. PBFT’s practicality comes from its optimal resilience threshold (\(t= \frac{n-1}{3}\)) and its high performance, comparable to non-replicated systems.⁶ We show the message flow of PBFT’s normal operation in Figure 2(b). In PBFT, the leader collects client operations in a block and broadcasts the block in a pre-prepare message to all replicas. Subsequently, all replicas vote and collect quorum certificates through the messages prepare and commit, which are realized as all-to-all broadcasts. PBFT does not scale well for larger system sizes, because all operations are tunneled through a single leader, who must disseminate large blocks to all of the other replicas. This makes the leader’s up-link bandwidth a bottleneck for the whole system’s performance. Further, PBFT’s all-to-all broadcasts incur \(O(n^2)\) messages (and authenticators⁷) to be transmitted in the system. PBFT was followed by a lineage of BFT protocols exploring the possible design space (see References [1, 20] for an overview).

The HotStuff leader implements linear message complexity by gathering votes from all other replicas and disseminating a quorum certificate [60]. To reduce the cost of transmitting message authenticators, the leader can use a simple aggregation technique to compress \(n-t\) signatures into a single fixed-size threshold signature. This threshold signature scheme uses the quorum size as a threshold, and a valid threshold signature implies that a quorum of replicas has signed it. Consequently, the threshold signature has a size of \(O(1),\) which is a significant improvement over transmitting \(O(n)\) individual signatures.

The original implementation of HotStuff (we refer to it as HotStuff-secp256k1) is based on elliptic curves and does not feature signature aggregation (i.e., combining multiple signatures into a single signature of fixed size). Later, an implementation was made available by Reference [40] that uses bls signatures [12] (which we refer to as HotStuff-bls) that features signature aggregation. As depicted in Figure 2(c), the communication flow remains imbalanced where each follower replica communicates exclusively with the leader (which is the center of a star topology), while the leader has to communicate with all other replicas.

The use of a tree-based communication topology offers an advantage, as it distributes the responsibility of aggregating and disseminating votes and quorum certificates, thus relieving the leader. Kauri [40] is a tree-based BFT SMR protocol (see Figure 2(d)) that organizes all replicas in a 3-layered tree (the root, who is also the leader, internal replicas, and leaf replicas). Kauri introduces a timeout for aggregation to address failures of the leaf replicas. To handle the failure of internal tree replicas, Kauri employs a reconfiguration scheme, which guarantees to find a correct set of internal replicas, given that the number of failures lies below a certain threshold.

The added latency caused by the additional number of communication steps is mitigated through a more sophisticated pipelining approach (that can start several agreement instances per protocol stage) than the pipelining mechanism employed in HotStuff, which launches only a single agreement instance for each protocol stage.

Narwhal [17] is an asynchronous BFT mempool protocol, which can be utilized for the reliable dissemination of operations. The main idea for improving scalability in Narwhal & Tusk is to separate the dissemination of data from the actual consensus. The Narwhal primary protocol is used to implement a quorum-based, reliable Byzantine broadcast, which creates a directed acyclic graph (DAG). Every block in the DAG structure needs to be acknowledged by a quorum of \(2t+1\) replicas, whose signatures form a certificate of availability. In Narwhal, each replica runs a primary for the reliable broadcast of small pieces of metadata (the block headers) while the actual blocks are disseminated by the workers (there can be several workers on each replica). The primary protocol as depicted in Figure 3(a) is executed by all replicas (not just by \(r_0\) as illustrated in the figure) to reliably broadcast block headers. The certificates of availability guarantee that missing blocks can be requested by worker threads replicas that voted on the respective block headers.

Tusk [17] is the asynchronous BFT consensus algorithm that runs on Narwhal. To achieve consensus, all that is needed is to interpret the DAG created by Narwhal through a deterministic rule, committing all blocks in a specific order. For this purpose, Tusk uses a shared random coin to select a leader in every second round (this is done in retrospect after two more rounds, i.e., round \(i+2\) selects the leader of round i). If a leader has sufficient support of \(t+1\) replicas (see the blue links in Figure 3(b)), then its block is committed along with all of its causal history of blocks (see the green blocks in Figure 3(b)). In this figure, all five rounds are necessary to commit the green blocks. Round 4 is used to confirm the unknown leader L2 through voting, while round 5 is the round that determines that \(r_2\) is the chosen leader for \(L2\) through the random coin.

BullShark [50] is a successor of Narwhal & Tusk that aims to achieve lower latency in synchronous networks by adding a fast path, so it can be viewed as an optimization of the former for the partially synchronous setting. BullShark works on the same DAG structure, as depicted in Figure 3(b), but interprets it as a succession of waves, where each wave consists of four rounds in the DAG. Different from Tusk, BullShark distinguishes between steady-state leaders and fallback leaders. Each wave contains a single fallback leader (in the wave’s first round but selected in retrospect) and two predefined steady-state leaders (in the first and third rounds). The envisioned reduction in latency comes from the fact that the partially synchronous BullShark can commit one round faster than Tusk (two rounds are needed instead of three), since in Tusk an additional round is necessary to determine the leader in retrospective using the random coin.

One of the main benefits of our concrete methodology is the plug-and-play utility. This means we can guarantee application realism because the actual implementation is used to start real Linux processes that serve as the application model, thus duplicating actual implementation behavior. In particular, it means in regard to the application level the overall approach can be considered an emulation. At the same time, users experience no re-implementation or modeling effort, which can easily introduce errors due to the high complexity of BFT protocols and is also time-consuming.

Furthermore, simulating actual BFT protocol implementations rather than specifically crafted models is useful for the purpose of rapid prototyping and validation. Some implementation-level bugs in BFT systems might not occur in “common” \(n=4\) scenarios, and thus simulations can be utilized to conduct integration tests at a larger scale. Similarly, they can be utilized by developers to create integration/regression tests thinking “did my last commit negatively affect the protocol performance at a larger scale?” Some advantages generally exist when using simulations. First, simulations make it easy to investigate the runtime behavior of BFT protocols in an inexpensive way, much cheaper than real-world deployments. Nowadays more and more BFT protocol implementations are published open-source. Simulations make it easy to compare these protocols under common conditions and fairly reason about their performance in scenarios in which performance becomes network-bound. In particular, it is possible to explore the parameter space of both protocol parameters and network conditions in a systematic way and in a controlled environment, which even produces deterministic results.

Moreover, in our methodology, we can create large network topologies by using latency maps (such as those provided by Wonderproxy⁹), which can provide more regions than what most cloud providers, e.g., AWS, can offer. Last, simulation can also serve a didactical purpose. Simulations can help to achieve a better understanding of how BFT protocols behave at a large scale. For instance, the methodology can be used to support teaching in distributed system labs at universities by letting students gain hands-on experience with a set of already implemented BFT protocols.

Conducting large-scale simulations of BFT protocols requires tackling a set of challenges first. This is because of the following reasons:

As backend, we use Phantom, which employs a hybrid simulation/emulation architecture, in which real, unmodified applications execute as normal processes on Linux and are hooked into the simulation through a system call interface using standard kernel facilities [32]. An advantage of this is that this method preserves application layer realism as real BFT protocol implementations are executed. At the same time, Phantom is resource-friendly and runs on a single machine.

By utilizing its hybrid architecture, Phantom occupies a favorable position between the pure simulator ns-3 [43] and the pure emulator Mininet [35]. It maintains sufficient application realism necessary for BFT protocol execution while exhibiting greater resource-friendliness and scalability compared to emulators. Because Phantom strikes a balance that caters to the needs of BFT protocol research, we chose it as the backend for conducting protocol simulations.

We justify the selection of BFT protocols in the following way: Our main ambition was to showcase the impact of different communication strategies (i.e., all-to-all, star, and tree) towards system performance, and thus we selected a single “representative” BFT protocol for each strategy (namely, PBFT, HotStuff, and Kauri, respectively). We also employ representatives of asynchronous, leaderless BFT protocols (Narwhal & Tusk and BullShark). We present an overview of the BFT protocols and corresponding implementations that we employ in Table 2.

Our simulator runs on an Ubuntu 20.04 VM with 214 GB memory and 20 threads (16 threads used for simulation) on a host with an Intel Xeon Gold 6210U CPU with 2.5 GHz and 20 cores. Since the simulation runs in a virtual environment, performance results such as throughput or latency only depend on the experimental description (i.e., the network, replica, and client settings or induced faults at runtime) but not on the specification of the host. If a host with a faster CPU or more cores is utilized, then it can accelerate the time needed to conduct simulations and the host must provide sufficient RAM to support large-scale simulations.

In our first evaluation, we try to mimic the evaluation setup of the HotStuff paper (the arXiv version; see Reference [59]) to compare their measurements with our simulation results. Their setup consists of more than a hundred virtual machines deployed in an AWS data center; each machine has up to 10 Gbit/s bandwidth and there is less than 1 ms latency between each pair of machines (we use 1 ms in the simulation). The employed block size is 400. We compare against two measurement series: “p1024,” where the payload size of request and responses is 1,024 bytes and “10ms” with an empty payload, but the latency of all communication links is set to 10 ms. Our goal is to investigate how faithfully the performance of HotStuff can be predicted by regarding only the networking capabilities of replicas, which manifests at the point where the network becomes the bottleneck for system performance.

Observations. We display our results in Figure 6. The simulation results for the payload experiment indicate a similar drop in performance as the real measurements for \(n \ge 32\). For a small-sized replica group, the network simulation predicts higher performance: 200k op/s. This equals the theoretical maximum limited only through the 1 ms link latency, which leads to pipelined HotStuff committing a block of 400 requests every 2 ms. The difference in throughput decreases once the performance of HotStuff becomes more bandwidth-throttled (at \(n\ge 32\)). We also achieve close results in the “10ms” setting: 80 ms in the simulation vs. 84.1 ms real, and 20k op/s in the simulation vs. 19.2k op/s real for \(n=4\); but with an increasing difference¹⁴ for higher n, i.e., 84 ms vs. 106 ms and 19k.2 op/s vs. 15.1k op/s for \(n=128\). The problem is that this experiment does not use any payload, which makes the performance less sensitive to a network bottleneck (which is usually caused by limited available bandwidth).

In our next experiment, we validate BFT-SMaRt and PBFT¹⁵ by using measurements taken from Reference [59] and conducting our own experiment on a WAN that is constructed using four different AWS regions.

Moreover, we mimic the global experiment from Kauri [40], which uses a varying number of 100, 200, and 400 replicas. The global setup assumes replicas being connected over a planetary-scale network, in which each replica possesses only 25 Mbit/s bandwidth and has a latency of 100 ms to every other replica. We validate two implementations that were made by Reference [40]: HotStuff-bls, an implementation of HotStuff that uses bls instead of secp256k1 (this the originally implemented version of HotStuff), and Kauri, which enriches HotStuff-bls through tree-based message dissemination (and aggregation) and an enhanced pipelining scheme.

Observations. Figure 9 shows our results. Overall, we observe that for both implementations, the results we could obtain for system throughput are almost identical. At \(n=400\), for Kauri, we observe 4,518 op/s (real: 4,584 op/s), and for HotStuff-bls it is 230 op/s (real: 252.67 op/s).

We also evaluated on the latency of Kauri deciding blocks (as in Figure 8 from Reference [40]) comparing with the \(n=100\) and 25 Mbit/s latency experiment. While the real experiment in the Kauri paper reports a latency of 563 ms, in the simulation, deciding a block seems to take at least 585 ms.

Last but not least, we validate the protocols Tusk and Bullshark, which are the representatives of asynchronous BFT protocols. For this purpose, we collect real system data by running benchmarks on the AWS cloud infrastructure and replicate geographic deployment that is also used in References [17, 50], and we set a bandwidth limit of 25 Mbit/s on each host to make it more consistent with the global experiment from Kauri [40]. To reproduce the deployment scenario that was originally proposed in References [17, 50] and ensure geographic dispersion, we utilize 20 replicas and 20 clients, which are evenly distributed among the AWS regions Virginia, Sydney, Stockholm, Tokyo, and California. We repeatedly run the benchmark application from Reference [17] using incrementally higher operation sending rates on the clients until the system throughput is saturated and only latency increases. In the benchmark, clients send requests of 500 Bytes size and replicas employ a block header size of 5 KB.

Observations. Figure 10 displays our observations. As expected, we see that the real experimental data of Bullshark indicates a performance improvement when compared to Tusk, most notably, displaying a request latency that is about 2 seconds lower while maintaining similar (or slightly better) throughput levels. The simulation results track real-world observations quite closely. To be concrete, the throughput results show almost no deviation until the saturation point is reached (around a sending rate of 5k requests/s). Further, we found that the latency results of the simulation engine resemble the real-world observation but display minor but noticeable deviations: In Bullshark the simulated latency seems to be about 0.2 s slower than the real measurement data, while the simulated Tusk system displays latencies roughly 1 s higher than what we observed on AWS.

Further, we investigate how resource utilization, i.e., memory usage and simulation time, grows with an increasing system scale. For this purpose, we use the HotStuff-secp256k1 “10ms” simulations (which display a somewhat steady system performance for increasing system scale) on a Ubuntu 20.04 VM with 214 GB memory and 20 threads (16 threads used for simulation) on a host with an Intel Xeon Gold 6210U CPU at 2.5 GHz. We observe that active host memory and elapsed time grow with increasing system scale (see Figure 11). Based on the practically linear increase in memory utilization in Figure 11, we estimate that 512 replicas will need about 64 GiB memory, and it should be feasible to simulate up to 512 HotStuff replicas with a well-equipped host.

During our validations, we tested several open-source BFT frameworks (see Table 2) that have been written in different programming languages (C++, Rust, Java). From our experience, the Java-based BFT-SMaRt library was the most memory-hungry implementation, but we were still able to simulate \(n=128\) replicas on our commodity hardware server without problems, which strengthens our belief in the scalability and resource-friendliness of our methodology.

In our controlled environment, we simulate a real planetary-scale network, using 21 existing regions from the AWS cloud infrastructure, as shown in Figure 12. Latencies are retrieved from real latency statistics by the cloudping component of our frontend. Replicas vary in number and are evenly distributed across all regions. We use a 25 Mbit/s bandwidth rate, consistent with related research to model commodity hardware in world-spanning networks (e.g., see the global setup of Reference [40]). We utilize a variable number of clients to submit requests to the replicas. For instance, to unleash the maximum performance of Tusk and Bullshark, both protocols demand at least one client per replica, while the other BFT protocols can be often saturated with fewer replicas. In such cases, we carefully select both the client count and concurrent request rate to fully saturate and thereby maximize¹⁶ the observable system throughput.

In our simulations, we use the protocols PBFT, HotStuff-secp256k1, HotStuff-bls, and Kauri as representatives for partially synchronous BFT protocols and Tusk and Bullshark as representatives for asynchronous BFT protocols. Operations carry a payload of 500 bytes (roughly the average size of a Bitcoin operation), and the default block size is 1,000 operations for the partially synchronous protocols and 10 operations for the DAG-based protocols Tusk and Bullshark, since in these protocols every replica disseminates blocks. Each simulation deploys replicas and clients and then runs the BFT protocol for at least 120 seconds of simulated time within the environment.

In our first experiment, we evaluate the baseline performance of the BFT protocols in our constructed environment assuming that no failures happen. Further, we repeat each simulation while varying the system size n (namely, using a total of 64, 128, and 256 replicas) and varying the block size (for instance, by using both the default size of 1,000 operations and a block size that is more optimal for a protocol in respect to achieving lower latency). We denote variations in the employed block size by adding the postfix “-blockSize” to the protocol name.

In our next experiment, we study the impact of lossy network links on system throughput. For this purpose, we employ the same environment as in the last section with a fixed size of \(n=128\) replicas but introduce a packet loss of \(2\%\) on every network link.

In this experiment, we examine how well BFT protocol implementations can tolerate specific clients trying to overload the system. We use the usual \(n=128\) replicas setup. To overload the system, we let a specific “malicious” client submit a larger number (i.e., \(10\times\) more than in Section 6.2) of outstanding operations to the system during a short time interval of 120 s and investigate the impact on request latency that normal clients observe.

Finally, we investigate the crash fault resilience of the protocol implementations we tested, using our usual \(n=128\) replicas setup. We induce a crash fault at the leader replica at time \(\tau =60\) s. During our simulations, we noticed that the PBFT implementation’s¹⁹ view change did not work properly. After contacting the developers, we received a patch (a recent commit was missing in the public GitHub repository) that resolved the issue, at least for smaller systems. This illustrates how our methodology can help detect protocol implementation bugs.

After comparing multiple protocols, we conclude that currently, Kauri seems to promise the biggest advantage in terms of performance, achieving a throughput of over \(10\times\) that of HotStuff. Despite this, the novel asynchronous, DAG-based BFT protocols, Tusk and BullShark, emerge as serious competitors, since they can make progress even when the network does temporarily not behave synchronously. A crucial role plays their decentralized nature, which naturally allows them to distribute the operation load more evenly and prevents performance degradation attacks. The Narwhal mempool protocol on which Tusk and BullShark are based can still be potentially further improved: An interesting feature would be automatic load balancing, i.e., coordinating client workload as evenly as possible among all replicas’ available bandwidth capabilities. To make Narwhal even more efficient, it could be refined to use the BLS signature scheme instead of ECDSA so the certificates of availability that need to be disseminated by Narwhal are compressed and require less bandwidth when there are many replicas (i.e., \(n\ge 256\)). We found that the choice of cryptographic primitives does make a difference, in particular, the BLS variant of HotStuff surpassing HotStuff (EDCSA) at a larger scale. In Kauri, we think future work should address automating the configuration of protocol parameters to optimize performance in a WAN environment—in particular, we experienced that configuring the pipeline parameters by hand can be quite bothersome and result in many dry runs to find a reasonably good configuration. The PBFT implementation that we employed for our tests came with a buggy view-change mechanism—a problem that we were able to quickly resolve, thanks to the judicious use of our simulation methodology to run integration tests at large scale, thus spotting implementation-level bugs that can not be easily found in the commonly tested \(n=4\) test scenario.