Transaction Fee Market Design for Parallel Execution

Given the low throughput of blockchains like Bitcoin and Ethereum, scalability -- the ability to process an increasing number of transactions -- has become a central focus of blockchain research. One promising approach is the parallelization of transaction execution across multiple threads. However, achieving efficient parallelization requires a redesign of the incentive structure within the fee market. Currently, the fee market does not differentiate between transactions that access multiple high-demand resources versus a single low-demand one, as long as they require the same computational effort. Addressing this discrepancy is crucial for enabling more effective parallel execution. In this work, we aim to bridge the gap between the current fee market and the need for parallel execution by exploring alternative fee market designs. To this end, we propose a framework consisting of two key components: a Gas Computation Mechanism (GCM), which quantifies the load a transaction places on the network in terms of parallelization and computation, measured in units of gas, and a Transaction Fee Mechanism (TFM), which assigns a price to each unit of gas. We also introduce a set of desirable properties for a GCM, present multiple candidate mechanisms, and evaluate them against the properties. One promising candidate emerges: the weighted area GCM. Notably, this mechanism can be seamlessly composed with existing TFMs, such as EIP-1559. While our exploration primarily focuses on the execution component of the fee, which directly relates to parallel execution, we also outline how it could be integrated with fees associated with other factors, such as storage and data bandwidth, by drawing a parallel to a multi-dimensional fee market.