Document Open Access Logo

Making Byzantine Consensus Live

Authors Manuel Bravo, Gregory Chockler, Alexey Gotsman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.23.pdf
  • Filesize: 1.13 MB
  • 17 pages

Document Identifiers

Author Details

Manuel Bravo
  • IMDEA Software Institute, Madrid, Spain
Gregory Chockler
  • University of Surrey, UK
Alexey Gotsman
  • IMDEA Software Institute, Madrid, Spain

Funding

This work was partially supported by an ERC Starting Grant RACCOON.

Acknowledgements

We want to thank Giuliano Losa, Dahlia Malkhi, Dragos-Adrian Seredinschi, Lacramioara Astefanoaei and Eugen Zalinescu for comments that helped improve the paper.

Cite As Get BibTex

Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making Byzantine Consensus Live. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.23

Abstract

Partially synchronous Byzantine consensus protocols typically structure their execution into a sequence of views, each with a designated leader process. The key to guaranteeing liveness in these protocols is to ensure that all correct processes eventually overlap in a view with a correct leader for long enough to reach a decision. We propose a simple view synchronizer abstraction that encapsulates the corresponding functionality for Byzantine consensus protocols, thus simplifying their design. We present a formal specification of a view synchronizer and its implementation under partial synchrony, which runs in bounded space despite tolerating message loss during asynchronous periods. We show that our synchronizer specification is strong enough to guarantee liveness for single-shot versions of several well-known Byzantine consensus protocols, including HotStuff, Tendermint, PBFT and SBFT. We furthermore give precise latency bounds for these protocols when using our synchronizer. By factoring out the functionality of view synchronization we are able to specify and analyze the protocols in a uniform framework, which allows comparing them and highlights trade-offs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Byzantine consensus
  • blockchain
  • partial synchrony
  • liveness

Metrics

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

Related Versions

References

  1. Incorrect by construction-CBC Casper isn't live. https://pyrofex.io/wp-content/uploads/2018/12/Incorrect-By-Construction.pdf. Google Scholar
  2. State machine replication in the Libra blockchain. https://developers.libra.org/docs/assets/papers/ libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf. Google Scholar
  3. Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren. Synchronous Byzantine agreement with expected O(1) rounds, expected O(n²) communication, and optimal resilience. In Conference on Financial Cryptography and Data Security (FC), 2019. Google Scholar
  4. Ittai Abraham, Guy Gueta, Dahlia Malkhi, Lorenzo Alvisi, Ramakrishna Kotla, and Jean-Philippe Martin. Revisiting fast practical Byzantine fault tolerance. arXiv, abs/1712.01367, 2017. URL: http://arxiv.org/abs/1712.01367.
  5. Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers. How to solve consensus in the smallest window of synchrony. In Symposium on Distributed Computing (DISC), 2008. Google Scholar
  6. Yair Amir, Brian A. Coan, Jonathan Kirsch, and John Lane. Prime: Byzantine replication under attack. IEEE Trans. Dependable Sec. Comput., 8(4):564-577, 2011. Google Scholar
  7. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. Correctness of Tendermint-core blockchains. In Conference on Principles of Distributed Systems (OPODIS), 2018. Google Scholar
  8. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. Dissecting Tendermint. In Conference on Networked Systems (NETYS), 2019. Google Scholar
  9. Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolic, Sharon Weed Cocco, and Jason Yellick. Hyperledger Fabric: a distributed operating system for permissioned blockchains. In European Conference on Computer Systems (EuroSys), 2018. Google Scholar
  10. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804–823, 1985. Google Scholar
  11. Rida A. Bazzi and Yin Ding. Non-skipping timestamps for Byzantine data storage systems. In Symposium on Distributed Computing (DISC), 2004. Google Scholar
  12. Martin Biely, Josef Widder, Bernadette Charron-Bost, Antoine Gaillard, Martin Hutle, and André Schiper. Tolerating corrupted communication. In Symposium on Principles of Distributed Computing (PODC), 2007. Google Scholar
  13. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  14. Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making Byzantine consensus live (extended version). arXiv CoRR, abs/2008.04167, 2020. URL: http://arxiv.org/abs/2008.04167.
  15. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. arXiv, abs/1807.04938, 2018. URL: http://arxiv.org/abs/1807.04938.
  16. Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv, abs/1710.09437, 2017. URL: http://arxiv.org/abs/1710.09437.
  17. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In International Cryptology Conference (CRYPTO), 2001. Google Scholar
  18. Christian Cachin and Marko Vukolic. Blockchain consensus protocols in the wild (keynote talk). In Symposium on Distributed Computing (DISC), 2017. Google Scholar
  19. Miguel Castro. Practical Byzantine Fault Tolerance. PhD thesis, Massachusetts Institute of Technology, 2001. Google Scholar
  20. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Symposium on Operating Systems Design and Implementation (OSDI), 1999. Google Scholar
  21. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4):685–722, 1996. Google Scholar
  22. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225–267, 1996. Google Scholar
  23. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Comput., 22(1):49-71, 2009. Google Scholar
  24. Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. DBFT: efficient leaderless Byzantine consensus and its application to blockchains. In Symposium on Network Computing and Applications (NCA), 2018. Google Scholar
  25. Danny Dolev, Joseph Y. Halpern, Barbara Simons, and Ray Strong. Dynamic fault-tolerant clock synchronization. J. ACM, 42(1):143–185, 1995. Google Scholar
  26. Partha Dutta, Rachid Guerraoui, and Leslie Lamport. How fast can eventual synchrony lead to consensus? In Conference on Dependable Systems and Networks (DSN), 2005. Google Scholar
  27. Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288-323, 1988. Google Scholar
  28. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. Google Scholar
  29. Eli Gafni. Round-by-round fault detectors: Unifying synchrony and asynchrony. In Symposium on Principles of Distributed Computing (PODC), 1998. Google Scholar
  30. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. In Symposium on Operating Systems Principles (SOSP), 2017. Google Scholar
  31. Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: A scalable and decentralized trust infrastructure. In Conference on Dependable Systems and Networks (DSN), 2019. Google Scholar
  32. Andreas Haeberlen and Petr Kuznetsov. The fault detection problem. In Conference on Principles of Distributed Systems (OPODIS), 2009. Google Scholar
  33. Idit Keidar and Alexander Shraer. Timeliness, failure-detectors, and consensus performance. In Symposium on Principles of Distributed Computing (PODC), 2006. Google Scholar
  34. Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133-169, 1998. Google Scholar
  35. Dahlia Malkhi and Michael Reiter. Unreliable intrusion detection in distributed computations. In Workshop on Computer Security Foundations (CSFW), 1997. Google Scholar
  36. Zarko Milosevic, Martin Biely, and André Schiper. Bounded delay in Byzantine-tolerant state machine replication. In Symposium on Reliable Distributed Systems (SRDS), 2013. Google Scholar
  37. Achour Mostéfaoui and Michel Raynal. Solving consensus using Chandra-Toueg’s unreliable failure detectors: A general quorum-based approach. In Symposium on Distributed Computing (DISC), 1999. Google Scholar
  38. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine view synchronization. In Cryptoeconomics Systems Conference (CES), 2020. Google Scholar
  39. Oded Naor and Idit Keidar. Expected linear round synchronization: The missing link for linear Byzantine SMR. In Symposium on Distributed Computing (DISC), 2020. Google Scholar
  40. Barbara Simons, Jennifer Welch, and Nancy Lynch. An overview of clock synchronization. In Fault-Tolerant Distributed Computing, 1986. Google Scholar
  41. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In Symposium on Principles of Distributed Computing (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