Technical Summary: Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty

1. Problem Statement

Modern blockchains are transitioning from serial to parallel execution to overcome throughput bottlenecks caused by execution rather than consensus. While parallel execution (used or planned by chains like Sui, Solana, Monad, and Ethereum) increases capacity, it introduces two critical economic challenges when transactions involve execution uncertainty (contingency) and resource contention:

1. Execution Contingency and Risk Allocation: In expressive smart contract languages (Turing-complete), a transaction's resource usage (objects accessed) often depends on the state of the blockchain at runtime, which cannot be known prior to execution. This creates a tension between User Risk (users overpaying for declared objects that go unused) and Scheduler Risk (schedulers losing revenue when reserved capacity goes unpaid due to under-execution).
2. Shill Attacks on Gas Computation: Existing Gas Computation Mechanisms (GCMs) designed for parallel settings (e.g., Shapley value or Time-Proportional Makespan) are vulnerable to rational manipulation. Both users and schedulers can inject "shill" (fake) transactions to strategically alter the calculated gas or fees. Users can lower their fees by adding useless parallel transactions, while schedulers can inflate fees by adding fake contention.

The paper argues that current designs fail to simultaneously account for parallelism, execution uncertainty, and economic robustness, leading to inefficiencies and exploitable vulnerabilities.

2. Methodology and Model

The authors formalize a framework for analyzing Transaction Fee Mechanisms (TFMs) under parallel execution with uncertainty.

• Transaction Model: A transaction $tx$ is defined by compute units $t$, a priority fee $g$, and declared read/write sets $(R, W)$. Crucially, the actual objects accessed ($X_R, X_W$) may be a subset of the declared sets depending on the execution path (contingency).
• Fee Definitions: The paper distinguishes between:
  • Attainable Fee ($f_{att}$): The fee if all declared objects are used.
  • Baseline Fee ($f_{base}$): The fee for only deterministic objects.
  • User-Ideal Fee ($f_{ui}$): The fee for exactly the objects actually used.
  • Actual Paid Fee ($f_{act}$): The fee charged.
• Risk Metrics:
  • **User Risk ($UR$):**$f_{act} - f_{ui}$ (overpayment).
  • **Scheduler Risk ($SR$):**$f_{att} - f_{act}$ (unrealized revenue).
• Adversarial Model: Users and schedulers are modeled as rational, economically motivated agents who can insert shill transactions to minimize their costs or maximize revenue, respectively.
• Complexity Analysis: The paper utilizes complexity theory (specifically P-completeness) to analyze the difficulty of predicting object usage without execution.

3. Key Contributions and Results

A. Impossibility of Simultaneous Risk Elimination

The paper proves a fundamental impossibility result: No mechanism can simultaneously eliminate both User Risk and Scheduler Risk without pre-executing transactions or collapsing to constant fees.

• Theorem 1: If a scheduler is constrained by a compute limit $G$ (cannot perform more work than the block allows), it is impossible to set payments such that $UR=0$ and $SR=0$ for all inputs involving conflicting contingent transactions.
• Theorem 2 (P-completeness): Deciding whether a specific object is used by a contingent transaction (the Object Usage Decision Problem) is P-complete. This implies that verifying object usage requires sequential work proportional to the execution time, making it computationally infeasible for a scheduler to predict usage "cheaply" before execution.
• Trade-off: There is an inherent linear trade-off. Reducing user risk (charging only for used objects) increases scheduler risk (revenue loss), and vice versa.

B. Characterization of Risk Division Mechanisms

Given the impossibility, the authors characterize the design space via three canonical risk division mechanisms, parameterized by $\alpha \in [0,1]$:

1. User-Friendly ($\alpha=0$): Users pay only for realized execution ($f_{act} = f_{ui}$). Scheduler bears all risk.
2. Scheduler-Friendly ($\alpha=1$): Users pay for all declared objects ($f_{act} = f_{att}$). User bears all risk.
3. Even-Steven ($\alpha=0.5$): Risk is split evenly.
   The paper analyzes these under different scheduler utility models (Optimistic, Pessimistic, Median) to map the revenue implications.

C. Shill Attacks and Fee-Based Shill-Proofness

The paper identifies that standard GCM properties (like Set Inclusion) are insufficient to prevent shill attacks in the presence of contingency.

• User Shill Attacks: Users inject fake transactions to reduce the effective gas/fee of their real transaction.
• Scheduler Shill Attacks: Schedulers inject fake transactions to increase the gas/fee charged to honest users.
• Fee-Based Shill-Proofness: The authors propose new definitions for shill-proofness based on fees rather than just gas, accounting for priority fees and execution contingency. They prove that for User-Friendly mechanisms, shill-proofness is only achievable if the fee is independent of the schedule (Theorem 3).

D. The Object-Weighted TFM (OW-TFM)

To resolve these issues, the authors propose the Object-Weighted Transaction Fee Mechanism (OW-TFM).

• Mechanism: Fees are calculated based on the price of objects declared by the transaction, where object prices are updated based on historical utilization (similar to EIP-1559).
• Risk Parameterization: The mechanism uses a parameter $\alpha$ to determine how much a user pays for declared-but-unused objects ($\alpha \cdot \text{price}$).
• Shill Resistance: The OW-TFM is shown to be shill-proof under specific conditions. Because prices are derived from past block utilization, a shill transaction in the current block cannot lower the price of an object for the current block (it can only raise future prices).
• Conditions: Lemma 4 establishes a threshold for $\alpha$ required to prevent scheduler shill attacks, dependent on the priority-to-base fee ratio ($\pi_o$), price responsiveness ($\eta$), and retention ratio ($\gamma$).

4. Significance and Claims

The paper claims to provide the rigorous foundations for evaluating and designing fee mechanisms for parallel blockchains. Its significance lies in:

1. Identifying Fundamental Limits: It demonstrates that the tension between user fairness and scheduler revenue in parallel execution is not a design flaw but a fundamental consequence of execution uncertainty and computational complexity.
2. Exposing Vulnerabilities: It reveals that existing proposals for parallel gas computation (e.g., Shapley-based approaches) are vulnerable to rational shill attacks, a threat previously unaddressed in the literature.
3. Providing a Design Framework: It offers a principled design space (the $\alpha$ spectrum) and a concrete mechanism (OW-TFM) that allows system designers to explicitly choose their risk allocation strategy while maintaining resistance to manipulation.
4. Relevance to Industry: The results directly apply to and critique the designs of prominent parallel chains (Sui, Monad, Solana) and Ethereum's roadmap for parallel execution via access lists.

The authors maintain a modest tone, noting that their work identifies fundamental limitations and trade-offs rather than prescribing a single "perfect" solution, acknowledging that practical deployment requires further consideration of probabilistic execution models and specific implementation details.