Paper 2023/679

ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path

Xiaohai Dai, Huazhong University of Science and Technology, University of Illinois Urbana-Champaign
Bolin Zhang, Zhejiang University, University of Illinois Urbana-Champaign
Hai Jin, Huazhong University of Science and Technology
Ling Ren, University of Illinois Urbana-Champaign

To reduce latency and communication overhead of asynchronous Byzantine Fault Tolerance (BFT) consensus, an optimistic path is often added, with Ditto and BDT as state-of-the-art representatives. These protocols first attempt to run an optimistic path that is typically adapted from partially-synchronous BFT and promises good performance in good situations. If the optimistic path fails to make progress, these protocols switch to a pessimistic path after a timeout, to guarantee liveness in an asynchronous network. This design crucially relies on an accurate estimation of the network delay Δ to set the timeout parameter correctly. A wrong estimation of Δ can lead to either premature or delayed switching to the pessimistic path, hurting the protocol's efficiency in both cases. To address the above issue, we propose ParBFT, which employs a parallel optimistic path. As long as the leader of the optimistic path is non-faulty, ParBFT ensures low latency without requiring an accurate estimation of the network delay. We propose two variants of ParBFT, namely ParBFT1 and ParBFT2, with a trade-off between latency and communication. ParBFT1 simultaneously launches the two paths, achieves lower latency under a faulty leader, but has a quadratic message complexity even in good situations. ParBFT2 reduces the message complexity in good situations by delaying the pessimistic path, at the cost of a higher latency under a faulty leader. Experimental results demonstrate that ParBFT outperforms Ditto or BDT. In particular, when the network condition is bad, ParBFT can reach consensus through the optimistic path, while Ditto and BDT suffer from path switching and have to make progress using the pessimistic path.

Available format(s)
Publication info
Published elsewhere. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
Byzantine fault toleranceByzantine generalsconsensusblockchain
Contact author(s)
xhdai @ hust edu cn
bolin 20 @ intl zju edu cn
renling @ illinois edu
2024-01-30: last of 3 revisions
2023-05-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaohai Dai and Bolin Zhang and Hai Jin and Ling Ren},
      title = {ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path},
      howpublished = {Cryptology ePrint Archive, Paper 2023/679},
      year = {2023},
      doi = {10.1145/3576915.3623101},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.