Skip to content
Crypto.world

Research

Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty

Blockchains like Sui, Solana, Monad, and Ethereum are moving to parallel execution to raise throughput, but parallelism makes fee design hard: a transaction's real cost depends on which other…

Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty
arXiv
2604.04193
Published
2026-04-05
Authors
Sarisht Wadhwa, Aviv Yaish, Fan Zhang, Kartik Nayak

AI summary

Overview

Research area: Blockchain systems security and mechanism design — specifically transaction fee mechanisms (TFMs) and gas computation mechanisms (GCMs) for blockchains that execute transactions in parallel.

Technical level: Advanced. The paper is a theory-heavy treatment using formal definitions, lemmas, and complexity-theoretic reductions (P-completeness), though it grounds every idea in a single worked example (Alice's automated-market-maker swap) that makes the intuition accessible.

Scope (one sentence): The paper formalizes how execution parallelism and contingent (state-dependent) transaction behavior create unavoidable trade-offs and profitable manipulation vectors in blockchain fee design, proves an impossibility result bounding what any mechanism can achieve, and proposes a fee mechanism (OW-TFM) that reaches that boundary.

What This Paper Is About

Blockchains like Sui, Solana, Monad, and Ethereum are moving to parallel execution to raise throughput, but parallelism makes fee design hard: a transaction's real cost depends on which other transactions it conflicts with, and smart contracts written in Turing-complete languages may touch different objects depending on state they cannot see in advance. The paper shows that tried-and-true fee designs break down in this setting — users can overpay for resources they never use, schedulers can lose revenue, and both parties can profitably inject fake ("shill") transactions to distort fees. The goal is to build a formal framework for this setting, prove what is and is not achievable, and design mechanisms that sit at the achievable frontier.

Key Contributions

  1. A formal model of parallel execution with contingency. The authors define transactions as compute time plus declared read/write sets, distinguish declared from used object sets, and define contingent objects and contingent transactions (Definitions 1 and 2). They also define four reference fees — attainable (f_att), baseline (f_base), user-ideal (f_ui), and actual paid/received (f_act, r_act) — with two monotonicity constraints.

  2. An impossibility result separating user risk and scheduler risk. They define user risk as f_act − f_ui (paying for unused declared objects) and scheduler risk as f_att − f_act (reserved capacity going unpaid). Lemma 1 shows the two always sum to f_att − f_ui, a constant; Theorem 1 shows that a scheduler limited to G compute cannot drive both to zero for a schedule with at least two conflicting contingent transactions, except under a constant fee (or by excluding conflicting transactions, or by burning all revenue while charging only for used objects).

  3. Identification and formalization of shill attacks. The paper defines user shill attacks (fake transactions that dilute the effective gas charged to a real transaction) and scheduler shill attacks (fake transactions that inflate charges to honest users), formalizes shill-proofness as a required property, and proves it is fundamentally incompatible with the efficiency requirement that total gas equals the schedule makespan. Building on the Gas Computation Mechanism framework of Acilan et al. (including Shapley and Time-Proportional Makespan approaches), they show natural proposals admit profitable manipulation.

  4. Object-Weighted TFM (OW-TFM). A fee mechanism that prices a transaction by the objects it declares in the parallel schedule rather than by serial execution time alone, using an EIP-1559-like per-object price updated from how often each object was used in previous blocks. The fee is the sum of object prices multiplied by the user-specified priority fee, and the authors identify parameters under which it is shill-proof.

Main Findings

  • Risk is conserved, not eliminated. For any transaction, state, and schedule, UR + SR = f_att − f_ui. In the running example (Alice's swap with declared objects costing 1, 3, and 1), f_att = 5 and, on the revert branch, f_ui = 1, so the total risk to allocate is exactly 4 units no matter the design.
  • A tunable linear trade-off. Pricing f_act = α·f_att + (1−α)·f_ui sweeps the frontier: at α = 0 Alice pays 1 (UR = 0, SR = 4); at α = 1 she pays 5 (UR = 4, SR = 0); at α = 1/2 she pays 3 (UR = SR = 2). Three canonical mechanisms instantiate the endpoints and midpoint: user-friendly (charges only realized execution), scheduler-friendly (charges worst-case declared execution), and Even-Steven (splits unrealized cost evenly), each analyzed under optimistic, pessimistic, and median scheduler models.
  • Burning breaks the clean transfer. Because the scheduler keeps only a retention ratio γ = r/f of what users pay (the rest burned, as with EIP-1559's base fee), shifting money from user to scheduler is not one-to-one, so combined welfare is not conserved even though the risk sum is.
  • The impossibility is computational, not just economic. The Object Usage Decision Problem (OUDP) — does a transaction access object o before gas limit G is exhausted? — is proven P-complete via reduction from the Generic Machine Simulation Problem, with G encoded in unary. Under widely believed complexity separations, there is no sub-polynomial shortcut to predicting object usage, so a scheduler cannot price contingency exactly without doing the sequential work of execution itself.
  • Parallelism alone creates manipulation incentives. If parallel work affects fees, users can insert functionally useless parallel transactions touching idle objects to spread out and lower their real transaction's charge, and schedulers can insert useless sequential transactions to raise revenue.
  • Contingency cheapens shill attacks. When a shill transaction does not pay the full price for every object it declares (i.e., when scheduler risk is non-zero), the cost of mounting shill attacks falls — so the risk-allocation choice and the shill-proofness choice are coupled.
  • Scheduling heuristics are revenue-suboptimal. The greedy heuristics used by systems like Sui and the random heuristics used by Aptos and Monad do not match optimal parallel schedules in revenue terms.
  • Not reported: The paper reports no experimental benchmarks, datasets, or measured throughput numbers; its results are analytical and proof-based.

Methodology in Plain English

The authors proceed as theorists building a model from the ground up. They start with one concrete scenario — Alice's swap to an AMM that reads an oracle price and only writes the pool reserves and her balance if the price is favorable — and use it as a running example for every new definition, so each abstraction can be checked against something tangible.

They then define the moving parts precisely: what a transaction is, what a schedule is, what counts as a "used" versus merely "declared" object, when an object is contingent, and when two transactions conflict. On top of that they define user risk and scheduler risk and prove the conservation lemma.

To show the trade-off is fundamental rather than a weakness of a particular design, they turn to complexity theory: they define a decision problem (does this transaction touch this object within this gas budget?) and reduce a known P-complete problem to it, establishing that no cheap general algorithm can predict object usage. Separately, they model users and the scheduler as rational, self-interested parties who may mis-declare objects or inject fake transactions, define shill-proofness, and check which mechanisms survive. Finally, they propose OW-TFM and derive the parameter regimes in which it satisfies the properties.

Why This Matters

Fee mechanism design has been studied mostly for serial execution, where gas is a one-dimensional, fungible resource. This paper is among the first to treat parallel execution and contingent smart-contract behavior as first-class constraints on fee design, and it shows that the intuitive fixes (charge for what is used, charge for what is declared) are the two ends of a trade-off rather than a solution. The P-completeness result gives a rigorous reason why this trade-off cannot be engineered away.

Real-world applications:

  • Layer-1 fee design for parallel chains (Sui, Solana, Monad, and Ethereum's parallel-execution roadmap): choosing where on the user-risk/scheduler-risk spectrum a chain's fee market should sit, and understanding what that choice costs the other side.
  • Validator and sequencer revenue modeling: understanding how contingent transactions systematically reduce collected fees, and how much revenue is at risk if base fees are burned while only realized execution is charged.
  • Protocol security review of gas metering: testing proposed gas computation rules against shill attacks before deployment, so that fee-dilution and fee-inflation strategies by users and block builders are caught at design time.
  • Block-builder and scheduler policy: replacing greedy or random scheduling heuristics with ones that account for revenue and for conflict structure under contention.

Industry relevance: the paper explicitly aims to provide "rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad," which matters directly to protocol teams, fee-market researchers, and auditors working on production parallel-execution systems.

Future Directions

  • Routing-style contingency. The authors explicitly leave out of scope transactions whose contingency comes from routing (e.g., a swap router that directs to whichever AMM offers the best price, making all AMMs' liquidity contingent objects). They argue a scheduler should expect the transaction not to access all objects there, and flag this as future work.
  • Dynamic (non-constant) retention ratios. The model assumes a constant retention ratio γ and notes that a dynamic burning constraint — where the retention ratio increases as a transaction uses more of its declared objects — could deter schedulers from forcing under-execution. Designing and analyzing such a rule is open.
  • Tightening OW-TFM's parameter range. The paper shows parameters under which OW-TFM is shill-proof; mapping the full parameter space, including how per-object price update rules interact with contingency, is a natural continuation.
  • Closing the loop between the two perils. Since contingent transactions reduce the cost of shill attacks when scheduler risk is non-zero, an integrated analysis of risk allocation and shill resistance — rather than treating them as separate design axes — remains open.

Target Audience

Blockchain protocol researchers and designers working on fee markets, gas metering, and parallel execution; mechanism-design and algorithmic-game-theory researchers interested in multidimensional and scheduling-based pricing; and security engineers or auditors at layer-1 teams (Sui, Monad, Solana, Ethereum) evaluating whether a proposed fee or gas rule can be gamed. The paper is also a useful read for graduate students in distributed systems or cryptography who want a worked example of combining an economic impossibility with a complexity-theoretic hardness proof. Readers need comfort with formal definitions and basic complexity classes; the running example makes the core intuitions reachable for those without that background.

Authors’ 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…

The full abstract on arXiv
Read the original paper