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
Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Usenix Security 2023
Keywords
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
History
2023-07-12: last of 3 revisions
2022-01-08: received
See all versions
Short URL
https://ia.cr/2022/021
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/021,
      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},
      url = {https://eprint.iacr.org/2022/021}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.