Cryptology ePrint Archive: Report 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 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 ]