On EIP 86 and EIP 648: account abstraction, DoS vectors, and parallelizability

[cdetrio]

One of the outstanding questions about EIP 86 (and earlier, EIP 101) is how miners can safely process NULL SENDER transactions (i.e. transactions sent from abstracted accounts) without opening up DoS attack vectors.[1,2,3] One possible answer, outlined in EIP 86, is the idea that miners employ a strategy of only processing NULL SENDER transactions to whitelisted "forwarding contracts", where only contracts that are known to be safe against DoS attacks, perhaps by static analysis or some other method, would be added to the whitelist.

In another proposal, EIP 648 (and earlier, EIP 105) defines transactions that specify activity ranges. This was proposed a means to parallelize transaction processing. But requiring transactions to restrict their activity ranges also provides a different solution to the outstanding EIP 86 miner strategy question.

To see how the parallelization in (EIP 105 / EIP 648) solves the miner strategy question of (EIP 101 / EIP 86), first let's look at how the DoS attack vector works and consider why traditional transactions, i.e. transactions that originate from non-contract accounts or Externally Owned Accounts (EOAs), are safe for miners to process.

The DoS vector works by overloading the pending pool with transactions that are valid when initially received by miners, but then later become invalid, so that a miner wastes resources attempting to include them in a pending block. When attacked, a miner could spend the entire block period (15 seconds on average) attempting to include invalid pending transactions. By the time the pending block is found, few or no valid transactions have been included.

So what makes it safe for miners to include traditional transactions? The key property, I think, is that when a pending transaction is valid (i.e. the sending account has a balance, and the tx is signed with the correct nonce; these two properties ensure that the miner will earn a gas fee), then it can be expected to remain valid. When new pending transactions arrive, or when a new block arrives, this expectation of validity may change for some of the transactions (i.e. other transactions from the same sending account), but the majority of pending transactions remain valid.

For example, take a sequence of nine pending transactions sent from a single account, with nonces 0x1 through 0x9. Now suppose the account sends a new pending tx, with duplicate nonce 0x2, that spends all remaining balance. Then the tx's with nonces 0x3 through 0x9 will become invalid and can be evicted from the pending pool. But all other tx's (i.e. those from other sending accounts) remain valid.

In contrast, with EIP 86 (NULL SENDER) transactions the ability for an account to pay the gas fee depends on not just a subset of the pending transactions, but on all pending transactions, since any pending transaction may affect the gas-paying account. This is the root issue which prevents miners from safely processing NULL SENDER transactions to generic (non-whitelisted) contracts. Attempting to censor traditional transactions by blacklisting a set of contract addresses or code hashes is also a DoS vector, for the same reason.[4]

With EIP 648, transactions specify an "activity range" of account addresses, which restricts the accounts a transaction can affect.[5,6] This restriction allows miners to safely include pending transactions with sets of disjoint (non-overlapping) ranges, since a new pending transaction with one activity range cannot affect the validity of pending transactions with other activity ranges. When activity ranges are not entirely disjoint but overlapping at some addresses, they form a dependency graph or "serialization graph". When a new block arrives and miners need to construct a new pending block, they check this dependency graph. Only those pending transactions with dependent activity ranges need to be reprocessed to check if they are still valid. All non-overlapping pending transactions are independent and remain valid, satisfying the key safety property.

Taking a dependency graph view of the traditional pending transaction pool, we can see that the reason traditional transactions are not a DoS vector (so long as the miner only cares that they earn gas fees, and does not attempt to censor which contracts the tx interacts with) is that transactions from different accounts are non-overlapping in the dependency graph. A sequence of pending transactions with increasing nonces from the same account forms a "dependency chain" that is independent of transactions from all other accounts; this is why they are safe for miners to process.

In summary, with (EIP 648 / EIP 105) miners know the activity ranges of all transactions. With this knowledge they can analyze the dependency graph of the pending pool, and this allows them to safely process (EIP 86 / EIP 101) transactions from abstracted accounts.

1. Proposed initial abstraction changes for Metropolis #86 - Proposed initial abstraction changes for Metropolis (EIP 86 issue)
2. Abstraction of transaction origin and signature.md #208 - Abstraction of transaction origin and signature (EIP 86 pull request)
3. https://github.com/ethereum/EIPs/blob/master/EIPS/eip-101.md - Serenity Currency and Crypto Abstraction
4. http://hackingdistributed.com/2016/06/28/ethereum-soft-fork-dos-vector/ - Ethereum's DAO Wars Soft Fork is a Potential DoS Vector
5. EIP 105 (Serenity): Binary sharding plus contract calling semantics #53 - EIP 105 (Serenity): Binary sharding plus contract calling semantics
6. Easy parallelizability #648 - Easy parallelizability

[cdetrio]

Discussion of account abstraction proposals has continued here https://ethresear.ch/t/tradeoffs-in-account-abstraction-proposals/263

[github-actions]

There has been no activity on this issue for two months. It will be closed in a week if no further activity occurs. If you would like to move this EIP forward, please respond to any outstanding feedback or add a comment indicating that you have addressed all required feedback and are ready for a review.

[github-actions]

This issue was closed due to inactivity. If you are still pursuing it, feel free to reopen it and respond to any feedback or request a review in a comment.