The secondary market for Ethereum non-fungible tokens (NFTs) has resulted in over $1.8bn being paid to creators in the form of a sales tax commonly called creator royalties. This was despite royalty payments being enforced by no more than social contract alone. Predictably, such an incentive structure led to zero-royalty alternatives becoming abundant and payments dwindled. A purely programmatic solution to royalty enforcement is hampered by the prevailing NFT standard, ERC-721, which is ignorant of sale values and royalty enforcement therefore relies on (potentially dishonest) third parties. We thus introduce an incentive-compatible mechanism for which there is a single rationalisable solution, in which royalties are paid in full, while maintaining full ERC-721 compatibility. The mechanism constitutes the core of ERC-7526.
Users bid in a transaction fee mechanism (TFM) to get their transactions included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated the formal treatment of TFMs and proposed three requirements: user incentive compatibility (UIC), miner incentive compatibility (MIC), and a form of collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism satisfies all three properties simultaneously when there is no contention between transactions, but loses the UIC property when there are too many eligible transactions to fit in a single block. Chung and Shi (SODA'23) considered an alternative notion of collusion-resilience, called $c$-side-contract-proofness ($c$-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and $c$-SCP for any $c\geq 1$. OCA-proofness asserts that the users and a miner should not be able to "steal from the protocol." On the other hand, the $c$-SCP condition requires that a coalition of a miner and a subset of users should not be able to profit through strategic deviations (whether at the expense of the protocol or of the users outside the coalition). Our main result is the first proof that, when there is contention between transactions, no (possibly randomized) TFM in which users are expected to bid truthfully satisfies UIC, MIC, and OCA-proofness.This result resolves the main open question in Roughgarden (EC'21). We also suggest several relaxations of the basic model that allow our impossibility result to be circumvented.
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.
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.
Ethereum is undergoing significant changes to its architecture as it evolves. These changes include its switch to PoS consensus and the introduction of significant infrastructural changes that do not require a change to the core protocol, but that fundamentally affect the way users interact with the network. These changes represent an evolution toward a more modular architecture, in which there exists new exogenous vectors for centralization. This paper builds on previous studies of decentralization of Ethereum to reflect these recent significant changes, and Ethereum's new modular paradigm.
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.
Currently, over 90% of Ethereum blocks are built using MEV-Boost, an auction that allows validators to sell their block-building power to builders who compete in an open English auction in each slot. Shortly after the merge, when MEV-Boost was in its infancy, most block builders were neutral, meaning they did not trade themselves but rather aggregated transactions from other traders. Over time, integrated builders, operated by trading firms, began to overtake many of the neutral builders. Outside of the integrated builder teams, little is known about which advantages integration confers beyond latency and how latency advantages distort on-chain trading. This paper explores these poorly understood advantages. We make two contributions. First, we point out that integrated builders are able to bid truthfully in their own bundle merge and then decide how much profit to take later in the final stages of the PBS auction when more information is available, making the auction for them look closer to a second-price auction while independent searchers are stuck in a first-price auction. Second, we find that latency disadvantages convey a winner's curse on slow bidders when underlying values depend on a stochastic price process that change as bids are submitted.
Consider a finite set of trade orders and automated market makers (AMMs) at some state. We propose a solution to the problem of finding an equilibrium price vector to execute all the orders jointly with corresponding optimal AMMs swaps. The solution is based on Brouwer's fixed-point theorem. We discuss computational aspects relevant for realistic situations in public blockchain activity.
We study the stochastic structure of cryptocurrency rates of returns as compared to stock returns by focusing on the associated cross-sectional distributions. We build two datasets. The first comprises forty-six major cryptocurrencies, and the second includes all the companies listed in the S&P 500. We collect individual data from January 2017 until December 2022. We then apply the Quantal Response Statistical Equilibrium (QRSE) model to recover the cross-sectional frequency distribution of the daily returns of cryptocurrencies and S&P 500 companies. We study the stochastic structure of these two markets and the properties of investors' behavior over bear and bull trends. Finally, we compare the degree of informational efficiency of these two markets.
Davide Crapis, Edward W. Felten, Akaki Mamageishvili
We study the economics of the Ethereum improvement proposal 4844 and its effect on rollups' data posting strategies. Rollups' cost consists of two parts: data posting and delay. In the new proposal, the data posting cost corresponds to a blob posting cost and is fixed in each block, no matter how much of the blob is utilized by the rollup. The tradeoff is clear: the rollup prefers to post a full blob, but if its transaction arrival rate is low, filling up a blob space causes too large delay cost. The first result of the paper shows that if a rollup transaction arrival rate is too low, it prefers to use the regular blockspace market for data posting, as it offers a more flexible cost structure. Second, we show that shared blob posting is not always beneficial for participating rollups and change in the aggregate blob posting cost in the equilibrium depends on the types of participating rollups. In the end, we discuss blob cost-sharing rules from an axiomatic angle.
We study a novel automated market maker design: the function maximizing AMM (FM-AMM). Our central assumption is that trades are batched before execution. Because of competition between arbitrageurs, the FM-AMM eliminates arbitrage profits (or LVR) and sandwich attacks, currently the two main problems in decentralized finance and blockchain design more broadly. We then consider 11 token pairs and use Binance price data to simulate the lower bound to the return of providing liquidity to an FM-AMM. Such a lower bound is, for the most part, slightly higher than the empirical returns of providing liquidity on Uniswap v3 (currently the dominant AMM).
The incentive-compatibility properties of blockchain transaction fee mechanisms have been investigated with *passive* block producers that are motivated purely by the net rewards earned at the consensus layer. This paper introduces a model of *active* block producers that have their own private valuations for blocks (representing, for example, additional value derived from the application layer). The block producer surplus in our model can be interpreted as one of the more common colloquial meanings of the term ``MEV.'' The main results of this paper show that transaction fee mechanism design is fundamentally more difficult with active block producers than with passive ones: with active block producers, no non-trivial or approximately welfare-maximizing transaction fee mechanism can be incentive-compatible for both users and block producers. These results can be interpreted as a mathematical justification for the current interest in augmenting transaction fee mechanisms with additional components such as order flow auctions, block producer competition, trusted hardware, or cryptographic techniques.
Aggelos Kiayias, Philip Lazos, Jan Christoph Schlegel
Cryptocurrencies come with a variety of tokenomic policies as well as aspirations of desirable monetary characteristics that have been described by proponents as 'sound money' or even 'ultra sound money.' These propositions are typically devoid of economic analysis so it is a pertinent question how such aspirations fit in the wider context of monetary economic theory. In this work, we develop a framework that determines the optimal token supply policy of a cryptocurrency, as well as investigate how such policy may be algorithmically implemented. Our findings suggest that the optimal policy complies with the Friedman rule and it is dependent on the risk free rate, as well as the growth of the cryptocurrency platform. Furthermore, we demonstrate a wide set of conditions under which such policy can be implemented via contractions and expansions of token supply that can be realized algorithmically with block rewards, taxation of consumption and burning the proceeds, and blockchain oracles.
Hans Gersbach, Akaki Mamageishvili, Fikri Pitsuwan
Systems and blockchains often have security vulnerabilities and can be attacked by adversaries, with potentially significant negative consequences. Therefore, infrastructure providers increasingly rely on bug bounty programs, where external individuals probe the system and report any vulnerabilities (bugs) in exchange for rewards (bounty). We develop a simple contest model of bug bounty. A group of individuals of arbitrary size is invited to undertake a costly search for bugs. The individuals differ with regard to their abilities, which we capture by different costs to achieve a certain probability to find bugs if any exist. Costs are private information. We study equilibria of the contest and characterize the optimal design of bug bounty schemes. In particular, the designer can vary the size of the group of individuals invited to search, add a paid expert, insert an artificial bug with some probability, and pay multiple prizes.
Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden
In decentralized finance ("DeFi"), automated market makers (AMMs) enable traders to programmatically exchange one asset for another. Such trades are enabled by the assets deposited by liquidity providers (LPs). The goal of this paper is to characterize and interpret the optimal (i.e., profit-maximizing) strategy of a monopolist liquidity provider, as a function of that LP's beliefs about asset prices and trader behavior. We introduce a general framework for reasoning about AMMs based on a Bayesian-like belief inference framework, where LPs maintain an asset price estimate. In this model, the market maker (i.e., LP) chooses a demand curve that specifies the quantity of a risky asset to be held at each dollar price. Traders arrive sequentially and submit a price bid that can be interpreted as their estimate of the risky asset price; the AMM responds to this submitted bid with an allocation of the risky asset to the trader, a payment that the trader must pay, and a revised internal estimate for the true asset price. We define an incentive-compatible (IC) AMM as one in which a trader's optimal strategy is to submit its true estimate of the asset price, and characterize the IC AMMs as those with downward-sloping demand curves and payments defined by a formula familiar from Myerson's optimal auction theory. We generalize Myerson's virtual values, and characterize the profit-maximizing IC AMM. The optimal demand curve generally has a jump that can be interpreted as a "bid-ask spread," which we show is caused by a combination of adverse selection risk (dominant when the degree of information asymmetry is large) and monopoly pricing (dominant when asymmetry is small). This work opens up new research directions into the study of automated exchange mechanisms from the lens of optimal auction theory and iterative belief inference, using tools of theoretical computer science in a novel way.
A central tenet in mechanism design is the ability to irrevocably commit to a mechanism. Commitment is achieved by public declaration, letting players verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that is private to the mechanism designer, such as her target function or costs. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome -- all without any mediators. Our framework leverages zero-knowledge proofs -- a cornerstone of modern cryptographic theory.
I study a repeated auction in which payments are made with a blockchain token created and initially owned by the auction designer. Unlike the ``virtual money'' previously examined in mechanism design, such tokens can be saved and traded outside the mechanism. I show that the present-discounted value of expected revenues equals that of a conventional dollar auction, but revenues accrue earlier and are less volatile. The optimal monetary policy burns the tokens used for payment, a practice common in blockchain-based protocols. I also show that the same outcome can be reproduced in a dollar auction if the auctioneer issues a suitable dollar-denominated security. This equivalence breaks down with moral hazard and contracting frictions: with severe contracting frictions the token auction dominates, whereas with mild contracting frictions the dollar auction combined with a dollar-denominated financial instrument is preferred.
The current Proposer-Builder Separation (PBS) equilibrium has several builders with different backgrounds winning blocks consistently. This paper considers how that equilibrium will shift when transactions are sold privately via order flow auctions (OFAs) rather than forwarded directly to the public mempool. We discuss a novel model that highlights the augmented value of private order flow for integrated builder searchers. We show that private order flow is complementary to top-of-block opportunities, and therefore integrated builder-searchers are more likely to participate in OFAs and outbid non integrated builders. They will then parlay access to these private transactions into an advantage in the PBS auction, winning blocks more often and extracting higher profits than non-integrated builders. To validate our main assumptions, we construct a novel dataset pairing post-merge PBS outcomes with realized 12-second volatility on a leading CEX (Binance). Our results show that integrated builder-searchers are more likely to win in the PBS auction when realized volatility is high, suggesting that indeed such builders have an advantage in extracting top-of-block opportunities. Our findings suggest that modifying PBS to disentangle the intertwined dynamics between top-of-block extraction and private order flow would pave the way for a fairer and more decentralized Ethereum.
Modern blockchains guarantee that submitted transactions will be included eventually; a property formally known as liveness. But financial activity requires transactions to be included in a timely manner. Unfortunately, classical liveness is not strong enough to guarantee this, particularly in the presence of a motivated adversary who benefits from censoring transactions. We define censorship resistance as the amount it would cost the adversary to censor a transaction for a fixed interval of time as a function of the associated tip. This definition has two advantages, first it captures the fact that transactions with a higher miner tip can be more costly to censor, and therefore are more likely to swiftly make their way onto the chain. Second, it applies to a finite time window, so it can be used to assess whether a blockchain is capable of hosting financial activity that relies on timely inclusion. We apply this definition in the context of auctions. Auctions are a building block for many financial applications, and censoring competing bids offers an easy-to-model motivation for our adversary. Traditional proof-of-stake blockchains have poor enough censorship resistance that it is difficult to retain the integrity of an auction when bids can only be submitted in a single block. As the number of bidders $n$ in a single block auction increases, the probability that the winner is not the adversary, and the economic efficiency of the auction, both decrease faster than $1/n$. Running the auction over multiple blocks, each with a different proposer, alleviates the problem only if the number of blocks grows faster than the number of bidders. We argue that blockchains with more than one concurrent proposer have can have strong censorship resistance. We achieve this by setting up a prisoner's dilemma among the proposers using conditional tips.
Cryptocurrencies employ auction-esque transaction fee mechanisms (TFMs) to allocate transactions to blocks, and to determine how much fees miners can collect from transactions. Several impossibility results show that TFMs that satisfy a standard set of "good" properties obtain low revenue, and in certain cases, no revenue at all. In this work, we circumvent previous impossibilities by showing that when desired TFM properties are reasonably relaxed, simple mechanisms can obtain strictly positive revenue. By discretizing fees, we design a TFM that satisfies the extended TFM desiderata: it is dominant strategy incentive-compatible (DSIC), myopic miner incentive-compatible (MMIC), side-contract-proof (SCP) and obtains asymptotically optimal revenue (i.e., linear in the number of allocated bids), and optimal revenue when considering separable TFMs. If instead of discretizing fees we relax the DSIC and SCP properties, we show that Bitcoin's TFM, after applying the revelation principle, is Bayesian incentive-compatible (BIC), MMIC, off-chain-agreement (OCA) proof, and approximately revenue-optimal. We reach our results by characterizing the class of multi-item OCA-proof mechanisms, which may be of independent interest.
Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S.~dollars. In the status quo, users broadcast transactions and miners are responsible for composing a block of transactions and picking an execution ordering -- the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. In this work, we propose to modify the interaction between miners and users and initiate the study of {\em verifiable sequencing rules}. As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance. We ask if there are sequencing rules that limit price manipulation from miners in a two-token liquidity pool exchange. Our first result is an impossibility theorem: for any sequencing rule, there is an instance of user transactions where the miner can obtain non-zero risk-free profits. In light of this impossibility result, our main result is a verifiable sequencing rule that provides execution price guarantees for users. In particular, for any user transaction A, it ensures that either (1) the execution price of A is at least as good as if A was the only transaction in the block, or (2) the execution price of A is worse than this ``standalone'' price and the miner does not gain (or lose) when including A in the block.
Christoph Schlegel, Mateusz Kwaśnicki, Akaki Mamageishvili
We study axiomatic foundations for different classes of constant-function automated market makers (CFMMs). We focus particularly on separability and on different invariance properties under scaling. Our main results are an axiomatic characterization of a natural generalization of constant product market makers (CPMMs), popular in decentralized finance, on the one hand, and a characterization of the Logarithmic Scoring Rule Market Makers (LMSR), popular in prediction markets, on the other hand. The first class is characterized by the combination of independence and scale invariance, whereas the second is characterized by the combination of independence and translation invariance. The two classes are therefore distinguished by a different invariance property that is motivated by different interpretations of the numéraire in the two applications. However, both are pinned down by the same separability property. Moreover, we characterize the CPMM as an extremal point within the class of scale invariant, independent, symmetric AMMs with non-concentrated liquidity provision. Our results add to a formal analysis of mechanisms that are currently used for decentralized exchanges and connect the most popular class of DeFi AMMs to the most popular class of prediction market AMMs.
Jason Milionis, Dean Hirsch, Andy Arditi, Pranav Garimidi
Lately, Non-Fungible Tokens (NFTs), i.e., uniquely discernible assets on a blockchain, have skyrocketed in popularity by addressing a broad audience. However, the typical NFT auctioning procedures are conducted in various, ad hoc ways, while mostly ignoring the context that the blockchain provides, i.e., new possibilities, but at the same time new challenges in auction design. One of the main targets of this work is to shed light on the vastly unexplored design space of NFT Auction Mechanisms, especially in those characteristics that fundamentally differ from traditional and more contemporaneous forms of auctions. We focus on the case that bidders have a valuation for the auctioned NFT, i.e., what we term the single-item NFT auction case. In this setting, we formally define an NFT Auction Mechanism, give the properties that we would ideally like a perfect mechanism to satisfy (broadly known as incentive compatibility and collusion resistance) and prove that it is impossible to have such a perfect mechanism. Even though we cannot have an all-powerful protocol like that, we move on to consider relaxed notions of those properties that we may desire the protocol to satisfy, as a trade-off between implementability and economic guarantees. Specifically, we define the notion of an equilibrium-truthful auction, where neither the seller nor the bidders can improve their utility by acting non-truthfully, so long as the counter-party acts truthfully. We also define asymptotically second-price auctions, in which the seller does not lose asymptotically any revenue in comparison to the theoretically-optimal (static) second-price sealed-bid auction, in the case that the bidders' valuations are drawn independently from some distribution. We showcase why these two are very desirable properties for an auction mechanism to enjoy, and construct the first known NFT Auction Mechanism which provably possesses such formal guarantees.