Paper 2020/406

Hybrid-BFT: Optimistically Responsive Synchronous Consensus with Optimal Latency or Resilience

Atsuki Momose, Jason Paul Cruz, and Yuichi Kaji

Abstract

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 $\Delta$. It states that a protocol makes a decision with latency on the order of actual network delay $ \delta $ 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 $\Delta + O(\delta)$ 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 leader-based 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) $3\delta$ under optimistic condition and (ii) $1.5\Delta + O(\delta)$ (or $3\Delta + O(\delta)$) 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.