**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 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.

**Category / Keywords: **public-key cryptography / accountability Byzantine consensus

**Date: **received 13 Sep 2021, last revised 22 Oct 2021

**Contact author: **pierrecivit at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20211022:102256 (All versions of this report)

**Short URL: **ia.cr/2021/1169

[ Cryptology ePrint archive ]