Cryptology ePrint Archive: Report 2021/671

Multi-Threshold Byzantine Fault Tolerance

Atsuki Momose and Ling Ren

Abstract: 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.

Category / Keywords: cryptographic protocols / Distributed Systems, Byzantine Fault Tolerance, Blockchain

Original Publication (in the same form): ACM CCS 2021

Date: received 23 May 2021, last revised 23 Sep 2021

Contact author: atsuki momose at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210923:060130 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]