WaterBear: Practical Asynchronous BFT Matching Security Guarantees of Partially Synchronous BFT

Asynchronous Byzantine fault-tolerant (BFT) protocols assuming no timing assumptions are inherently more robust than their partially synchronous counterparts, but typically have much weaker security guarantees. We design and implement WaterBear, a family of new and efficient asynchronous BFT protocols matching all security guarantees of partially synchronous protocols. To achieve the goal, we have developed the local coin (flipping a coin locally and independently at each replica) based BFT approach-one long deemed as being inefficient-and designed more efficient asynchronous binary agreement (ABA) protocols and their reproposable ABA (RABA) versions from local coins. Our techniques on ABA and RABA are of independent interests and also allow us to build more efficient ABA protocols from common coins (distributively generating the same random coins for all replicas), helping improve various other protocols such as distributed key generation and BFT assuming trusted setup. We implemented in total five BFT protocols in a new golang library, including four WaterBear protocols and BEAT. Via extensive evaluation, we show that our protocols are efficient under both failure-free and failure scenarios, achieving at least comparable or superior performance to BEAT with much weaker security guarantees. Specifically, the most efficient WaterBear protocol consistently outperforms BEAT in terms of all metrics. For instance, when the number of replicas is 16, the latency of our protocol is about 1/8 of that of BEAT and the throughput of our protocol is 1.23x that of BEAT. Our work pushes the boundaries of asynchronous BFT, showing the strongest security levels that we know of and high performance can co-exist.