Document Open Access Logo

Asymmetric Distributed Trust

Authors Christian Cachin , Björn Tackmann

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.7.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

Christian Cachin
  • University of Bern, Switzerland
Björn Tackmann
  • DFINITY Foundation, Zürich, Switzerland

Funding

This work has been supported in part by the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 780477 PRIViLEDGE.

Acknowledgements

The authors thank Orestis Alpos, Sabine Brunner, Marko Vukolić, and Luca Zanolini for interesting discussions. Work done while both authors were at IBM Research - Zurich.

Cite AsGet BibTex

Christian Cachin and Björn Tackmann. Asymmetric Distributed Trust. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.7

Abstract

Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Software and its engineering → Distributed systems organizing principles
Keywords
  • Quorums
  • consensus
  • distributed trust
  • blockchains
  • cryptocurrencies

Metrics

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

Related Versions

References

  1. 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 Vukolić, Sharon Weed, and Jason Yellick. Hyperledger Fabric: A distributed operating system for permissioned blockchains. In Proc. 13th European Conference on Computer Systems (EuroSys), pages 30:1-30:15, April 2018. URL: https://doi.org/10.1145/3190508.3190538.
  2. Frederik Armknecht, Ghassan O. Karame, Avikarsha Mandal, Franck Youssef, and Erik Zenner. Ripple: Overview and Outlook. In Mauro Conti, Matthias Schunter, and Ioannis G. Askoxylakis, editors, Proc. Trust and Trustworthy Computing (TRUST), volume 9229 of Lecture Notes in Computer Science, pages 163-180. Springer, 2015. Google Scholar
  3. Gabriel Bracha. Asynchronous Byzantine Agreement Protocols. Information and Computation, 75:130-143, 1987. Google Scholar
  4. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming (Second Edition). Springer, 2011. Google Scholar
  5. Christian Cachin and Björn Tackmann. Asymmetric Distributed Trust. e-print, arXiv:1906.09314 [cs.DC], 2019. URL: http://arxiv.org/abs/1906.09314.
  6. Christian Cachin and Marko Vukolić. Blockchain Consensus Protocols in the Wild. In Andréa W. Richa, editor, Proc. 31st Intl. Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.1.
  7. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems, 20(4):398-461, 2002. Google Scholar
  8. Bernadette Charron-Bost, Fernando Pedone, and André Schiper, editors. Replication: Theory and Practice, volume 5959 of Lecture Notes in Computer Science. Springer, 2010. Google Scholar
  9. Brad Chase and Ethan MacBrough. Analysis of the XRP Ledger Consensus Protocol. e-print, arXiv:1802.07242 [cs.DC], 2018. Google Scholar
  10. Ivan Damgård, Yvo Desmedt, Matthias Fitzi, and Jesper Buus Nielsen. Secure Protocols with Asymmetric Trust. In Kaoru Kurosawa, editor, Advances in Cryptology: ASIACRYPT 2007, volume 4833 of Lecture Notes in Computer Science. Springer, 2007. Google Scholar
  11. Hector Garcia-Molina and Daniel Barbara. How to Assign Votes in a Distributed System. jacm, 32(4):841-860, 1985. Google Scholar
  12. Álvaro García-Pérez and Alexey Gotsman. Federated Byzantine Quorum Systems. In Proc. 22nd Conference on Principles of Distributed Systems (OPODIS), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:16, 2018. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.17.
  13. David K. Gifford. Weighted Voting for Replicated Data. In Proc. 7th ACM Symposium on Operating System Principles (SOSP), pages 150-162, 1979. Google Scholar
  14. Vassos Hadzilacos and Sam Toueg. Fault-Tolerant Broadcasts and Related Problems. In Sape J. Mullender, editor, Distributed Systems (2nd Ed.). ACM Press & Addison-Wesley, New York, 1993. Google Scholar
  15. Martin Hirt and Ueli Maurer. Player Simulation and General Adversary Structures in Perfect Multi-Party Computation. Journal of Cryptology, 13(1):31-60, 2000. Google Scholar
  16. Flavio P. Junqueira, Keith Marzullo, Maurice Herlihy, and Lucia Draque Penso. Threshold Protocols in Survivor Set Systems. Distributed Computing, 23:135–149, 2010. Google Scholar
  17. Leslie Lamport. On Interprocess Communication. Distributed Computing, 1(2):77-85, 86-101, 1986. Google Scholar
  18. Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafal Malinowsky, and Jed McCaleb. Fast and secure global payments with Stellar. In Proc. 27th ACM Symposium on Operating Systems Principles (SOSP), pages 80-96, 2019. Google Scholar
  19. Giuliano Losa, Eli Gafni, and David Mazières. Stellar Consensus by Instantiation. In Jukka Suomela, editor, Proc. 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of LIPIcs, pages 27:1-27:15, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.27.
  20. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, San Francisco, 1996. Google Scholar
  21. Dahlia Malkhi and Michael K. Reiter. Byzantine quorum systems. Distributed Computing, 11(4):203-213, 1998. Google Scholar
  22. David Mazières. The Stellar Consensus Protocol: A Federated Model for Internet-level Consensus. Stellar, available online, https://www.stellar.org/papers/stellar-consensus-protocol.pdf, 2016.
  23. Moni Naor and Avishai Wool. The Load, Capacity and Availability of Quorum Systems. SIAM Journal on Computing, 27(2):423-447, 1998. Google Scholar
  24. M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. Journal of the ACM, 27(2):228-234, 1980. Google Scholar
  25. David Schwartz, Noah Youngs, and Arthur Britto. The Ripple Protocol Consensus Algorithm. Ripple Labs, available online, https://ripple.com/files/ripple_consensus_whitepaper.pdf, 2014.
  26. T. K. Srikanth and Sam Toueg. Simulating Authenticated Broadcasts to Derive Simple Fault-Tolerant Algorithms. Distributed Computing, 2:80-94, 1987. 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 Imprint Privacy Contact