Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty

• URL: http://arxiv.org/abs/2604.04193v1
• Date: Sun, 05 Apr 2026 17:26:23 GMT
• Title: Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty
• Abstract summary: Modern blockchains increasingly rely on parallel execution to improve throughput.<n>We show several industry and academic transaction fee mechanisms struggle to simultaneously account for execution parallelism while remaining performant and fair.<n>Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.
• Score: 11.303442819201337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern blockchains increasingly rely on parallel execution to improve throughput. We show several industry and academic transaction fee mechanisms (TFMs) struggle to simultaneously account for execution parallelism while remaining performant and fair. First, if parallelism affects fees, adversarial protocol manipulations that offset possible benefits to throughput by introducing fake transactions become rational: users can insert functionally useless parallel transactions solely to reduce fees, and schedulers can create useless sequential transactions to increase revenue. Execution contingency, a core feature of expressive programming languages, both exacerbates the aforementioned threats and introduces new ones: (1) users may overpay for unused resources, and (2) scheduler revenue is harmed when reserved scheduling slots go unused due to contingency. We introduce a framework for this challenging setting, and prove an impossibility, highlighting an inherent tension: both parallelism and contingency involve a trade-off between minimizing risks for users and schedulers, as favoring one comes at the expense of the other. To complete the picture, we introduce a fee mechanisms and prove that they achieve the boundaries of this trade-off. Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.

Related papers

• DeFiFusion: Combining Transaction Events with Smart Contracts to Detect Price Manipulation Attacks [24.680454716643325]
  Decentralized Finance (DeFi) has emerged as a rapidly growing blockchain-based financial service, where market transaction dynamics and smart contract logic are intricately intertwined.<n>Price Manipulation Attacks (PMAs) have already inflicted catastrophic financial losses.<n>We present DeFiFusion, a dual-modal PMA detection framework that closes this gap by jointly modeling transaction events and smart contract semantics.
  arXiv  Detail & Related papers  (2026-09-10T02:36:45Z)
• Time Is Money: Incentivized Causal Transaction Ordering [9.096175121355737]
  We present PRECEDE, a mechanism-design approach that enforces transaction causality by removing the economic incentive to front-run.<n> PRECEDE can be directly deployed in any censorship-resistant blockchain with a simple change to its transaction ordering mechanism.
  arXiv  Detail & Related papers  (2026-07-13T12:49:34Z)
• Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers [48.17065660350331]
  Transaction selection in DAG-based distributed ledger technologies (DLTs) is a crucial challenge that directly impacts throughput, fairness, and validator incentives.<n>We analyze two fee allocation mechanisms used in practice: Random Fee Allocation (RFA) and Collaborative Fee Sharing (CFS)<n> 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.<n>These findings may provide actionable insights into the design of transaction selection and incentive mechanisms, enabling more robust and high-performance DAG-based DLTs.
  arXiv  Detail & Related papers  (2026-05-08T07:42:42Z)
• Adversarial procurement in blockchains [2.7433496624899383]
  An emerging blockchain protocol design pattern leverages the asymmetry between the computational effort in performing versus verifying tasks.<n>We formalize this as a mechanism design question.<n>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.
  arXiv  Detail & Related papers  (2026-05-07T01:08:10Z)
• GoAT-X: A Graph of Auditing Thoughts for Securing Token Transactions in Cross-Chain Contracts [52.51342355102833]
  Cross-chain bridges, the critical infrastructure of the multi-chain ecosystem, have become a primary target for attackers.<n>Existing defenses, such as bytecode-level static analysis, are ill-equipped to handle the semantic complexity of cross-chain interactions.<n>We propose GoAT-X, a framework that shifts automated cross-chain smart contracts auditing from pattern matching toward systematic first-principles verification.
  arXiv  Detail & Related papers  (2026-04-27T11:34:21Z)
• Unleashing Implicit Rewards: Prefix-Value Learning for Distribution-Level Optimization [74.91418266859297]
  Implicit process reward models (PRMs) provide fine-grained reward signals along the reasoning process.<n>PRMs suffer from a train-inference mismatch: training only constrains a sequence-level aggregate, whereas inference requires token-level scores to reflect local step quality.<n>We propose a novel Implicit Prefix-Value Reward Model (IPVRM), which directly learns a prefix-conditioned value function estimating the probability of eventual correctness.<n>We also propose Distribution-Level RL (DistRL), which computes TD advantages for both sampled tokens and high-probability candidate tokens.
  arXiv  Detail & Related papers  (2026-04-14T18:19:54Z)
• Parallel-Probe: Towards Efficient Parallel Thinking via 2D Probing [76.48164395646019]
  Parallel-Probe is a training-free controller designed to optimize online parallel thinking.<n>It reduces sequential tokens by up to $textbf35.8$% and total token cost by over $textbf25.8$% while maintaining competitive accuracy.
  arXiv  Detail & Related papers  (2026-02-03T18:59:41Z)
• Hollow Victory: How Malicious Proposers Exploit Validator Incentives in Optimistic Rollup Dispute Games [2.88268082568407]
  A popular layer-2 approach is the Optimistic Rollup, which relies on a mechanism known as a dispute game for block proposals.<n>In these systems, validators can challenge blocks that they believe contain errors, and a successful challenge results in the transfer of a portion of the proposer's deposit as a reward.<n>We reveal a structural vulnerability in the mechanism: validators may not be awarded a proper profit despite winning a dispute challenge.
  arXiv  Detail & Related papers  (2025-04-07T14:00:46Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• StealthDust: Secret Quorums for Faster Fractional Spending [0.2446948464551684]
  We address the Fractional Spending Problem using (k1, k2)-quorum systems - both introduced by Bazzi and Tucci-Piergiovanni (PODC 2024)<n>We propose a new protocol called StealthDust, where secret quorums allow to reduce payment latency from five to three communications steps and improve settlment message complexity from O(n3) to O(n2) compared to the original protocol.
  arXiv  Detail & Related papers  (2024-12-21T14:37:36Z)
• Designing Redistribution Mechanisms for Reducing Transaction Fees in Blockchains [10.647087323578477]
  Transaction Fee Mechanisms (TFMs) determine which user transactions to include in blocks and determine their payments. We propose Transaction Fee Redistribution Mechanisms (TFRMs) -- redistributing VCG payments as rebates to minimize transaction fees. Our results show that TFRMs provide a promising new direction for reducing transaction fees in public blockchains.
  arXiv  Detail & Related papers  (2024-01-24T07:09:32Z)
• LookAhead: Preventing DeFi Attacks via Unveiling Adversarial Contracts [15.071155232677643]
  Decentralized Finance (DeFi) has resulted in financial losses exceeding 3 billion US dollars.<n>Current detection tools face significant challenges in identifying attack activities effectively.<n>We propose LookAhead, a new framework for detecting DeFi attacks via unveiling adversarial contracts.
  arXiv  Detail & Related papers  (2024-01-14T11:39:33Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.