Paper 2025/816 Original: eprint.iacr.org/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.
- History
- 2026-02-12: last updated
- 2025-05-08: published
- Short URL
- https://ia.cr/2025/816
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}