Paper 2025/816

Randomized vs. Deterministic? Practical Randomized Synchronous BFT in Expected Constant Time

Xufeng Zhang, Beijing Institute of Technology
Baohan Huang, Beijing Institute of Technology
Sisi Duan, Tsinghua University
Haibin Zhang, Yangtze Delta Region Institute of Tsinghua University, Zhejiang
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.