Efficient Scheduling of Smart Contract Transactions via Conflict Graph Coloring

Abstract

A smart contract is a special type of transaction designed for the execution of automated logic on blockchains. Alas, smart contracts transactions are one of the major hindrances to blockchain throughput. Hence, improving the execution time of smart contracts is a prime challenge for Blockchains at large. To that end, concurrent execution of smart contract is an appealing direction, which has been adopted by several contemporary Blockchains like Solana, Aptos, Sui, Sei, and Monad. Executing smart contracts in parallel requires applying deterministic concurrency controls based on ensuring consistent ordering of all conflicting transactions in all miners/validators. Existing implementations rely on the Block's total ordering to resolve this requirement. Recently, it has been suggested that relying on minimal coloring of the conflict graph corresponding to the Block's transactions can provide a better performance potential, yet without any evaluation. In this paper, we compare between approaches to smart contracts parallelization. Our study’ finds that in many situations, indeed the coloring-based ordering leads to significantly better performance than the Block order preserving approach. However, this gain has its limits, and it is not always guaranteed. In particular, the results are largely dependent on the conflict ratio in the conflict graph and the type of application.