Paper 2022/625

Dashing and Star: Byzantine Fault Tolerance Using Weak Certificates

Sisi Duan
Haibin Zhang
Xiao Sui
Baohan Huang
Changchun Mu
Gang Di
Xiaoyun Wang

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 in this paper 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 demonstrate that Dashing1 outperforms HotStuff in various failure-free and failures scenarios. We further show in Dashing2 how to further enable a \textit{one-phase} fast path by using \textit{strong certificates} obtained from $3f+1$ signatures, a highly challenging task we tackled in the paper. We then leverage weak certificates to build Star, a highly efficient BFT framework that delivers transactions from $n-f$ replicas using only a single consensus instance. Star compares favorably with existing protocols in terms of censorship resistance, communication complexity, pipelining, state transfer, performance and scalability, and/or robustness under failures. We demonstrate that the Dashing protocols achieve 47\%-107\% higher peak throughput than HotStuff for experiments conducted on Amazon EC2. Meanwhile, unlike all known BFT protocols whose performance degrades as $f$ grows large, the peak throughput of Star keeps increasing as $f$ grows. When deployed in a WAN with 91 replicas across five continents, Star achieves an impressive throughput of 256 ktx/sec, 35.9x that of HotStuff, 23.9x that of Dashing1, and 2.38x that of Narwhal.

Available format(s)
Cryptographic protocols
Publication info
Byzantine fault toleranceBFTDashingStarweak certificatesconsensusblockchainparallel BFTpipelining
Contact author(s)
duansisi @ tsinghua edu cn
haibin @ bit edu cn
2023-06-23: last of 3 revisions
2022-05-23: received
See all versions
Short URL
Creative Commons Attribution


      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 Using Weak Certificates},
      howpublished = {Cryptology ePrint Archive, Paper 2022/625},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.