Paper 2021/1169

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

Pierre Civit, Sorbonne University
Seth Gilbert, National University of Singapore
Vincent Gramoli, University of Sydney
Rachid Guerraoui, École Polytechnique Fédérale de Lausanne
Jovan Komatovic, École Polytechnique Fédérale de Lausanne

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 - 1$. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed $t_0$) and allowing correct processes to obtain proof of culpability of (at least) $t_0 + 1$ faulty processes whenever correct processes disagree. We present four complementary contributions: 1) 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 (i.e., in the common case). 2) We define the accountability complexity, a complexity metric representing the number of accountability-specific messages that correct processes must send. Furthermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus algorithm incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the $ABC$ transformation to any Byzantine consensus protocol. 3) 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 with respect to the communication complexity, and (2) optimal in obtaining accountability whenever disagreement occurs with respect to the accountability complexity. 4) 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
Published elsewhere. 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
accountability Byzantine consensus
Contact author(s)
pierrecivit @ gmail com
seth gilbert @ comp nus edu sg
vincent gramoli @ sydney edu au
rachid guerraoui @ epfl ch
jovan komatovic @ epfl ch
2023-04-01: last of 2 revisions
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},
      doi = {10.1109/IPDPS53621.2022.00061},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.