Paper 2022/625
Dashing and Star: Byzantine Fault Tolerance with Weak Certificates
Abstract
State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use \textit{regular certificates} obtained from $2f+1$ (partial) signatures. We show that one can use \textit{weak certificates} obtained from only $f+1$ signatures to \textit{assist} in designing more robust and more efficient BFT protocols. We design and implement two BFT systems: Dashing (a family of two HotStuff-style BFT protocols) and Star (a parallel BFT framework). We first present Dashing1 that targets both efficiency and robustness using weak certificates. Dashing1 is also network-adaptive in the sense that it can leverage network connection discrepancy to improve performance. We show that Dashing1 outperforms HotStuff in various failure-free and failure scenarios. We then present Dashing2 enabling a \textit{one-phase} fast path by using \textit{strong certificates} from $3f+1$ signatures. We then leverage weak certificates to build Star, a highly scalable BFT framework that delivers transactions from $n-f$ replicas. Star compares favorably with existing protocols in terms of liveness, communication, state transfer, scalability, and/or robustness under failures. We demonstrate that Dashing achieves 47\%-107\% higher peak throughput than HotStuff for experiments on Amazon EC2. Meanwhile, unlike all known BFT protocols whose performance degrades as $f$ grows large, the peak throughput of Star increases as $f$ grows. When deployed in a WAN with 91 replicas across five continents, Star achieves an impressive throughput of 256 ktx/sec, 2.38x that of Narwhal.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. Eurosys 2024
- Keywords
- Byzantine fault toleranceBFTDashingStarweak certificatesconsensusblockchainparallel BFTpipelining
- Contact author(s)
-
duansisi @ tsinghua edu cn
bchainzhang @ aliyun com
suixiao @ mail sdu edu cn - History
- 2024-05-07: last of 7 revisions
- 2022-05-23: received
- See all versions
- Short URL
- https://ia.cr/2022/625
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/625, author = {Sisi Duan and Haibin Zhang and Xiao Sui and Baohan Huang and Changchun Mu and Gang Di and Xiaoyun Wang}, title = {Dashing and Star: Byzantine Fault Tolerance with Weak Certificates}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/625}, year = {2022}, url = {https://eprint.iacr.org/2022/625} }