# Account Abstraction Case Study: UTXOs on Ethereum

The (currently incomplete) implementation of this case study can be found here: [UTXO relayer](https://github.com/quilt/utxo-relayer).

**This case study is built on Quilt's proof of concept implementation of account abstraction, which differs slightly from the EIP.**

## Introduction

To explore the features, limitations, and peculiarities of our [proposed account abstraction approach][eip], Quilt has built an example application on top of our [geth fork][geth].

The system we've chosen is a toy UTXO implementation that supports deposits to and withdrawals from regular Ethereum externally owned accounts (EOAs), and internal transfers within the contract. The Utxo contract itself pays for transactions using its internal balances, so once funds are deposited in the contract, no external gas is required.

[eip]: <!-- TODO -->
[geth]: https://github.com/quilt/go-ethereum/

## Overview

### Limitations

Quilt's implementation of account abstraction has a number of limitations. The relevant limitations to this system are summarized below.

#### Pending Transaction Limit

Only a single pending transaction is kept or propagated by nodes.

This places an upper limit on how many pending transactions can be invalidated by a block, and mitigates some types of denial-of-service attacks. See [this post][block-dos] for a more detailed analysis.

[block-dos]: <!-- TODO -->

#### Traditional Transactions

Traditional transactions, or transactions paid for by an EOA, cannot call into an AA contract.

Without further changes to the transaction format, traditional transactions cannot call into AA contracts without opening the same invalidation denial-of-service vulnerability.

#### External State

Before the `PAYGAS` opcode is invoked, AA contracts are prohibited from accessing any external state. In particular, they cannot call into other contracts.

### Requirements & Features

To consider this a reasonable case study for Quilt-flavored account abstraction, we chose the following (somewhat contrived) set of features to implement:

- Transfers
- Users should be able to divide an amount of funds from up to two inputs into a destination output and a change output.
- Fees for the transfer should be paid by the contract and be deducted from input UTXOs.
- Deposits
- EOAs should be able to deposit funds into the Utxo contract.
- Deposits should be trustless.
- The EOA will pay the gas for the deposit.
- Withdrawals
- Users should be able to withdraw from matching outputs.
- Withdrawals should be trustless.
- Fees for withdrawals should be paid by the contract and be deducted from the input.

## Implementation

### Overall Architecture


This system is split into a pair of on-chain contracts, and an off-chain bundler. The contracts contain the logic implementing UTXO transactions, and the bundler works around the one-pending-transaction limit and provides a command line interface.

#### On-Chain Contracts

The two contracts implementing the on-chain half of the system are [`Utxo.sol`][utxo] which contains the bulk of the implementation, and [`Dropsafe.sol`][dropsafe] which is a utility enabling deposits.

[utxo]: https://github.com/quilt/utxo-relayer/blob/master/contracts/Utxo.sol
[dropsafe]: https://github.com/quilt/utxo-relayer/blob/master/contracts/Dropsafe.sol

##### Dropsafe

Because of the aforementioned restriction preventing traditional transactions from touching abstract accounts, the deposit flow is split into two parts, the first of which is handled by the Dropsafe.

The user initiates a deposit by sending funds to the Dropsafe contract, designating a portion as a bounty. The Dropsafe records the deposit, waiting for a claim to come in the second step.

##### Utxo

The core of the system. This contract implements transfers, withdrawals, the second half of the deposit flow, and the incentive mechanism for bundling.

#### Off-Chain Bundler

The off-chain bundler application subscribes to a number of events exposed by the JSON-RPC interface to monitor the blockchain for relevant events, like new deposits, new bundles, and newly mined transactions.

End users can create new transactions using the bundler's command line interface. New transactions are either appended to an existing bundle, or broadcast alone depending on the bundle's gas price and the contracts fee base.

### Selected Implementation Details

#### Deposit Flow

A transaction from an EOA to the Dropsafe contract initiates the deposit flow. The Dropsafe emits a `NewDeposit` event and records the following information. Each `Deposit` is assigned a unique `uint256` identifier.

struct Deposit {
    // Portion of the deposit belonging to the owner.
    uint256 amount;
    
    // Portion of the deposit set aside as a reward for the claimant.
    uint256 bounty;
    
    // Address of the EOA owning the deposit.
    address owner;
}

Upon receiving the `NewDeposit` event, the bundler application records the `Deposit`. Whenever the bundler constructs a new bundle, it will claim any deposits whose bounties will be profitable at the bundle's expected gas price.

When a bundle with claims arrives at the Utxo contract, each claim's unique identifier is checked against a bitfield, ensuring that each deposit can only be claimed once. A bundle with an already claimed deposit is reverted before `PAYGAS`, removing any risk to a well-behaved claimant.

Once all other transactions in the bundle are validated, the Utxo contract calls `PAYGAS`, calls out to the Dropsafe's `claim` method to collect the deposits, and creates new UTXOs.

#### Bundle Construction

The bundler maintains a pool of UTXO transactions created by the end user, and further populated by subscribing to [`eth_newPendingTransactionFilter`][filter] and `NewDeposit` events from the Dropsafe. Transactions in the pool that conflict with bundles from newly mined blocks (provided by [`eth_newBlockFilter`][blocks]) are removed.

When the contents of the pool change, the bundler attempts to assemble a new bundle by first including the transfer or withdrawal with the highest gas price, and then including deposits profitable at that price. The bundler repeats the selection as long as adding the next transaction increases the bundle's offered gas price and there is room in the bundle.

[filter]: https://eth.wiki/json-rpc/API#eth_newpendingtransactionfilter
[blocks]: https://eth.wiki/json-rpc/API#eth_newblockfilter

#### Bundle Incentives

To promote the creation and propagation of bundles, and conversely to discourage single high paying transactions from consuming the full bandwidth of the Utxo contract, the system has a mechanism to incentivize participants to bundle transactions.

Each bundle is divided into a constant number of "slots". When added to a bundle, each type of transaction (claim, transfer, withdrawal) consumes a number of slots depending on their relative gas cost.

The Utxo contract maintains a value, `fee_base`, that is set to `gasprice * 0.8` whenever a bundle is successfully mined, where `gasprice` was the argument to `PAYGAS`.

The gas price for an entire bundle is calculated as follows:

1. Set `min_gasprice` to the minimum gas price of all transactions in the bundle.
2. Check if `min_gasprice <= fee_base`:
a. If true, set `bundle_gasprice = min_gasprice`
b. Otherwise, set `bundle_gasprice = (min_gasprice - fee_base) * (USED_SLOTS/MAX_SLOTS) + fee_base`

While this simple model is very likely flawed and hasn't been subjected to rigorous analysis, it does display useful properties:

- Fuller bundles generally pay more than less full bundles.
- If the main chain gas price falls below the last bundle gas price, new transactions are not required to overpay, though bundles might be less full, reducing throughput for one block.
- If the main chain gas price rises significantly since the last bundle, a single transaction can still force its way onto the chain by offering a significantly higher gas price, but would only actually pay a fraction of that.

## Lessons Learned

### Deposits

Deposits, as implemented, are functional but extremely inconvenient. They require an active second party with funds already in the Utxo contract who is actively running the bundler software.

Lifting the limitation and allowing traditional transactions to call into AA contracts would simplify deposits, and remove the requirement for a second party.

If EOA-initiated transactions included an account access list (i.e a pre-calculated list of accounts called by the transaction), the EOA-initiated transactions could be subjected to the same rules as AA transactions, mitigating denial-of-service or mass invalidation attacks in the same way. This approach alone does not allow multiple transactions to the same AA contract per block.

### Bundling & Multiple Transactions per Block

Bundling is a less than ideal solution. It requires off-chain software, complex incentives, and still does not optimize gas price relative to non-bundled transactions.

While the mechanism proposed seems to have the correct incentives to promote bundling, it is non-trivial and requires rigorous analysis before production use. It is unlikely that the deposit bounties provide sufficient incentive to even run the bundler software. On the other hand, the gas price system used by traditional transactions (highest fee first) is simple and battle tested. If multiple pending transactions per AA contract were allowed to propagate, AA transactions could use the same fee structure as traditional transactions. There are some similarities between the bundler and rollup operator software.

Instead of propagating a single transaction per AA contract, nodes could propagate any number of transactions up to a configurable validation gas limit.

### Gas Observability

The recent direction of Ethereum research has pushed for reducing the observability of gas by smart contracts (ex. [oil][oil]). This direction, however, is detrimental to the usability of AA contracts. Aside from smart contract wallets, most use cases depend on recording or predicting exactly how much gas a transaction will use, to deduct that amount from an internal account.

Some additional exploration into mitigating the impact of instruction repricing while maintaining gas observability for meta-transactions is warranted.

[oil]: https://ethresear.ch/t/oil-adding-a-second-fuel-source-to-the-evm-pre-eip-v1-1/7425

### Implementation Difficulties

Creating a command line application with out-of-band notifications is non-trivial. There are some issues getting input in the current prototype.

[ethersrs]: https://github.com/gakonst/ethers-rs