Paper 2021/1169

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Pierre Civit and Seth Gilbert and Vincent Gramoli and Rachid Guerraoui and Jovan Komatovic

Abstract

It is known that the Byzantine consensus problem among $n$ processes cannot be solved in a non-synchronous system if the number of faulty processes exceeds $t_0$, where $t_0 = n/3$. Indeed, if the number of faulty processes is greater than the $t_0$ threshold, correct processes might never decide or (even worse) correct processes might decide and disagree. We focus in this paper on the latter case, where disagreement occurs. Specifically, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (i.e., whenever the number of faulty processes does not exceed the $t_0$ bound) and otherwise allowing correct processes to obtain a proof of culpability of (at least) $t_0 + 1$ faulty processes whenever correct processes disagree. We present three complementary contributions: (i) We give a simple transformation named $AB$ that enables any Byzantine consensus protocol to obtain accountability. Besides being simple, $ABC$ is also efficient: it induces an overhead of (1) two all-to-all communication rounds and $O(n^2)$ exchanged bits of information in all executions with up to $t_0$ faults, and (2) three all-to-all communication rounds and $O(n^3)$ exchanged bits of information otherwise. Therefore, any protocol that solves the Byzantine consensus problem with quadratic (or greater) communication complexity retains its complexity in solving the problem after our transformation. (ii) We show that $ABC$, despite its simplicity, allows for optimal communication complexity in solving the accountable Byzantine consensus problem. That is, (1) we prove that any accountable Byzantine consensus incurs cubic communication complexity whenever disagreement occurs, and (2) we demonstrate that the lower bound is tight by applying $ABC$ to any cubic Byzantine consensus protocol (e.g., binary DBFT). (iii) We show that $ABC$ is not limited to the Byzantine consensus problem. Specifically, we define a class of easily accountable agreement tasks and we prove that generalized $ABC$ transformation indeed provides accountability for such tasks. Important distributed tasks, like Byzantine reliable and Byzantine consistent broadcast, fall into this class.