2026-09-22T03:10:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26027 2026-09-05T19:34:59Z ddc:004 open_access

Exploiting Multi-Core Parallelism in Blockchain Validation and Construction Karmegam, Arivarasan Kiffer, Lucianna Fernández Anta, Antonio Block construction Block execution Deterministic parallelism Conflict-aware scheduling 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 block on p cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit B to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime. MILPs quickly become intractable as heterogeneity or core count increases, whereas our heuristics run in milliseconds and achieve near-optimal quality. For ordered-block execution, heuristic makespans are typically within a few percent of the MILP solutions (and can even surpass the MILP incumbent when the solver times out), yielding up to 1.5 speedup with p = 2 and 2.3 speedup with p = 8 over sequential execution, despite tight ordering constraints. For block construction, the heuristic achieves 99-100% of the MILP optimum reward on homogeneous workloads, and 74-100% of an LP-relaxation upper bound on heterogeneous workloads, where exact optimization often times out. The resulting block-construction throughput scales close to linearly with p, reaching up to 7.9 speedup with p = 8 in our experiments. These results demonstrate that lightweight, conflict-aware scheduling and selection can unlock substantial parallelism in blockchain validation, bridging the gap between sequential execution and the true potential of multi-core hardware. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arivarasan Karmegam and Lucianna Kiffer and Antonio Fernández Anta 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.23 urn:nbn:de:0030-drops-260271 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode