Welcome to the resource topic for 2021/1169
Title:
As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!
Authors: Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, 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.
ePrint: https://eprint.iacr.org/2021/1169
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .