Document Open Access Logo

Decentralization in Open Quorum Systems: Limitative Results for Ripple and Stellar

Authors Andrea Bracciali , Davide Grossi , Ronald de Haan

PDF
Thumbnail PDF

File

OASIcs.Tokenomics.2020.5.pdf
  • Filesize: 0.54 MB
  • 20 pages

Document Identifiers

Author Details

Andrea Bracciali
  • Department of Computer Science, University of Stirling, UK
Davide Grossi
  • Bernoulli Institute for Maths, CS and AI, University of Groningen, The Netherlands
  • Amsterdam Center for Law and Economics, University of Amsterdam, The Netherlands
  • Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands
Ronald de Haan
  • Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands

Acknowledgements

We are indebted to the anonymous reviewers of Tokenomics 2020 for several punctual and helpful suggestions on an earlier version of the paper.

Cite AsGet BibTex

Andrea Bracciali, Davide Grossi, and Ronald de Haan. Decentralization in Open Quorum Systems: Limitative Results for Ripple and Stellar. In 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020). Open Access Series in Informatics (OASIcs), Volume 82, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.Tokenomics.2020.5

Abstract

Decentralisation is one of the promises introduced by blockchain technologies: fair and secure interaction amongst peers with no dominant positions, single points of failure or censorship. Decentralisation, however, appears difficult to be formally defined, possibly a continuum property of systems that can be more or less decentralised, or can tend to decentralisation in their lifetime. In this paper we focus on decentralisation in quorum-based approaches to open (permissionless) consensus as illustrated in influential protocols such as the Ripple and Stellar protocols. Drawing from game theory and computational complexity, we establish limiting results concerning the decentralisation vs. safety trade-off in Ripple and Stellar, and we propose a novel methodology to formalise and quantitatively analyse decentralisation in this type of blockchains.

Subject Classification

ACM Subject Classification
  • Security and privacy → Distributed systems security
Keywords
  • Blockchain
  • decentralization
  • game theory
  • computational complexity

Metrics

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

Related Versions

References

  1. J. Banzhaf. Weighted voting doesn't work: A mathematical analysis. Rutgeres Law Review, 19:317-343, 1965. Google Scholar
  2. J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. Kroll, and E. Felten. Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. In Security and Privacy (SP), 2015 IEEE Symposium on, pages 104-121. IEEE, 2015. Google Scholar
  3. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. Google Scholar
  4. C. Cachin and M. Vukolic. Blockchain consensus protocols in the wild. Technical report, CoRR abs/1707.01873, 2017. Google Scholar
  5. M. Castro and B. Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI '99, pages 173-186, Berkeley, CA, USA, 1999. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=296806.296824.
  6. B. Chase and MacBrough E. Analysis of the XRP ledger consensus protocol. Technical report, Ripple Research, 2018. Google Scholar
  7. Morris H. DeGroot. Reaching a Consensus. Journal of the American Statistical Association, 69(345):118-121, 1974. Google Scholar
  8. D. Dolev. Byzantine generals stike again. Journal of Algorithms, 3(1):14-30, 1982. Google Scholar
  9. C. Dwork and M. Naor. Pricing via processing or combatting junk mail. In Ernest F. Brickell, editor, Advances in Cryptology - CRYPTO' 92, pages 139-147, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg. Google Scholar
  10. MacBrough E. Cobalt: BFT governance in open networks. Technical report, Ripple Research, 2018. Google Scholar
  11. D. Felsenthal and M. Machover. The Measurement of Voting Power. Edward Elgar Publishing, 1998. Google Scholar
  12. M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, April 1985. URL: https://doi.org/10.1145/3149.214121.
  13. J. French. A formal theory of social power. Psychological Review, 61:181-194, 1956. Google Scholar
  14. F. Gantmacher. The Theory of Matrices. AMS Chealsea Publishing, 1959. Google Scholar
  15. J. Garay, A. Kiayias, and Nikos L. The bitcoin backbone protocol: Analysis and applications. In E. Oswald and M. Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46803-6_10.
  16. H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. J. ACM, 32(4):841-860, October 1985. URL: https://doi.org/10.1145/4221.4223.
  17. C. García-Pérez and A. Gotsman. Federated Byzantine Quorum Systems. In J. Cao, F. Ellen, L. Rodrigues, and B. Ferreira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of LIPIcs, pages 17:1-17:16, 2018. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.17.
  18. U. Grandi. Social choice on social networks. In U. Endriss, editor, Trends in Computational Social Choice, pages 169-184. COST, 2018. Google Scholar
  19. X. Hu and L. Shapley. On authority distributions in organizations: Controls. Games and Economic Behavior, 45:153-170, 2003. Google Scholar
  20. X. Hu and L. Shapley. On authority distributions in organizations: Equilibrium. Games and Economic Behavior, 45:132-152, 2003. Google Scholar
  21. M. O. Jackson. Social and Economic Networks. Princeton University Press, Princeton, NJ, USA, 2008. Google Scholar
  22. D. Karos and H. Peters. Indirect control and power in mutual control structures. Games and Economic Behavior, 92, 2015. Google Scholar
  23. M. Kim, Y. Kwon, and Y. Kim. Is stellar as secure as you think? In IEEE Security and Privacy on the Blockchain (IEEE S&B '19). IEEE, 2019. Google Scholar
  24. L. Lachowski. Complexity of the quorum intersection property of the federated byzantine agreement system, 2019. URL: https://arxiv.org/abs/1902.06493.
  25. L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. Google Scholar
  26. M. Lokhava, G. Losa, D. Maziéres, G. Hoare, N. Barry, E. Gafni, J. Jove, and Jed McCaleb R. Malinowsky. Fast and secure global payments with Stellar. In Proceedings of SOSP'19. ACM, 2019. Google Scholar
  27. D. Malkhi and M. Reiter. Byzantine quorum systems. Distributed Computing, 11:203-213, 1998. Google Scholar
  28. D. Mazierès. The stellar consensus protocol: A federated model for internet-level consensus. Stellar Development Foundation, 2016. Google Scholar
  29. S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Bitcoin project white paper, 2009. Google Scholar
  30. A. Narayanan, J. Bonneau, E. Felten, A. Miller, and S. Goldfeder. Bitcoin and Cryptocurrency Technologies. Princeton University Press, 2016. Google Scholar
  31. M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the Association for Computing Machinery, 27(2):228-234, 1980. Google Scholar
  32. D. Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci., 282(2):231-257, 2002. Google Scholar
  33. L. Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):53-57, 1946. Google Scholar
  34. A. Proskurnikov and R. Tempo. A tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control, 43:65-79, 2017. Google Scholar
  35. A. Proskurnikov and R. Tempo. A tutorial on modeling and analysis of dynamic social networks. Part II. Annual Reviews in Control, 45:166-190, 2018. Google Scholar
  36. F. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299-319, 1990. Google Scholar
  37. D. Schwartz, N. Youngs, and A. Britto. The ripple protocol consensus algorithm. Technical report, Ripple Labs, 2014. Google Scholar
  38. L. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48:787-792, 1954. Google Scholar
  39. M. Vukolic. Quorum Systems with Applications to Storage and Consensus. Morgan & Claypool Publishers, 2012. Google Scholar
  40. M. Vukolic. The quest for scalable blockchain fabric: Proof-of-work vs. BFT replication. In Proceedings of iNetSec'15, volume 9591 of LNCS, pages 112-125, 2015. Google Scholar
  41. R. Wattenhofer. Distributed Ledger Technology: The Science of the Blockchain. Createspace Independent Publishing Platform, 2017. 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