[{"language":[{"iso":"eng"}],"quality_controlled":"1","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"oa_version":"Published Version","oa":1,"_id":"17328","publication_identifier":{"isbn":["9798400706684"]},"date_created":"2024-07-28T22:01:10Z","doi":"10.1145/3662158.3662769","acknowledgement":"This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) grant and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.\r\n","citation":{"ista":"Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. 2024. Fully automated selfish mining analysis in efficient proof systems blockchains.  Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 268–278.","apa":"Chatterjee, K., Ebrahimzadeh, A., Karrabi, M., Pietrzak, K. Z., Yeo, M. X., &#38; Zikelic, D. (2024). Fully automated selfish mining analysis in efficient proof systems blockchains. In <i> Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 268–278). Nantes, France: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3662158.3662769\">https://doi.org/10.1145/3662158.3662769</a>","ieee":"K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K. Z. Pietrzak, M. X. Yeo, and D. Zikelic, “Fully automated selfish mining analysis in efficient proof systems blockchains,” in <i> Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Nantes, France, 2024, pp. 268–278.","mla":"Chatterjee, Krishnendu, et al. “Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains.” <i> Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2024, pp. 268–78, doi:<a href=\"https://doi.org/10.1145/3662158.3662769\">10.1145/3662158.3662769</a>.","short":"K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K.Z. Pietrzak, M.X. Yeo, D. Zikelic, in:,  Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2024, pp. 268–278.","chicago":"Chatterjee, Krishnendu, Amirali Ebrahimzadeh, Mehrdad Karrabi, Krzysztof Z Pietrzak, Michelle X Yeo, and Dorde Zikelic. “Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains.” In <i> Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, 268–78. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3662158.3662769\">https://doi.org/10.1145/3662158.3662769</a>.","ama":"Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. Fully automated selfish mining analysis in efficient proof systems blockchains. In: <i> Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2024:268-278. doi:<a href=\"https://doi.org/10.1145/3662158.3662769\">10.1145/3662158.3662769</a>"},"scopus_import":"1","type":"conference","month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"conference":{"name":"PODC: Symposium on Principles of Distributed Computing","location":"Nantes, France","start_date":"2024-06-17","end_date":"2024-06-21"},"external_id":{"arxiv":["2405.04420"]},"article_processing_charge":"Yes (via OA deal)","page":"268-278","file_date_updated":"2024-07-29T07:18:12Z","ec_funded":1,"abstract":[{"text":"We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems - like proofs of stake or proofs of space - and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (MDP). We then present a formal analysis procedure which computes an ϵ-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be any specified precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines.\r\nIn concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.","lang":"eng"}],"publication":" Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing","title":"Fully automated selfish mining analysis in efficient proof systems blockchains","day":"17","year":"2024","file":[{"file_id":"17334","file_name":"2024_ACM_Chatterjee.pdf","success":1,"access_level":"open_access","date_created":"2024-07-29T07:18:12Z","checksum":"6122bd97b42751ff81c452a19970f67d","relation":"main_file","content_type":"application/pdf","date_updated":"2024-07-29T07:18:12Z","file_size":832034,"creator":"dernst"}],"publication_status":"published","status":"public","publisher":"Association for Computing Machinery","date_updated":"2025-04-14T07:52:47Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"has_accepted_license":"1","ddc":["000"],"date_published":"2024-06-17T00:00:00Z","corr_author":"1","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Ebrahimzadeh, Amirali","last_name":"Ebrahimzadeh","first_name":"Amirali"},{"id":"67638922-f394-11eb-9cf6-f20423e08757","full_name":"Karrabi, Mehrdad","last_name":"Karrabi","first_name":"Mehrdad"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X"},{"orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","last_name":"Zikelic"}]},{"page":"40-49","article_processing_charge":"Yes (via OA deal)","conference":{"start_date":"2024-06-17","end_date":"2024-06-21","location":"Nantes, France","name":"PODC: Symposium on Principles of Distributed Computing"},"project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"title":"Game dynamics and equilibrium computation in the population protocol model","publication":"Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing","abstract":[{"lang":"eng","text":"We initiate the study of game dynamics in the population protocol model: n agents each maintain a current local strategy and interact in pairs uniformly at random. Upon each interaction, the agents play a two-person game and receive a payoff from an underlying utility function, and they can subsequently update their strategies according to a fixed local algorithm. In this setting, we ask how the distribution over agent strategies evolves over a sequence of interactions, and we introduce a new distributional equilibrium concept to quantify the quality of such distributions. As an initial example, we study a class of repeated prisoner's dilemma games, and we consider a family of simple local update algorithms that yield non-trivial dynamics over the distribution of agent strategies. We show that these dynamics are related to a new class of high-dimensional Ehrenfest random walks, and we derive exact characterizations of their stationary distributions, bounds on their mixing times, and prove their convergence to approximate distributional equilibria. Our results highlight trade-offs between the local state space of each agent, and the convergence rate and approximation factor of the underlying dynamics. Our approach opens the door towards the further characterization of equilibrium computation for other classes of games and dynamics in the population setting."}],"ec_funded":1,"file_date_updated":"2024-07-29T07:37:31Z","oa":1,"oa_version":"Published Version","department":[{"_id":"DaAl"},{"_id":"KrCh"}],"language":[{"iso":"eng"}],"quality_controlled":"1","month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","scopus_import":"1","citation":{"apa":"Alistarh, D.-A., Chatterjee, K., Karrabi, M., &#38; Lazarsfeld, J. M. (2024). Game dynamics and equilibrium computation in the population protocol model. In <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 40–49). Nantes, France: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3662158.3662768\">https://doi.org/10.1145/3662158.3662768</a>","ista":"Alistarh D-A, Chatterjee K, Karrabi M, Lazarsfeld JM. 2024. Game dynamics and equilibrium computation in the population protocol model. Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 40–49.","ama":"Alistarh D-A, Chatterjee K, Karrabi M, Lazarsfeld JM. Game dynamics and equilibrium computation in the population protocol model. In: <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2024:40-49. doi:<a href=\"https://doi.org/10.1145/3662158.3662768\">10.1145/3662158.3662768</a>","chicago":"Alistarh, Dan-Adrian, Krishnendu Chatterjee, Mehrdad Karrabi, and John M Lazarsfeld. “Game Dynamics and Equilibrium Computation in the Population Protocol Model.” In <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, 40–49. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3662158.3662768\">https://doi.org/10.1145/3662158.3662768</a>.","short":"D.-A. Alistarh, K. Chatterjee, M. Karrabi, J.M. Lazarsfeld, in:, Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2024, pp. 40–49.","ieee":"D.-A. Alistarh, K. Chatterjee, M. Karrabi, and J. M. Lazarsfeld, “Game dynamics and equilibrium computation in the population protocol model,” in <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Nantes, France, 2024, pp. 40–49.","mla":"Alistarh, Dan-Adrian, et al. “Game Dynamics and Equilibrium Computation in the Population Protocol Model.” <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2024, pp. 40–49, doi:<a href=\"https://doi.org/10.1145/3662158.3662768\">10.1145/3662158.3662768</a>."},"acknowledgement":"This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) grant. We thank James Aspnes and Thomas Sauerwald for several helpful discussions on Ehrenfest random walks.","doi":"10.1145/3662158.3662768","date_created":"2024-07-28T22:01:10Z","publication_identifier":{"isbn":["9798400706684"]},"_id":"17329","has_accepted_license":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Karrabi, Mehrdad","id":"67638922-f394-11eb-9cf6-f20423e08757","first_name":"Mehrdad","last_name":"Karrabi"},{"full_name":"Lazarsfeld, John M","id":"17ce3656-183e-11ef-84c3-8932383e1b23","first_name":"John M","last_name":"Lazarsfeld"}],"corr_author":"1","ddc":["000"],"date_published":"2024-06-17T00:00:00Z","file":[{"access_level":"open_access","relation":"main_file","checksum":"65a40437f83373fa79dd999d5287509e","date_created":"2024-07-29T07:37:31Z","file_size":750908,"content_type":"application/pdf","date_updated":"2024-07-29T07:37:31Z","creator":"dernst","file_id":"17335","file_name":"2024_ACMPODC_Alistarh.pdf","success":1}],"year":"2024","day":"17","date_updated":"2025-04-14T07:52:47Z","publisher":"Association for Computing Machinery","status":"public","publication_status":"published"}]