To allocate transactions to blocks, cryptocurrencies use an auction-like transaction fee mechanism (TFM). A conjecture of Roughgarden [44] asks whether there is a TFM that is incentive compatible for both the users and the miner, and is also resistant to off-chain agreements (OCAs) between these parties, a collusion notion that captures the ability of users and the miner to jointly deviate for profit. The work of Chung and Shi [12] tackles the problem using the different collusion resistance notion of side-channel proofness (SCP), and shows an impossibility given this notion. We show that OCA-proofness and SCP are different, with SCP being strictly stronger. We then fully characterize the intersection of deterministic dominant strategy incentive-compatible (DSIC) and OCA-proof mechanisms, as well as deterministic MMIC and OCA-proof ones, and use this characterization to show that only the trivial mechanism is DSIC, myopic miner incentive-compatible (MMIC) and OCA-proof. We also show that a randomized mechanism can be at most 0.842-efficient in the worst case, and that the impossibility of a non-trivial DSIC, MMIC and OCA-proof extends to a couple of natural classes of randomized mechanisms.
Tullock contests model real-life scenarios that range from competition among proof-of-work blockchain miners to rent-seeking and lobbying activities. We show that continuous-time best-response dynamics in Tullock contests with convex costs converges to the unique equilibrium using Lyapunov-style arguments. We then use this result to provide an algorithm for computing an approximate equilibrium. We also establish convergence of related discrete-time dynamics, e.g., when the agents best-respond to the empirical average action of other agents. These results indicate that the equilibrium is a reliable predictor of the agents' behavior in these games.
In this paper, we studyhow to optimize existing non-fungible token (NFT) incentives. Upon exploring a large number of NFT-related standards and real-world projects, we uncover an unexpected finding: current NFT incentive mechanisms, often organized in an isolated and one-time-use fashion, tend to overlook their potential for scalable organizational structures. To address this, we propose, analyze, and implement a novelreference incentivemodel, inherently structured as a directed acyclic graph (DAG)-based NFT network. Leveraging the Stackelberg game framework and deep reinforcement learning (DRL), this model aims to maximize connections (or references) between NFTs, enabling isolated NFTs to expand their networks and accumulate rewards from subsequent or subscribed ones. Through both theoretical and practical analyses, we demonstrate the optimal utility of the proposed model.
Dimitris Karakostas, Aggelos Kiayias, Thomas Zacharias
We analyze bribing attacks in Proof-of-Stake distributed ledgers from a game theoretic perspective. In bribing attacks, an adversary offers participants a reward in exchange for instructing them how to behave, with the goal of attacking the protocol's properties. Specifically, our work focuses on adversaries that target blockchain safety. We consider two types of bribing, depending on how the bribes are awarded: i) guided bribing, where the bribe is given as long as the bribed party behaves as instructed; ii) effective bribing, where bribes are conditional on the attack's success, w.r.t. well-defined metrics. We analyze each type of attack in a game theoretic setting and identify relevant equilibria. In guided bribing, we show that the protocol is not an equilibrium and then describe good equilibria, where the attack is unsuccessful, and a negative one, where all parties are bribed such that the attack succeeds. In effective bribing, we show that both the protocol and the "all bribed" setting are equilibria. Using the identified equilibria, we then compute bounds on the Prices of Stability and Anarchy. Our results indicate that additional mitigations are needed for guided bribing, so our analysis concludes with incentive-based mitigation techniques, namely slashing and dilution. Here, we present two positive results, that both render the protocol an equilibrium and achieve maximal welfare for all parties, and a negative result, wherein an attack becomes more plausible if it severely affects the ledger's token's market price.
Automated Market Makers (AMMs) are an integral component of the decentralized finance (DeFi) ecosystem, as they allow users to exchange crypto-assets without the need for trusted authorities or external price oracles. Although these protocols are based on relatively simple mechanisms, e.g., to algorithmically determine the exchange rate between crypto-assets, they give rise to complex economic behaviours. This complexity is witnessed by the proliferation of models that study their structural and economic properties. Currently, most of theoretical results obtained on these models are supported by pen-and-paper proofs. This work proposes a formalization of constant-product AMMs in the Lean 4 Theorem Prover. To demonstrate the utility of our model, we provide mechanized proofs of key economic properties like arbitrage, that at the best of our knowledge have only been proved by pen-and-paper before.
The recently proposed Transaction Fee Mechanism (TFM) literature studies the strategic interaction between the miner of a block and the transaction creators (or users) in a blockchain. In a TFM, the miner includes transactions that maximize its utility while users submit fees for a slot in the block. The existing TFM literature focuses on satisfying standard incentive properties -- which may limit widespread adoption. We argue that a TFM is "fair" to the transaction creators if it satisfies specific notions, namely Zero-fee Transaction Inclusion and Monotonicity. First, we prove that one generally cannot ensure both these properties and prevent a miner's strategic manipulation. We also show that existing TFMs either do not satisfy these notions or do so at a high cost to the miners' utility. As such, we introduce a novel TFM using on-chain randomness -- rTFM. We prove that rTFM guarantees incentive compatibility for miners and users while satisfying our novel fairness constraints.
In recent years, the Decentralized Finance (DeFi) market has witnessed numerous attacks on the price oracle, leading to substantial economic losses. Despite the advent of truth discovery methods opening up new avenues for oracle development, it falls short in addressing high-value attacks on price oracle tasks. Consequently, this paper introduces a dynamically adjusted truth discovery method safeguarding the truth of high-value price oracle tasks. In the truth aggregation stage, we enhance future considerations to improve the precision of aggregated truth. During the credibility update phase, credibility is dynamically assessed based on the task's value and the Cumulative Potential Economic Contribution (CPEC) of information sources. Experimental results demonstrate a significant reduction in data deviation by 65.8\% and potential economic loss by 66.5\%, compared to the baseline scheme, in the presence of high-value attacks.
This paper presents a novel solution concept, called BAR Nash Equilibrium (BARNE) and apply it to analyse the Verifier's dilemma, a fundamental problem in blockchain. Our solution concept adapts the Nash equilibrium (NE) to accommodate interactions among Byzantine, altruistic and rational agents, which became known as the BAR setting in the literature. We prove the existence of BARNE in a large class of games and introduce two natural refinements, global and local stability. Using this equilibrium and its refinement, we analyse the free-rider problem in the context of byzantine consensus. We demonstrate that by incorporating fines and forced errors into a standard quorum-based blockchain protocol, we can effectively reestablish honest behavior as a globally stable BARNE.
Blockchains deploy Transaction Fee Mechanisms (TFMs) to determine which user transactions to include in blocks and determine their payments (i.e., transaction fees). Increasing demand and scarce block resources have led to high user transaction fees. As these blockchains are a public resource, it may be preferable to reduce these transaction fees. To this end, we introduce Transaction Fee Redistribution Mechanisms (TFRMs) -- redistributing VCG payments collected from such TFM as rebates to minimize transaction fees. Classic redistribution mechanisms (RMs) achieve this while ensuring Allocative Efficiency (AE) and User Incentive Compatibility (UIC). Our first result shows the non-triviality of applying RM in TFMs. More concretely, we prove that it is impossible to reduce transaction fees when (i) transactions that are not confirmed do not receive rebates and (ii) the miner can strategically manipulate the mechanism. Driven by this, we propose \emph{Robust} TFRM (\textsf{R-TFRM}): a mechanism that compromises on an honest miner's individual rationality to guarantee strictly positive rebates to the users. We then introduce \emph{robust} and \emph{rational} TFRM (\textsf{R}$^2$\textsf{-TFRM}) that uses trusted on-chain randomness that additionally guarantees miner's individual rationality (in expectation) and strictly positive rebates. Our results show that TFRMs provide a promising new direction for reducing transaction fees in public blockchains.
Proof-of-Work is a consensus algorithm where miners solve cryptographic puzzles to mine blocks and obtain a reward through some Block Reward Mechanism (BRM). PoW blockchain faces the problem of centralization due to the formation of mining pools, where miners mine blocks as a group and distribute rewards. The rationale is to reduce the risk (variance) in reward while obtaining the same expected block reward. In this work, we address the problem of centralization due to mining pools in PoW blockchain. We propose a two-player game between the new miner joining the system and the PoW blockchain system. We model the utility for the incoming miner as a combination of (i) expected block reward, (ii) risk, and (iii) cost of switching between different mining pools. With this utility structure, we analyze the equilibrium strategy of the incoming miner for different BRMs: (a) memoryless -- block reward is history independent (e.g., Bitcoin) (b) retentive: block reward is history-dependent (e.g., Fruitchains). For memoryless BRMs, we show that depending on the coefficient of switching cost $c$, the protocol is decentralized when $c = 0$ and centralized when $c > \underline{c}$. In addition, we show the impossibility of constructing a memoryless BRM where solo mining gives a higher payoff than forming/joining mining pools. While retentive BRM in Fruitchains reduces risk in solo mining, the equilibrium strategy for incoming miners is still to join mining pools, leading to centralization. We then propose our novel retentive BRM -- \textsf{Decent-BRM}. We show that under \textsf{Decent-BRM}, incoming miners obtain higher utility in solo mining than joining mining pools. Therefore, no mining pools are formed, and the Pow blockchain using \textsf{Decent-BRM} is decentralized.
We study a new "laminated" queueing model for orders on batched trading venues such as decentralised exchanges. The model aims to capture and generalise transaction queueing infrastructure that has arisen to organise MEV activity on public blockchains such as Ethereum, providing convenient channels for sophisticated agents to extract value by acting on end-user order flow by performing arbitrage and related HFT activities. In our model, market orders are interspersed with orders created by arbitrageurs that under idealised conditions reset the marginal price to a global equilibrium between each trade, improving predictability of execution for liquidity traders. If an arbitrageur has a chance to land multiple opportunities in a row, he may attempt to manipulate the execution price of the intervening market order by a probabilistic blind sandwiching strategy. To study how bad this manipulation can get, we introduce and bound a price manipulation coefficient that measures the deviation from global equilibrium of local pricing quoted by a rational arbitrageur. We exhibit cases in which this coefficient is well approximated by a "zeta value' with interpretable and empirically measurable parameters.
Akaki Mamageishvili, Christoph Schlegel, Benny Sudakov, Danning Sui
We study the amount of maximal extractable value (MEV) captured by validators, as a function of searcher competition, in blockchains with competitive block building markets such as Ethereum. We argue that the core is a suitable solution concept in this context that makes robust predictions that are independent of implementation details or specific mechanisms chosen. We characterize how much value validators extract in the core and quantify the surplus share of validators as a function of searcher competition. Searchers can obtain at most the marginal value increase of the winning block relative to the best block that can be built without their bundles. Dually this gives a lower bound on the value extracted by the validator. If arbitrages are easy to find and many searchers find similar bundles, the validator gets paid all value almost surely, while searchers can capture most value if there is little searcher competition per arbitrage. Moreover, mechanisms that implement core allocations in dominant strategies, for submodular values, there is a unique dominant-strategy incentive compatible core-selecting mechanism that gives each searcher exactly their marginal value contribution to the winning block. We extend our model to multiple concurrent proposers in which, under mild assumptions, the core is empty. We validate our theoretical prediction empirically with aggregate bundle data and find a significant positive relation between the number of submitted backruns for the same opportunity and the median value captured by the proposer from the opportunity.
Byzantine fault-tolerant consensus protocols have provable safety and liveness properties for static validator sets. In practice, however, the validator set changes over time, potentially eroding the protocol's security guarantees. For example, systems with accountable safety may lose some of that accountability over time as adversarial validators exit. As a result, protocols must rate limit entry and exit so that the set changes slowly enough to ensure security. Here, the system designer faces a fundamental trade-off. Slower exits increase friction, making it less attractive to stake in the first place. Faster exits provide more utility to stakers but weaken the protocol's security. This paper provides the first systematic study of exit queues for Proof-of-Stake blockchains. Given a collection of validator-set consistency constraints imposed by the protocol, the social planner's goal is to provide a constrained-optimal mechanism that minimizes disutility for the participants. We introduce the MINSLACK mechanism, a dynamic capacity first-come-first-served queue in which the amount of stake that can exit in a period depends on the number of previous exits and the consistency constraints. We show that MINSLACK is optimal when stakers equally value the processing of their withdrawal. When stakers values are heterogeneous, the optimal mechanism resembles a priority queue with dynamic capacity. However, this mechanism must reserve exit capacity for the future in case a staker with a much higher need for liquidity arrives. We conclude with a survey of known consistency constraints and highlight the diversity of existing exit mechanisms.
Aggelos Kiayias, Ηλίας Κουτσουπιάς, Francisco J. Marmolejo-CossÃo, Aikaterini-Panagiota Stouka
Proof-of-stake blockchain protocols have emerged as a compelling paradigm for organizing distributed ledger systems. In proof-of-stake (PoS), a subset of stakeholders participate in validating a growing ledger of transactions. For the safety and liveness of the underlying system, it is desirable for the set of validators to include multiple independent entities as well as represent a non-negligible percentage of the total stake issued. In this paper, we study a secondary form of participation in the transaction validation process, which takes the form of stake delegation, whereby an agent delegates their stake to an active validator who acts as a stake pool operator. We study payment schemes that reward agents as a function of their collective actions regarding stake pool operation and delegation. Such payment schemes serve as a mechanism to incentivize participation in the validation process while maintaining decentralization. We observe natural trade-offs between these objectives and the total expenditure required to run the relevant payment schemes. Ultimately, we provide a family of payment schemes which can strike different balances between these competing objectives at equilibrium in a Bayesian game theoretic framework.
Andrea Carotti, Cosimo Sguanci, Anastasios Sidiropoulos
The Bitcoin Lightning Network (LN) is designed to improve the scalability of blockchain systems by using off-chain payment paths to settle transactions in a faster, cheaper, and more private manner. This work aims to empirically study LN's fee revenue for network participants. Under realistic assumptions on payment amounts, routing algorithms and traffic distribution, we analyze the economic returns of the network's largest routing nodes which currently hold the network together, and assess whether the centralizing tendency is incentive-compatible from an economic viewpoint. Moreover, since recent literature has proved that participation is economically irrational for the majority of large nodes, we evaluate the long-term impact on the network topology when participants start behaving rationally.
Fei Wu, Thomas Thiery, Stefanos Leonardos, Carmine Ventre
The Ethereum block-building process has changed significantly since the emergence of Proposer-Builder Separation. Validators access blocks through a marketplace, where block builders bid for the right to construct the block and earn MEV (Maximal Extractable Value) rewards in an on-chain competition, known as the MEV-boost auction. While more than 90% of blocks are currently built via MEV-Boost, trade-offs between builders' strategic behaviors and auction design remain poorly understood. In this paper we address this gap. We introduce a game-theoretic model for MEV-Boost auctions and use simulations to study different builders' bidding strategies observed in practice. We study various strategic interactions and auction setups and evaluate how the interplay between critical elements such as access to MEV opportunities and improved connectivity to relays impact bidding performance. Our results demonstrate the importance of latency on the effectiveness of builders' strategies and the overall auction outcome from the proposer's perspective.
Niclas Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein · 6 authors
We provide the first large-scale data collection of real-world approval-based committee elections. These elections have been conducted on the Polkadot blockchain as part of their Nominated Proof-of-Stake mechanism and contain around one thousand candidates and tens of thousands of (weighted) voters each. We conduct an in-depth study of application-relevant questions, including a quantitative and qualitative analysis of the outcomes returned by different voting rules. Besides considering proportionality measures that are standard in the multiwinner voting literature, we pay particular attention to less-studied measures of overrepresentation, as these are closely related to the security of the Polkadot network. We also analyze how different design decisions such as the committee size affect the examined measures.
We present a comprehensive analysis of the implications of artificial latency in the Proposer-Builder Separation framework on the Ethereum network. Focusing on the MEV-Boost auction system, we analyze how strategic latency manipulation affects Maximum Extractable Value yields and network integrity. Our findings reveal both increased profitability for node operators and significant systemic challenges, including heightened network inefficiencies and centralization risks. We empirically validates these insights with a pilot that Chorus One has been operating on Ethereum mainnet. We demonstrate the nuanced effects of latency on bid selection and validator dynamics. Ultimately, this research underscores the need for balanced strategies that optimize Maximum Extractable Value capture while preserving the Ethereum network's decentralization ethos.
Yanni Georghiades, Rajesh Mishra, Karl Kreder, Sriram Vishwanath
We study the incentives behind double-spend attacks on Nakamoto-style Proof-of-Work cryptocurrencies. In these systems, miners are allowed to choose which transactions to reference with their block, and a common strategy for selecting transactions is to simply choose those with the highest fees. This can be problematic if these transactions originate from an adversary with substantial (but less than 50\%) computational power, as high-value transactions can present an incentive for a rational adversary to attempt a double-spend attack if they expect to profit. The most common mechanism for deterring double-spend attacks is for the recipients of large transactions to wait for additional block confirmations (i.e., to increase the attack cost). We argue that this defense mechanism is not satisfactory, as the security of the system is contingent on the actions of its users. Instead, we propose that defending against double-spend attacks should be the responsibility of the miners; specifically, miners should limit the amount of transaction value they include in a block (i.e., reduce the attack reward). To this end, we model cryptocurrency mining as a mean-field game in which we augment the standard mining reward function to simulate the presence of a rational, double-spending adversary. We design and implement an algorithm which characterizes the behavior of miners at equilibrium, and we show that miners who use the adversary-aware reward function accumulate more wealth than those who do not. We show that the optimal strategy for honest miners is to limit the amount of value transferred by each block such that the adversary's expected profit is 0. Additionally, we examine Bitcoin's resilience to double-spend attacks. Assuming a 6 block confirmation time, we find that an attacker with at least 25% of the network mining power can expect to profit from a double-spend attack.
A growing number of products use layer 2 solutions to expand the capabilities of primary blockchains like Ethereum, where computation is off-loaded from the root chain, and the results are published to it in bulk. Those include optimistic and zero-knowledge rollups, information oracles, and app-specific chains. This work presents an analysis of layer 2 blockchain strategies determining the optimal times for publishing transactions on the root chain. There is a trade-off between waiting for a better layer 1 gas price and the urgency to finalize layer 2 transactions. We present a model for the problem that captures this trade-off, generalizing previous works, and we analyze the properties of optimal publishing strategies. We show that such optimal strategies hold a computable simple form for a large class of cost functions.
We study game-theoretic models for capturing participation in blockchain systems. Permissionless blockchains can be naturally viewed as games, where a set of potentially interested users is faced with the dilemma of whether to engage with the protocol or not. Engagement here implies that the user will be asked to complete certain tasks, whenever they are selected to contribute (typically according to some stochastic process) and be rewarded if they choose to do so. Apart from the basic dilemma of engaging or not, even more strategic considerations arise in settings where users may be able to declare participation and then retract before completing their tasks (but are still able to receive rewards) or are rewarded independently of whether they contribute. Such variations occur naturally in the blockchain setting due to the complexity of tracking ``on-chain'' the behavior of the participants. We capture these participation considerations offering a series of models that enable us to reason about the basic dilemma, the case where retraction effects influence the outcome and the case when payments are given universally irrespective of the stochastic process. In all cases we provide characterization results or necessary conditions on the structure of Nash equilibria. Our findings reveal that appropriate reward mechanisms can be used to stimulate participation and avoid negative effects of free riding, results that are in line but also can inform real world blockchain system deployments.
Decentralised organisations use blockchains as a basis for governance: they use on-chain transactions to allocate voting weight, publish proposals, cast votes, and enact the results. However, blockchain-based governance structures have challenges, mostly notably, the need to align the short-term outlook of pseudononymous voters with the long-term growth and success of the decentralised organisation. The Vote-Escrowed Token (veToken) model attempts to resolve this tension by requiring voters to escrow or lock tokens of value for an extended period in exchange for voting weight. In this paper, we describe the veToken model and analyse its emergent outcomes. We show that voting behaviour follows bribes set by higher-level protocols, and that the cost per vote varies depending on how it is acquired. We describe the implementation of the veToken model by Curve Finance, a popular automated market maker for stablecoins, and the ecosystem of protocols that has arisen on top of this implementation. We show that voting markets such as Votium largely determine the outcome of fortnightly votes held by Convex Finance, and we show that Frax Finance, a stablecoin issuer, plays a central role in the ecosystem even though they directly lock relatively few tokens with Curve. Instead, they indirectly lock tokens through yield aggregators such as Convex Finance and purchase voting weight through voting markets such as Votium. Although the veToken model in isolation is straight-forward and easily explained, it leads to many complex and emergent outcomes. Decentralised organisations should consider these outcomes before adopting the model.
We study the following problem that is motivated by Blockchains where ``miners'' are serially given the monopoly for assembling transactions into the next block. Our model has a single good that is sold repeatedly every day where new demand for the good arrives every day. The novel element in our model is that all unsatisfied demand from one day remains in the system and is added to the new demand of the next day. Every day there is a new monopolist that gets to sell a fixed supply $s$ of the good and naturally chooses to do so at the monopolist's price for the combined demand. What will the dynamics of the prices chosen by the sequence of monopolists be? What level of efficiency will be obtained in the long term? We start with a non-strategic analysis of users' behavior and our main result shows that prices keep fluctuating wildly and this is an endogenous property of the model and happens even when demand is stable with nothing stochastic in the model. These price fluctuations underscore the necessity of an analysis under strategic behavior of the users, which we show results in the prices being stable at the market equilibrium price.