{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T18:18:34Z","timestamp":1770833914032,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T00:00:00Z","timestamp":1710720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Distrib. Ledger Technol."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Recent advances in blockchain research have been made in two important directions. One is refined resilience analysis utilizing game theory to study the consequences of selfish behavior of users (miners), and the other is the extension from a linear (chain) structure to a non-linear (graphical) structure for performance improvements, such as IOTA and Graphcoin. The first question that comes to mind is what improvements a blockchain system would see by leveraging these new advances. In this article, we consider three major properties for a blockchain system: \u03b1-partial verification, scalability, and finality-duration. We establish a formal framework and prove that no blockchain system can achieve \u03b1-partial verification for any fixed constant \u03b1, high scalability, and low finality-duration simultaneously. We observe that classical blockchain systems like Bitcoin achieve full verification (\u03b1 =1) and low finality-duration, Ethereum 2.0 Sharding achieves low finality-duration and high scalability. We are interested in whether it is possible to partially satisfy the three properties.<\/jats:p>","DOI":"10.1145\/3607195","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T12:01:51Z","timestamp":1689336111000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Game Theoretical Analysis of Non-linear Blockchain System"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3909-4916","authenticated-orcid":false,"given":"Lin","family":"Chen","sequence":"first","affiliation":[{"name":"Texas Tech University, Lubbock, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7662-2119","authenticated-orcid":false,"given":"Lei","family":"Xu","sequence":"additional","affiliation":[{"name":"Kent State University, Edinburg, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0785-0609","authenticated-orcid":false,"given":"Zhimin","family":"Gao","sequence":"additional","affiliation":[{"name":"Auburn University at Montgomery, , Montgomery, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2040-2969","authenticated-orcid":false,"given":"Ahmed Imtiaz","family":"Sunny","sequence":"additional","affiliation":[{"name":"Texas Tech University, Lubbock, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4385-966X","authenticated-orcid":false,"given":"Keshav","family":"Kasichainula","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1994-4218","authenticated-orcid":false,"given":"Weidong","family":"Shi","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,3,18]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2021. Ethereum 2.0 Phase 1: Boosting Throughput with Sharding? Sharding. https:\/\/www.gemini.com\/cryptopedia\/ethereum-2-0-proof-of-stake-pos-blockchain-serenity"},{"key":"e_1_3_2_3_2","unstructured":"2022. What Is IOTA? IOTA Parameters. https:\/\/www.iota-services.com\/what-is-iota\/#::text=Confirmation%20time%20for%20value%20transactions need%20to%20pay%20any%20fees"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2886932"},{"key":"e_1_3_2_5_2","article-title":"Betting on blockchain consensus with fantomette","volume":"1805","author":"Azouvi Sarah","year":"2018","unstructured":"Sarah Azouvi, Patrick McCorry, and Sarah Meiklejohn. 2018. Betting on blockchain consensus with fantomette. CoRR abs\/1805.06786 (2018). arxiv:1805.06786http:\/\/arxiv.org\/abs\/1805.06786","journal-title":"CoRR"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318041.3355458"},{"key":"e_1_3_2_7_2","unstructured":"Xavier Boyen Christopher Carr and Thomas Haines. 2017. Blockchain-free cryptocurrencies. (2017)."},{"key":"e_1_3_2_8_2","unstructured":"C. Cachin and M. Vukoli\u0107. 2017. Blockchain consensus protocols in the wild. In International Symposium on Distributed Computing. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH Dagstuhl Publishing."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978408"},{"key":"e_1_3_2_10_2","first-page":"199","volume-title":"Advances in Cryptology: Proceedings of CRYPTO\u201982","author":"Chaum David","year":"1982","unstructured":"David Chaum. 1982. Blind signatures for untraceable payments. In Advances in Cryptology: Proceedings of CRYPTO\u201982. 199\u2013203."},{"key":"e_1_3_2_11_2","volume-title":"International Conference on Autonomous Agents and Multiagent Systems","author":"Chen Lin","year":"2021","unstructured":"Lin Chen, Lei Xu, Zhimin Gao, Ahmed Sunny, Keshav Kasichainula, and Weidong Shi. 2021. A game theoretical analysis of non-linear blockchain system. In International Conference on Autonomous Agents and Multiagent Systems."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2842460"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.13"},{"key":"e_1_3_2_14_2","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller William","year":"1991","unstructured":"William Feller. 1991. An Introduction to Probability Theory and its Applications. Vol. 81. John Wiley & Sons."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2021.103035"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2019.2950873"},{"key":"e_1_3_2_17_2","unstructured":"B. F. Fran\u00e7a. 2015. Homomorphic mini-blockchain scheme. HMBC. pdf."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40186-3_13"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.3390\/electronics9101610"},{"key":"e_1_3_2_20_2","unstructured":"Keith Alfaro. 2022. Polkadot and Ethereum 2.0. Wikipedia The Free Encyclopedia. Retrieved April 9 2023 from https:\/\/wiki.polkadot.network\/docs\/learn-comparisons-ethereum-2"},{"key":"e_1_3_2_21_2","unstructured":"Keith Alfaro. 2023. Bitcoin scalability problem Wikipedia The Free Encyclopedia. Retrieved April 9 2023 from https:\/\/wiki.polkadot.network\/docs\/learn-comparisons-ethereum-2"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2818623"},{"key":"e_1_3_2_23_2","first-page":"27","article-title":"Cosmos whitepaper","author":"Kwon Jae","year":"2019","unstructured":"Jae Kwon and Ethan Buchman. 2019. Cosmos whitepaper. A Netw. Distrib. Ledgers (2019), 27.","journal-title":"A Netw. Distrib. Ledgers"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3065880"},{"key":"e_1_3_2_25_2","article-title":"A survey on applications of game theory in blockchain","volume":"1902","author":"Liu Ziyao","year":"2019","unstructured":"Ziyao Liu, Nguyen Cong Luong, Wenbo Wang, Dusit Niyato, Ping Wang, Ying-Chang Liang, and Dong In Kim. 2019. A survey on applications of game theory in blockchain. CoRR abs\/1902.10865 (2019). http:\/\/arxiv.org\/abs\/1902.10865","journal-title":"CoRR"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2015.34"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1109\/SP.2013.34","volume-title":"2013 IEEE Symposium on Security and Privacy (SP\u201913)","author":"Miers Ian","year":"2013","unstructured":"Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. 2013. Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy (SP\u201913). IEEE Computer Society, 397\u2013411."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-25538-0_14"},{"key":"e_1_3_2_29_2","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008)."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_2_31_2","first-page":"131","article-title":"The tangle","author":"Popov Serguei","year":"2016","unstructured":"Serguei Popov. 2016. The tangle. cit. on (2016), 131.","journal-title":"cit. on"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.07.025"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.3390\/s22041411"},{"key":"e_1_3_2_34_2","unstructured":"Team Rocket. 2018. Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies. (2018)."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2863956"},{"key":"e_1_3_2_36_2","first-page":"555","volume-title":"Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO\u201999) (Lecture Notes in Computer Science)","volume":"1666","author":"Sander Tomas","year":"1999","unstructured":"Tomas Sander and Amnon Ta-Shma. 1999. Auditable, anonymous electronic cash extended abstract. In Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO\u201999) (Lecture Notes in Computer Science), Vol. 1666. Springer, 555\u2013572."},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/SP.2014.36","volume-title":"2014 IEEE Symposium on Security and Privacy (SP\u201914)","author":"Ben-Sasson Eli","year":"2014","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy (SP\u201914). IEEE, 459\u2013474."},{"key":"e_1_3_2_38_2","article-title":"Layer 2 blockchain scaling: A survey","author":"Sguanci Cosimo","year":"2021","unstructured":"Cosimo Sguanci, Roberto Spatafora, and Andrea Mario Vergani. 2021. Layer 2 blockchain scaling: A survey. arXiv preprint arXiv:2107.10881 (2021).","journal-title":"arXiv preprint arXiv:2107.10881"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3129314"},{"key":"e_1_3_2_40_2","first-page":"1159","article-title":"SPECTRE: A fast and scalable cryptocurrency protocol","volume":"2016","author":"Sompolinsky Yonatan","year":"2016","unstructured":"Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. 2016. SPECTRE: A fast and scalable cryptocurrency protocol. IACR Cryptology ePrint Archive 2016 (2016), 1159. http:\/\/eprint.iacr.org\/2016\/1159","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47854-7_32"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Yonatan Sompolinsky and Aviv Zohar. 2020. Phantom Ghostdag. (2020).","DOI":"10.1145\/3479722.3480990"},{"key":"e_1_3_2_43_2","unstructured":"The Ethereum Team. 2019. On sharding blockchains. (2019)."},{"key":"e_1_3_2_44_2","unstructured":"The Harmony Team. 2018. Harmony - technical whitepaper. (2018)."},{"key":"e_1_3_2_45_2","unstructured":"The Zilliqa Team. 2017. The Zilliqa technical whitepaper. (2017)."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3200051"},{"key":"e_1_3_2_47_2","unstructured":"N. P. Triantafyllidis and T. O. van Deventer. 2016. Developing an ethereum blockchain application.University of Amsterdam System and Network Engineering MSc 2015\u20132016."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2535718"},{"key":"e_1_3_2_49_2","first-page":"112","volume-title":"IFIP WG 11.4 International Workshop on Open Problems in Network Security (iNetSec\u201915), Revised Selected Papers (Lecture Notes in Computer Science)","author":"Vukolic Marko","year":"2015","unstructured":"Marko Vukolic. 2015. The quest for scalable blockchain fabric: Proof-of-work vs. BFT replication. In IFIP WG 11.4 International Workshop on Open Problems in Network Security (iNetSec\u201915), Revised Selected Papers (Lecture Notes in Computer Science), Vol. 9591. Springer, 112\u2013125."},{"key":"e_1_3_2_50_2","article-title":"Nash equilibrium. Wikipedia, The Free Encyclopedia","year":"2023","unstructured":"Wikipedia. 2023. Nash equilibrium. Wikipedia, The Free Encyclopedia. Retrieved June 2, 2023, from http:\/\/en.wikipedia.org\/w\/index.php?title=Nash%20equilibrium&oldid=1154772152","journal-title":"http:\/\/en.wikipedia.org\/w\/index.php?title=Nash%20equilibrium&oldid=1154772152"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3152824.3152825"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-96527-3_4"},{"key":"e_1_3_2_53_2","article-title":"Solana: A new architecture for a high performance blockchain v0. 8.13","author":"Yakovenko Anatoly","year":"2018","unstructured":"Anatoly Yakovenko. 2018. Solana: A new architecture for a high performance blockchain v0. 8.13. Whitepaper.","journal-title":"Whitepaper"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2019.2894727"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.icte.2021.09.014"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68711-7_2"}],"container-title":["Distributed Ledger Technologies: Research and Practice"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607195","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:34Z","timestamp":1750178254000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,18]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3607195"],"URL":"https:\/\/doi.org\/10.1145\/3607195","relation":{},"ISSN":["2769-6480","2769-6480"],"issn-type":[{"value":"2769-6480","type":"print"},{"value":"2769-6480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,18]]},"assertion":[{"value":"2022-12-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}