Optimally efficient multi-valued byzantine agreement

ABSTRACT

All known protocols for Byzantine agreement (BA) among n players require the message to be communicated at least Ω(n²) times, which results in an overall communication complexity of at least Ω(ln²) bits for an l-bit message. We present the first BA protocol in which the message is communicated only O(n) times (the hidden factor is less than 2). More concretely, for a given synchronous broadcast protocol which communicates B(b) bits for reaching agreement on a b-bit message with security parameter κ, our construction yields a synchronous BA protocol with communication complexity O(ln+nB(n+κ)) bits. Our reduction is information theoretically secure and tolerates up to t<n/2 corrupted players, which is optimal for the consensus variant of BA. Although this resilience is not optimal for the broadcast (Byzantine generals) variant, it is sufficient for most distributed applications that involve BA protocols since they typically require t<n/2.

REFERENCES

• 1: Piotr Berman , Juan A. Garay , Kenneth J. Perry, Bit optimal distributed consensus, Computer science: research and applications, Plenum Press, New York, NY, 1992
• 2: David Chaum , Sandra Roijakkers, Unconditionally Secure Digital Signatures, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.206-214, August 11-15, 1990
• 3: L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences (JCSS), 18(4):143--154, 1979. Preliminary version appeared in STOC '77.
• 4: Brian A. Coan , Jennifer L. Welch, Modular construction of a Byzantine agreement protocol with optimal message bit complexity, Information and Computation, v.97 n.1, p.61-85, March 1992 [doi>10.1016/0890-5401(92)90004-Y]
• 5: Danny Dolev , Rüdiger Reischuk, Bounds on information exchange for Byzantine agreement, Journal of the ACM (JACM), v.32 n.1, p.191-204, Jan. 1985 [doi>10.1145/2455.214112]
• 6: D. Dolev and H. R. Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656--666, Nov. 1983. Preliminary version appeared in STOC '82.
• 7: Paul Feldman , Silvio Micali, An Optimal Probabilistic Algorithm For Synchronous Byzantine Agreement, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.341-378, July 11-15, 1989
• 8: 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]
• 9: B. Pfitzmann and M. Waidner. Information-theoretic pseudosignatures and byzantine agreement for t>=n/3. Technical report, IBM Research, 1996.
• 10: R. Turpin and B. A. Coan. Extending binary Byzantine agreement to multivalued Byzantine agreement. Information Processing Letters, 18(2):73--76, Feb. 1984.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance, Reliability, Security, Theory

Keywords:
byzantine agreement, communication complexity, cryptographic security, information-theoretic security