Research
Exploiting Multi-Core Parallelism in Blockchain Validation and Construction
Most deployed blockchains, including Ethereum-style execution, run transactions one after another in a fixed total order, which leaves modern multi-core CPUs largely idle even though many…

- arXiv
- 2602.03444
- Published
- 2026-02-03
- Authors
- Arivarasan Karmegam, Lucianna Kiffer, Antonio Fernández Anta
AI summary
Overview
- Research area: Distributed and parallel computing applied to blockchain systems — specifically deterministic parallel execution and conflict-aware block building.
- Technical level: Advanced. The paper formalizes two NP-hard optimization problems, gives Mixed-Integer Linear Programming (MILP) formulations, and proves an approximation bound, so comfort with scheduling theory and ILP is assumed.
- Scope (one sentence): The paper studies how a blockchain validator can use multiple CPU cores to execute an already-ordered block faster and to assemble a new block that earns more reward, without ever breaking the deterministic state semantics of the chain.
What This Paper Is About
Most deployed blockchains, including Ethereum-style execution, run transactions one after another in a fixed total order, which leaves modern multi-core CPUs largely idle even though many transactions touch disjoint accounts or storage slots. The authors ask two concrete questions a validator actually faces: given a block whose transaction order is already fixed, how should its cores be used to finish it in the least time, and given a mempool of pending transactions with different costs and fees, which transactions should be picked and how should they be spread across cores to maximize reward within a runtime limit. Throughout, any parallel schedule must be provably equivalent to running the block sequentially in its given order.
Key Contributions
- Two formalized validator-side problems. Ordered-Block Scheduling (OBS) asks for a minimum-makespan schedule of a fixed, totally ordered block on
pcores with conflicts respected; Parallel-Block Construction (PBC) jointly selects a subset of mempool transactions and schedules them onpcores so that the makespan stays within a runtime limitBand validator reward is maximized. Conflicts are defined purely by read/write set overlap involving at least one write. - Exact MILP formulations for both problems. Separate models are given for homogeneous transactions (equal execution time, time discretized into rounds
R) and heterogeneous ones (varying execution times, explicit start/end times, core assignment, and ordering indicators). The authors state these are optimal on small-to-medium instances but become intractable at realistic scale. - Fast deterministic heuristics with guarantees. For OBS the pipeline is: build a conflict dependency DAG, compute critical-path/volume/fan-out priority keys in one backward pass, then run an event-driven list scheduler that assigns the highest-priority ready transaction to any free core. It inherits the classical list-scheduling guarantee of makespan at most
2 - 1/ptimes optimal, and runs inO(n^2)worst case, dominated by DAG construction. - An empirical study on Ethereum mainnet traces, benchmarking MILPs against the heuristics in both solution quality and solve time, with two additional baselines:
Sol, a Solana-inspired declared-access baseline for ordered-block scheduling, andRG, a simple reward-greedy baseline for block construction.
Main Findings
- Modest but real parallel speedups on ordered blocks. Despite tight ordering constraints, the heuristic reaches up to
1.5speedup withp = 2and2.3withp = 8over sequential execution according to the abstract; the introduction phrases the same result as a factor of1.57with 2 cores and more than2with 8 cores. The two statements differ in wording and should be read from the paper's results tables. - Heuristics track the optimum closely. Heuristic makespans for ordered-block execution are typically within a few percent of the MILP solutions, and can even beat the MILP incumbent when the solver times out, while running in milliseconds.
- Exact optimization collapses at scale. MILPs quickly become intractable as transaction heterogeneity, core count, or the runtime limit increases; the heterogeneous OBS model alone needs
O(n^2 p)binary variables andO(n^2 p + |E|)constraints. - Block construction is where the larger gains are. The heuristic achieves
99–100%of the MILP optimum reward on homogeneous workloads, and74–100%of an LP-relaxation upper bound on heterogeneous workloads where exact optimization often times out. - Throughput scales nearly linearly with cores. Block-construction throughput reaches up to
7.9speedup withp = 8, and the introduction reports the achieved reward more than doubling even with only4cores. - The problems are provably hard. OBS is the classical precedence-constrained makespan problem
P|prec|C_max, known to be NP-hard on 3 cores and on 2 cores when execution times are in{1,2}; PBC generalizes knapsack with conflict graphs and parallel-machine scheduling with conflicts. - A systems gap in deployed block building. Existing block-assembly pipelines select transactions by fee greedily and do not systematically account for parallelizability, which the authors identify as the main practical opening for this work.
- Not reported in the provided content: the exact number of transactions or blocks in the Ethereum traces, the specific values of
Bused, and the per-experiment result tables (the text is truncated partway through Section 5.1.1).
Methodology in Plain English
The authors start from a simple observation: two transactions can safely run at the same time only if their reads and writes do not overlap on any account or storage slot, or if they overlap only on reads. So they treat each transaction as declaring an access list of the state keys it reads (R) and writes (W), and label a pair as conflicting exactly when at least one of them writes a key the other touches. Transaction execution time is modeled as proportional to its gas usage, and reward as gasU × tip.
For a fixed block, they draw an arrow from transaction i to transaction j whenever the two conflict and i comes earlier in the block. The result is a dependency DAG, and scheduling becomes the familiar problem of packing work onto p machines while respecting arrows. They write down an exact optimization program for this (in two variants, one for equal-length transactions using discrete rounds and one allowing arbitrary start times), then replace it with a greedy rule that repeatedly hands the free core to whichever ready transaction sits at the head of the longest remaining chain of dependent work.
For building a new block, they flip the objective: instead of a fixed set of transactions, there is a mempool where transactions differ in both reward and cost, and a hard cap on total execution time. This couples selection and scheduling into one packing problem, again written as an exact program and again replaced by a fast heuristic. Both approaches are then run against real Ethereum traces and compared to the exact models, to a Solana-style declared-access baseline, and to a plain reward-greedy baseline, measuring both how good the answer is and how long it takes to produce.
Why This Matters
- Research impact: The paper converts an engineering question ("can we parallelize block execution?") into two clean, comparable optimization problems with published baselines, exact models, and approximation guarantees. It makes explicit the gap between opportunistic in-order parallelism (as in Block-STM or Solana's Sealevel) and truly makespan-optimal order-equivalent scheduling, and it extends parallelism into transaction selection, which prior work largely left to fee-greedy heuristics.
- Validator and client engineering: Execution clients can adopt the conflict-DAG plus list-scheduling approach directly, since it preserves state-identical results while cutting block processing time.
- Block building and proposer economics: Builders who currently sort by fee can, within the same runtime limit, include more or better-paying transactions by accounting for which ones can actually run side by side — the paper reports reward more than doubling with 4 cores.
- Hardware and cloud provisioning: Because throughput scales close to linearly up to 8 cores, the results inform whether a validator operator should buy fewer faster cores or more slower ones.
- Design of new chains and access lists: The
Solbaseline shows the value of requiring transactions to declare their access sets, feeding into ongoing discussion about access-list design in Ethereum-style protocols.
Future Directions
- Scaling past 8 cores and past the tested workloads: whether the near-linear construction speedup and the few-percent makespan gap hold at larger
p, larger blocks, and higher contention is left open. - Tighter exact methods: the MILP formulations time out under heterogeneity; better formulations, cutting planes, or decomposition could extend the range where optimal baselines are computable.
- Closing the theory gap for PBC: OBS has a
2 - 1/pguarantee, but the block-construction heuristic is evaluated only empirically (against MILP optima and an LP upper bound), so an approximation bound for joint selection-and-scheduling remains to be established. - Integration with real mempools and dependency structures: real transactions have nonce chains, cross-transaction dependencies, and dynamic access patterns, and the paper's traces are historical snapshots rather than a live adversarial mempool.
- Interaction with fee markets and MEV: how parallelizability-aware selection interacts with gas-price dynamics, private order flow, and builder competition is not addressed.
Target Audience
Blockchain protocol researchers and validator/execution-client engineers will get the most from this paper, particularly those working on parallel execution engines, block building, or transaction scheduling. It also suits operations researchers and scheduling theorists interested in a concrete applied domain with a clean DAG structure, and graduate students in distributed systems looking for a well-posed problem with both exact and heuristic solutions. Readers need some background in NP-hard scheduling and integer programming to follow the formal sections, though the problem statements themselves are readable by anyone familiar with how blockchains order transactions.
Authors’ abstract
Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered…
The full abstract on arXiv