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

Xufeng Zhang; Baohan Huang; Sisi Duan; Haibin Zhang

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 BFT randomized BFT Byzantine 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}
}