Simple and efficient asynchronous byzantine agreement with optimal resilience

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] − 1) out of n parties in Byzantine fashion. In this setting, we say that π is a t-resilient, (1 − ε)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if π satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A_t and terminates (i.e every honest party terminates π with probability at least (1 − ε). In this work, we present a new t-resilient, (1 − ε)-terminating ABA protocol which privately communicates O(Cn⁶ κ) bits and A-casts¹ O(Cn⁶ κ) bits, where ε = 2^−Ω(κ) and C is the expected running time of the protocol. 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 − ε)-terminating ABA protocol of [5] in the same settings, which privately communicates O(Cn¹¹ κ⁴) bits and A-casts O(Cn¹¹ κ² log(n)) bits, where ε = 2^−Ω(κ) and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient, 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates O(Cn⁶ log n) bits and A-casts O(Cn⁶ log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n²)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any κ < n² 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 κ), whereas ABA of Abraham et. al. takes polynomial expected time. 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 [5, 1].

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 [5] 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.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Joseph Y. Halpern, An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400804]
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806743]
• 4: R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute, Israel, 1995.
• 5: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 6: B. Chor and C. Dwork. Randomization in Byzantine Agreement. Advances in Computing Research, 5:443--497, 1989.
• 7: R. Cramer, I. Damg&#229;rd, S. Dziembowski, M. Hirt, and T. Rabin. Efficient Multiparty Computations Secure Against an Adaptive Adversary. In EUROCRYPT, pages 311--326, 1999.
• 8: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 9: M. Fischer. The Consensus Problem in Unreliable Distributed System. Technical Report, Department of Computer Science, Yale University, 1983.
• 10: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 11: M. Fitzi, J. Garay, S. Gollakota, C. Pandu Rangan, and K. Srinathan. Round-Optimal and Efficient Verifiable Secret Sharing. In TCC, pages 329--342, 2006.
• 12: Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece [doi>10.1145/380752.380853]
• 13: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 15: Michael O. Rabin, Randomized byzantine generals, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.403-409, November 07-09, 1983 [doi>10.1109/SFCS.1983.48]
• 16: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Reliability, Security

Keywords:
VSS, asynchronous networks, byzantine agreement, unbounded computing power