Document Open Access Logo

Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP

Authors Shir Cohen, Idit Keidar, Alexander Spiegelman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.25.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Shir Cohen
  • Technion - Israel Institute of Technology, Haifa, Israel
Idit Keidar
  • Technion - Israel Institute of Technology, Haifa, Israel
Alexander Spiegelman
  • VMware Research, Herzliya, Israel

Acknowledgements

We thank Ittai Abraham, Dahlia Malkhi, Kartik Nayak and Ling Ren for insightful initial discussions.

Cite AsGet BibTex

Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.25

Abstract

King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of Õ(n) and O(1) expected time, breaking the O(n²) bit barrier for asynchronous Byzantine Agreement.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Cryptographic primitives
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • shared coin
  • Byzantine Agreement
  • VRF
  • sub-quadratic consensus protocol

Metrics

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

Related Versions

References

  1. Ittai Abraham, TH Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 317-326, 2019. Google Scholar
  2. Ittai Abraham, Guy Golan-Gueta, and Dahlia Malkhi. Hot-stuff the linear, optimal-resilience, one-message bft devil. CoRR, abs/1803.05069, 2018. Google Scholar
  3. 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
  4. Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla. The cost of global broadcast in dynamic radio networks. Theoretical Computer Science, 806:363-387, 2020. Google Scholar
  5. Avi Asayag, Gad Cohen, Ido Grayevsky, Maya Leshkowitz, Ori Rottenstreich, Ronen Tamari, and David Yakira. Helix: A scalable and fair consensus algorithm resistant to ordering manipulation. IACR Cryptology ePrint Archive, 2018:863, 2018. Google Scholar
  6. Hagit Attiya and Jennifer Welch. Distributed computing: fundamentals, simulations, and advanced topics, volume 19. John Wiley & Sons, 2004. Google Scholar
  7. Baruch Awerbuch and Christian Scheideler. A denial-of-service resistant dht. In International Symposium on Distributed Computing, pages 33-47. Springer, 2007. Google Scholar
  8. Mathieu Baudet, Avery Ching, Andrey Chursin, George Danezis, François Garillot, Zekun Li, Dahlia Malkhi, Oded Naor, Dmitri Perelman, and Alberto Sonnino. State machine replication in the libra blockchain. The Libra Assn., Tech. Rep, 2019. Google Scholar
  9. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27-30. ACM, 1983. Google Scholar
  10. Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. Cryptology ePrint Archive, Report 2020/851, 2020. Google Scholar
  11. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  12. Gabriel Bracha and Sam Toueg. Resilient consensus protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 12-26. ACM, 1983. Google Scholar
  13. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous byzantine agreement using cryptography. Journal of Cryptology, 18(3):219-246, 2005. Google Scholar
  14. Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In STOC, volume 93, pages 42-51. Citeseer, 1993. Google Scholar
  15. Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos. Algorand agreement: Super fast and partition resilient byzantine agreement. IACR Cryptology ePrint Archive, 2018:377, 2018. Google Scholar
  16. Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. arXiv preprint arXiv:2002.06545, 2020. Google Scholar
  17. Yevgeniy Dodis and Aleksandr Yampolskiy. A verifiable random function with short proofs and keys. In International Workshop on Public Key Cryptography, pages 416-431. Springer, 2005. Google Scholar
  18. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191–204, January 1985. Google Scholar
  19. 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
  20. Matthew Franklin and Haibin Zhang. Unique ring signatures: A practical construction. In International Conference on Financial Cryptography and Data Security, pages 162-170. Springer, 2013. Google Scholar
  21. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51-68, 2017. Google Scholar
  22. Timo Hanke, Mahnush Movahedi, and Dominic Williams. Dfinity technology overview series, consensus system. arXiv preprint arXiv:1805.04548, 2018. Google Scholar
  23. Valerie King and Jared Saia. Breaking the O(n²) bit barrier: scalable byzantine agreement with an adaptive adversary. Journal of the ACM (JACM), 58(4):1-24, 2011. Google Scholar
  24. Valerie King and Jared Saia. Byzantine agreement in polynomial expected time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 401-410. ACM, 2013. Google Scholar
  25. Marek Klonowski, Dariusz R Kowalski, and Jarosław Mirek. Ordered and delayed adversaries and how to work against them on a shared channel. Distributed Computing, 32(5):379-403, 2019. Google Scholar
  26. Jae Kwon. Tendermint: Consensus without mining. Draft v. 0.6, fall, 1(11), 2014. Google Scholar
  27. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, July 1978. Google Scholar
  28. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982. Google Scholar
  29. Silvio Micali. Very simple and efficient byzantine agreement. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 6:1-6:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.6.
  30. Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 120-130. IEEE, 1999. Google Scholar
  31. 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):31, 2015. Google Scholar
  32. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2009. Google Scholar
  33. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine view synchronization. arXiv preprint arXiv:1909.05204, 2019. Google Scholar
  34. Michael O Rabin. Randomized byzantine generals. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pages 403-409. IEEE, 1983. Google Scholar
  35. Peter Robinson, Christian Scheideler, and Alexander Setzer. Breaking the Ω(√n) barrier: Fast consensus under a late adversary. In 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, pages 173-182. ACM New York, 2018. Google Scholar
  36. Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979. Google Scholar
  37. Alexander Spiegelman. In search for a linear byzantine agreement. arXiv preprint arXiv:2002.06993, 2020. 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