Paper 2024/704

Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains

Krishnendu Chatterjee, Institute of Science and Technology Austria
Amirali Ebrahim-Zadeh, Sharif University of Technology
Mehrdad Karrabi, Institute of Science and Technology Austria
Krzysztof Pietrzak, Institute of Science and Technology Austria
Michelle Yeo, National University of Singapore
Djordje Zikelic
Abstract

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 $\epsilon$-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this $\epsilon$-tight lower bound, where $\epsilon>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. In 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. PODC
Keywords
BlockchainFormal MethodsEfficient Proof SystemsSelfish MiningMarkov Decision Process
Contact author(s)
krishnendu chatterjee @ ist ac at
ebrahimzadeh amirali @ gmail com
mehrdad karrabi @ ist ac at
krzysztof pietrzak @ ist ac at
mxyeo @ nus edu sg
dzikelic @ smu edu sg
History
2024-05-10: approved
2024-05-07: received
See all versions
Short URL
https://ia.cr/2024/704
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/704,
      author = {Krishnendu Chatterjee and Amirali Ebrahim-Zadeh and Mehrdad Karrabi and Krzysztof Pietrzak and Michelle Yeo and Djordje Zikelic},
      title = {Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/704},
      year = {2024},
      url = {https://eprint.iacr.org/2024/704}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.