LIPIcs.OPODIS.2019.5.pdf
- Filesize: 0.57 MB
- 16 pages
Document
Deconstructing Stellar Consensus
Authors
-
Part of:
Volume:
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-02-11
File
Document Identifiers
Acknowledgements
We thank Ilya Sergey, Giuliano Losa and Alexey Gotsman for their comments.
Cite As Get BibTex
Álvaro García-Pérez and Maria A. Schett. Deconstructing Stellar Consensus. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.5
Abstract
Some of the recent blockchain proposals, such as Stellar and Ripple, allow for open membership while using quorum-like structures typical for classical Byzantine consensus with closed membership. This is achieved by constructing quorums in a decentralised way: each participant independently chooses whom to trust, and quorums arise from these individual decisions. Unfortunately, the consensus protocols underlying such blockchains are poorly understood, and their correctness has not been rigorously investigated. In this paper we rigorously prove correct the Stellar Consensus Protocol (SCP), with our proof giving insights into the protocol structure and its use of lower-level abstractions. To this end, we first propose an abstract version of SCP that uses as a black box Stellar’s federated voting primitive (analogous to reliable Byzantine broadcast), previously investigated by García-Pérez and Gotsman [Álvaro García-Pérez and Alexey Gotsman, 2018]. The abstract consensus protocol highlights a modular structure in Stellar and can be proved correct by reusing the previous results on federated voting. However, it is unsuited for realistic implementations, since its processes maintain infinite state. We thus establish a refinement between the abstract protocol and the concrete SCP that uses only finite state, thereby carrying over the result about the correctness of former to the latter. Our results help establish the theoretical foundations of decentralised blockchains like Stellar and gain confidence in their correctness.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- Blockchain
- Consensus protocol
- Stellar
- Byzantine quorum systems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Gabriel Bracha. Asynchronous Byzantine Agreement Protocols. Information and Computation, 75(2):130-143, 1987.
-
Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011.
-
Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild. In International Symposium on Distributed Computing (DISC), 2017.
-
Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398-461, 2002.
-
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Bastian Pochon. The perfectly synchronized round-based model of distributed computing. Information and Computation, 205(5):783-815, 2007.
-
Ivana Filipovic, Peter W. O'Hearn, Noam Rinetzky, and Hongseok Yang. Abstraction for concurrent objects. Theoretical Computer Science, 411(51-52):4379-4398, 2010.
-
Álvaro García-Pérez and Alexey Gotsman. Federated Byzantine Quorum Systems. In International Conference on Principles of Distributed Systems (OPODIS), volume 125 of LIPIcs, pages 17:1-17:16. Schloss Dagstuhl, 2018.
- Álvaro García-Pérez and Maria A. Schet. Deconstructing Stellar Consensus (extended version). CoRR, abs/1911.05145, 2019. URL: http://arxiv.org/abs/1911.05145.
-
Leslie Lamport. The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2):133-169, 1998.
-
Giuliano Losa, Eli Gafni, and David Mazières. Stellar consensus by instantiation. In 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of LIPIcs, pages 27:1-27:15. Schloss Dagstuhl, 2019.
- Ethan MacBrough. Cobalt: BFT Governance in Open Networks. CoRR, abs/1802.07240, 2018. URL: http://arxiv.org/abs/1802.07240.
-
Dahlia Malkhi and Michael K. Reiter. Byzantine quorum systems. Distributed Computing, 11(4):203-213, 1998.
- David Mazières. The Stellar consensus protocol: a federated model for internet-Level consensus, 2015. URL: https://www.stellar.org/papers/stellar-consensus-protocol.pdf.
- David Mazières, Giuliano Losa, and Eli Gafni. Simplifed SCP, 2019. URL: http://www.scs.stanford.edu/~dm/blog/simplified-scp.html.
- David Schwartz, Noah Youngs, and Arthur Britto. The Ripple Protocol Consensus Algorithm, 2014. URL: https://ripple.com/files/ripple_consensus_whitepaper.pdf.
-
Yee Jiun Song, Robbert van Renesse, Fred B. Schneider, and Danny Dolev. The Building Blocks of Consensus. In International Conference on Distributed Computing and Networking (ICDCN), 2008.