Byzantine Fault Tolerance with Non-Determinism, Revisited

Sisi Duan; Yue Huang

Paper 2024/134

Byzantine Fault Tolerance with Non-Determinism, Revisited

Sisi Duan

, Tsinghua University

Yue Huang, Tsinghua University

Abstract

The conventional Byzantine fault tolerance (BFT) paradigm requires replicated state machines to execute deterministic operations only. In practice, numerous applications and scenarios, especially in the era of blockchains, contain various sources of non-determinism. Despite decades of research on BFT, we still lack an efficient and easy-to-deploy solution for BFT with non-determinism—BFT-ND, especially in the asynchronous setting. We revisit the problem of BFT-ND and provide a formal and asynchronous treatment of BFT-ND. In particular, we design and implement Block-ND that insightfully separates the task of agreeing on the order of transactions from the task of agreement on the state: Block-ND allows reusing existing BFT implementations; on top of BFT, we reduce the agreement on the state to multivalued Byzantine agreement (MBA), a somewhat neglected primitive by practical systems. Block-ND is completely asynchronous as long as the underlying BFT is asynchronous. We provide a new MBA construction significantly faster than existing MBA constructions. We instantiate Block-ND in both the partially synchronous setting (with PBFT, OSDI 1999) and the purely asynchronous setting (with PACE, CCS 2022). Via a 91-instance WAN deployment on Amazon EC2, we show that Block-ND has only marginal performance degradation compared to conventional BFT.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Byzantine fault tolerance BFT Multivalued Byzantine Agreement non-determinism
Contact author(s): duansisi @ mail tsinghua edu cn
y-huang22 @ mails tsinghua edu cn
History: 2024-01-31: approved; 2024-01-31: received; See all versions
Short URL: https://ia.cr/2024/134
License: CC BY

BibTeX

@misc{cryptoeprint:2024/134,
      author = {Sisi Duan and Yue Huang},
      title = {Byzantine Fault Tolerance with Non-Determinism, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2024/134},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/134}},
      url = {https://eprint.iacr.org/2024/134}
}