CryptoDB
Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t < n / 3 parties in Byzantine fashion. In these settings, we say that \pi is a $t$-resilient, $(1-\epsilon)$-terminating Asynchronous Byzantine Agreement (ABA) protocol, if $\pi$ satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A_t and terminates (i.e every honest party terminates $\pi$) with probability at least $(1-\epsilon)$. In this work, we present a new $t$-resilient, $(1-\epsilon)$-terminating ABA protocol which privately communicates O(C n^{5} \kappa) bits and A-casts O(C n^{5} \kappa) bits, where $\epsilon = 2^{-O(\kappa)$ and C is the expected running time of the protocol. Here A-Cast is a primitive in asynchronous world, allowing a party to send the same value to all the other parties. Hence A-Cast in asynchronous world is the parallel notion of broadcast in synchronous world. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known $t$-resilient, $(1-\epsilon)$-terminating ABA protocol of \cite{CanettiSTOC93} in the same settings, which privately communicates O(C n^{11} \kappa^{4}) bits and A-casts O(C n^{11} \kappa^2 \log(n)) bits, where $\epsilon = 2^{-O(\kappa)} and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of \cite{CanettiSTOC93}, while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al \cite{DolevAsynchronousBAPODC2008} proposed a $t$-resilient, $1$-terminating (called as almost-surely terminating in \cite{DolevAsynchronousBAPODC2008}) ABA protocol which communicates O(C n^{6} \log{n}) bits and A-casts O(C n^{6} \log{n}) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n^2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any \kappa < n^3 \log{n}, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and \kappa), whereas ABA of Abraham et. al. takes polynomial expected time. However, it should be noted that our ABA is only $(1-\epsilon)$-terminating whereas ABA of Abraham et al. is almost-surely terminating. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of \cite{CanettiSTOC93,DolevAsynchronousBAPODC2008}. For designing our ABA protocol, we present a novel and simple asynchronous verifiable secret sharing (AVSS) protocol which significantly improves the communication complexity of the only known AVSS protocol of \cite{CanettiSTOC93} in the same settings. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest. |
BibTeX
@misc{eprint-2008-18158,
title={Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience},
booktitle={IACR Eprint archive},
keywords={foundations /},
url={http://eprint.iacr.org/2008/424},
note={ arpitapatra_10@yahoo.co.in 14285 received 1 Oct 2008, last revised 9 Feb 2009},
author={Arpita Patra and Ashish Choudhary and C. Pandu Rangan},
year=2008
}