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 $\mathrm{\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 $\mathrm{\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) $$ under optimistic condition and (ii) $$ (or $$) in the presence of $$ faults, which is more than a factor of two better than current state-of-the-art rotating-leader BFT protocols.