Current state-of-the-art Byzantine fault-tolerant protocols state a limit on the number of Byzantine faults that can be tolerated. Of course, there are lower bounds stating that only a certain number of Byzantine faults can be tolerated in a given setting. On the other hand, it’s unclear why Byzantine faults are the primary faults one should consider! For instance, for high-stake transactions, often it is essential to guard its safety against adversaries who intend to earn by double-spending. Moreover, depending on their beliefs and external assumptions, two clients in the system may have entirely different interpretations of the state of the system. There may be conservative clients who wish to tolerate more faults and may wait for the state to be in a certain conservative state to commit. Or there may be clients who believe in stronger message timing assumptions. And just in case these clients are incorrect, all of them they may want to be able to update their assumptions and recover!
In a recent work called Flexible Byzantine Fault Tolerance, we address many of these intriguing questions. First, Flexible BFT introduces a new fault model called alive-but-corrupt faults — adversaries who intend to break safety of the protocol but not liveness. Flexible BFT shows that in the presence of such alive-but-corrupt faults (in addition to Byzantine faults), we can support a higher number of total faults than known in the distributed computing literature. Second, Flexible BFT enables the co-existence of clients with different beliefs and assumptions. This allows supporting clients having their own assumptions or using the additional external information they have access to. If the assumption made by a client is incorrect, some of her commits may be unsafe. But subsequently, the protocol allows updating assumptions and a recovery mechanism.
At a technical level, Flexible BFT makes two key contributions. First, it introduces a synchronous BFT protocol in which only the commit step requires to know the synchrony network delay bound and thus replicas execute the protocol without any synchrony assumption. Second, it introduces a notion called Flexible Byzantine Quorums by deconstructing the roles of different quorums in existing consensus protocols. A preliminary draft of this work is available at ArXiv and a short presentation is available here.