Paper 2022/021

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

Haibin Zhang, Beijing Institute of Technology
Sisi Duan, Tsinghua University
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. 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.

Available format(s)
Publication info
Published elsewhere. Major revision. Usenix Security 2023
asynchronous BFTblockchaininformation-theoretic BFTquantum securityasynchronous binary agreementABA
Contact author(s)
hchainzhang @ aliyun cn
duansisi @ tsinghua edu cn
zhaobx @ zgclab edu cn
liehuangz @ bit edu cn
2023-07-12: last of 3 revisions
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Haibin Zhang and Sisi Duan and Boxin Zhao and Liehuang Zhu},
      title = {WaterBear: Practical Asynchronous BFT Matching Security Guarantees of Partially Synchronous BFT},
      howpublished = {Cryptology ePrint Archive, Paper 2022/021},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.