Ergodic mean-payo games for the analysis of attacks in crypto-currencies Conference Paper

Author(s): Chatterjee, Krishnendu; Goharshady A K; Ibsen-Jensen, Rasmus; Velner, Yaron
Title: Ergodic mean-payo games for the analysis of attacks in crypto-currencies
Title Series: LIPIcs
Affiliation IST Austria
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-payo 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.
Keywords: quantitative verification; Mean-payo games; Phrases crypto-currency
Conference Title: CONCUR: Conference on Concurrency Theory
Volume: 118
Conference Dates: September 4-7, 2018
Conference Location: Beijing, China
ISBN: 978-395977087-3
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2018-09-01
Start Page: Article number: 11
DOI: 10.4230/LIPIcs.CONCUR.2018.11
Notes: The research was partially supported by Vienna Science and Technology Fund (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Starting Grant (279307: Graph Games), and an IBM PhD Fellowship.
Open access: no
IST Austria Authors
Related IST Austria Work