Paper 2019/1460

Byzantine Fault Tolerance in Partially Connected Asynchronous Networks

Yongge Wang

Abstract

We review several widely deployed solutions for the Byzantine Fault Tolerance (BFT) problem and analyze their security in asynchronous networks. There are two types of widely accepted definitions for partial synchronous networks. In the Type I network, Denial of Service (DoS) attack is not allowed and in the Type II network, DoS attack is allowed before the Global Stabilization Time (GST). When DoS attack is allowed, the point-to-point communication channel and the broadcast channel are not reliable. We show that if either the broadcast channel or the point-to-point communication channel is not reliable (e.g., before GST) then several widely deployed BFT protocols would reach a deadlock before GST and the deadlock could not be removed after GST. Specifically, we show that if a malicious participant could broadcast a message to a subset of users instead of all users (before or after GST), then several widely deployed BFT systems would reach a deadlock. To make things worse, we show that, for most of our attacks, the adversary only needs to control one participant to carry out the attack instead of controlling $\lfloor \frac{n-1}{3}\rfloor$ participants. Thus these BFT protocols are not secure in the Type II partial synchronous networks. Furthermore, in these protocols, if a participant does not receive appropriate messages within a fixed time period, it initiates a view change process. After a view change, participants will no long accept messages from previous views. Thus our attacks on these protocols in Type II networks will work in the Type I network also. Consequently, these protocols are not secure in any of the widely accepted partial synchronous networks. It should be noted that Tendermint BFT has been adopted in more than 40% deployed Proof of Stake Blockchains such as Cosmos and Hyperledger burrow. Based on our analysis of BFT security requirements for partial synchronous networks, we propose a BFT protocol BDLS and prove its security in partial synchronous networks. The BDLS protocol could be used in several application scenarios such as state machine replication or as blockchain finality gadgets.