Paper 2021/671

Multi-Threshold Byzantine Fault Tolerance

Atsuki Momose and Ling Ren


Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present inherent trade-offs. Synchronous protocols tolerate up to $n/2$ Byzantine faults, while asynchronous or partially synchronous protocols tolerate only up to $n/3$ Byzantine faults. In this work, we generalize the fault thresholds of BFT and introduce a new problem called multi-threshold BFT. Multi-threshold BFT has four separate fault thresholds for safety and liveness under synchrony and asynchrony (or partial-synchrony), respectively. Decomposing the fault thresholds in this way allows us to design protocols that provide meaningful fault tolerance under both synchrony and asynchrony (or partial synchrony). We establish tight fault thresholds bounds for multi-threshold BFT and present protocols achieving them. As an example, we show a BFT state machine replication (SMR) protocol that tolerates up to $2n/3$ faults for safety under synchrony while tolerating up to $n/3$ faults for other scenarios (liveness under synchrony as well as safety and liveness under partial synchrony). This is strictly stronger than classic partially synchronous SMR protocols. We also present a general framework to transform known partially synchronous or asynchronous BFT SMR protocols to additionally enjoy the optimal $2n/3$ fault tolerance for safety under synchrony.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2021
Distributed SystemsByzantine Fault ToleranceBlockchain
Contact author(s)
atsuki momose @ gmail com
2021-09-23: revised
2021-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Atsuki Momose and Ling Ren},
      title = {Multi-Threshold Byzantine Fault Tolerance},
      howpublished = {Cryptology ePrint Archive, Paper 2021/671},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.