Massimo Bartoletti, James Hsin-yu Chiang, Alberto Lluch Lafuente
Automated market makers (AMMs) are one of the most prominent decentralized finance (DeFi) applications. AMMs allow users to trade different types of crypto-tokens, without the need to find a counter-party. There are several implementations and models for AMMs, featuring a variety of sophisticated economic mechanisms. We present a theory of AMMs. The core of our theory is an abstract operational model of the interactions between users and AMMs, which can be concretised by instantiating the economic mechanisms. We exploit our theory to formally prove a set of fundamental properties of AMMs, characterizing both structural and economic aspects. We do this by abstracting from the actual economic mechanisms used in implementations, and identifying sufficient conditions which ensure the relevant properties. Notably, we devise a general solution to the arbitrage problem, the main game-theoretic foundation behind the economic mechanisms of AMMs.
Peer-review is a necessary and essential quality control step for scientific publications but lacks proper incentives. Indeed, the process, which is very costly in terms of time and intellectual investment, not only is not remunerated by the journals but is also not openly recognized by the academic community as a relevant scientific output for a researcher. Therefore, scientific dissemination is affected in timeliness, quality, and fairness. Here, to solve this issue, we propose a blockchain-based incentive system that rewards scientists for peer-reviewing other scientists' work and that builds up trust and reputation. We designed a privacy-oriented protocol of smart contracts called Ants-Review that allows authors to issue a bounty for open anonymous peer-reviews on Ethereum. If requirements are met, peer-reviews will be accepted and paid by the approver proportionally to their assessed quality. To promote ethical behavior and inclusiveness the system implements a gamified mechanism that allows the whole community to evaluate the peer-reviews and vote for the best ones.
Bitcoin has witnessed a prevailing transition that employing transaction fees paid by users rather than subsidy assigned by the system as the main incentive for mining.
Massimo Bartoletti, James Hsin-yu Chiang, Alberto Lluch Lafuente
Lending pools are decentralized applications which allow mutually untrusted users to lend and borrow crypto-assets. These applications feature complex, highly parametric incentive mechanisms to equilibrate the loan market. This complexity makes the behaviour of lending pools difficult to understand and to predict: indeed, ineffective incentives and attacks could potentially lead to emergent unwanted behaviours. Reasoning about lending pools is made even harder by the lack of executable models of their behaviour: to precisely understand how users interact with lending pools, eventually one has to inspect their implementations, where the incentive mechanisms are intertwined with low-level implementation details. Further, the variety of existing implementations makes it difficult to distill the common aspects of lending pools. We systematize the existing knowledge about lending pools, leveraging a new formal model of interactions with users, which reflects the archetypal features of mainstream implementations. This enables us to prove some general properties of lending pools, such as the correct handling of funds, and to precisely describe vulnerabilities and attacks. We also discuss the role of lending pools in the broader context of decentralized finance.
Payment channels networks drastically increase the throughput and hence scalability of blockchains by performing transactions \emph{off-chain}. In an off-chain payment, parties deposit coins in a channel and then perform transactions without invoking the global consensus mechanism of the blockchain. However, the transaction value is limited by the capacity of the channel, i.e., the amount of funds available on a channel. These funds decrease when a transaction is sent and increase when a transaction is received on the channel. Recent research indicates that there is an imbalance between sending and receiving transactions, which leads to channel depletion in the sense that one of these operations becomes impossible over time due to the lack of available funds. We incentivize the balanced use of payment channels through fees. Whereas the current fee model depends solely on the transaction value, our fee policies encourage transactions that have a positive effect on the balance in a channel and discourage those that have a negative effect. This paper first defines necessary properties of fee strategies. Then, it introduces two novel fees strategies that provably satisfy all necessary properties. Our extensive simulation study reveals that these incentives increase the effectiveness of payments by $8\%$ to $19\%$.
EIP-1559 is a proposal to make several tightly coupled additions to Ethereum's transaction fee mechanism, including variable-size blocks and a burned base fee that rises and falls with demand. This report assesses the game-theoretic strengths and weaknesses of the proposal and explores some alternative designs.
Private blockchain is driving the creation of business networks, resulting in the creation of new value or new business models to the enterprises participating in the network. Such business networks form when enterprises come together to derive value through a network which is greater than the value that can be derived solely by any single company. This results in a setting that combines both competitive and cooperative behavior, and which we call strategic coopetition. Traditionally, cooperative and competitive behavior have been analyzed separately in game theory. In this article, we provide a formal model enabling to jointly analyze these different types of behaviors and the interdependencies between them. Using this model, we formally demonstrate and analyze the incentives for both cooperative and competitive behavior.
Temporary fork is a fundamental phenomenon in many blockchains with proof of work, and the analysis of temporary fork has recently drawn great attention. Different from existing efforts that focus on the blockchain system factors such as block size, network propagation delay or block generation speed, in this paper we explore a new key dimension of computing power from the miners' perspective. Specifically, we first propose a detailed mathematical model to characterize the impact of computing power competition of the mining pools on the temporary fork. We also derive closed-form formula of the probability of temporary fork and the expected mining reward of a mining pool. To reveal the long-term trends on the computing power distributions over the competing mining pools, we then develop an evolutionary game framework based on the temporary fork modeling and accordingly characterize the set of stable evolution equilibriums. Both extensive numerical simulations and realistic blockchain data based evaluation provide evidence to support our theoretical models and discoveries.
Smart contract-enabled blockchains allow building decentralized applications in which mutually-distrusted parties can work together. Recently, oracle services emerged to provide these applications with real-world data feeds. Unfortunately, these capabilities have been used for malicious purposes under what is called criminal smart contracts. A few works explored this dark side and showed a variety of such attacks. However, none of them considered collaborative attacks against targets that reside outside the blockchain ecosystem. In this paper, we bridge this gap and introduce a smart contract-based framework that allows a sponsor to orchestrate a collaborative attack among (pseudo)anonymous attackers and reward them for that. While all previous works required a technique to quantify an attacker's individual contribution, which could be infeasible with respect to real-world targets, our framework avoids that. This is done by developing a novel scheme for trustless collaboration through betting. That is, attackers bet on an event (i.e., the attack takes place) and then work on making that event happen (i.e., perform the attack). By taking DDoS as a usecase, we formulate attackers' interaction as a game, and formally prove that these attackers will collaborate in proportion to the amount of their bets in the game's unique equilibrium. We also model our framework and its reward function as an incentive mechanism and prove that it is a strategy proof and budget-balanced one. Finally, we conduct numerical simulations to demonstrate the equilibrium behavior of our framework.
Amir Ziashahabi, Mohammad Ali Maddah-Ali, Abbas Heydarnoori
In today's world, social networks have become one of the primary sources for creation and propagation of news. Social news aggregators are one of the actors in this area in which users post news items and use positive or negative votes to indicate their preference toward a news item. News items will be ordered and displayed according to their aggregated votes. This approach suffers from several problems raging from being prone to the dominance of the majority to difficulty in discerning between correct and fake news, and lack of incentive for honest behaviors. In this paper, we propose a graph-based news aggregator in which instead of voting on the news items, users submit their votes on the relations between pairs of news items. More precisely, if a user believes two news items support each other, he will submit a positive vote on the link between the two items, and if he believes that two news items undermine each other, he will submit a negative vote on the corresponding link. This approach has mainly two desirable features: (1) mitigating the effect of personal preferences on voting, (2) connection of new items to endorsing and disputing evidence. This approach helps the newsreaders to understand different aspects of a news item better. We also introduce an incentive layer that uses blockchain as a distributed transparent manager to encourages users to behave honestly and abstain from adversary behaviors. The incentive layer takes into account that users can have different viewpoints toward news, enabling users from a wide range of viewpoints to contribute to the network and benefit from its rewards. In addition, we introduce a protocol that enables us to prove fraud in computations of the incentive layer model on the blockchain. Ultimately, we will analyze the fraud proof protocol and examine our incentive layer on a wide range of synthesized datasets.
It is an important decision-making problem for a miner in the blockchain networks if he/she participates in the mining so that he/she earns a reward by creating a new block earlier than other miners. We formulate this decision-making problem as a noncooperative game, because the probability of creating a block depends not only on one's own available computational resources, but also those of other miners. Through theoretical and numerical analyses, we show a hysteresis phenomenon of Nash equilibria depending on the reward and a jump phenomenon of miner decisions by a slight change in reward. We also show that the reward for which miners decide not to participate in the mining becomes smaller as the number of miners increases.
Jianxiong Guo, Xingjian Ding, Weili Wu, Ding‐Zhu Du
Electric Vehicles (EVs) are becoming more and more popular in our daily life, which replaces traditional fuel vehicles to reduce carbon emissions and protect the environment. EVs need to be charged, but the number of charging piles in a Charging Station (CS) is limited and charging is usually more time-consuming than fueling. According to this scenario, we propose a secure and efficient charging scheduling system based on a Directed Acyclic Graph (DAG)-blockchain and double auction mechanism. In a smart area, it attempts to assign EVs to the available CSs in the light of their submitted charging requests and status information. First, we design a lightweight charging scheduling framework that integrates DAG-blockchain and modern cryptography technology to ensure security and scalability during performing scheduling and completing tradings. In this process, a constrained multi-item double auction problem is formulated because of the limited charging resources in a CS, which motivates EVs and CSs in this area to participate in the market based on their preferences and statuses. Due to this constraint, our problem is more complicated and harder to achieve truthfulness as well as system efficiency compared to the existing double auction model. To adapt to it, we propose two algorithms, namely Truthful Mechanism for Charging (TMC) and Efficient Mechanism for Charging (EMC), to determine an assignment between EVs and CSs and pricing strategies. Then, both theoretical analysis and numerical simulations show the correctness and effectiveness of our proposed algorithms.
We propose a smart contract that allows two mutually distrusting parties to transact any non-digital good or service by deploying a smart contract on a blockchain to act as escrow. The contract settles disputes by letting parties wager that they can convince an arbiter that they were the honest party. We analyse the contract as an extensive-form game and prove that the honest strategy is secure in a strong game-theoretic sense if and only if the arbiter is biased in favor of honest parties. By relaxing the security notion, we can replace the arbiter by a random coin toss. Finally, we show how to generalize the contract to multiparty transactions in a way that amortizes the transaction fees.
Attracted by the inherent security and privacy protection of the blockchain, incorporating blockchain into Internet of Things (IoT) has been widely studied in these years. However, the mining process requires high computational power, which prevents IoT devices from directly participating in blockchain construction. For this reason, edge computing service is introduced to help build the IoT blockchain, where IoT devices could purchase computational resources from the edge servers. In this paper, we consider the case that IoT devices also have other tasks that need the help of edge servers, such as data analysis and data storage. The profits they can get from these tasks is closely related to the amounts of resources they purchased from the edge servers. In this scenario, IoT devices will allocate their limited budgets to purchase different resources from different edge servers, such that their profits can be maximized. Moreover, edge servers will set "best" prices such that they can get the biggest benefits. Accordingly, there raise a pricing and budget allocation problem between edge servers and IoT devices. We model the interaction between edge servers and IoT devices as a multi-leader multi-follower Stackelberg game, whose objective is to reach the Stackelberg Equilibrium (SE). We prove the existence and uniqueness of the SE point, and design efficient algorithms to reach the SE point. In the end, we verify our model and algorithms by performing extensive simulations, and the results show the correctness and effectiveness of our designs.
Real-time traffic monitoring is a fundamental mission in a smart city to understand traffic conditions and avoid dangerous accidents. In this article, we propose a reliable and efficient traffic monitoring system that integrates blockchain and the Internet of Vehicles technologies effectively. It can crowdsource its tasks of traffic information collection to vehicles that run on the road instead of installing cameras in every corner. First, we design a lightweight blockchain-based information trading framework to model the interactions between traffic administration and vehicles. It guarantees reliability, efficiency, and security during executing trading. Second, we define the utility functions for the entities in this system and come up with a budgeted auction mechanism that motivates vehicles to undertake the collection tasks actively. In our algorithm, it not only ensures that the total payment to the selected vehicles does not exceed a given budget but also maintains the truthfulness of the auction process that prevents some vehicles from offering unreal bids for getting greater utilities. Finally, we conduct a group of numerical simulations to evaluate the reliability of our trading framework and performance of our algorithms, whose results demonstrate their correctness and efficiency perfectly.
Zhihuai Chen, Bo Li, Xiaohan Shan, Xiaoming Sun · 5 authors
The arisen of Bitcoin has led to much enthusiasm for blockchain research and block mining, and the extensive existence of mining pools helps its participants (i.e., miners) gain reward more frequently. Recently, the mining pools are proved to be vulnerable for several possible attacks, and pool block withholding attack is one of them: one strategic pool manager sends some of her miners to other pools and these miners pretend to work on the puzzles but actually do nothing. And these miners still get reward since the pool manager can not recognize these malicious miners. In this work, we revisit the game-theoretic model for pool block withholding attacks and propose a revised approach to reallocate the reward to the miners. Fortunately, in the new model, the pool managers have strong incentive to not launch such attacks. We show that for any number of mining pools, no-pool-attacks is always a Nash equilibrium. Moreover, with only two minority mining pools participating, no-pool-attacks is actually the unique Nash equilibrium.
Tiantian Gong, Mohsen Minaei, Wenhai Sun, Aniket Kate
Mining processes of Bitcoin and similar cryptocurrencies are currently incentivized with voluntary transaction fees and fixed block rewards which will halve gradually to zero. In the setting where optional and arbitrary transaction fee becomes the remaining incentive, Carlsten et al.\ [CCS~2016] find that an undercutting attack can become the equilibrium strategy for miners. In undercutting, the attacker deliberately forks an existing chain by leaving wealthy transactions unclaimed to attract petty complaint miners to its fork. We observe that two simplifying assumptions in [CCS~2016] of fees arriving at fixed rates and miners collecting {\em all} accumulated fees regardless of block size limit are often infeasible in practice and find that they are inaccurately inflating the profitability of undercutting. Studying Bitcoin and Monero blockchain data, we find that the fees deliberately left out by an undercutter may not be attractive to other miners (hence to the attacker itself): the deliberately left out transactions may not fit into a new block without "squeezing out" some other to-be transactions, and thus claimable fees in the next round cannot be raised arbitrarily. This work views undercutting and shifting among chains rationally as mining strategies of rational miners. We model profitability of undercutting strategy with block size limit present, which bounds the claimable fees in a round and gives rise to a pending (cushion) transaction set. In the proposed model, we first identify the conditions necessary to make undercutting profitable. We then present an easy-to-deploy defense against undercutting by selectively assembling transactions into the new block to invalidate the identified conditions. Under a typical setting with undercutters present, applying this avoidance technique is a Nash Equilibrium. Finally, we complement the above analytical results with experiments.
Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies such as Bitcoin. They allow multiple agents to route payments through one another. So far, the topology and construction of payment networks has not been explored much. Participants are expected to minimize costs that are due to the allocation of liquidity as well as blockchain record fees. In this paper we study the optimization of maintenance costs of such networks. We present for the first time, a closed model for symmetric off-chain channels, and provide efficient algorithms for constructing minimal cost spanning-tree networks under this model. We prove that for any network demands, a simple hub topology provides a 2-approximation to the minimal maintenance cost showing that spanning trees in general are efficient. We also show an unbounded price of anarchy in a greedy game between the transactors, when each player wishes to minimize his costs by changing the network's structure. Finally, we simulate and compare the costs of payment networks with scale free demand topologies.
David Yakira, Avi Asayag, Ido Grayevsky, Idit Keidar
We study the problem of providing blockchain applications with \emph{economically viable randomness} (EVR), namely, randomness that has significant economic consequences. Applications of EVR include blockchain-based lotteries and gambling. An EVR source guarantees (i) secrecy, assuring that the random bits are kept secret until some predefined condition indicates that they are safe to reveal (e.g., the lottery's ticket sale closes), and (ii) robustness, guaranteeing that the random bits are published once the condition holds. We formalize the EVR problem and solve it on top of an Ethereum-like blockchain abstraction, which supports smart contracts and a transferable native coin. Randomness is generated via a distributed open commit-reveal scheme by game-theoretic agents who strive to maximize their coin holdings. Note that in an economic setting, such agents might profit from breaking secrecy or robustness, and may engage in side agreements (via smart contracts) to this end. Our solution creates an incentive structure that counters such attacks. We prove that following the protocol gives rise to a stable state, called Coalition-Proof Nash Equilibrium, from which no coalition comprised of a subset of the players can agree to deviate. In this stable state, robustness and secrecy are satisfied. Finally, we implement our EVR source over Ethereum.
Itay Tsabary, Matan Yechieli, Alex Manuskin, Ittay Eyal
Smart Contracts and transactions allow users to implement elaborate constructions on cryptocurrency blockchains like Bitcoin and Ethereum. Many of these constructions, including operational payment channels and atomic swaps, use a building block called Hashed Time-Locked Contract (HTLC). In this work, we distill from HTLC a specification (HTLC-Spec), and present an implementation called Mutual-Assured-Destruction Hashed Time-Locked Contract (MAD-HTLC). MAD-HTLC employs a novel approach of utilizing the existing blockchain operators, called miners, as part of the design. If a user misbehaves, MAD-HTLC incentivizes the miners to confiscate all her funds. We prove MAD-HTLC's security using the UC framework and game-theoretic analysis. We demonstrate MAD-HTLC's efficacy and analyze its overhead by instantiating it on Bitcoin's and Ethereum's operational blockchains. Notably, current miner software makes only little effort to optimize revenue, since the advantage is relatively small. However, as the demand grows and other revenue components shrink, miners are more motivated to fully optimize their fund intake. By patching the standard Bitcoin client, we demonstrate such optimization is easy to implement, making the miners natural enforcers of MAD-HTLC. Finally, we extend previous results regarding HTLC vulnerability to bribery attacks. An attacker can incentivize miners to prefer her transactions by offering high transaction fees. We demonstrate this attack can be easily implemented by patching the Bitcoin client, and use game-theoretic tools to qualitatively tighten the known cost bound of such bribery attacks in presence of rational miners. We identify bribe opportunities occurring on the Bitcoin and Ethereum main networks where a few dollars bribe could yield tens of thousands of dollars in reward (e.g., \$2 for over \$25K).
Mining in the blockchain requires high computing power to solve the hash puzzle for example proof-of-work puzzle. It takes high cost to achieve the calculation of this problem in devices of IOT, especially the mobile devices of IOT. It consequently restricts the application of blockchain in mobile environment. However, edge computing can be utilized to solve the problem for insufficient computing power of mobile devices in IOT. Edge servers can recruit many mobile devices to contribute computing power together to mining and share the reward of mining with these recruited mobile devices. In this paper, we propose an incentivizing mechanism based on edge computing for mobile blockchain. We design a two-stage Stackelberg Game to jointly optimize the reward of edge servers and recruited mobile devices. The edge server as the leader sets the expected fee for the recruited mobile devices in Stage I. The mobile device as a follower provides its computing power to mine according to the expected fee in Stage. It proves that this game can obtain a uniqueness Nash Equilibrium solution under the same or different expected fee. In the simulation experiment, we obtain a result curve of the profit for the edge server with the different ratio between the computing power from the edge server and mobile devices. In addition, the proposed scheme has been compared with the MDG scheme for the profit of the edge server. The experimental results show that the profit of the proposed scheme is more than that of the MDG scheme under the same total computing power.
Lewis Gudgeon, Sam M. Werner, Daniel Perez, William J. Knottenbelt
We coin the term *Protocols for Loanable Funds (PLFs)* to refer to protocols which establish distributed ledger-based markets for loanable funds. PLFs are emerging as one of the main applications within Decentralized Finance (DeFi), and use smart contract code to facilitate the intermediation of loanable funds. In doing so, these protocols allow agents to borrow and save programmatically. Within these protocols, interest rate mechanisms seek to equilibrate the supply and demand for funds. In this paper, we review the methodologies used to set interest rates on three prominent DeFi PLFs, namely Compound, Aave and dYdX. We provide an empirical examination of how these interest rate rules have behaved since their inception in response to differing degrees of liquidity. We then investigate the market efficiency and inter-connectedness between multiple protocols, examining first whether Uncovered Interest Parity holds within a particular protocol and second whether the interest rates for a particular token market show dependence across protocols, developing a Vector Error Correction Model for the dynamics.
Cryptocurrencies are a digital medium of exchange with decentralized control that renders the community operating the cryptocurrency its sovereign. Leading cryptocurrencies use proof-of-work or proof-of-stake to reach consensus, thus are inherently plutocratic. This plutocracy is reflected not only in control over execution, but also in the distribution of new wealth, giving rise to ``rich get richer'' phenomena. Here, we explore the possibility of an alternative digital currency that is egalitarian in control and just in the distribution of created wealth. Such currencies can form and grow in grassroots and sybil-resilient way. A single currency community can achieve distributive justice by egalitarian coin minting, whereby each member mints one coin at every time step. Egalitarian minting results, in the limit, in the dilution of any inherited assets and in each member having an equal share of the minted currency, adjusted by the relative productivity of the members. Our main theorem shows that a currency network, where agents can be members of more than one currency community, can achieve distributive justice globally across the network by joint egalitarian minting, whereby each agent mints one coin in only one community at each timestep. Specifically, we show that a sufficiently large intersection between two communities -- relative to the gap in their productivity -- will cause the exchange rates between their currencies to converge to 1:1, resulting in global distributive justice.
Ranvir Rana, Sreeram Kannan, David Tse, Pramod Viswanath
Propelled by the growth of large-scale blockchain deployments, much recent progress has been made in designing sharding protocols that achieve throughput scaling linearly in the number of nodes. However, existing protocols are not robust to an adversary adaptively corrupting a fixed fraction of nodes. In this paper, we propose Free2Shard -- a new architecture that achieves near-linear scaling while being secure against a fully adaptive adversary. The focal point of this architecture is a dynamic self-allocation algorithm that lets users allocate themselves to shards in response to adversarial action, without requiring a central or cryptographic proof. This architecture has several attractive features unusual for sharding protocols, including: (a) the ability to handle the regime of large number of shards (relative to the number of nodes); (b) heterogeneous shard demands; (c) requiring only a small minority to follow the self-allocation; (d) asynchronous shard rotation; (e) operation in a purely identity-free proof-of-work setting. The key technical contribution is a deep mathematical connection to the classical work of Blackwell in dynamic game theory.