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

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
accountability Byzantine consensus
Contact author(s)
pierrecivit @ gmail com
History
2021-10-22: revised
2021-09-14: received
See all versions
Short URL
https://ia.cr/2021/1169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1169,
      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{https://eprint.iacr.org/2021/1169}},
      url = {https://eprint.iacr.org/2021/1169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.