Paper 2021/1169

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

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


It is known that the agreement property of the Byzantine consensus problem among $n$ processes can be violated in a non-synchronous system if the number of faulty processes exceeds $t_0 =n/3$. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (i.e., when the number of faulty processes does not exceed $t_0$) and allowing correct processes to obtain a proof of culpability of $t_0 + 1$ faulty processes whenever correct processes disagree. We present four complementary contributions: (i) We introduce $ABC$: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. $ABC$ introduces an overhead of (1) only two all-to-all communication rounds and $O(n^2)$ additional bits in executions with up to $t_0$ faults, and (2) three all-to-all communication rounds and $O(n^3)$ additional bits in executions with more faults. (ii) We prove a tight lower bound on the communication complexity needed for any accountable Byzantine consensus protocol. In particular, we show that any algorithm incurs a cubic communication complexity in an execution in which disagreement occurs and that this bound is tight by applying $ABC$ to the binary DBFT consensus protocol. (iii) We demonstrate that, when applied to an optimal Byzantine consensus protocol, $ABC$ constructs an accountable Byzantine consensus protocol that is (1) optimal in solving consensus whenever consensus is solvable, and (2) optimal in obtaining accountability whenever disagreement happens. (iv) We generalize $ABC$ to other distributed computing problems besides the classic consensus problem. We characterize a class of agreement tasks, including reliable and consistent broadcast, that $ABC$ renders accountable.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
accountability Byzantine consensus
Contact author(s)
pierrecivit @ gmail com
2021-10-22: revised
2021-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre Civit and Seth Gilbert and Vincent Gramoli and Rachid Guerraoui and Jovan Komatovic},
      title = {As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1169},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.