Lock-Free Concurrent Smart Contracts

Smart contracts are commonly used on blockchains to define complex behaviors not possible with simple transactions. Miners and validators could achieve significant performance gains by executing smart contracts in parallel, but validators must be able to re-execute the proposed block deterministically. Existing works capture the execution order of concurrently executed transactions using locks, or Software Transactional Memory, enabling validators to re-execute the block deterministically. These approaches can introduce a costly overhead for large blocks, in which many transactions must be compared to deduce their ordering. In this paper, we present a methodology for executing smart contracts concurrently without locks by associating each smart contract state variable with a descriptor, and updating these descriptors with Compare-And-Swap (CAS). Whenever a descriptor is updated, we create a reference to the previous descriptor within the new one. The resulting graph represents all conflicts between transactions, and can be used to deterministically re-execute the transactions in parallel. Our approach captures the ordering between transactions whenever a semantic conflict is detected, eliminating the need to compare lock acquisitions, or timestamps. Additionally, our approach provides a guarantee of Lock-Free progress. In our experimental evaluation, our approach achieves a maximum speedup of 70x against related work when tested on block sizes similar to that of Bitcoin, or Ethereum.