Consensus Protocols for Realistic Distributed Systems

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavors of termination guarantee – with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely 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 (who can deviate from the protocol in any manner), we present two almost-surely terminating BA protocols in the asynchronous setting. Our first protocol runs for expected time linear in n and tolerates optimal corrupt parties i.e. t < n/3. Existing protocols in this setting either run for expected time quadratic in n or exponential computing power from the honest parties. In terms of communication complexity, our construction outperforms all known constructions that offer almost-surely terminating feature. Our Second protocol runs in constant expected running time (independent of n) and tolerates slightly less than one-third corrupt parties i.e. t < n/(3 + ε) for some constant ε > 0. All known constructions with constant expected running time either require ε ≥ 1 implying t < n/4 or calls for exponential computing power from the honest parties.

https://eprint.iacr.org/2018/394

My webpage: http://www.csa.iisc.ac.in/~arpita

My Lab webpage: http://www.csa.iisc.ac.in/~cris/