Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract)

ABSTRACT

Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are corrupted. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of cryptography, specifically of threshold signatures and coin-tossing protocols. These cryptographic protocols have practical and provably secure implementations in the “random oracle” model. In particular, a coin-tossing protocol based on the Diffie-Hellman problem is presented and analyzed. The resulting asynchronous Byzantine agreement protocol is both practical and nearly matches the known theoretical lower bounds. More precisely, it tolerates the maximum number of corrupted parties, runs in constant expected time, has message and communication complexity close to the maximum, and uses a trusted dealer only in a setup phase, after which it can process a virtually unlimited number of transactions. Novel dual-threshold variants of both cryptographic protocols are used. The protocol is formulated as a transaction processing service in a cryptographic security model, which differs from the standard information-theoretic formalization and may be of independent interest.

REFERENCES

• BCK98: Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276854]
• Ben83: 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]
• BG93: P. Berman and J. A. Garay, Randomized distributed agreement revisited, Proc. 23th International Symposium on Fault-Tolerant Computing (FTCS-23), 1993, pp. 412-419.
• Boy89: C. Boyd, Public-key cryptography and re-usable shared secrets, Cryptography and Coding (H. Baker and F. Piper, eds.), Clarendon Press, 1989, pp. 241-246.
• BR93: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• BR95: Mihir Bellare , Phillip Rogaway, Provably secure session key distribution: the three party case, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.57-66, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225084]
• Bra84: 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]
• BS94: Donald Beaver , Nicol So, Global, unpredictable bit generation without broadcast, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.424-434, January 1994, Lofthus, Norway
• Can96: R. Canetti, Studies in secure multiparty computation and applications, Ph.D. thesis, Weizmann Institute of Science, 1996.
• CD89: B. Chor and C. Dwork, Randomization in Byzantine agreement, Randomness and Computation (S. Micali, ed.), Advances in Computing Research, vol. 5, JAI Press, 1989, pp. 443-497.
• CG99: R. Canetti and S. Goldwasser, An efficient threshold public-key cryptosystem secure against adaptive chosen-ciphertext attack, Advances in Cryptology: EUROCRYPT '99 (J. Stern, ed.), Lecture Notes in Computer Science, vol. 1592, Springer, 1999, pp. 90-106.
• CH89: R.A. Croft and S. P. Harris, Public-key cryptography and re-usable shared secrets, Cryptography and Coding (H. Baker and F. Piper, eds.), Clarendon Press, 1989, pp. 189-201.
• CKS00: C. Cachin, K. Kursawe, and V. Shoup, Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography, To appear in Cryptology ePrint Archive, http: //eprint. iacr. org, 2000.
• CP93: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• CR93: 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]
• CT96: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• Des88: Yvo Desmedt, Society and Group Oriented Cryptography: A New Concept, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.120-127, August 16-20, 1987
• DF90: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• DS83: D. Dolev and H. R. Strong, Authenticated algorithms for Byzantine agreement, SIAM Journal on Computing 12 (1983), no. 4, 656-666.
• FLP85: 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]
• FM97: 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]
• FS87: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• GMR88: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• Lyn96: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• MS95: Silvio Micali , Ray Sidney, A Simple Method for Generating and Sharing Pseudo-Random Functions, with Applications to Clipper-like Escrow Systems, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.185-196, August 27-31, 1995
• NPR99: M. Naor, B. Pinkas, and O. Reingold, Distributed pseudo-random functions and KDCs, Advances in Cryptology: EUROCRYPT '99 (J. Stern, ed.), Lecture Notes in Computer Science, vol. 1592, Springer, 1999.
• Rab83: M. O. Rabin, Randomized Byzantine generals, Proc. 24th IEEE Symposium on Foundations of Computer Science (FOCS), 1983, pp. 403-409.
• Rab98: Tal Rabin, A Simplified Approach to Threshold and Proactive RSA, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.89-104, August 23-27, 1998
• Rei96: Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996 [doi>10.1109/32.481515]
• Sha79: 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]
• Sho99: V. Shoup, On .formal models for secure key exchange, Research Report RZ 3120, IBM Research, 1999, revision 4, available from http://w~, shoup. net.
• Sho00: V. Shoup, Practical threshold signatures, Advances in Cryptology: EUROCRYPT 2000 (B. Preneel, ed.), Lecture Notes in Computer Science, Springer, 2000, (to appear).
• Tou84: Sam Toueg, Randomized Byzantine Agreements, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.163-178, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806744]

INDEX TERMS

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

General Terms:
Management, Theory

Keywords:
Byzantine faults, asynchronous consensus, crytographic common coin, dual-threshold schemes, threshold signatures