Document Open Access Logo

Optimal Good-Case Latency for Rotating Leader Synchronous BFT

Authors Ittai Abraham, Kartik Nayak, Nibesh Shrestha

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.27.pdf
  • Filesize: 0.97 MB
  • 19 pages

Document Identifiers

Author Details

Ittai Abraham
  • VMware Research, Herzliya, Israel
Kartik Nayak
  • Duke University, Durham, NC, USA
Nibesh Shrestha
  • Rochester Institute of Technology, NY, USA

Cite As Get BibTex

Ittai Abraham, Kartik Nayak, and Nibesh Shrestha. Optimal Good-Case Latency for Rotating Leader Synchronous BFT. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.27

Abstract

This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of switching to the next sender. We then present a matching upper bound with a latency of 2Δ (Δ is the pessimistic synchronous delay) with an optimistically responsive change to the next sender. The results imply that both our lower and upper bounds are tight. We implement and evaluate our protocol and show that our protocol obtains similar latency compared to state-of-the-art stable-leader protocol Sync HotStuff while allowing optimistically responsive leader rotation.

Subject Classification

ACM Subject Classification
  • Security and privacy → Distributed systems security
Keywords
  • Distributed Computing
  • Byzantine Fault Tolerance
  • Synchrony

Metrics

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

Related Versions

References

  1. Ittai Abraham, Dahlia Malkhi, Kartik Nayak, and Ling Ren. Dfinity consensus, explored. IACR Cryptol. ePrint Arch., 2018:1153, 2018. Google Scholar
  2. Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. Sync hotstuff: Simple and practical synchronous state machine replication. In 2020 IEEE Symposium on Security and Privacy (SP), pages 654-667, 2020. Google Scholar
  3. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-case latency of byzantine broadcast: A complete categorization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 331-341, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465084.3467899.
  4. Adithya Bhat, Akhil Bandarupalli, Saurabh Bagchi, Aniket Kate, and Michael K Reiter. Apollo-optimistically linear and responsive smr. Cryptology ePrint Archive, Report 2021/180, 2021. URL: https://eprint.iacr.org/2021/180.
  5. Adithya Bhat, Nibesh Shrestha, Aniket Kate, and Kartik Nayak. Randpiper - reconfiguration-friendly random beacons with quadratic communication. Cryptology ePrint Archive, Report 2020/1590, 2020. , To appear in ACM SIGSAC CCS 2021. URL: https://eprint.iacr.org/2020/1590.
  6. Jan Camenisch, Manu Drijvers, Timo Hanke, Yvonne-Anne Pignolet, Victor Shoup, and Dominic Williams. Internet computer consensus. Cryptology ePrint Archive, Report 2021/632, 2021. URL: https://eprint.iacr.org/2021/632.
  7. Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173-186, 1999. Google Scholar
  8. Benjamin Y Chan and Elaine Shi. Streamlet: Textbook streamlined blockchains. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, pages 1-11, 2020. Google Scholar
  9. T-H Hubert Chan, Rafael Pass, and Elaine Shi. Pala: A simple partially synchronous blockchain. IACR Cryptology ePrint Archive, 2018:981, 2018. Google Scholar
  10. T-H Hubert Chan, Rafael Pass, and Elaine Shi. Pili: An extremely simple synchronous blockchain. IACR Cryptology ePrint Archive, 2018:980, 2018. Google Scholar
  11. Determinant. Sync-HotStuff. URL: https://github.com/hot-stuff/librightstuff.
  12. Drand. Drand - a distributed randomness beacon daemon. URL: https://github.com/drand/drand.
  13. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  14. Michael J Fischer, Nancy A Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986. Google Scholar
  15. Matthias Fitzi. Generalized communication and security models in Byzantine agreement. PhD thesis, ETH Zurich, 2002. Google Scholar
  16. 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
  17. Timo Hanke, Mahnush Movahedi, and Dominic Williams. Dfinity technology overview series, consensus system. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.04548.
  18. Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Annual International Cryptology Conference, pages 445-462. Springer, 2006. Google Scholar
  19. Dahlia Malkhi, Kartik Nayak, and Ling Ren. Flexible byzantine fault tolerance. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1041-1053, 2019. Google Scholar
  20. Zarko Milosevic, Martin Biely, and André Schiper. Bounded delay in byzantine-tolerant state machine replication. In 2013 IEEE 32nd International Symposium on Reliable Distributed Systems, pages 61-70. IEEE, 2013. Google Scholar
  21. Atsuki Momose, Jason Paul Cruz, and Yuichi Kaji. Hybrid-bft: Optimistically responsive synchronous consensus with optimal latency or resilience. IACR Cryptol. ePrint Arch., 2020:406, 2020. Google Scholar
  22. Rafael Pass and Elaine Shi. Thunderella: Blockchains with optimistic instant confirmation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3-33. Springer, 2018. Google Scholar
  23. Fred B Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR), 22(4):299-319, 1990. Google Scholar
  24. Elaine Shi. Streamlined blockchains: A simple and elegant approach (a tutorial and survey). In International Conference on the Theory and Application of Cryptology and Information Security, pages 3-17. Springer, 2019. Google Scholar
  25. Nibesh Shrestha, Ittai Abraham, Ling Ren, and Kartik Nayak. On the optimality of optimistic responsiveness. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 839-857, 2020. Google Scholar
  26. Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347-356, 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