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.

Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain's performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs' execution runtime. A unique challenge of blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order to maintain the semantics of State Machine Replication (SMR). In this work, we study the maximal level of parallelism attainable when focusing on the conflict graph between transactions packaged in the same block. This exposes a performance vulnerability that block creators may exploit against existing blockchain concurrency solutions, which rely on a total ordering phase for maintaining consistency amongst all replicas. To facilitate the formal aspects of our study, we develop a novel generic framework for Active State Machine Replication (ASMR) that is strictly serializable. We introduce the concept of graph scheduling and the definition of the minimal latency scheduling problem, which we prove to be NP-hard. We show that the restricted version of this problem for homogeneous transactions is equivalent to the classic Graph Vertex Coloring Problem, yet show that the heterogeneous case is more complex. We discuss the practical implications of these results.