Multi-Threshold Byzantine Fault Tolerance

Atsuki Momose, Ling Ren

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationCCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Electronic)9781450384544
StatePublished - Nov 12 2021
Event27th ACM Annual Conference on Computer and Communication Security, CCS 2021 - Virtual, Online, Korea, Republic of
Duration: Nov 15 2021Nov 19 2021

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Conference27th ACM Annual Conference on Computer and Communication Security, CCS 2021
Country/TerritoryKorea, Republic of
CityVirtual, Online


  • blockchain
  • byzantine fault tolerance
  • distributed systems

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Multi-Threshold Byzantine Fault Tolerance'. Together they form a unique fingerprint.

Cite this