Hybrid BFT: Optimistically Responsive Synchronous Consensus with Optimal Latency or Resilience
Optimistic responsiveness was introduced to shorten the latency of a synchronous Byzantine consensus protocol that is inherently lower bounded by the pessimistic bound on the network delay It states that a protocol makes a decision with latency on the order of actual network delay d if the number of actual faults is significantly smaller than f which is the worst case allowed. In this paper, we investigate if a Byzantine consensus can simultaneously achieve (i) optimistic responsiveness, and (ii) optimal latency of O(d) in the presence of f faults. To do this, we provide a tight upper bound on the number of actual faults by showing matching feasibility and infeasibility results. Furthermore, we present a simple leaderbased Byzantine fault tolerant (BFT) replication protocol as a practical application. Even while being able to rotate leaders after every decision, our protocol simultaneously achieves average latency of (i) 3d under optimistic condition and (ii) 1.5 +O(d) (or 3 +O(d) in the presence of f faults, which is more than a factor of two better than current state of the art rotating leader BFT protocols.
IACR Cryptol. ePrint Arch.