Minimal Byzantine Fault Tolerance: Algorithm and Evaluation

Abstract

This paper presents two asynchronous Byzantine faulttolerant state machine replication (BFT) algorithms that are minimal in several senses. First, they require only 2 f +1 replicas, instead of the usual 3 f +1. Second, the trusted service in which this reduction of replicas is based is arguably minimal, so it is simple to verify and implement (which is possible even using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for nonspeculative and speculative algorithms, respectively 4 and 3 steps. Besides the obvious benefits in terms of cost, resilience and management complexity of having less replicas to tolerate a certain number of faults, our algorithms are simpler than previous ones (being closer to crash faulttolerant replication algorithms). The performance evaluation shows that, even with the trusted component access overhead, they can have better throughput than Castro and Liskov’s PBFT, and better latency in networks with nonnegligible communication delays. Comparing with the previous paper [49], this version presents a slight modifications of the algorithms, the proof of their correctness and a new performance evaluation.