Accounts, Strict Access Lists, and UTXOs
===

<small>Thanks to Mustafa Al-Bassam (@musalbas), James Prestwich (@prestwich), and Sam Wilson (@SamWilsn) for review.</small>

<small>HackMD mirror: https://hackmd.io/KOJdKANHSvaGC_8IugEAJA</small>

To date there has been widespread confusion around the limits of the UTXO data model, with claims that it is more challenging if not impossible to implement Ethereum-style smart contracts with it. We present here an execution model built on top of UTXOs that can support (depending on the specifics of the virtual machine) the totality of Ethereum's smart contract functionality. These ideas are by no means new, but are fragmented in online discourse. This post should serve as a monolithic resource for introducing and discussing this model for those unfamiliar with it.

## Background

### Prerequisite Reading

- [Bitcoin: A Peer-to-Peer Electronic Cash System](https://bitcoin.org/bitcoin.pdf), Nakamoto
- [(Ethereum Design Rationale) Accounts and not UTXOs](https://eth.wiki/en/fundamentals/design-rationale#accounts-and-not-utxos), Buterin
- [(Bitcoin Stack Exchange) UTXO model vs. account/balance model](https://bitcoin.stackexchange.com/a/49872), Wuille
- [The Stateless Client Concept](https://ethresear.ch/t/the-stateless-client-concept/172), Buterin
- [EIP-648: Easy parallelizability](https://github.com/ethereum/EIPs/issues/648), Buterin
- [Practical parallel transaction validation without state lookups using Merkle accumulators](https://ethresear.ch/t/practical-parallel-transaction-validation-without-state-lookups-using-merkle-accumulators/5547), Adler
- [Intro to CKB Script Programming 1: Validation Model](https://medium.com/nervosnetwork/intro-to-ckb-script-programming-1-validation-model-9a7d84679266), Xiao

### Extra Reading

- [State Provider Models in Ethereum 2.0](https://ethresear.ch/t/state-provider-models-in-ethereum-2-0/6750), Dietrichs et al.
- [Automated Detection of Dynamic State Access in Solidity](https://ethresear.ch/t/automated-detection-of-dynamic-state-access-in-solidity/7003), Wilson
- [The "Direct Push" model can’t handle stale witnesses](https://ethresear.ch/t/the-direct-push-model-cant-handle-stale-witnesses/7019), Cloutier
- [Optimizing sparse Merkle trees](https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751), Buterin
- [Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities](https://arxiv.org/abs/1809.09044), Al-Bassam et al.
- [Zexe: Enabling Decentralized Private Computation](https://eprint.iacr.org/2018/962), Bowe et al.

## Ethereum-style Execution in the UTXO Model

### Data Model

In addition to the usual _coin_ UTXOs found in traditional UTXO-based systems such as Bitcoin, we will define a new UTXO type, _contract_ UTXOs.

Coin UTXOs have the following fields:
1. Amount of coins
1. Spend script hash (which can define an owner) or owner

Contract UTXOs are composed of the following fields:
1. Amount of coins
1. Contract ID
1. Contract code hash
1. Storage root

In practice, optimizations and additions will certainly be made to these fields, such as [storing the root of Merkleized scripts or code](https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki) rather than the hash. We present a minimal list here to simplify analysis by focusing on the core required features.

The contract code hash and storage root are only needed if using the [stateless execution model](https://ethresear.ch/t/the-stateless-client-concept/172). In the stateful execution model, they can be omitted from contract UTXOs, but a separate storage element UTXO type is needed.

The UTXO ID (a unique identifier for each UTXO, which can be used as the key in a key-value store database) is the [outpoint](https://btcinformation.org/en/developer-reference#outpoint) that produced the UTXO, or some variant thereof (e.g. the hash of the outpoint and the fields).

Note that contracts in this model do not have a defined "owner" (i.e. a secret key that has exclusive control over them), just as is the case with contracts on Ethereum today. Rather, the contract code is expected to define its own internal concept of ownership, e.g. [with an `onlyOwner()` method](https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/access/Ownable.sol). As such, contract UTXOs are _anyone-can-spend_.

### Execution Model

Smart contracts in the [Ethereum Virtual Machine (EVM)](https://github.com/ethereum/yellowpaper) have three essential features that distinguish them from [Bitcoin scripts](https://en.bitcoin.it/wiki/Script):
1. State elements can define rules under which they can be mutated. This distinction is commonly but imprecisely classified as being able to upload persistent code, but that is simply a means to an end.
1. Users can interact with contracts. This means that Ethereum-style contracts do not have an innate concept of ownership.
1. Contracts can interact with other contracts.

How can we accomplish the above using the UTXO data model instead of the accounts data model?

The first is simple: we can use [covenants](https://fc16.ifca.ai/bitcoin/papers/MES16.pdf) to enforce that contract UTXOs, when spent in a transaction, must create exactly one new UTXO with particular spending conditions; specifically, with the same contract code but an updated state root (depending on the outcome of the transaction). An exception can be made for destroying contracts if that feature is desired.

Users being able to interact with contracts follows naturally from covenants: since contract UTXOs are anyone-can-spend, any user can interact with any number of contracts individually.

Next, contracts must be able to interact with other contracts (and as a result, a user can interact with many contracts simultaneously). This can be done by simply allowing contracts to interact with other contracts whose UTXOs are spent in the same transaction. From another perspective, transactions declare which contracts they will touch (and in the stateful model, additionally which state elements they which touch). This is known as a [_strict access list_](https://github.com/ethereum/EIPs/issues/648).

Finally, we need to discuss how contracts are created and updated. Contract UTXOs can be created using an opcode which assigns a cryptographically unique contract ID deterministically, e.g. similarly to [the Ethereum `CREATE2` opcode](https://eips.ethereum.org/EIPS/eip-1014). As a contract UTXO is spent and re-created, its contract ID remains the same, but its UTXO ID changes and is different each time since the UTXO ID is determined from the outpoint.

### Transaction Format

Transactions are a tuple of:
1. Inputs: uniquely identify which UTXOs are consumed, and provide non-malleable data to unlock coins or interact with contracts.
1. Outputs: define which UTXOs are created.
1. Gas price and gas limit.
1. Witnesses: additional metadata, including digital signatures that authorize the transaction and stateless Merkle branches.

Transactions are uniquely identified only by their inputs and outputs, i.e. signatures are over only the inputs and outputs. Witness data is malleable by the block producer.

The key to enabling multiple uses of the same contract in a single block is that contract UTXOs can be uniquely identified by their contract ID (in addition to their UTXO ID of course), since at most a single contract UTXO with a particular contract ID exists at any time. Therefore, users only need to provide the contract IDs of all contracts their transaction will touch as inputs, _not_ the UTXO IDs. Block proposers provide the appropriate UTXO IDs as part of the witness data for each transaction. Coin UTXOs are spent as usual.

### One Last Thing...

Astute readers will note that in the scheme presented in this post, transactions that only have contract UTXOs as input and perform no operations (i.e. consume no gas) may have the same transaction ID. In order to avoid this, at least one coin UTXO must be spent in a transaction.

_More generally, this rule can be relaxed to only require that at least one input is explicitly specified as a UTXO ID, which may include contract UTXOs. This would enable native [account abstraction](https://eips.ethereum.org/EIPS/eip-2938)._

There are other good reasons to enforce this rule, including DoS protection though a minimum fee level, and enabling [flexible blocksizes in the form of non-proportional dynamic fee burning](https://eips.ethereum.org/EIPS/eip-1559).

## Benefits of UTXOs over Accounts

There are a number of benefits to using UTXOs over accounts, most notably a much higher potential for highly-scalable implementations through parallelism.
1. By defining which contracts will be touched, transactions that touch disjoint sets of contracts can be executed in parallel (even by block-producing nodes). This can be accomplished in the accounts data model with strict access lists.
1. Transactions in the UTXO data model [explicitly define their state transition](https://twitter.com/_prestwich/status/1151740902848622593). Therefore, transactions can be validated in parallel by non-block-producing nodes, _even if they read from or write to the same contracts_. In the scheme presented in this post, block-producing nodes still need to execute transactions with overlapping access lists sequentially.
1. The UTXO data model uses implicit nonces in the form of outpoints, so there is no need to explicitly keep track of the nonces of addresses with zero balance, as is the case in the accounts data model.

## Intuitions

We note that UTXOs do not provide any fundamentally different functionality to accounts, nor do they lack any fundamental functionality. This should come as no surprise, since [they can both be described under a single unified model](https://arxiv.org/abs/1809.09044). The built-in strict access lists provided by the UTXO data model do allow for greater scalability however.

One key intuition is that the underlying data model is orthogonal to the execution model, which may be stateful or stateless, and may allow for contracts to interact with other contracts or may not.

## Conclusion

We present a scheme for general-purpose, Ethereum-style smart contracts with rich state in the UTXO data model. This is accomplished using covenants, and allowing contracts with interact with other contracts that are declared in the same transaction. We note an equivalence between the UTXO data model and the accounts data model with strict access lists.