Optimal Communication Complexity of Byzantine Consensus under Honest Majority

Communication complexity is one of the most important efficiency metrics for distributed algorithms, but considerable gaps in the communication complexity still exist for Byzantine consensus, one of the most fundamental problems in distributed computing. This paper provides three results that help close some of these gaps. We present a Byzantine agreement (BA) protocol with quadratic communication complexity with optimal resilience $f < n/2$. This result shows the tightness of the quadratic lower bound by Dolev and Reischuk, which has been an open challenge for almost forty years. Our protocol is inspired by the BA protocol under unauthenticated model with $f < n/3$ (optimal for unauthenticated model) by Berman et al. As a practical direction, we present a Byzantine fault-tolerant (BFT) replication protocol, a.k.a., blockchain, with amortized linear communication complexity with $f \leq (1/2 - \varepsilon)n$ where $\varepsilon$ is any positive constant. As BFT replication is promised to be applied to large-scale systems, linear communication complexity (clearly optimal) is a mandatory today. To get this result, we present a Byzantine consistent broadcast (BCB) protocol with linear communication complexity with the same resilience $f \leq (1/2 - \varepsilon)n$. Our new BCB protocol relies on an expander graph and a threshold signature scheme. Finally, we also show a quadratic communication lower bound of BCB with $f \ge (1/2 + \varepsilon)n$. As BCB is one the easiest consensus problems and a build block of most BFT protocols, the result implies the impossibility of linear BFT protocol under corrupt majority.