Document Open Access Logo

In Search for an Optimal Authenticated Byzantine Agreement

Author Alexander Spiegelman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.38.pdf
  • Filesize: 1.28 MB
  • 19 pages

Document Identifiers

Author Details

Alexander Spiegelman
  • Novi Research, Menlo Park, USA

Cite As Get BibTex

Alexander Spiegelman. In Search for an Optimal Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.38

Abstract

In this paper, we challenge the conventional approach of state machine replication systems to design deterministic agreement protocols in the eventually synchronous communication model. We first prove that no such protocol can guarantee bounded communication cost before the global stabilization time and propose a different approach that hopes for the best (synchrony) but prepares for the worst (asynchrony). Accordingly, we design an optimistic byzantine agreement protocol that first tries an efficient deterministic algorithm that relies on synchrony for termination only, and then, only if an agreement was not reached due to asynchrony, the protocol uses a randomized asynchronous protocol for fallback that guarantees termination with probability 1.
We formally prove that our protocol achieves optimal communication complexity under all network conditions and failure scenarios. We first prove a lower bound of Ω(ft+ t) for synchronous deterministic byzantine agreement protocols, where t is the failure threshold, and f is the actual number of failures. Then, we present a tight upper bound and use it for the synchronous part of the optimistic protocol. Finally, for the asynchronous fallback, we use a variant of the (optimal) VABA protocol, which we reconstruct to safely combine it with the synchronous part.
We believe that our adaptive to failures synchronous byzantine agreement protocol has an independent interest since it is the first protocol we are aware of which communication complexity optimally depends on the actual number of failures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Security and privacy → Distributed systems security
Keywords
  • Byzantine agreement
  • Optimistic
  • Asynchronous fallback

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 PODC. ACM, 2019. Google Scholar
  2. Marcos Kawazoe Aguilera and Sam Toueg. Randomization and failure detection: A hybrid approach to solve consensus. In IWDA, 1996. Google Scholar
  3. Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis. Sok: Consensus in the age of blockchains. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 183-198, 2019. Google Scholar
  4. Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Theory of Cryptography Conference, 2020. Google Scholar
  5. Erica Blum, Jonathan Katz, and Julian Loss. Synchronous consensus with optimal asynchronous fallback guarantees. In Theory of Cryptography Conference. Springer, 2019. Google Scholar
  6. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM (JACM), 32(4):824-840, 1985. Google Scholar
  7. Francisco Brasileiro, Fabíola Greve, Achour Mostéfaoui, and Michel Raynal. Consensus in one communication step. In International Conference on Parallel Computing Technologies, 2001. Google Scholar
  8. Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc. Fast byzantine agreement. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, 2013. Google Scholar
  9. Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making byzantine consensus live. In DISC. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, 2020. Google Scholar
  10. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on bft consensus. arXiv preprint, 2018. URL: http://arxiv.org/abs/1807.04938.
  11. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Advances in Cryptology, 2001. Google Scholar
  12. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, 1999. Google Scholar
  13. Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In DISC 2020, 2020. Google Scholar
  14. Danny Dolev and Rudiger Reischuk. Bounds on information exchange for byzantine agreement. JACM, 1985. Google Scholar
  15. Danny Dolev, Ruediger Reischuk, and H Raymond Strong. Early stopping in byzantine agreement. Journal of the ACM (JACM), 1990. Google Scholar
  16. Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  17. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. JACM, 1985. Google Scholar
  18. Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. The next 700 bft protocols. In Proceedings of the 5th European conference on Computer systems, 2010. Google Scholar
  19. Rachid Guerraoui, Viktor Kuncak, and Giuliano Losa. Speculative linearizability. ACM Sigplan Notices, 47(6):55-66, 2012. Google Scholar
  20. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. Sbft: a scalable and decentralized trust infrastructure. In DSN 2019. IEEE, 2019. Google Scholar
  21. Idit Keidar and Sergio Rajsbaum. A simple proof of the uniform consensus synchronous lower bound. Information Processing Letters, 2003. Google Scholar
  22. Valerie King and Jared Saia. Byzantine agreement in expected polynomial time. Journal of the ACM (JACM), 63(2):13, 2016. Google Scholar
  23. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative byzantine fault tolerance. In ACM SIGOPS Operating Systems Review, 2007. Google Scholar
  24. Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Fairledger: A fair blockchain protocol for financial institutions. In OPODIS, 2019. Google Scholar
  25. Dahlia Malkhi. Concurrency: The Works of Leslie Lamport. Morgan & Claypool, 2019. Google Scholar
  26. Dahlia Malkhi, Kartik Nayak, and Ling Ren. Flexible byzantine fault tolerance. In CCS, 2019. Google Scholar
  27. J-P Martin and Lorenzo Alvisi. Fast byzantine consensus. IEEE Transactions on Dependable and Secure Computing, 3(3):202-215, 2006. Google Scholar
  28. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In CCS 2016. ACM, 2016. Google Scholar
  29. Atsuki Momose and Ling Ren. Optimal communication complexity of byzantine consensus under honest majority. DISC, 2020. Google Scholar
  30. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine view synchronization. In CryptoEconSys 2020, 2019. Google Scholar
  31. Oded Naor and Idit Keidar. Expected linear round synchronization: The missing link for linear byzantine smr. In DISC, 2020. Google Scholar
  32. Kartik Nayak, Ling Ren, Elaine Shi, Nitin H Vaidya, and Zhuolun Xiang. Improved extension protocols for byzantine broadcast and agreement. DISC, 2020. Google Scholar
  33. M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2), 1980. Google Scholar
  34. Victor Shoup. Practical threshold signatures. In ICTACT, 2000. Google Scholar
  35. Yee Jiun Song and Robbert van Renesse. Bosco: One-step byzantine asynchronous consensus. In International Symposium on Distributed Computing, pages 438-450. Springer, 2008. Google Scholar
  36. Alexander Spiegelman. In search for an optimal authenticated byzantine agreement. CoRR, abs/2002.06993, 2020. URL: http://arxiv.org/abs/2002.06993.
  37. Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi. Ace: Abstract consensus encapsulation for liveness boosting of state machine replication. In OPODIS' 2020, 2020. Google Scholar
  38. Maofan Yin, Dahlia Malkhi, MK Reiterand, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In PODC, 2019. 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 About DROPS Imprint Privacy Contact