Research
Beyond Incentive Compatibility: Rational Harm-Proof Transaction Fee Mechanisms
Blockchains sell scarce block space through an auction run by the miner, and most prior work asks whether the auction is incentive compatible (IC) — that is, whether honest behavior maximizes each…

- arXiv
- 2609.32005
- Published
- 2026-09-25
- Authors
- Forest Zhang, Elain Park, Ke Wu
AI summary
Overview
Research area: Blockchain transaction fee mechanism (TFM) design, sitting at the intersection of algorithmic game theory, mechanism design, and distributed-systems security.
Technical level: Advanced. The paper is a formal theory paper: it defines new incentive properties, proves impossibility and characterization theorems, and constructs a mechanism. The prose here is plain-language, but the underlying arguments are proof-based and assume familiarity with auctions, incentive compatibility, and multi-party computation.
Scope: The paper introduces "rational-harm proofness" (RHP) as a TFM design requirement, characterizes which TFMs satisfy it together with user and miner incentive compatibility in both a single-miner ("plain") and a committee-based ("MPC-assisted") model, and shows that incentive compatibility and RHP are incomparable.
What This Paper Is About
Blockchains sell scarce block space through an auction run by the miner, and most prior work asks whether the auction is incentive compatible (IC) — that is, whether honest behavior maximizes each player's own payoff. The authors point out that IC leaves a gap: a player can deviate in a way that does not change their own utility at all, yet makes honest participants strictly worse off. The paper formalizes a requirement that closes this gap — rational-harm proofness — and then determines exactly when TFMs can satisfy it alongside the standard incentive guarantees and positive miner revenue.
Key Contributions
-
A new design property: rational-harm proofness (RHP). The authors formalize the requirement that no strategic player — an individual user, the miner (or a colluding subset of miners), or a miner–user coalition — can make any honest participant strictly worse off unless the deviators also make themselves worse off relative to the honest baseline. The definition is ex-post and is stated as a property of the mechanism for every valuation profile, rather than being tied to equilibrium existence or selection.
-
Three role-specific instantiations. RHP is split into user RHP (URHP), miner RHP (MRHP), and d-coalition RHP (d-CRHP), each being the same definition applied to a different deviating strategy space and protected set of honest players.
-
A complete characterization in the plain model. The authors prove a "tetrilemma": among positive miner revenue, UIC, MIC, and RHP against miner–user coalitions, no mechanism achieves all four with finite block size k. The trade-off is shown to be tight — any three are jointly achievable.
-
A feasibility result and a randomness-necessity result in the MPC-assisted model. A posted-price-with-random-selection mechanism achieves UIC, MIC, all three RHP variants, and positive miner revenue; separately, any deterministic UIC and URHP mechanism in that model must confirm no transactions when the number of bids exceeds k. The paper also proves that IC and RHP are incomparable for each strategic role in both models.
Main Findings
-
IC does not imply protection from costless harm. In a second-price auction, the second-highest bidder can raise their bid slightly, remain a loser paying nothing, and thereby increase the winner's payment. The deviator's utility is unchanged; the winner is harmed. IC does not forbid this, and RHP does.
-
Plain-model impossibility (Theorem 1.2). With finite block size k, any TFM that is UIC, MIC, and 1-CRHP must be degenerate: it confirms no bids when there are more than k bids, and miner revenue must always be zero.
-
The impossibility survives weakening the coalition notion (Theorem 1.3). Even if 1-CRHP is relaxed to weak 1-CRHP (which only constrains strictly profitable deviations), miner revenue in any UIC and MIC mechanism must still always be zero.
-
Only trivial mechanisms survive the full set (Corollary 1.4). No mechanism satisfies UIC, MIC, MRHP, and (weak) 1-CRHP in the plain model except trivial ones that never confirm any bid.
-
The plain-model trade-off is tight (Theorem 1.5). Any three of UIC, MIC, 1-CRHP, and positive miner revenue can be achieved simultaneously; witness mechanisms are given in the paper's Section 4.1.
-
MPC-assisted feasibility (Mechanism 1.6 and Theorem 1.7). Let res > 0 be a reserve and 0 < ε ≤ res a revenue parameter. Let E be the set of bids at least res. The mechanism randomly chooses min{k, |E|} bids from E, confirms them, charges each the reserve price, and gives the miner total revenue ε if at least one bid is confirmed and zero otherwise. This achieves UIC, MIC, URHP, MRHP, d-CRHP for any d ≤ k, and positive miner revenue in the MPC-assisted model (M ≥ 3 miners, fewer than half corrupted, i.e. m < M/2).
-
Randomness is necessary in the MPC-assisted model (Theorem 1.8). Any deterministic UIC and URHP TFM must be degenerate: no bid can be confirmed whenever the number of bids exceeds k.
-
IC and RHP are incomparable (Theorem 1.9). In both models, and for each strategic role (user, miner, miner–user coalition), there exist mechanisms that are X-IC but not X-RHP, and vice versa. The first-price auction (RHP but not UIC) and second-price auction (UIC but not URHP) are the illustrative examples.
-
RHP is distinct from side-contract proofness (SCP). The posted-price mechanism is not SCP: if no honest user has value at least res, a coalition of m < M/2 miners plus one user with value v ∈ (res − mε/M, res) can bid res, get confirmed, pay res, and collect mε/M in miner revenue, for coalition utility v − res + mε/M > 0. Crucially, this deviation harms no protected participant — honest users stay unconfirmed with zero utility and non-colluding miners gain revenue — which is exactly the distinction CRHP draws.
-
RHP is distinct from approximate IC and from griefing-factor analysis. ε-IC bounds how much a deviator can gain; RHP bounds the external harm a rational deviation can cause, allowing the gain itself to be arbitrarily large. Griefing-factor work studies harm relative to attacker cost, including attacks where the attacker accepts a loss; RHP addresses the conservative case where harming others costs the deviator nothing in modeled utility.
-
The plain-model barrier traces to censorship. The driving force behind the plain-model impossibilities is the miner's ability to censor honest bids without reducing its own payoff — the "censor-then-replace" attack, which underpins the proof's "above-payment-guarantee" lemma and the induction on bid vectors.
Methodology in Plain English
The authors proceed as a mechanism-design theory paper would.
First, they fix a model. A single block of finite size k is treated as k identical slots. Each user has a private true value for inclusion, submits a bid, and a TFM decides which bids are included and confirmed, what each confirmed bid pays, and what the miner earns. The mechanism must be individually rational (no one pays more than their value), budget feasible (miner revenue does not exceed total payments), and weakly symmetric (metadata is used only for tie-breaking). Three strategic roles are considered — a single user, the miner or miner subset, and a miner–user coalition — and the honest profile is the baseline against which harm is measured.
Second, they define RHP by quantifying over all true value profiles and all deviating strategies: if a coalition's strategy gives it at least its honest utility, then every protected honest player must also get at least their honest utility. This is an ex-post requirement, chosen because mempools are public and miners see bids before deciding what to include.
Third, they prove impossibility in the plain model using a proof by induction. Starting from an assumed case where some bid is confirmed under congestion, they construct a sequence of bid vectors v^(1), v^(2), … and show by induction that m bids must be confirmed in v^(m). Taking m = k + 1 contradicts the block size. The engine of the induction is a collusion argument: if a bid above some confirmed bid's payment were left unconfirmed, the miner and that bidder could censor the confirmed bid and replace it with an identical value, leaving the miner's revenue unchanged while the colluder gains — which 1-CRHP forbids. A separate argument lifts the result from deterministic to randomized mechanisms.
Fourth, they show tightness by exhibiting witness mechanisms achieving each subset of three properties, and then move to the MPC-assisted model, where M ≥ 3 miners evaluate the mechanism jointly through an ideal functionality with guaranteed output delivery and m < M/2 corruption. There they construct the posted-price-with-random-selection mechanism and prove it satisfies the full target set, then prove that determinism forces degeneracy by a separate argument.
Finally, they build a catalogue of example mechanisms in Section 6, summarized in the paper's Table 1 (plain model) and Table 2 (MPC-assisted model), to demonstrate that IC and RHP fail in both directions for every strategic role.
Why This Matters
Impact on research. The paper reframes what a "good" TFM must guarantee. Prior work treated incentive compatibility — UIC, MIC, SCP — as the finish line; this paper shows that a mechanism can be fully IC and still let rational players impose uncompensated losses on honest ones. It also adds a new point to the impossibility landscape (a tetrilemma, alongside existing trilemmas and UIC/SCP impossibilities) and shows that the barrier is specifically about censorship, which points to committee-based block construction as the structural fix. Because RHP is defined for arbitrary coalitions and both individual and group deviations, it also connects TFM design to the classical non-bossiness literature while extending it to settings with a strategic auctioneer.
Real-world applications:
- Base-fee and priority-fee design on production chains. The paper notes that Ethereum's move to a posted-price structure in EIP-1559 was motivated in part by simplifying fee estimation; the posted-price-with-random-selection mechanism is in the same family and inherits that usability argument, while adding harm protections during congestion.
- Committee-based block building. The MPC-assisted model maps onto architectures where multiple block producers participate in block construction, including FOCIL-style inclusion lists and committee-based proposals referenced in the paper.
- Sequencer and rollup fee markets. Any system where a small set of operators selects transactions from a public mempool faces the same censor-then-replace pressure that drives the plain-model impossibility.
- Side-contract and collusion analysis. Because smart contracts make miner–user side payments easy, the paper's CRHP gives a residual guarantee for the common case where SCP is unattainable: a coalition may still profit, but not at honest participants' expense.
Industry relevance. The authors argue the mechanism is practical to deploy: because bids are public, Mechanism 1.6 does not require generic MPC, only a censorship-resistant inclusion mechanism that fixes the set of submitted bids plus an independent, non-biasable randomness beacon sampled after those bids are fixed. The result is a lightweight, publicly verifiable rule. The design guidance is blunt: if congestion is possible, no plain-model mechanism gets all four desiderata, so operators must either provision capacity so the constraint is effectively non-binding or explicitly choose which property to sacrifice.
Future Directions
- Characterizing RHP under alternative plain-model strategy spaces. The paper notes that a different line of work (citing [22]) lets the miner omit and inject bids but evaluates deviations under the prescribed randomized allocation rule, rather than letting the miner control the realized randomness. Characterizing RHP in that model is stated as an open direction.
- Combining RHP with Bayesian or approximate incentive notions. The authors observe that approximate IC and RHP constrain different things — the deviator's gain versus the harm to others — and that neither substitutes for the other. How they interact jointly is left open.
- Achieving protection beyond CRHP. Since UIC and d-SCP for d ≥ 2 cannot coexist with non-zero honest utility under finite block size, SCP was set aside. Whether some stronger coalition guarantee than CRHP is compatible with the full target set is unresolved.
- Instantiating the MPC-assisted mechanism end-to-end. The paper sketches the building blocks (a censorship-resistant inclusion list and a non-biasable randomness beacon) but leaves the concrete protocol design and its deployment properties as engineering work.
Target Audience
Researchers in blockchain protocol economics and algorithmic game theory who work on transaction fee mechanisms, auction design with strategic auctioneers, or collusion-resistance notions. It is also useful for protocol designers and applied cryptographers who need to reason about miner–user collusion, censorship, and mempool-level manipulation in production systems, and for graduate students looking for a worked example of how to extend an incentive-compatibility definition to cover externalities. Readers should be comfortable with formal definitions and impossibility proofs; the paper's own Section 1.1 and Section 2 provide the accessible entry points.
Authors’ abstract
Transaction fee mechanisms (TFMs) allocate scarce block space in blockchains. Prior work focuses on incentive compatibility (IC): honest behavior maximizes the payoff of each strategic player. We introduce rational-harm proofness (RHP), which rules out deviations that harm honest participants without reducing the deviator's utility relative to honest behavior. IC alone does not exclude such costless harm: in a second-price auction, a losing bidder can raise the winner's…
The full abstract on arXiv