Document Open Access Logo

Improved Extension Protocols for Byzantine Broadcast and Agreement

Authors Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, Zhuolun Xiang

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.28.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Kartik Nayak
  • Duke University, Durham, NC, USA
Ling Ren
  • University of Illinois at Urbana-Champaign, Champaign, IL, USA
Elaine Shi
  • Cornell University, Ithaca, NY, USA
Nitin H. Vaidya
  • Georgetown University, Washington, D.C., USA
Zhuolun Xiang
  • University of Illinois at Urbana-Champaign, Champaign, IL, USA

Funding

Kartik Nayak and Ling Ren are supported in part by a VMware early career faculty grant.
  • Shi, Elaine: Elaine Shi is supported in part by NSF award 1561209, and part of the work was done when the author was a long-terms visitor in Simons Institute for the "Proofs, Consensus, and Decentralizing Societ" program.
  • Vaidya, Nitin H.: Nitin H. Vaidya is supported in part by NSF award 1849599.

Cite AsGet BibTex

Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.28

Abstract

Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1-ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Cryptographic protocols
Keywords
  • Byzantine agreement
  • Byzantine broadcast
  • extension protocol
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 337-346, 2019. Google Scholar
  2. Niko Barić and Birgit Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 480-494. Springer, 1997. Google Scholar
  3. Piotr Berman, Juan A Garay, and Kenneth J Perry. Bit optimal distributed consensus. In Computer science, pages 313-321. Springer, 1992. Google Scholar
  4. Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 416-432. Springer, 2003. Google Scholar
  5. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  6. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524-541. Springer, 2001. Google Scholar
  7. Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05), pages 191-201. IEEE, 2005. Google Scholar
  8. Wutichai Chongchitmate and Rafail Ostrovsky. Information-theoretic broadcast with dishonest majority for long messages. In Theory of Cryptography Conference, pages 370-388. Springer, 2018. Google Scholar
  9. David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Cryptographers’ Track at the RSA Conference, pages 127-144. Springer, 2015. Google Scholar
  10. Danny Dolev and Ruediger Reischuk. Bounds on information exchange for byzantine agreement. In Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 132-140. ACM, 1982. Google Scholar
  11. Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  12. Sisi Duan, Michael K Reiter, and Haibin Zhang. Beat: Asynchronous bft made practical. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 2028-2041, 2018. Google Scholar
  13. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  14. Matthias Fitzi and Martin Hirt. Optimally efficient multi-valued byzantine agreement. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 163-168. ACM, 2006. Google Scholar
  15. Chaya Ganesh and Arpita Patra. Broadcast extensions with optimal communication and round complexity. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 371-380. ACM, 2016. Google Scholar
  16. Chaya Ganesh and Arpita Patra. Optimal extension protocols for byzantine broadcast and agreement. Distributed Computing, pages 1-19, 2020. Google Scholar
  17. Aniket Kate, Gregory M Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 177-194. Springer, 2010. Google Scholar
  18. Taechan Kim and Razvan Barbulescu. Extended tower number field sieve: A new complexity for the medium prime case. In Annual International Cryptology Conference, pages 543-571. Springer, 2016. Google Scholar
  19. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. Google Scholar
  20. Guanfeng Liang and Nitin Vaidya. Error-free multi-valued consensus with byzantine failures. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 11-20. ACM, 2011. Google Scholar
  21. Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In Proceedings of the 39th Symposium on Principles of Distributed Computing, page 129–138, 2020. Google Scholar
  22. Nancy A Lynch. Distributed algorithms. Elsevier, 1996. Google Scholar
  23. Ralph C Merkle. A digital signature based on a conventional encryption function. In Conference on the theory and application of cryptographic techniques, pages 369-378. Springer, 1987. Google Scholar
  24. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31-42. ACM, 2016. Google Scholar
  25. Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. Journal of the ACM (JACM), 62(4):1-21, 2015. Google Scholar
  26. Shuai Mu, Kang Chen, Yongwei Wu, and Weimin Zheng. When paxos meets erasure code: Reduce network and storage cost in state machine replication. In Proceedings of the 23rd international symposium on High-performance parallel and distributed computing, pages 61-72, 2014. Google Scholar
  27. Lan Nguyen. Accumulators from bilinear pairings and applications. In Cryptographers’ Track at the RSA Conference, pages 275-292. Springer, 2005. Google Scholar
  28. Arpita Patra. Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity. In International Conference On Principles Of Distributed Systems, pages 34-49. Springer, 2011. Google Scholar
  29. Birgit Pfitzmann and Michael Waidner. Information-theoretic pseudosignatures and byzantine agreement for t ≥ n/3. Research report, IBM Research, 1996. Google Scholar
  30. Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304, 1960. Google Scholar
  31. Zizhong Wang, Tongliang Li, Haixia Wang, Airan Shao, Yunren Bai, Shangming Cai, Zihan Xu, and Dongsheng Wang. Craft: An erasure-coding-supported version of raft for reducing storage cost and network cost. In 18th USENIX Conference on File and Storage Technologies, pages 297-308, 2020. Google Scholar
  32. Andrew C Yao. Protocols for secure computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 160-164. IEEE Computer Society, 1982. Google Scholar
  33. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209-213. ACM, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact