We study auctions where two positions are sold to unit-demand bidders with private heterogeneous order preferences: some are specialists who value only the first position, while others are generalists who are indifferent between the two. First, we consider a standard first-price rule which allocates the first and second items to the highest and second-highest bidders, respectively. We show that no strategy profile ex-post implements the efficient allocation at every type profile, irrespective of payments, and provide a distribution-free equilibrium welfare guarantee of $\frac{1}{2}$. To augment this result, we prove that for deterministic one-round auctions and discrete bids, the efficient allocation requires each bidder to communicate at least one bit more than its bid's binary representation. We next ask what the same bit accomplishes in winner-pays-bid formats where bidders can also specify specific item preferences. In particular, we show that this strengthens our distribution-free equilibrium welfare guarantee to $1-\frac{1}{e}$. Finally, we discuss our results' applicability to priority service auctions and blockchain transaction sequencing.
Empirical work on algorithmic collusion asks one question of the data: are prices supracompetitive? We show this can be answered "no" by a conspiracy that is nonetheless profitable. Consider bidding agents that couple only through the joint distribution of their unexplained bid components, leaving every agent's own bid law exactly at the competitive law. Any test whose input is a single agent's price or bid history then has power exactly equal to its false-positive rate, for every coupling strength up to comonotonicity. The published detection methodology is therefore blind to this conduct by construction rather than underpowered, and no sample size repairs it. Three empirical results follow. First, the mechanism appears in real language-model agents: twenty models from nineteen independent developers, three deployment prompts each, show residual correlation of $+0.053$ between two deployments of one model against $+0.0001$ across models, with a 95% interval clustered by developer of $[0.030, 0.078]$, under an auditor that sees every order feature and is fitted out of sample. Second, the coupling falls monotonically as sampling temperature rises ($p=0.002$), turning a deployment parameter into a candidate mitigation. Third, on 24 days of Ethereum block-building auction data covering 77,684 bids from 39 bidders, the honest population of bidder pairs is itself so dependent that a screen held at a 5% false-positive rate must sit above a floor of $+0.50$ to $+0.81$, which is 20 to 32 times the family-wise sampling threshold and does not fall as the audit window grows. Since lawful multi-identity operation and conspiracy are behaviourally indistinguishable here, the tractable regulatory target is not detection but counting: resolving 40 bidding identities into 23 operators raises the Herfindahl index by 247.5%, and adding behavioural clusters from public bid streams reaches 324.5%.
Decentralized manufacturing faces a pre-contractual impasse: a Provider cannot price a service accurately without inspecting the design file, yet the Consumer cannot share that file without exposing intellectual property. We introduce the Optimistic Verifiable Claim (OVC), a blockchain protocol that lets a Consumer publish a verifiable claim about a concealed design (such as the material it consumes) and a Provider price and bid on it without seeing the design. The claim is committed when the service is posted and stands unless the selected Provider challenges it; a challenge triggers a deterministic on-chain check that exposes any dishonesty, and the design is disclosed only to settle a dispute, never on the honest path. We implement four checks (authorized key access, delivery-channel integrity, syntactic conformance, and declared material consumption) in Solidity and measure them on a real 6.41 MB G-code file, the 3DBenchy, across Ethereum, Arbitrum, and opBNB. Every service incurs the cost of posting the encrypted design, with or without a dispute. For the 3DBenchy, the no-dispute outcome costs \$7,207 in up to 9 hours on Ethereum, \$288 in 3 min on Arbitrum, and \$2.87 in 2 min on opBNB, and a fully contested dispute costs \$49,660 in up to 57 hours on Ethereum, \$1,988 in 19 min on Arbitrum, and \$19.73 in 13 min on opBNB. Costs and times grow with size: for a 50 MB industrial design, an undisputed service reaches \$56,173 and up to 3 days on Ethereum against \$22.36 and 16 min on opBNB, and a fully contested dispute reaches \$488,440 over up to 18 days on Ethereum against \$195 and 1.6 hours on opBNB. Of the four, the material-consumption check is the costliest, its predicate being the most expensive to evaluate on-chain. OVC makes confidential, claim-based bidding economically feasible on Arbitrum and opBNB, but not on Ethereum at industrial scale.
When is honest Bitcoin mining rational? This question is central to the incentive design of proof-of-work blockchains. Sapirshtein et al. computationally derived near-tight lower and upper bounds on the incentive-compatibility threshold using a Markov Decision Process. Kiayias et al.'s Blockchain Mining Games instead derived theoretical lower and upper bounds. However, this theoretical approach has two limitations: its model restricts miners to a narrow action space and assumes idealized tie behavior, and its lower and upper bounds are far from tight. We resolve both limitations. We develop a more realistic model with a broader miner action space and asymmetric tie-breaking parameters $γ^-$ and $γ^+$. We then propose an algorithm that computes lower and upper bounds on the incentive-compatibility threshold with a maximum error of $9.98006\times10^{-4}$.
We study the impact that two miners equipped with quantum computers purpose-built for quantum Bitcoin mining will have on the 51% attack threshold of the Bitcoin network, given that the miners are playing a competitive game against each other to be the first to mine a block. We extend an existing game-theoretic framework for Bitcoin mining and compute the resultant payoff matrices. From these payoff matrices, we determine optimal quantum mining strategies for two non-colluding and aggressive quantum miners with multiple opportunities at finding a valid block in an otherwise classical Bitcoin network. We show that these optimal quantum mining strategies have a negligible effect on the 51% attack threshold. The novelty of our work is the inclusion of the Aggressive Quantum Mining Strategy and the realistic approach of allowing the quantum miners to restart their search if their measurements do not yield a valid block when determining the optimal quantum mining strategies. Our result is important for evaluating quantum-mining threats on cryptocurrencies based on Proof-of-Work, e.g. Bitcoin
Aditya Saraf, Ioannis Kaklamanis, Sarisht Wadhwa, Fatima Elsheimy
Censorship resistance is the defining advantage of blockchains over their centralized counterparts. Yet block proposers censor transactions for many reasons, from legal consequences to economic incentives. We study economically-incentivized censorship, modeled by an adversary who bribes proposers to exclude a target transaction, and define the economic censorship resistance (eCR) of a transaction as the adversary's expected cost of successful censorship divided by the user's expected payment for inclusion. Single-proposer systems are structurally weak by this measure: under a first-price auction the adversary need only match the user's bid, and fee burning pushes eCR to a few percent of what the user pays. We therefore turn to multiple concurrent proposers (MCP), where block capacity is divided among $n$ proposers and the block is the union of their sub-blocks. While MCP can substantially increase the cost of censorship by requiring the adversary to bribe many proposers, it also introduces transaction duplication, reducing throughput. The resulting trade-off depends critically on the transaction fee mechanism (TFM), which determines how fees are shared among competing proposers. We create a game theoretic model where validators construct blocks from a shared mempool, subject to an adversary's bribery attempt. We provide an algorithm that solves for the mixed equilibrium of a given mempool, which is characterized by the probability of including each transaction. This algorithm works for a wide class of TFMs, and allows us to calculate the expected throughput and censorship resistance for any bid distribution. We then use simulations to show how the eCR and throughput vary as the number of proposers increases. We compare three TFMs, finding that the duplication-penalizing TFM dominates the others across many settings. We also validate our findings with empirical Ethereum data.
Sai Srikanth Madugula, Peplluis Esteva De La Rosa, Daya Shankar
The rapid proliferation of Agentic Artificial Intelligence fundamentally disrupts traditional customer loyalty paradigms. As AI evolves from passive recommendation algorithms to autonomous, goal-directed agents capable of executing purchasing decisions, the conventional understanding of consumer-brand relationships requires a structural reevaluation. By synthesizing extant literature across human-machine teaming, consumer decision-making, and algorithmic trust dynamics, we demonstrate that traditional loyalty models fail to account for algorithmic bounded rationality and constructed autonomy. To address this, we introduce the Dynamic Verifiable Multi-Agent Human Agentic Loyalty Loop (DVM-HALL) model. We formalize brand choice via a softmax probability formulation where human emotional equity, agentic machine-experience utility, calibrated trust, delegated authority, and verifiable execution jointly determine selection. The model features recursive updating mechanisms to dynamically calibrate trust and delegation after each interaction. Crucially, the framework integrates a verifiable execution layer for Decentralized Finance (DeFi) and tokenized loyalty settings, incorporating execution risks -- such as gas costs, slippage, MEV exposure, and smart-contract vulnerabilities -- as core predictors of agentic brand preference. Furthermore, we introduce the Net Human-Agent Score (NHAS), an auditable, risk-weighted metric designed to measure human-agent alignment using human feedback, execution logs, benchmark comparisons, and verifiable receipts. Finally, we propose a comprehensive three-stage empirical validation plan spanning controlled shopping experiments, multi-agent market simulations, and DeFi testbeds. This framework provides the foundational theory required for brands to navigate the impending transition toward machine customers.
Jingyu Liu, Bolin Zhang, Lin William Cong, Siguang Li · 5 authors
Ethereum's Glamsterdam upgrade introduces enshrined proposer-builder separation (ePBS), replacing relay-centric PBS with direct builder bids to proposers. We study how this shift changes the block-building microstructure through a general imperfect-information two-stage auction with verifiable messages, where an early bid serves as both a price offer and a signal. PBS and ePBS are modeled as restrictions of the same block-building game: PBS fixes stopping and disclosure exogenously, while ePBS lets the proposer choose stopping and disclosure ex post. Latency heterogeneity is captured by asymmetric information updates: fast builders observe disclosed early information before rebidding, while slow builders do not. We combine exact perfect Bayesian equilibrium characterizations in tractable cases with calibrated no-regret learning in finite games. For PBS, we show that separating equilibria preserve the standard first-price-auction payoff benchmark and provide conditions for their existence. For ePBS, we demonstrate a ratchet effect: because the proposer can defer block proposal and use early bid information in the second stage, builders anticipate ex-post extraction and shade or pool early bids, generating allocation inefficiency and revenue-efficiency valleys. We interpret this ratchet distortion as a commitment failure. Under full commitment, the optimal policy collapses to the static Myerson auction and removes the ratchet channel. To realize part of this commitment advantage in a feasible mechanism, we propose a Trusted Execution Environment (TEE) sidecar that enforces limited commitment. We formulate the revenue-maximizing TEE mechanism as a bilinear optimization problem. In conservative finite benchmarks, the TEE design increases the proposer revenue relative to the first-price benchmark by approximately \(25\%\).
Despite the promise of decentralization, measurement studies have identified a conspicuous lack of decentralization in blockchains. Centralization has been observed in almost all layers of the blockchain, in decentralized applications, and in decentralized autonomous organizations. In many cases, it is practically impossible to definitively determine the extent of centralization in the system. While multiple works have proposed methods to decrease centralization, by and large blockchains continue to be significantly centralized. In this paper, we develop a general framework for building verifiably decentralized blockchain systems. Our framework is motivated by the core observation that the richness and diversity of collaborative interactions between users -- rather than resource uniformity -- captures the essence and extent of decentralization in a blockchain system. Existing blockchains do not have any incentive mechanisms to encourage inter-coalition collaboration, which directly contributes to centralization. We propose a novel reward design that incentivizes users to collaborate with other users without forming isolated coalitions. Technically, our method uses a Sybil-resistant asymmetric Shapley value for reward attribution within a collaboration group, and the theory of expander graphs for measuring and enforcing decentralization. Our framework is general and can be adapted to alleviate centralization in any layer, application, or decentralized organization. It also has important implications beyond the topic of centralization. For example, we show that our solution can naturally address the blockchain scalability problem. We also identify a new class of decentralized collaborative applications that have hitherto been unexplored in blockchains.
We estimate the causal price elasticity of gas demand on Ethereum mainnet (L1) and Arbitrum One (L2), a quantity necessary for calibrating fee mechanism simulations, evaluating resource pricing reforms, and explaining observed usage patterns. A two-way fixed effects panel regression instrumented by each wallet's own lagged base fee removes the congestion-driven endogeneity that causes naive regressions to substantially underestimate demand sensitivity. On Ethereum mainnet (full year 2025), the pooled IV elasticity is -0.006***, near-inelastic: a 10% fee increase reduces total gas demand by approximately 0.06%. On Arbitrum One (October 2025--April 2026), the pooled IV elasticity is -0.036**. Both chains are inelastic in the aggregate, with L2 measurably more responsive than L1. A per-resource decomposition of L2 demand reveals elasticities ranging from modestly elastic computation (-0.027*) to -0.27*** for refunds, with storage growth (-0.15***) and calldata (-0.06*) in between. Behavioral clustering identifies always-on protocol wallets as near-inelastic and high-volume operators as substantially more responsive, with cluster-level elasticities up to roughly 6x the pooled estimate. These results establish an empirical foundation for downstream simulations and for evaluating fee mechanism designs.
This paper presents an open-economy macroeconomic equilibrium model for Proof-of-Stake (PoS) networks with fee-burn mechanics (EIP-1559) that formalizes the strategic interplay between a Kelly-optimizing rational institutional investor and a utility-driven retail consumer. We analyze network dynamics across two behavioral regimes. In The Unbounded Accumulation Model, the consumer purely accumulates tokens, creating an exclusive buy-side pressure that interacts with institutional portfolio rebalancing to fuel an ever-expanding speculative bubble and generate compounding excess returns for investors. Conversely, in The Utility-Consumption Model, the consumer dynamically buys and sells tokens to balance crypto wealth against real-world fiat consumption. Within this framework, we derive an explicit steady-state equilibrium price for ETH, demonstrating how token valuation anchors to a stable fundamental baseline that scales directly with network adoption while completely dissolving the institutional yield premium. Our numerical simulations show that while exogenous traditional finance (TradFi) shocks propagate through portfolio rebalancing to drive high token price volatility, network inflation remains highly stable. Furthermore, we prove that network security is insulated from institutional monopoly by counter-cyclical consumer behavior. Our findings reveal that institutional excess wealth creation in PoS ecosystems is not native to the staking protocol itself, but is strictly driven by the leveraged extraction of the retail consumer's continuous demand for transactional utility.
Proof-of-work (PoW) blockchains rely on computational expenditure to secure a ledger supporting a native cryptocurrency. In existing systems such as Bitcoin, this expenditure is intentionally useless: the computation secures consensus but produces no external economic output. An emerging alternative -- proof of useful work (PoUW) -- enables the same computation to simultaneously secure the blockchain and generate economically valuable output. However, PoUW is often criticized on economic grounds: if the work is useful, attackers might be "paid to attack," potentially weakening security. We develop a competitive-equilibrium model of a PoUW blockchain in which compute can be allocated across pure mining, pure useful work -- instantiated as machine-learning inference -- or "duplex" work that produces both with computational overheads. We provide a complete closed-form characterization of equilibrium allocations and prices as a function of the duplex overheads and a single economic parameter -- the token-inference ratio -- measuring token adoption relative to the inference market. This characterization reveals three regimes: "Bitconia," in which the economy reduces to classical PoW; "Fortessia," in which duplex replaces mining, increasing security while useful output remains unchanged; and "Duplexia," in which token rewards subsidize inference, lowering prices and expanding inference supply. Contrary to the common strawman argument, PoUW does not make attacks economically cheap: once equilibrium prices are taken into account, the economic cost of a majority attack remains tied to the block reward. Moreover, in Duplexia, block rewards act as rebates on inference prices, generating additional socially useful computation that would not arise without the blockchain -- an expansion monotonically increasing in token adoption and technological efficiency.
We analyze competing auctions in intermediated markets, where a seller selects among parallel mechanisms for the sale of a single good, most prominently the relay-and-protocol architecture of proposer-builder separation in Ethereum. When the intermediary can enforce single-homing on its bidders, sealed-bid second-price intermediary auctions fully unravel into the sealed first-price principal auction; open bidding-format intermediaries unravel only partially, collapsing into first-price in equilibrium under symmetric latency and sorting fast bidders to the intermediary under asymmetric latency. Any last-look advantage is removed through the availability of a credible sealed bidding channel. These results extend to multi-plexing environments (no enforcement by the intermediary). While the unraveling result indicates that the availability of a sealed first-price bidding channel pushes the overall market to the same auction structure, the very assumption of the credibility of such channel is problematic, as the seller may have an incentive to leak information: a first-price auction is leakage-resistant in the presence of a single ``fast'' bidder but not against two or more. However, if the seller can credibly commit to not leak bids, it is optimal for them to do so. A main motivation is the forthcoming Glamsterdam update of Ethereum: our analysis suggests that the availability of an in-protocol (first-price) bidding channel severely limits the design space for out-of-protocol auctions by relays and other intermediaries.
Many proof-of-stake protocols finance validator rewards from two sources: transaction fees and a finite reserve of tokens. This creates a dynamic hand-off problem. Early in the life of the system, fees may be too small to fund the target level of security; later, fees may become sufficient. The central question is whether the reserve provides enough runway for the protocol to remain secure until this fee-only region is reached. We study this problem in a discrete-time stochastic model of validator participation. Token price and transaction demand fluctuate over time, while validators choose participation strategically. We solve the validator entry game and derive an exact state-dependent reserve threshold, i.e., the minimal reserve stock necessary and sufficient to sustain a target security level. This threshold separates three regions: infeasibility, reserve-dependent security, and fee-only security. Security fails if the reserve first falls below the state-dependent threshold, and a successful hand-off occurs exactly if the fee-only region is reached before that failure time. We derive stress-test guarantees that convert lower confidence bands for token price and demand into reserve requirements, and obtain explicit failure-probability and expected hand-off-time bounds. Finally, we extend the model to forward-looking validators and derive the Markov participation condition that captures how current participation affects future reserve-funded rewards. The main implication is that reserve policy should not be evaluated by nominal depletion dates or steady-state reward ratios alone. A protocol can have a large nominal reserve and still be close to security failure after adverse price or demand shocks. Conversely, once demand crosses the fee-only threshold, the reserve becomes redundant for security. This paper provides a tractable equilibrium framework for stress-testing this transition.
Blockchains have popularized the Automated Market Makers (AMMs), where users trade crypto-assets directly with a smart contract, governed by a pricing function embedded in the contract's code. Today, users of AMMs are often forced to accept unfavorable prices due to widespread front-running and back-running attacks, commonly known as Miner Extractable Value (MEV). Several earlier works show impossibility results suggesting that completely removing MEV at the consensus layer is impossible, partly because the consensus layer is agnostic of application-level semantics. For this reason, more recent works have advocated mechanism design approaches at the application (i.e., smart contract) level. We study a natural two-asset AMM mechanism design problem recently initiated and explored in prior work by Chan, Wu, and Shi, in which they proposed a mechanism that satisfies a surprisingly strong notion of incentive compatibility (IC), under the consensus assumption that the underlying blockchain provides sequencing fairness. In this paper, we investigate the (in)feasibility of simultaneously achieving IC and other desirable properties such as weak local efficiency (wLE) and uniform pricing (UP). At a high level, wLE requires that the mechanism should not leave any unfulfilled demand from users whose asking prices are not overly restrictive, and whose orders could have been executed directly against the pool. UP requires that all orders that get (partially) executed must trade at the same exchange rate. We unveil the underlying mathematical structure of AMM mechanism design, and our main results can be summarized as a trilemma-style theorem: among the desirable properties IC, wLE, and UP, any two out of three are possible, but no mechanism can satisfy all three.
Validators on generic Proof of Stake chains earn the same fees whether they handle attestation work correctly or selectively censor it. For chains whose main activity is moving tokens around, that indifference is fine. For chains whose primary economic activity is recording attestations (content provenance, AI-output attribution, threshold-signed credentials, supply-chain receipts), the indifference becomes a problem. Proof of Useful Attestation (PoUA) makes attestation handling first-class in the consensus weighting itself. Validator vote weight is the product of bonded stake and a reputation scalar in [r_min, r_max] that accumulates from valid attestation work. The reputation update is additive, fee-weighted, non-transferable, and capped per epoch. We prove a cost-to-grind floor (Lemma 1): under chain-wide adaptive burn fraction tau_burn, the non-recoverable cost an adversary pays to inflate reputation by Delta_r is bounded below by tau_burn * Delta_r / (eta * alpha_eff). Under the recommended v0 calibration (r_max/r_min in [4, 10]), the cost premium against a capital adversary is 4x to 10x over equivalent pure-stake PoS at steady state. The paper specifies the mechanism, six layered Sybil and grinding defenses, empirical Monte Carlo strategy-search across the full layered defense, and grinding detectors with explicit threshold derivations. It is a mechanism-design proposal with a formal economic floor and inherited BFT safety and liveness, not a complete cryptographic security proof. This release incorporates feedback from Jiangshan Yu (University of Sydney) and Marko Vukolić (Bitcoin Scaling Labs).
Aleksei Adadurov, Sergey Barseghyan, Anton Chtepine, Antero Eloranta · 6 authors
Ethereum block builders run sealed auctions among searchers, but nothing in the protocol forces a builder to honor the auction outcome after observing submitted bundles. This paper studies the commitment problem. We model a builder who defects with probability $\varepsilon$ and, upon defection, replicates a type-specific fraction $γ(τ)$ of the winning MEV opportunity. Searchers anticipate this behavior and choose between a risky first-price bid and a safe deterrence bid that makes frontrunning unprofitable. The resulting equilibrium is piecewise, with the cost of imperfect commitment depending jointly on replicability and competition. Using the libMEV dataset, we estimate $γ(τ)$ from right-tail bribe plateaus and decompose observed auction revenue against the surplus a defecting builder could capture. The results show sharp heterogeneity across MEV types: sandwich opportunities are already highly competitive, while naked arbitrage and liquidations leave substantially more surplus exposed to builder defection. Credible MEV auctions, therefore, require not only an auction format, but also constraints on the builder's ability to use observed bid and payload information ex post.
Jingyi Liu, Aviad Rubinstein, Ertem Nusret Tas, S. Matthew Weinberg · 5 authors
Classical optimal auction theory assumes that bids reach the seller directly. We study how this picture changes when a revenue-maximizing intermediary controls access to the seller's auction. Motivated by blockchain auctions, online platforms, and other intermediated markets, we consider a single-item auction with independent private values and a monopolist intermediary who can decide which bidder messages are forwarded to the seller. We establish approximation guarantees and impossibility results across three timing models: seller-first, intermediary-first, and simultaneous. In the seller-first model, arbitrary deterministic seller mechanisms collapse to posted-price mechanisms, and the intermediary's best response is a shifted Myerson auction. This yields a sharp separation: for regular distributions, the seller's revenue can be arbitrarily small relative to the no-intermediary optimum, while for $α$-strongly regular distributions, posted prices recover a constant fraction of the optimum with a tight dependence on $α$. We further show that timing matters: neither Stackelberg order uniformly dominates, and simultaneous play can leave both parties unboundedly worse off than in either sequential model.
Austin Bennett, Preston Vander Vos, Duc V. Le, Mira Belenkiy
Decentralized Autonomous Organizations (DAOs) run protocol governance by letting token holders vote on proposals. The dominant rule, voting power proportional to wallet balance, concentrates control among a small number of large holders, fueling the token-control governance attacks that have already compromised real protocols. To counter this concentration, the community has turned to anti-plutocratic voting mechanisms such as Quadratic Voting (QV), which assign sublinear voting power per token with the goal of dampening the influence of large holders. We prove that no voting rule that derives power solely from wallet balance can succeed on a permissionless blockchain. Through a costed model of on-chain voting that captures realistic blockchain frictions -- including per-wallet splitting and voting costs, fixed setup costs, and minimum-balance requirements -- we show that whenever a wallet of any size yields nonzero voting power, a Sybil attacker who splits tokens across many wallets achieves total voting power that grows at least linearly in their token holdings. For concave rules actually proposed to dampen governance power -- those that are positive, increasing, and finite -- we show that the optimal strategy yields power that is asymptotically linear in token holdings, regardless of the cost scheme. Instantiating the model on real DAOs reveals attack costs orders of magnitude below the value at stake. Replaying the ten most recent finalized proposals of five major DAOs (ENS, Compound, Uniswap, Arbitrum, and ZKsync) under linear, quadratic, logarithmic, and power-($β= 0.25$) voting, we measure Sybil amplification factors between $1,172\times$ and $4,039\times$ under Quadratic Voting, and exceeding $229,000\times$ under steeper power rules.
Privacy-preserving cryptocurrency exchanges alter what the pricing mechanism observes about order flow. We derive the unique linear Kyle equilibrium when a committed Bayesian market maker observes order flow perturbed by independent Gaussian privacy noise. The price-impact coefficient and informed-trader strategy rescale by reciprocal factors of the privacy parameter (one down, one up), so their product is invariant. A welfare decomposition then identifies a closed-form per-period transfer from the protocol's LP pool to traders -- the "privacy subsidy", the break-even fee any privacy-aggregated exchange must charge. The result is the single-period closed-form privacy-noise analog of Loss-Versus-Rebalancing (Milionis et al. 2022). The primary application is shielded AMMs with explicit additive-noise injection (e.g., differential privacy); related designs (batched swaps, sealed-bid auctions, oracle-pegged crossings) require separate frameworks that we leave to future work.
The Ethereum blockchain utilizes the EIP-1559 algorithm to manage transaction inclusion and block assembly. However, EIP-1559 and much of the existing literature study this problem from a static perspective, focusing on price evolution without modelling transaction dynamics within the mempool. Motivated by this limitation, we study a dynamic transaction scheduling problem in which transactions with heterogeneous sizes and per-unit values arrive over time and remain in the mempool until scheduled. To capture the stochastic mempool evolution, we formulate the problem as a Markov Decision Process (MDP) whose state represents the mempool configuration and whose actions correspond to block prices. We first provide a primal-dual interpretation of the static EIP-1559 mechanism, showing that block prices arise naturally as dual variables of a social-welfare maximization problem. Building on this perspective, we extend the framework to the dynamic setting and formulate an objective that maximizes long-run discounted reward while incorporating holding costs and overshoot penalties. We then employ a Natural Policy Gradient (NPG) algorithm to compute the optimal policy. Our results show that dynamic pricing stabilizes the mempool while maximizing long-run discounted reward. In particular, as the overshoot penalty increases, the average scheduled transaction volume converges to the target block capacity, and the resulting NPG updates closely resemble the EIP-1559 price update rule. Finally, we study two special cases of the MDP formulation: homogeneous transactions and uniform arrivals. In the homogeneous setting, where the protocol directly controls scheduled volume, we show that the optimal policy has a threshold structure. We then propose a bang-bang pricing mechanism for uniform arrivals and derive a lower bound on the block capacity needed to ensure system stability.
Transaction selection in parallel or DAG-based distributed ledger technologies (DLTs) is a crucial challenge that directly impacts throughput, fairness, and validator incentives. In these systems, validators independently choose transactions to include in their blocks, often relying on naive heuristics like uniform or proportional selection. This can lead to inefficient outcomes when validators prioritize their own rewards without considering collective impacts. We analyze two fee allocation mechanisms used in practice: Random Fee Allocation (RFA), where transaction fees are randomly assigned to one validator, and Collaborative Fee Sharing (CFS), where fees are distributed equally among all validators. Using a single-shot game-theoretic framework, we derive symmetric Nash equilibria (NE) for selecting transactions for both mechanisms and propose an optimization-based method to compute these equilibria. Numerical simulations demonstrate that the NE of CFS consistently achieves higher throughput and rewards compared to the NE of RFA, particularly under skewed fee distributions. Additionally, we compare these equilibrium strategies to naive benchmarks (uniform and proportional selection), showing that the proportional strategy outperforms the NE of RSA in many situations. These findings may provide actionable insights into the design of transaction selection and incentive mechanisms, enabling more robust and high-performance DAG-based DLTs.
Maryam Bahrani, Michael Neuder, S. Matthew Weinberg
An emerging blockchain protocol design pattern leverages the asymmetry between the computational effort in performing versus verifying tasks. For example, cryptographic validity proofs (e.g., SNARKS) require the prover to expend significant effort demonstrating the correctness of their claim, while the verifiers benefit from extremely easy validation. The operationalization of this paradigm requires efficiently soliciting the performance of expensive tasks in pseudonymous, adversarial environments. We formalize this as a mechanism design question. The protocol balances the economic cost of a liveness fault, where the work is not completed, with the payments required to incentivize specific behavior from candidate suppliers. We show that the loss of the optimal protocol scales logarithmically in the cost of a liveness fault, scaled up by the adversarial fraction of the network. Further, we find that the optimal equilibria have an intuitive structure, allowing us to provide concrete advice to practitioners. Specifically, in many regimes, the optimum designates a single, random node as the primary worker and a committee as a fallback, which is reminiscent of leader-based consensus mechanisms. We also characterize the asymptotic regimes where having negative payments (i.e., slashing in blockchain parlance) is especially helpful.
Leon Witt, Togrul Abbasli, Kentaroh Toyoda, Wojciech Samek · 5 authors
We introduce Knowledge-Free Correlated Agreement (KFCA) to reward client contributions in federated learning (FL) without relying on ground truth, a public test set, or distribution knowledge. Under categorical reports and an honest majority, KFCA is strictly truthful, addressing the label-flipping vulnerability of Correlated Agreement (CA). We evaluate KFCA on federated LLM adapter tuning and a real-world PCB inspection task, showing efficient real-time reward computation suitable for decentralized and blockchain-based incentive designs.