1 of 16

Tool: An Efficient and Flexible Simulator for Byzantine Fault-Tolerant Protocols

* National Taiwan University, Taiwan ^† Academia Sinica, Taiwan

Ping-Lun Wang*

R09922058@csie.ntu.edu.tw

Tzu-Wei Chao*

CheshireCatNick@gmail.com

Chia-Chien Wu*

gccbs02590@gmail.com

Hsu-Chun Hsiao*^†

hchsiao@csie.ntu.edu.tw

2 of 16

Byzantine Fault-Tolerant (BFT) Protocols

Reach consensuses through network messages
Tolerate less than 1/3 faulty nodes

Aircraft systems
Blockchain systems

2

3 of 16

BFT Protocols: Security Guarantees

3

Safety

Ensure consistent state of nodes

Liveness

Consensus will be reached

FLP impossibility^[1]: cannot be provided at the same time!

(in an asynchronous network)

Assume a partially-synchronous network

[1] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.

Impossibility of distributed consensus with one faulty process. (PODS '83).

Since BFT protocols are usually applied to critical systems, we need rigorous security proofs to make sure that they can function properly. A BFT protocol needs to satisfy two security guarantees. The first one is safety, which makes sure that all the honest nodes share a consistent state, and they will not generate conflict results when a consensus is reached. The second one is liveness, which ensures that a consensus will eventually be reached after a certain period of time.

[Animation]

However, FLP impossibility states that a BFT protocol cannot provide safety and liveness at the same time in an asynchronous network. Because most network environments in the reality are asynchronous, this caused a difficult situation for BFT protocol designers to design a protocol that satisfies safety and liveness at the same time.

[Animation]

To overcome this impossibility, a lot of BFT protocols assume a partially synchronous network, which allows them to achieve both safety and liveness.

4 of 16

Partially-Synchronous Network Assumption

4

Transfer time: bounded

After GST

(Global Stabilization Time)

Theoretical Analysis

Reality

Transfer time: ?

How can we evaluate the performance in a realistic setting?

Unbounded network delays

Network attacks

5 of 16

BFT Protocol Simulation

Why simulation?

5

Overall performance

Various network

Under attacks

High efficiency

Easy to deploy

… more

May differ from a real system

Calculation cost cannot be evaluated

Our work solves this problem by simulating BFT protocols under a real-world situation.

The reason we choose to use simulation to study a BFT protocol is that it provides several advantages over theoretical analysis or actual implementation of a BFT protocol.

The advantages are:

We can evaluate the overall performance rather than only calculating the communication complexity which theoretical analysis can only provide.
We can simulate various network environments, such as different distribution of network latencies and connectivity between nodes. Theoretical analysis can only assume a simple network model, and an actual implementation also requires some network simulation to achieve this.
We can simulate a BFT protocol under various attack scenarios, while these scenarious are usually too complex to analyze theoretically.

Other than these points, simulation can also provide high efficiency to reduce experiment time, and it is much easier to deploy when compared to a real implementation, and even more.

However, simulation also comes with some limitations. One example is that our simulation result can be different from the actual behavior of a real system, which can be caused by some implementation bugs of our simulator or the BFT protocol. Also, there are some aspects of a BFT protocol that cannot be easily captured by simulation, such as the calculation cost. We will describe how we attempt to overcome these limitations.

[04:20]

6 of 16

Our BFT Simulator

7 of 16

Our Simulator Compare to Others

There are already some BFT simulators… ^{[2, 3]}
What can we achieve?

1. Much better performance

Simplified network
Only protocol messages
Only connectivity between nodes and no topology

2. Global attacker

Byzantine nodes collude together
Network attacks
Adaptive attacker

7

[2] A. Singh, T. Das, P. Maniatis, P. Druschel, and T. Roscoe.

BFT protocols under fire, NSDI 2008

[3] S. Bano, A. Sonnino, A. Chursin, D. Perelman, and D. Malkhi.

Twins: White-Glove Approach for BFT Testing. arXiv 2020.

Before we introduce our simulator, I want to point out how our work stands out from the existing BFT simulators. Even though previous work already proposed some BFT simulators, out work provides several significant improvements.

[Animation]

First, our simulator has much better performance, which allows us to simulate more number of nodes.

[Animation]

How we achieved this is by using a simplified network. As we are focusing on the BFT protocols, the detailed behavior of the network is usually not important, such as TCP/IP and other network layers.

Therefore, we only transmit the protocol messages, and we neglect all other network layers’ messages.

We also do not simulate the topology of the network and only control the connectivity between nodes. This allows us to further simplify the network while preserves a high flexibility to add specific rules between nodes.

[Animation]

Another distinct characteristic of our simulator is that we model Byzantine behavior using a global attacker rather than a set of Byzantine nodes.

The advantages of a global attacker is that we can easily simulate attack scenarios that Byzantine nodes collude together.

Additionally, because a global attacker can access all network packets, we can also support a wide range of network attacks.

Furthermore, a global attacker can gather information from honest nodes before deciding which nodes are faulty nodes, allowing us to support an adaptive attacker model.

[06:10]

8 of 16

Structure

Four major components

Controller
Consensus module
Network module
Attacker module

Configuration file

BFT protocol and nodes
Network environment
Attacker

Simulation result

Time and message usage
Execution trace of each node

8

The diagram on the right illustrates the structure of our simulator. There are four major components.

The first one is the controller, which manages all events inside an event queue, and it will dispatch events to other compoenents, and other components can also register events with the controller.

The second one is the consensus module. This is where the BFT protocol lies in, and it controls the behavior of honest nodes. When nodes need to send messages to each other, they deliver their messages to the network module, which is the third component.

The network module determines the latency of each message, passing the messages to the attackers, and finally deliver the messages to the controller as message events.

The last component is the attacker module, which is a global attacker that can view or modify network messages. By modifying or inserting new messages, the attacker module can simulate the behavior of Byzantine nodes. By chaning the network latencies or dropping some of the messages, the attacker can simulate a network attack.

[Animation]

The user of our simulator needs to provide a configuration file which specifies which BFT protocol will be simulated and the number of nodes, the network environment, and the type of the attacker.

[Animation]

After the simulation, our tool generates a result that tells the time and message usage of the protocol, and the execution trace of each node for more detailed information.

[08:00]

9 of 16

BFT Protocol Implementation

Flexible design

BFT protocol logic
Handler for message and time events
Communication interface to the controller

We implemented

Three versions of ADD+ BA
Algorand Agreement
Async BA
PBFT
HotStuff with a naive view synchronizer
LibraBFT

Implementation validation

Validator module - PBFT

9

Let’s take a closer look at the consensus module. We provide a flexible design such that we can support several different kinds of BFT protocols. In addition, it is fairly easy to extend our simulator to support other BFT protocols. To add support to a new protocol, apart from its protocol logic, only a handler for message and time events and a communication interface to the controller are needed to be implemented.

[Animation]

We currently implemented the following BFT protocols: 1. three versions of Add+BA, 2. Algorand agreement, 3. async BA, 4. PBFT, 5. HotStuff with a naive view synchronizer, and 6. LibraBFT.

[Animation]

To make sure that our implementation can correctly reflect the behavior of the BFT protocol, we also added a validator module to our simulator to compare our simulation results with execution traces generated by other tools, and we used this validator to check the correctness of our PBFT implementation.

[09:10]

10 of 16

Attack Implementation

Extendable design

Attack logic
Handler for message and time events

Attacker models

Fail-stop
Network partition
Static and adaptive
Rushing

10

11 of 16

Experiment Results

12 of 16

Performance Comparison

12

13 of 16

Various Network Environments

13

14 of 16

Simulation With Attacks

14

↑ Different number of fail-stop nodes

↑ Network partition attack

These diagrams are the experiment results when we simulate BFT protocols under attacks. The left diagram is the execution time of BFT protocols when they try to reach a consensus with a certain amount of fail-stop nodes. We can see that when the number of fail-stop nodes is increased, most BFT protocols need more time to reach a consensus. In particular, HotStuff with a naive synchronizer has a huge efficiency degradation when the number of fail-stop nodes increases. This is because the naive synchronizer cannot easily keep the honest nodes in the same view, and when the number of honest nodes is decreased, it needs much longer time for them to synchronize to the same view.

The right diagram is the execution time of BFT protocols when they are under a network partition attack. The network partition is resolved 60 seconds after the execution, and most BFT protocols can reach a consensus almost immediately after the partition is resolved. However, HotStuff with a naive synchronizer spent much longer time to reach a consensus even when the partition is resolved. This is because this synchronizer uses a view doubling mechanism that exponentially grows its timeout when no consensus is reached, and so the timeout grows to a large value during the attack. After the partition is resolved, it still needs to wait for another long timeout before it can finally reach a consensus.

[13:20]

15 of 16

Visualizaing BFT Protocols

15

16 of 16

Conclusion

Simulation has several advantages over other methods, such as more efficient, support various environments, and easier to deploy
Our simulator supports a wide range of BFT protocols and attacks, and it has much better performance than existing work
Our simulator allows us to discover interesting behavior of BFT protocols, and we anticipate it to empower future research

16