Lars Brünjes, Aggelos Kiayias, Ηλίας Κουτσουπιάς, Aikaterini-Panagiota Stouka
We introduce and study reward sharing schemes (RSS) that promote the fair formation of {\em stake pools}\ in collaborative projects that involve a large number of stakeholders such as the maintenance of a proof-of-stake (PoS) blockchain. Our mechanisms are parameterized by a target value for the desired number of pools. We show that by properly incentivizing participants, the desired number of stake pools is a Nash equilibrium arising from rational play. Our equilibria also exhibit an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. We then describe how RSS can be deployed in the PoS setting, mitigating a number of potential deployment attacks and protocol deviations that include censoring transactions, performing Sybil attacks with the objective to control the majority of stake, lying about the actual cost and others. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more "fair", perhaps counterintuitively, converge to centralized equilibria.
This paper deals with the design of the secure blockchain network framework to prevent damages from an attacker. The decentralized network design called the Blockchain Governance Game is a new hybrid theoretical model and it provides the stochastic game framework to find best strategies towards preparation for preventing a network malfunction by an attacker. Analytically tractable results are obtained by using the fluctuation theory and the mixed strategy game theory. These results enable to predict the moment for operations and deliver the optimal portion of backup nodes to protect the blockchain network. This research helps for whom considers the initial coin offering or launching new blockchain based services with enhancing the security features.
A fundamental problem for electronic commerce is the buying and selling of digital goods between individuals that may not know or trust each other. Traditionally, this problem has been addressed by the use of trusted third-parties such as credit-card companies, mediated escrows, legal adjudication, or reputation systems. Despite the rise of blockchain protocols as a way to send payments without trusted third parties, the important problem of exchanging a digital good for payment without trusted third parties has been paid much less attention. We refer to this problem as the Buyer and Seller's Dilemma and present for it a dual-deposit escrow trade protocol which uses double-sided payment deposits in conjunction with simple cryptographic primitives, and that can be implemented using a blockchain-based smart contract. We analyze our protocol as an extensive-form game and prove that the Sub-game Perfect Nash Equilibrium for this game is for both the buyer and seller to cooperate and behave honestly. We address this problem under the assumption that the digital good being traded is known and verifiable, with a fixed price known to both parties.
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, Yaron Velner
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.
Alexander Spiegelman, Idit Keidar, Moshe Tennenholtz
We formalize the current practice of strategic mining in multi-cryptocurrency markets as a game, and prove that any better-response learning in such games converges to equilibrium. We then offer a reward design scheme that moves the system configuration from any initial equilibrium to a desired one for any better-response learning of the miners. Our work introduces the first multi-coin strategic attack for adaptive and learning miners, as well as the study of reward design in a multi-agent system of learning agents.
We review the so called selfish mining strategy in the Bitcoin network and compare its profitability to honest mining.We build a rigorous profitability model for repetition games. The time analysis of the attack has been ignored in the previous literature based on a Markov model,but is critical. Using martingale's techniques and Doob Stopping Time Theorem we compute the expected duration of attack cycles. We discover a remarkable property of the bitcoin network: no strategy is more profitable than the honest strategy before a difficulty adjustment. So selfish mining can only become profitable afterwards, thus it is an attack on the difficulty adjustment algorithm. We propose an improvement of Bitcoin protocol making it immune to selfish mining attacks. We also study miner's attraction to selfish mining pools. We calculate the expected duration time before profit for the selfish miner, a computation that is out of reach by the previous Markov models.
Open-access blockchains based on proof-of-work protocols have gained tremendous popularity for their capabilities of providing decentralized tamper-proof ledgers and platforms for data-driven autonomous organization. Nevertheless, the proof-of-work based consensus protocols are vulnerable to cyber-attacks such as double-spending. In this paper, we propose a novel approach of cyber risk management for blockchain-based service. In particular, we adopt the cyber-insurance as an economic tool for neutralizing cyber risks due to attacks in blockchain networks. We consider a blockchain service market, which is composed of the infrastructure provider, the blockchain provider, the cyber-insurer, and the users. The blockchain provider purchases from the infrastructure provider, e.g., a cloud, the computing resources to maintain the blockchain consensus, and then offers blockchain services to the users. The blockchain provider strategizes its investment in the infrastructure and the service price charged to the users, in order to improve the security of the blockchain and thus optimize its profit. Meanwhile, the blockchain provider also purchases a cyber-insurance from the cyber-insurer to protect itself from the potential damage due to the attacks. In return, the cyber-insurer adjusts the insurance premium according to the perceived risk level of the blockchain service. Based on the assumption of rationality for the market entities, we model the interaction among the blockchain provider, the users, and the cyber-insurer as a two-level Stackelberg game. Namely, the blockchain provider and the cyber-insurer lead to set their pricing/investment strategies, and then the users follow to determine their demand of the blockchain service. Specifically, we consider the scenario of double-spending attacks and provide a series of analytical results about the Stackelberg equilibrium in the market game.
As an emerging decentralized secure data management platform, blockchain has gained much popularity recently. To maintain a canonical state of blockchain data record, proof-of-work based consensus protocols provide the nodes, referred to as miners, in the network with incentives for confirming new block of transactions through a process of “block mining” by solving a cryptographic puzzle. Under the circumstance of limited local computing resources, e.g., mobile devices, it is natural for rational miners, i.e., consensus nodes, to offload computational tasks for proof of work to the cloud/fog computing servers. Therefore, we focus on the trading between the cloud/fog computing service provider and miners, and propose an auction-based market model for efficient computing resource allocation. In particular, we consider a proof-of-work based blockchain network, which is constrained by the computing resource and deployed as an infrastructure for decentralized data management applications. Due to the competition among miners in the blockchain network, the allocative externalities are particularly taken into account when designing the auction mechanisms. Specifically, we consider two bidding schemes: the constant-demand scheme where each miner bids for a fixed quantity of resources, and the multi-demand scheme where the miners can submit their preferable demands and bids. For the constant-demand bidding scheme, we propose an auction mechanism that achieves optimal social welfare. In the multi-demand bidding scheme, the social welfare maximization problem is NP-hard. Therefore, we design an approximate algorithm which guarantees the truthfulness, individual rationality and computational efficiency. Through extensive simulations, we show that our proposed auction mechanisms with the two bidding schemes can efficiently maximize the social welfare of the blockchain network and provide effective strategies for the cloud/fog computing service provider.
We consider users which may have renewable energy harvesting devices, or distributed generators. Such users can behave as consumer or producer (hence, we denote them as prosumers) at different time instances. A prosumer may sell the energy to other prosumers in exchange of money. We consider a demand response model, where the price of conventional energy depends on the total demand of all the prosumers at a certain time. A prosumer depending on its own utility has to select the amount of energy it wants to buy either from the grid or from other prosumers, or the amount of excess energy it wants to sell to other prosumers. However, the strategy, and the payoff of a prosumer inherently depends on the strategy of other prosumers as a prosumer can only buy if the other prosumers are willing to sell. We formulate the problem as a coupled constrained game, and seek to obtain the generalized Nash equilibrium. We show that the game is a concave potential game and show that there exists a unique generalized Nash equilibrium. We consider that a platform will set the price for distributed interchange of energy among the prosumers in order to minimize the consumption of the conventional energy. We propose a distributed algorithm where the platform sets a price to each prosumer, and then each prosumer at a certain time only optimizes its own payoff. The prosumer then updates the price depending on the supply and demand for each prosumer. We show that the algorithm converges to an optimal generalized Nash equilibrium. The distributed algorithm also provides an optimal price for the exchange market.
Given the parallels between game theory and consensus, it makes sense to intelligently design blockchain or DAG protocols with an incentive-compatible-first mentality. To that end, we propose a new blockchain or DAG protocol enhancement based on delayed rewards. We devise a new method for imposing slashing conditions on miner behavior, using their delayed rewards as stake in a Proof of Work system. Using fraud proofs, we can slash malicious miner behavior and reward long-lived, honest behavior.
Many of today's crypto currencies use blockchains as decentralized ledgers and secure them with proof of work. In case of a fork of the chain, Bitcoin's rule for achieving consensus is selecting the longest chain and discarding the other chain as stale. It has been demonstrated that this consensus rule has a weakness against selfish mining in which the selfish miner exploits the variance in block generation by partially withholding blocks. In Ethereum, however, under certain conditions stale blocks don't have to be discarded but can be referenced from the main chain as uncle blocks yielding a partial reward. This concept limits the impact of network delays on the expected revenue for miners. But the concept also reduces the risk for a selfish miner to gain no rewards from withholding a freshly minted block. This paper uses a Monte Carlo simulation to quantify the effect of uncle blocks both to the profitability of selfish mining and the blockchain's security in Ethereum (ETH). A brief outlook about a recent Ethereum Classic (ETC) improvement proposal that weighs uncle blocks during the selection of the main chain will be given.
Tin Leelavimolsilp, Long Tran-Thanh, Sebastian Stein
Eyal and Sirer's selfish mining strategy has demonstrated that Bitcoin system is not secure even if 50% of total mining power is held by altruistic miners. Since then, researchers have been investigating either to improve the efficiency of selfish mining, or how to defend against it, typically in a single selfish miner setting. Yet there is no research on a selfish mining strategies concurrently used by multiple miners in the system. The effectiveness of such selfish mining strategies and their required mining power under such multiple selfish miners setting remains unknown. In this paper, a preliminary investigation and our findings of selfish mining strategy used by multiple miners are reported. In addition, the conventional model of Bitcoin system is slightly redesigned to tackle its shortcoming: namely, a concurrency of individual mining processes. Although a theoretical analysis of selfish mining strategy under this setting is yet to be established, the current findings based on simulations is promising and of great interest. In particular, our work shows that a lower bound of power threshold required for selfish mining strategy decreases in proportion to a number of selfish miners. Moreover, there exist Nash equilibria where all selfish miners in the system do not change to an honest mining strategy and simultaneously earn their unfair amount of mining reward given that they equally possess sufficiently large mining power. Lastly, our new model yields a power threshold for mounting selfish mining strategy slightly greater than one from the conventional model.
Mohammad Hossein Manshaei, Murtuza Jadliwala, Anindya Maiti, Mahdi Fooladgar
Low transaction throughput and poor scalability are significant issues in public blockchain consensus protocols such as Bitcoins. Recent research efforts in this direction have proposed shard-based consensus protocols where the key idea is to split the transactions among multiple committees (or shards), which then process these shards or set of transactions in parallel. Such a parallel processing of disjoint sets of transactions or shards by multiple committees significantly improves the overall scalability and transaction throughout of the system. However, one significant research gap is a lack of understanding of the strategic behavior of rational processors within committees in such shard-based consensus protocols. Such an understanding is critical for designing appropriate incentives that will foster cooperation within committees and prevent free-riding. In this paper, we address this research gap by analyzing the behavior of processors using a game-theoretic model, where each processor aims at maximizing its reward at a minimum cost of participating in the protocol. We first analyze the Nash equilibria in an N-player static game model of the sharding protocol. We show that depending on the reward sharing approach employed, processors can potentially increase their payoff by unilaterally behaving in a defective fashion, thus resulting in a social dilemma. In order to overcome this social dilemma, we propose a novel incentive-compatible reward sharing mechanism to promote cooperation among processors. Our numerical results show that achieving a majority of cooperating processors (required to ensure a healthy state of the blockchain network) is easier to achieve with the proposed incentive-compatible reward sharing mechanism than with other reward sharing mechanisms.
Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies. However, the economic effect of transaction channels on the system has not been explored much until now. We study the economics of Bitcoin transaction channels, and present a framework for an economic analysis of the lightning network and its effect on transaction fees on the blockchain. Our framework allows us to reason about different patterns of demand for transactions and different topologies of the lightning network, and to derive the resulting fees for transacting both on and off the blockchain. Our initial results indicate that while the lightning network does allow for a substantially higher number of transactions to pass through the system, it does not necessarily provide higher fees to miners, and as a result may in fact lead to lower participation in mining within the system.
Strategic interactions between competitive entities are generally considered from the perspective of complete revelation of benefits achieved from those interactions, in the form of public payoff functions and/or beliefs, in the announced games. However, there exist strategic interplays between competitors where the players have a choice to strategise under the availability of private payoffs, in similar competitive settings. In this contribution, we propose a formal framework for a competitive ecosystem where each player is permitted to defect from publicly optimal strategies under certain private payoffs greater than announced payoffs, given that these defections have certain acceptable bounds in the long run as agreed by all players. We call this game theoretic construction an Intention Game. We formally define an Intention Game, and notions of participational equilibria that exist in such interactions that permit public defections. We compare Intention Games with conventional strategic form games, and demonstrate a type-theoretic construction of Intention Games. In a partially honest setting, we give Intention Game instances of a Cournot competition, secure interactions between mobile applications, an Internet services' data sourcing competition between Internet service providers through content delivery networks, and a Bitcoin mining competition. We give a use of Intention Games to determine player participation in a cryptographic protocol. Finally, we demonstrate the possibility of a dual model of the Intention Games framework.
We analyse the Tangle --- a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment's locations are chosen by means of random walks on that graph. These new vertices, also thought of as "transactions", are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system (www.iota.org). We prove existence of "almost symmetric" Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the "selfish" players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the "recommended" one.
In blockchain networks adopting the proof-of-work schemes, the monetary incentive is introduced by the Nakamoto consensus protocol to guide the behaviors of the full nodes (i.e., block miners) in the process of maintaining the consensus about the blockchain state. The block miners have to devote their computation power measured in hash rate in a crypto-puzzle solving competition to win the reward of publishing (a.k.a., mining) new blocks. Due to the exponentially increasing difficulty of the crypto-puzzle, individual block miners tends to join mining pools, i.e., the coalitions of miners, in order to reduce the income variance and earn stable profits. In this paper, we study the dynamics of mining pool selection in a blockchain network, where mining pools may choose arbitrary block mining strategies. We identify the hash rate and the block propagation delay as two major factors determining the outcomes of mining competition, and then model the strategy evolution of the individual miners as an evolutionary game. We provide the theoretical analysis of the evolutionary stability for the pool selection dynamics in a case study of two mining pools. The numerical simulations provide the evidence to support our theoretical discoveries as well as demonstrating the stability in the evolution of miners' strategies in a general case.
José Horta, Daniel Kofman, David Menga, Alonso Silva
Future electricity distribution grids will host a considerable share of variable renewable energy sources and local storage resources. Moreover, they will face new load structures due for example to the growth of the electric vehicle market. These trends raise the need for new paradigms for distribution grids operation, in which Distribution System Operators will increasingly rely on demand side flexibility and households will progressively become prosumers playing an active role on smart grid energy management. However, in present energy management architectures, the lack of coordination among actors limits the capability of the grid to enable the mentioned trends. In this paper we tackle this problem by proposing an architecture that enables households to autonomously exchange energy blocks and flexibility services with neighbors, operators and market actors. The solution is based on a blockchain transactive platform. We focus on a market application, where households can trade energy with their neighbors, aimed to locally balancing renewable energy production. We propose a market mechanism and dynamic transport prices that provide an incentive for households to locally manage energy resources in a way that responds to both pro-sumer and operator needs. We evaluate the impact of such markets through comprehensive simulations using power flow analysis and realistic load profiles, providing valuable insight for the design of appropriate mechanisms and incentives.
Blockchain has recently been applied in many applications such as bitcoin, smart grid, and Internet of Things (IoT) as a public ledger of transactions. However, the use of blockchain in mobile environments is still limited because the mining process consumes too much computing and energy resources on mobile devices. Edge computing offered by the Edge Computing Service Provider can be adopted as a viable solution for offloading the mining tasks from the mobile devices, i.e., miners, in the mobile blockchain environment. However, a mechanism needs to be designed for edge resource allocation to maximize the revenue for the Edge Computing Service Provider and to ensure incentive compatibility and individual rationality is still open. In this paper, we develop an optimal auction based on deep learning for the edge resource allocation. Specifically, we construct a multi-layer neural network architecture based on an analytical solution of the optimal auction. The neural networks first perform monotone transformations of the miners' bids. Then, they calculate allocation and conditional payment rules for the miners. We use valuations of the miners as the data training to adjust parameters of the neural networks so as to optimize the loss function which is the expected, negated revenue of the Edge Computing Service Provider. We show the experimental results to confirm the benefits of using the deep learning for deriving the optimal auction for mobile blockchain with high revenue
As the core issue of blockchain, the mining requires solving a proof-of-work puzzle, which is resource expensive to implement in mobile devices due to the high computing power needed. Thus, the development of blockchain in mobile applications is restricted. In this paper, we, for the first time, consider the edge computing as the network enabler for mobile blockchain. In particular, we study optimal pricing-based edge computing resource management to support mobile blockchain applications where the mining process can be offloaded to an Edge computing Service Provider (ESP). We adopt a two-stage Stackelberg game to jointly maximize the profit of the ESP and the individual utilities of different miners. In Stage~I, the ESP sets the price of edge computing services. In Stage~II, the miners decide on the service demand to purchase based on the observed prices. We apply the backward induction to analyze the sub-game perfect equilibrium in each stage for uniform and discriminatory pricing schemes. Further, the existence and uniqueness of Stackelberg game are validated for both pricing schemes. At last, the performance evaluation shows that the ESP intends to set the maximum possible value as optimal price for profit maximization under uniform pricing. In addition, the discriminatory pricing helps the ESP to encourage higher total service demand from miners and achieve greater profit correspondingly.
Blockchain, an emerging decentralized security system, has been applied in many applications, such as bitcoin, smart grid, and Internet-of-Things. However, running the mining process may cost too much energy consumption and computing resource usage on handheld devices, which restricts the use of blockchain in mobile environments. In this paper, we consider deploying edge computing service to support the mobile blockchain. We propose an auction-based edge computing resource market of the edge computing service provider. Since there is competition among miners, the allocative externalities (positive and negative) are taken into account in the model. In our auction mechanism, we maximize the social welfare while guaranteeing the truthfulness, individual rationality and computational efficiency. Based on blockchain mining experiment results, we define a hash power function that characterizes the probability of successfully mining a block. Through extensive simulations, we evaluate the performance of our auction mechanism which shows that our edge computing resources market model can efficiently solve the social welfare maximization problem for the edge computing service provider.
Public blockchain networks using proof of work (PoW)-based consensus protocols are considered as a promising platform for decentralized resource management with financial incentive mechanisms. In order to maintain a secured, universal state of the blockchain, PoW-based consensus protocols financially incentivize the nodes in the network to compete for the privilege of block generation through cryptographic puzzle solving. For rational consensus nodes, i.e., miners with limited local computational resources, offloading the computation load for PoW to the cloud/fog providers (CFPs) becomes a viable option. In this paper, we study the interaction between the CFPs and the miners in a PoW-based blockchain network using a game theoretic approach. In particular, we propose a lightweight infrastructure of the PoW-based blockchains, where the computation-intensive part of the consensus process is offloaded to the cloud/fog. We formulate the computation resource management in the blockchain consensus process as a two-stage Stackelberg game, where the profit of the CFP and the utilities of the individual miners are jointly optimized. In the first stage of the game, the CFP sets the price of offered computing resource. In the second stage, the miners decide on the amount of service to purchase accordingly. We apply backward induction to analyze the subgame perfect equilibria in each stage for both uniform and discriminatory pricing schemes. For uniform pricing where the same price applies to all miners, the uniqueness of the Stackelberg equilibrium is validated by identifying the best response strategies of the miners. For discriminatory pricing where the different prices are applied, the uniqueness of the Stackelberg equilibrium is proved by capitalizing on the variational inequality theory. Further, the real experimental results are employed to justify our proposed model.
The Bitcoin payment system involves two agent types: Users that transact with the currency and pay fees and miners in charge of authorizing transactions and securing the system in return for these fees. Two of Bitcoin's challenges are (i) securing sufficient miner revenues as block rewards decrease, and (ii) alleviating the throughput limitation due to a small maximal block size cap. These issues are strongly related as increasing the maximal block size may decrease revenue due to Bitcoin's pay-your-bid approach. To decouple them, we analyze the “monopolistic auction” [8], showing: (i) its revenue does not decrease as the maximal block size increases, (ii) it is resilient to an untrusted auctioneer (the miner), and (iii) simplicity for transaction issuers (bidders), as the average gain from strategic bid shading (relative to bidding one's true maximal willingness to pay) diminishes as the number of bids increases.
Mining for Bitcoins is a high-risk high-reward activity. Miners, seeking to reduce their variance and earn steadier rewards, collaborate in pooling strategies where they jointly mine for Bitcoins. Whenever some pool participant is successful, the earned rewards are appropriately split among all pool participants. Currently a dozen of different pooling strategies (i.e., methods for distributing the rewards) are in use for Bitcoin mining. We here propose a formal model of utility and social welfare for Bitcoin mining (and analogous mining systems) based on the theory of discounted expected utility, and next study pooling strategies that maximize the social welfare of miners. Our main result shows that one of the pooling strategies actually employed in practice--the so-called geometric pay pool--achieves the optimal steady-state utility for miners when its parameters are set appropriately. Our results apply not only to Bitcoin mining pools, but any other form of pooled mining or crowdsourcing computations where the participants engage in repeated random trials towards a common goal, and where "partial" solutions can be efficiently verified.