Paper 2025/2247 Original: eprint.iacr.org/2025/2247 ↗

Beyond Incentive Compatibility: Rational Harm-Proof Transaction Fee Mechanisms

Abstract

On a blockchain, users compete for scarce block space in an auction run by the miner to get their transactions confirmed in the block. This auction is called transaction fee mechanism (TFM). Recent work [Rou21, CS23, SCW23] has been focused on incentive compatibility (IC), requiring that honest behavior maximizes the payoff for each type of strategic player: users, the miner, or miner–user coalitions. In this work, we introduce rational-harm proofness (RHP), which rules out deviations that harm honest parties without also reducing the deviator’s own utility relative to the honest baseline. RHP closes a gap left by IC: IC does not forbid utility neutral yet externally harmful deviations. For example, in a second-price auction, the second-highest bidder can increase the winner’s payment without affecting their own payoff. Such deviation is eliminated by RHP. We characterize TFMs satisfying RHP alongside incentive compatibility for users (UIC) and miners (MIC). For finite block size, we develop a complete characterization in two models: - In the plain model---where a single miner unilaterally implements the auction---we prove a tetrilemma (3-out-of-4 impossibility): among the four desired properties {positive miner revenue, UIC, MIC, RHP against miner–user coalitions}, no mechanism achieves all four simultaneously. This trade-off is tight: any three are jointly achievable in the plain model. - In the MPC-assisted model---where a committee of miners jointly implement the auction via multi-party computation (MPC)---we construct a randomized TFM with a positive miner revenue that achieves UIC, MIC, and RHP against all three types of strategic players. We further show that randomness is necessary: any deterministic TFM satisfying UIC and RHP in this model must confirm no transactions when the number of users exceeds the block size. Finally, we show that IC and RHP are incomparable: for each strategic role, there are mechanisms satisfying one but not the other in both models. Our results broaden the design objectives for TFMs: beyond incentive compatibility, mechanisms should also preclude costless harm to honest participants.