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


Haibin Zhang, Beijing Institute of Technology; Sisi Duan, Tsinghua University, Zhongguancun Laboratory; Boxin Zhao, Zhongguancun Laboratory; Liehuang Zhu, Beijing Institute of Technology


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.

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 for asynchronous BFT.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {291048,
author = {Haibin Zhang and Sisi Duan and Boxin Zhao and Liehuang Zhu},
title = {{WaterBear}: Practical Asynchronous {BFT} Matching Security Guarantees of Partially Synchronous {BFT}},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {5341--5357},
url = {https://www.usenix.org/conference/usenixsecurity23/presentation/zhang-haibin},
publisher = {USENIX Association},
month = aug

Presentation Video