Optimal algorithms for Byzantine agreement

ABSTRACT

We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments. Given private communication lines, we show that n processors can reach BA in expected constant time in a syncronous network if any < n/3 faults occur in an asynchronous network if any < n/4 faults occur For both synchronous and asynchronous networks whose lines do not guarantee private communication, we may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries. (Thus, in this setting, we tolerate up to n/3 faults even in an asynchronous network.)

REFERENCES

• B: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• Be: J. Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret, 1986 Crypto
• BGW: 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]
• Bl: G. Blakely, Safeguarding Cryptographic Keys, Proc. AFIPS June 1979 NCC Vol. 48, pp.313-317.
• Br: G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22180]
• C: B. A. Coan, Achieving consensus in fault-tolerant distributed computer systems: protocols, lower bounds, and simulations, Massachusetts Institute of Technology, Cambridge, MA, 1987
• CC: B. Chor and B. Coan, A Simple and Efficient Randomized Byzantine Agreement Algorithm, IEEE Transactions on Software Engineering, Vol. SE-11, No.6 1985.
• CCD: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• CD: B Chor, and C. Dwork, Randomization in Byzantine Agreement, To appear in Randomness and Comput~tion edited by Silvio Micali.
• CGMA: B. Chor, S. Goidwasser, S Micali, and B. Awerbuch Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, 1985 FOCS.
• CMS: Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323610]
• D: D. Dolev, The Byzantine Generals Strike Again, Journal of Algorithms, Vol. 3, No. 1, pp. 14-30, March 1982.
• Dolev, Dwork and Stockmeyer 1987: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• DD: D. Dolev and C. Dwork, manuscript.
• DFFLS: D. Dolev, M. Fischer, R. Fowler, N. Lynch, and H. Strong, An Efficient Algorithm for Byzantine Agreement Without Authentication, Information and ControI,Vol. 52, Nos. 1-3, pp. 257-274, Jan-Maxch/1982.
• DS: D. Dolev and H. Strong, Authenticated Algorithms for Byzantine Agreement, IBM Technical Report RJ3416, M arch 1982.
• DSS: C. D work, D Shmoys and L. Stockmeyer, Flipping Persuasively in Constant Expected Time, 1986 FOCS.
• F: P. Feldman, A Practical Scheme for Non-lnteractive Verifiable Secret Sharing, 1987 FOCS
• F1: P. Feldman, Optimal Algorithms for Byzantine Agreement, PhD. Thesis, to appear.
• FLP: 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]
• FL: M. Fischer and N. Lynch, A Lower Bound for the Time to Assure Interactive Consistency, Information Processing Letters, 14(4), pp.183-186, 1982.
• FM: P. Feldman and S. Micali, Byzantine Agreement in Constant Expected Time, 1985 FOCS.
• GMR: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• GMW: O, Goldreich, S. Micali, and A. Wigderson, Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design, 1986 FOCS.
• KY: A. Karlin and A. Yao, manuscript.
• PSL: 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]
• PW: Peterson and Weldon, Error Correcting Codes, Second Ed., MIT Press, 1972.
• R: M. Rabin, Randomized Byzantine Generals, 1983 FOCS, pp.403-409.
• S: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• ST: T. Srikanth and S. Toueg, Byzantine Agreement Made Simple: Simulating Authentication without Signatares, Cornell Technical Report 84-623, July 1984.
• TC: R. Turpin and B. Coan, Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement, information Processing Letters, Vol. 18, pp. 73-76, Feb. 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

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

General Terms:
Algorithms, Design, Performance, Theory