  Current UTXO-based smart contracts face an efficiency bottleneck, requiring
any transaction sent to a contract to specify the entire updated contract
state. This requirement becomes particularly burdensome when the contract state
contains dynamic data structures, such as maps, which are needed in many use
cases for tracking users interactions with the contract. The problem is
twofold: on the one hand, a large state in transactions implies a large
transaction fee; on the other hand, a large centralized state is detrimental to
the parallelization of transactions, which should be one of the main selling
points of UTXO-based blockchains compared to account-based ones. We propose a
technique to efficiently execute smart contracts on an extended UTXO
blockchain, which allows the contract state to be distributed across multiple
UTXOs. In this way, transactions only need to specify the part of the state
they need to access, reducing their size (and fees). We also show how to
exploit our model to parallelize the validation of transactions on multi-core
CPUs. We implement our technique and provide an empirical validation of its
effectiveness.
