Paper 2008/424

Asynchronous Byzantine Agreement with Optimal Resilience

Arpita Patra, Ashish Choudhury, and C. Pandu Rangan

Abstract

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting at most t out of the n parties. In comparison with the best known optimally-resilient ABA protocols of Canetti and Rabin (STOC 1993) and Abraham, Dolev and Halpern (PODC 2008), our protocol is significantly more efficient in terms of the communication complexity. Our ABA protocol is built on a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience. Our AVSS protocol significantly improves the communication complexity of the only known statistical and optimally-resilient AVSS protocol of Canetti et al. Our AVSS protocol is further built on an asynchronous primitive called asynchronous weak commitment (AWC), while the AVSS of Canetti et al. is built on the primitive called asynchronous weak secret sharing (AWSS). We observe that AWC has weaker requirements than AWSS and hence it can be designed more efficiently than AWSS. The common coin primitive is one of the most important building blocks for the construction of an ABA protocol. In this paper, we extend the existing common coin protocol to make it compatible with our new AVSS protocol that shares multiple secrets simultaneously. As a byproduct, our new common coin protocol is more communication efficient than all the existing common coin protocols.