Paper 2025/816
Randomized vs. Deterministic? Practical Randomized Synchronous BFT in Expected Constant Time
Abstract
Most practical synchronous Byzantine fault-tolerant (BFT) protocols, such as Sync HotStuff (S&P 2020), follow the convention of partially synchronous BFT and adopt a deterministic design. Indeed, while these protocols achieve O(n) time complexity, they exhibit impressive performance in failure-free scenarios. This paper challenges this conventional wisdom, showing that a randomized paradigm terminating in expected O(1) time may well outperform prior ones even in the failure-free scenarios. Our framework reduces synchronous BFT to a new primitive called multi-valued Byzantine agreement with strong external validity (MBA-SEV). Inspired by the external validity property of multi-valued validated Byzantine agreement (MVBA), the additional validity properties allow us to build a BFT protocol where replicas agree on the hashes of the blocks. Our instantiation of the paradigm, Sonic, achieves O(n) amortized message complexity per block proposal, expected O(1) time, and enables a fast path of only two communication step. Our evaluation results using up to 91 instances on Amazon EC2 show that the peak throughput of Sonic and P-Sonic (a pipelining variant of Sonic) is 2.24x-14.52x and 3.08x-24.25x that of Sync HotStuff, respectively.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Byzantine fault-tolerant (BFT)synchronous BFTrandomized BFTByzantine agreement
- Contact author(s)
-
sicherzoeng @ gmail com
huangbaohan @ bit edu cn
duansisi @ tsinghua edu cn
bchainzhang @ aliyun com - History
- 2025-05-09: approved
- 2025-05-08: received
- See all versions
- Short URL
- https://ia.cr/2025/816
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/816, author = {Xufeng Zhang and Baohan Huang and Sisi Duan and Haibin Zhang}, title = {Randomized vs. Deterministic? Practical Randomized Synchronous {BFT} in Expected Constant Time}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/816}, year = {2025}, url = {https://eprint.iacr.org/2025/816} }