LIPIcs.OPODIS.2018.17.pdf
- Filesize: 480 kB
- 16 pages
Document
Federated Byzantine Quorum Systems
Authors
-
Part of:
Volume:
22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
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: 2019-01-15
Cite As Get BibTex
Álvaro García-Pérez and Alexey Gotsman. Federated Byzantine Quorum Systems. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.17
Abstract
Some of the recent blockchain proposals, such as Stellar and Ripple, use quorum-like structures typical for Byzantine consensus while allowing for open 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 theoretical foundations underlying such blockchains have not been thoroughly investigated. To close this gap, in this paper we study decentralised quorum construction by means of federated Byzantine quorum systems, used by Stellar. We rigorously prove the correctness of basic broadcast abstractions over federated quorum systems and establish their relationship to the classical Byzantine quorum systems. In particular, we prove correctness in the realistic setting where Byzantine nodes may lie about their trust choices. We show that this setting leads to a novel variant of Byzantine quorum systems where different nodes may have different understanding of what constitutes a quorum.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
Keywords
- Blockchain
- Stellar
- Byzantine quorum systems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ittai Abraham, Gregory V. Chockler, Idit Keidar, and Dahlia Malkhi. Byzantine disk Paxos: optimal resilience with Byzantine shared memory. Distributed Computing, 18(5):387-408, 2006.
-
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 (2nd ed.). Springer, 2011.
-
Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In International Symposium on Distributed Computing (DISC), pages 1:1-1:16, 2017.
-
Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398-461, 2002.
-
Allen Clement, Edmund L. Wong, Lorenzo Alvisi, Michael Dahlin, and Mirco Marchetti. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In Symposium on Networked Systems Design and Implementation (NSDI), pages 153-168, 2009.
-
Cynthia Dwork and Moni Naor. Pricing via Processing or Combatting Junk Mail. In International Cryptology Conference on Advances in Cryptology (CRYPTO), pages 139-147, 1993.
- Álvaro García-Pérez and Alexey Gotsman. Federated Byzantine Quorum Systems (Extended Version). CoRR, 2018. URL: http://arxiv.org/abs/1811.03642.
-
Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative Byzantine Fault Tolerance. In Symposium on Operating Systems Principles (SOSP), pages 45-58, 2007.
-
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, 2016. URL: https://www.stellar.org/papers/stellar-consensus-protocol.pdf.
-
Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, 2009.
- David Schwartz, Noah Youngs, and Arthur Britto. The Ripple Protocol Consensus Algorithm, 2014. URL: https://ripple.com/files/ripple_consensus_whitepaper.pdf.
-
Marko Vukolic. Quorum Systems: With Applications to Storage and Consensus. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2012.