License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.11
URN: urn:nbn:de:0030-drops-95497
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9549/
Chatterjee, Krishnendu ;
Kafshdar Goharshady, Amir ;
Ibsen-Jensen, Rasmus ;
Velner, Yaron
Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
Abstract
Crypto-currencies are digital assets designed to work as a medium of exchange, e.g., Bitcoin, but they are susceptible to attacks (dishonest behavior of participants). A framework for the analysis of attacks in crypto-currencies requires (a) modeling of game-theoretic aspects to analyze incentives for deviation from honest behavior; (b) concurrent interactions between participants; and (c) analysis of long-term monetary gains. Traditional game-theoretic approaches for the analysis of security protocols consider either qualitative temporal properties such as safety and termination, or the very special class of one-shot (stateless) games. However, to analyze general attacks on protocols for crypto-currencies, both stateful analysis and quantitative objectives are necessary. In this work our main contributions are as follows: (a) we show how a class of concurrent mean-payoff games, namely ergodic games, can model various attacks that arise naturally in crypto-currencies; (b) we present the first practical implementation of algorithms for ergodic games that scales to model realistic problems for crypto-currencies; and (c) we present experimental results showing that our framework can handle games with thousands of states and millions of transitions.
BibTeX - Entry
@InProceedings{chatterjee_et_al:LIPIcs:2018:9549,
author = {Krishnendu Chatterjee and Amir Kafshdar Goharshady and Rasmus Ibsen-Jensen and Yaron Velner},
title = {{Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies}},
booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)},
pages = {11:1--11:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-087-3},
ISSN = {1868-8969},
year = {2018},
volume = {118},
editor = {Sven Schewe and Lijun Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9549},
URN = {urn:nbn:de:0030-drops-95497},
doi = {10.4230/LIPIcs.CONCUR.2018.11},
annote = {Keywords: Crypto-currency, Quantitative Verification, Mean-payoff Games}
}
|
Keywords: |
|
Crypto-currency, Quantitative Verification, Mean-payoff Games |
|
Collection: |
|
29th International Conference on Concurrency Theory (CONCUR 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
31.08.2018 |
