Paper 2018/394
AlmostSurely Terminating Asynchronous Byzantine Agreement Revisited
Laasya Bangalore, Ashish Choudhury, and Arpita Patra
Abstract
The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following wellknown results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable nontermination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee  with overwhelming probability and with probability one. The latter type termed as almostsurely terminating BAs are the focus of this paper. An eluding problem in the domain of almostsurely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction. In a setting with $n$ parties and an adversary with unbounded computing power controlling at most $t$ parties in Byzantine fashion, we present two almostsurely terminating BA protocols in the asynchronous setting: 1. With the optimal resilience of $t < \frac{n}{3}$, our first protocol runs for expected ${\cal O}(n)$ time. The existing protocols in the same setting either runs for expected ${\cal O}(n^2)$ time (Abraham et al, PODC 2008) or requires exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions that offer almostsurely terminating feature. 2. With the resilience of $t < \frac{n}{3 + \epsilon}$ for any $\epsilon > 0$, our second protocol runs for expected ${\cal O}(\frac{1}{\epsilon})$ time. The expected running time of our protocol turns constant when $\epsilon$ is a constant fraction. The known constructions with constant expected running time either require $\epsilon$ to be at least $1$ (FeldmanMicali, STOC 1988), implying $t < n/4$, or calls for exponential computing power from the honest parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to asynchronous verifiable secretsharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning. A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with $t < n/3$ and $t < \frac{n}{3 + \epsilon}$ guarantee $\Omega(n)$ and respectively $\Omega(\epsilon t^2)$ conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of our paper.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Major revision. PODC 2018
 Contact author(s)
 ashish choudhury @ iiitb ac in
 History
 20180501: received
 Short URL
 https://ia.cr/2018/394
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/394, author = {Laasya Bangalore and Ashish Choudhury and Arpita Patra}, title = {AlmostSurely Terminating Asynchronous Byzantine Agreement Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2018/394}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/394}}, url = {https://eprint.iacr.org/2018/394} }