Document Open Access Logo

Game Theoretical Framework for Analyzing Blockchains Robustness

Authors Paolo Zappalà, Marianna Belotti, Maria Potop-Butucaru, Stefano Secci

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.42.pdf
  • Filesize: 0.66 MB
  • 18 pages

Document Identifiers

Author Details

Paolo Zappalà
  • Orange Labs, 92320 Chatillon, France
  • LIA, Avignon Université, 84029 Avignon, France
Marianna Belotti
  • BDTD 60, Caisse des Dépôts, 75013 Paris, France
  • Cedric, Cnam, 75003 Paris, France
Maria Potop-Butucaru
  • Lip6, CNRS UMR 7606, Sorbonne University, 75005 Paris, France
Stefano Secci
  • Cedric, Cnam, 75003 Paris, France

Cite AsGet BibTex

Paolo Zappalà, Marianna Belotti, Maria Potop-Butucaru, and Stefano Secci. Game Theoretical Framework for Analyzing Blockchains Robustness. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.42

Abstract

In this paper we propose a game theoretical framework in order to formally characterize the robustness of blockchains systems in terms of resilience to rational deviations and immunity to Byzantine behaviors. Our framework includes necessary and sufficient conditions for checking the immunity and resilience of games and an original technique for composing games that preserves the robustness of individual games. We prove the practical interest of our formal framework by characterizing the robustness of various blockchain protocols: Bitcoin (the most popular permissionless blockchain), Tendermint (the first permissioned blockchain used by the practitioners), Lightning Network, a side-chain protocol and a cross-chain swap protocol. For each one of the studied protocols we identify upper and lower bounds with respect to their resilience and immunity (expressed as no worse payoff than the initial state) face to rational and Byzantine behaviors.

Subject Classification

ACM Subject Classification
  • Networks
Keywords
  • Blockchain protocols
  • Distributed algorithms
  • Game-theoretical modeling
  • Fault tolerance
  • Failure robustness

Metrics

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

Related Versions

References

  1. Ittai Abraham, Danny Dolev, Rica Gonen, and Joe Halpern. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC '06, pages 53-62, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1146381.1146393.
  2. Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth. Bar fault tolerance for cooperative services. In SOSP '05, 2005. Google Scholar
  3. Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, and Sara Tucci Piergiovanni. Rational vs byzantine players in consensus-based blockchains. In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An, and Neil Yorke-Smith, editors, Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand, May 9-13, 2020, pages 43-51. International Foundation for Autonomous Agents and Multiagent Systems, 2020. URL: https://dl.acm.org/doi/abs/10.5555/3398761.3398772.
  4. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. Dissecting tendermint. In Mohamed Faouzi Atig and Alexander A. Schwarzmann, editors, Networked Systems, pages 166-182, Cham, 2019. Springer International Publishing. Google Scholar
  5. Zeta Avarikioti, Eleftherios Kokoris-Kogias, Roger Wattenhofer, and Dionysis Zindros. Brick: Asynchronous incentive-compatible payment channels. In International Conference on Financial Cryptography and Data Security, 2021. Google Scholar
  6. Marianna Belotti, Stefano Moretti, Maria Potop-Butucaru, and Stefano Secci. Game theoretical analysis of Atomic Cross-Chain Swaps. In 40th IEEE International Conference on Distributed Computing Systems (ICDCS), Singapore, Singapore, 2020. URL: https://hal.archives-ouvertes.fr/hal-02414356.
  7. Marianna Belotti, Stefano Moretti, and Paolo Zappalà. Rewarding miners: bankruptcy situations and pooling strategies. In 17th European Conference on Multi-Agent Systems (EUMAS), Tessaloniki, Greece, 2020. URL: https://hal.archives-ouvertes.fr/hal-02481155.
  8. Iddo Bentov, Pavel Hubácek, Tal Moran, and Asaf Nadler. Tortoise and hares consensus: the meshcash framework for incentive-compatible, scalable cryptocurrencies. IACR Cryptology ePrint Archive, 2017:300, 2017. Google Scholar
  9. B.Douglas Bernheim, Bezalel Peleg, and Michael D Whinston. Coalition-proof nash equilibria i. concepts. Journal of Economic Theory, 42(1):1-12, 1987. URL: https://doi.org/10.1016/0022-0531(87)90099-8.
  10. Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci., 777:155-183, 2019. URL: https://doi.org/10.1016/j.tcs.2019.02.001.
  11. Altannar Chinchuluun, Panos Pardalos, Athanasios Migdalas, and Leonidas Pitsoulis. Pareto Optimality, Game Theory And Equilibria, volume 17. Springer, 2008. URL: https://doi.org/10.1007/978-0-387-77247-9.
  12. Christian Ewerhart. Finite blockchain games. Economics Letters, 197:109614, 2020. URL: https://doi.org/10.1016/j.econlet.2020.109614.
  13. Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In International conference on financial cryptography and data security, pages 436-454. Springer, 2014. Google Scholar
  14. Peter Hammond. Utility Invariance in Non-Cooperative Games, volume 38, pages 31-50. Springer, June 2006. URL: https://doi.org/10.1007/0-387-25706-3.
  15. Maurice Herlihy. Atomic cross-chain swaps. In Proceedings of the 2018 ACM symposium on principles of distributed computing, pages 245-254, 2018. Google Scholar
  16. John Hillas. On the definition of the strategic stability of equilibria. Econometrica, 58(6):1365-1390, 1990. URL: http://www.jstor.org/stable/2938320.
  17. OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2021. URL: https://oeis.org/A178682.
  18. Aggelos Kiayias and Aikaterini-Panagiota Stouka. Coalition-safe equilibria with virtual payoffs. arXiv preprint, 2019. URL: http://arxiv.org/abs/2001.00047.
  19. Elon Kohlberg and Jean-Francois Mertens. On the strategic stability of equilibria. Econometrica: Journal of the Econometric Society, pages 1003-1037, 1986. Google Scholar
  20. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Christoph Meinel and Sophie Tison, editors, STACS 99, pages 404-413, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. Google Scholar
  21. Harold William Kuhn and Albert William Tucker. Contributions to the Theory of Games, volume 2. Princeton University Press, 1953. Google Scholar
  22. Jae Kwon. Tendermint: Consensus without mining. Draft v. 0.6, fall, 1(11), 2014. Google Scholar
  23. Z. Liu, N. C. Luong, W. Wang, D. Niyato, P. Wang, Y. Liang, and D. I. Kim. A survey on blockchain: A game theoretical perspective. IEEE Access, 7:47615-47643, 2019. Google Scholar
  24. Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer. When selfish meets evil: Byzantine players in a virus inoculation game. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, volume 2006, pages 35-44, January 2006. URL: https://doi.org/10.1145/1146381.1146391.
  25. Satoshi Nakamoto. A peer-to-peer electronic cash system, 2008. Google Scholar
  26. John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-49, 1950. URL: https://doi.org/10.1073/pnas.36.1.48.
  27. Tier Nolan. Re: Alt chains and atomic transfers. accessed on January 10, 2020. URL: https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949.
  28. Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 315-324, 2017. Google Scholar
  29. Alejandro Ranchal Pedrosa and Vincent Gramoli. Platypus: Offchain protocol without synchrony. In Aris Gkoulalas-Divanis, Mirco Marchetti, and Dimiter R. Avresky, editors, 18th IEEE International Symposium on Network Computing and Applications, NCA 2019, Cambridge, MA, USA, September 26-28, 2019, pages 1-8. IEEE, 2019. URL: https://doi.org/10.1109/NCA.2019.8935037.
  30. Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016. Google Scholar
  31. Serguei Popov, Olivia Saa, and Paulo Finardi. Equilibria in the tangle. Comput. Ind. Eng., 136:160-172, 2019. URL: https://doi.org/10.1016/j.cie.2019.07.025.
  32. Okke Schrijvers et al. Incentive compatibility of bitcoin mining pool reward functions. In International Conference on Financial Cryptography and Data Security, pages 477-498. Springer, 2016. Google Scholar
  33. Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol. IACR Cryptol. ePrint Arch., 2016:1159, 2016. Google Scholar
  34. Yonatan Sompolinsky and Aviv Zohar. Phantom. IACR Cryptology ePrint Archive, Report 2018/104, 2018. Google Scholar
  35. Itay Tsabary and Ittay Eyal. The gap game. In Proceedings of the 2018 ACM SIGSAC conference on Computer and Communications Security, pages 713-728, 2018. Google Scholar
  36. Florian Tschorsch and Björn Scheuermann. Bitcoin and beyond: A technical survey on decentralized digital currencies. IEEE Communications Surveys & Tutorials, 18(3):2084-2123, 2016. Google Scholar
  37. Wenbo Wang, Dinh Thai Hoang, Zehui Xiong, Dusit Niyato, Ping Wang, Peizhao Hu, and Yonggang Wen. A survey on consensus mechanisms and mining management in blockchain networks. arXiv preprint, pages 1-33, 2018. URL: http://arxiv.org/abs/1805.02707.
  38. Paolo Zappalà, Marianna Belotti, Maria Potop-Butucaru, and Stefano Secci. Game theoretical framework for analyzing blockchains robustness. Technical report, Sorbonne Université, CNRS, Laboratoire d'Informatique de Paris 6, LIP6, 2020. URL: https://hal.archives-ouvertes.fr/hal-02634752/document.
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