EIP2583 - Penalty for account trie misses

# Simple Summary

This EIP introduces a gas penalty for opcodes which access the account for trie non-existent accounts.

# Abstract

This EIP adds a gas penalty for accesses to the account trie, where the address being looked up does not exist. Non-existing accounts can be used in DoS attacks, since they bypass cache mechanisms, thus creating a large discrepancy between 'normal' mode of execution and 'worst-case' execution of an opcode.

# Motivation

As the ethereum trie becomes more and more saturated, the number of disk lookups that a node is required to do in order to access a piece of state increases too. This means that checking e.g. EXTCODEHASH of an account at block 5 was inherently a cheaper operation that it is at, say 8.5M.

From an implementation perspective, a node can (and does) use various caching mechanisms to cope with the problem, but there's an inherent problem with caches: when they yield a 'hit', they're great, but when they 'miss', they're useless.

This is attackable. By forcing a node to lookup non-existent keys, an attacker can maximize the number of disk lookups. Sidenote: even if the 'non-existence' is cached, it's trivial to use a new non-existent key the next time, and never hit the same non-existent key again. Thus, caching 'non-existence' might be dangerous, since it will evict 'good' entries.

So far, the attempts to handle this problem has been in raising the gas cost, e.g. EIP-150, EIP-1884.

However, when determining gas-costs, a secondary problem that arises due to the large discrepancy between 'happy-path' and 'notorious path' -- how do we determine the pricing?

The 'happy-path', assuming all items are cached?
- Doing so would that would underprice all trie-accesses, and could be DoS-attacked.
The 'normal' usage, based on benchmarks of actual usage?
- This is basically what we do now, but that means that intentionally notorious executions are underpriced -- which constitutes a DoS vulnerability.
The 'paranoid' case: price everything as if caching did not exist?
- This would severely harm basically every contract due to the gas-cost increase. Also, if the gas limits were raised in order to allow the same amount of computation as before, the notorious case could again be used for DoS attacks.

From an engineering point of view, a node implementor is left with few options:

Implement bloom filters for existence. This is difficult, not least because of the problems of reorgs, and the fact that it's difficult to undo bloom filter modifications.
Implement flattened account databases. This is also difficult, both because of reorgs and also because it needs to be an additional data structure aside from the trie -- we need the trie for consensus. So it's an extra data structure of around 15G that needs to be kept in check. This is currently being pursued by the Geth-team.

This EIP proposes a mechanism to alleviate the situation.

# Specification

We define the constant penalty as TBD (suggested 2000 gas).

For opcodes which access the account trie, whenever the operation is invoked targeting an address which does not exist in the trie, then penalty gas is deducted from the available gas.

# Detailed specification

These are the opcodes which triggers lookup into the main account trie:

Opcode	Affected	Comment
BALANCE	Yes	`balance(nonexistent_addr)` would incur `penalty`
EXTCODEHASH	Yes	`extcodehash(nonexistent_addr)` would incur `penalty`
EXTCODECOPY	Yes	`extcodecopy(nonexistent_addr)` would incur `penalty`
EXTCODESIZE	Yes	`extcodesize(nonexistent_addr)` would incur `penalty`
CALL	Yes	See details below about call variants
CALLCODE	Yes	See details below about call variants
DELEGATECALL	Yes	See details below about call variants
STATICCALL	Yes	See details below about call variants
SELFDESTRUCT	No	See details below.
CREATE	No	Create destination not explicitly settable, and assumed to be nonexistent already.
CREATE2	No	Create destination not explicitly settable, and assumed to be nonexistent already.

# Notes on Call-derivatives

A CALL triggers a lookup of the CALL destination address. The base cost for CALL is at 700 gas. A few other characteristics determine the actual gas cost of a call:

If the CALL (or CALLCODE) transfers value, an additional 9K is added as cost. 1.1 If the CALL destination did not previously exist, an additional 25K gas is added to the cost.

This EIP adds a second rule in the following way:

If the call does not transfer value and the callee does not exist, then penalty gas is added to the cost.

In the table below,

value means non-zero value transfer,
!value means zero value transfer,
dest means destination already exists, or is a precompile
!dest means destination does not exist and is not a precompile

Op	value,dest	value, !dest	!value, dest	!value, !dest
CALL	no change	no change	no change	`penalty`
CALLCODE	no change	no change	no change	`penalty`
DELEGATECALL	N/A	N/A	no change	`penalty`
STATICCALL	N/A	N/A	no change	`penalty`

Whether the rules of this EIP is to be applied for regular ether-sends in transactions is TBD. See the 'Backwards Compatibility'-section for some more discussion on that topic.

# Note on `SELFDESTRUCT`

The SELFDESTRUCT opcode also triggers an account trie lookup of the beneficiary. However, due to the following reasons, it has been omitted from having a penalty since it already costs 5K gas.

# Clarifications:

The base costs of any opcodes are not modified by the EIP.
The opcode SELFBALANCE is not modified by this EIP, regardless of whether the self address exists or not.

# Rationale

With this scheme, we could continue to price these operations based on the 'normal' usage, but gain protection from attacks that try to maximize disk lookups/cache misses. This EIP does not modify anything regarding storage trie accesses, which might be relevant for a future EIP. However, there are a few crucial differences.

Storage tries are typically small, and there's a high cost to populate a storage trie with sufficient density for it to be in the same league as the account trie.
If an attacker wants to use an existing large storage trie, e.g. some popular token, he would typically have to make a CALL to cause a lookup in that token -- something like token.balanceOf(<nonexistent-address>). That adds quite a lot of extra gas-impediments, as each CALL is another 700 gas, plus gas for arguments to the CALL.

# Determining the `penalty`

A transaction with 10M gas can today cause ~14K trie lookups.

A penalty of 1000would lower the number to ~5800 lookups, 41% of the original.
A penalty of 2000would lower the number to ~3700 lookups, 26% of the original.
A penalty of 3000would lower the number to ~2700 lookups, 20% of the original.
A penalty of 4000would lower the number to ~2100 lookups, 15% of the original.

There exists a roofing function for the penalty. Since the penalty is deducted from gas, that means that a malicious contract can always invoke a malicious relay to perform the trie lookup. Let's refer to this as the 'shielded relay' attack.

In such a scenario, the malicious would spend ~750 gas each call to relay, and would need to provide the relay with at least 700 gas to do a trie access.

Thus, the effective cost would be on the order of 1500. It can thus be argued that penalty above ~800 would not achieve better protection against trie-miss attacks.

# Backwards Compatibility

This EIP requires a hard-fork.

# Ether transfers

A regular transaction from one EOA to another, with value, is not affected.

A transaction with 0 value, to a destination which does not exist, would be. This scenario is highly unlikely to matter, since such a transaction is useless -- even during success, all it would accomplish would be to spend some gas. With this EIP, it would potentially spend some more gas.

# Layer 2

Regarding layer-2 backward compatibility, this EIP is a lot less disruptive than EIPs which modify the base cost of an opcode. For state accesses, there are seldom legitimate scenarios where

A contract checks BALANCE/EXTCODEHASH/EXTCODECOPY/EXTCODESIZE of another contract b, and,
If such b does not exist, continues the execution

# Solidity remote calls

Example: When a remote call is made in Solidity:

    recipient.invokeMethod(1)

Solidity does a pre-flight EXTCODESIZE on recipient.
If the pre-flight check returns 0, then revert(0,0) is executed, to stop the execution.
If the pre-flight check returns non-zero, then the execution continues and the CALL is made.

With this EIP in place, the 'happy-path' would work as previously, and the 'notorious'-path where recipient does not exist would cost an extra penalty gas, but the actual execution-flow would be unchanged.

# ERC223

ERC223 Token Standard (opens new window) is, at the time of writing, marked as 'Draft', but is deployed and in use on mainnet today.

The ERC specifies that when a token transfer(_to,...) method is invoked, then:

This function must transfer tokens and invoke the function tokenFallback (address, uint256, bytes) in _to, if _to is a contract. ... NOTE: The recommended way to check whether the _to is a contract or an address is to assemble the code of _to. If there is no code in _to, then this is an externally owned address, otherwise it's a contract.

The reference implementations from Dexaran (opens new window) and OpenZeppelin (opens new window) both implement the isContract check using an EXTCODESIZE invocation.

This scenario could be affected, but in practice should not be. Let's consider the possibilities:

The _to is a contract: Then ERC223 specifies that the function tokenFallback(...) is invoked.
- The gas expenditure for that call is at least700 gas.
- In order for the callee to be able to perform any action, best practice it to ensure that it has at least 2300 gas along with the call.
- In summary: this path requires there to be least 3000 extra gas available (which is not due to any penalty)
The _to exists, but is no contract. The flow exits here, and is not affected by this EIP
The _to does not exist: A penalty is deducted.

In summary, it would seem that ERC223 should not be affected, as long as the penalty does not go above around 3000 gas.

# Other

The contract Dentacoin (opens new window) would be affected.

    function transfer(address _to, uint256 _value) returns (bool success) {
    ... // omitted for brevity
        if (balances[msg.sender] >= _value && balances[_to] + _value > balances[_to]) {               // Check if sender has enough and for overflows
            balances[msg.sender] = safeSub(balances[msg.sender], _value);   // Subtract DCN from the sender

            if (msg.sender.balance >= minBalanceForAccounts && _to.balance >= minBalanceForAccounts) {    // Check if sender can pay gas and if recipient could
                balances[_to] = safeAdd(balances[_to], _value);             // Add the same amount of DCN to the recipient
                Transfer(msg.sender, _to, _value);                          // Notify anyone listening that this transfer took place
                return true;
            } else {
                balances[this] = safeAdd(balances[this], DCNForGas);        // Pay DCNForGas to the contract
                balances[_to] = safeAdd(balances[_to], safeSub(_value, DCNForGas));  // Recipient balance -DCNForGas
                Transfer(msg.sender, _to, safeSub(_value, DCNForGas));      // Notify anyone listening that this transfer took place

                if(msg.sender.balance < minBalanceForAccounts) {
                    if(!msg.sender.send(gasForDCN)) throw;                  // Send eth to sender
                  }
                if(_to.balance < minBalanceForAccounts) {
                    if(!_to.send(gasForDCN)) throw;                         // Send eth to recipient
                }
            }
        } else { throw; }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

The contract checks _to.balance >= minBalanceForAccounts, and if the balance is too low, some DCN is converted to ether and sent to the _to. This is a mechanism to ease on-boarding, whereby a new user who has received some DCN can immediately create a transaction.

Before this EIP:

When sending DCN to a non-existing address, the additional gas expenditure would be:
- 9000 for an ether-transfer
- 25000 for a new account-creation
- (2300 would be refunded to the caller later)
- A total runtime gas-cost of 34K gas would be required to handle this case.

After this EIP:

In addition to the 34K an additional penalty would be added.
- Possibly two, since the reference implementation does the balance-check twice, but it's unclear whether the compiled code would indeed perform the check twice.
A total runtime gas-cost of 34K+penalty (or 34K + 2 * penalty) would be required to handle this case.

It can be argued that the extra penalty of 2-3K gas can be considered marginal in relation to the other 34K gas already required to handle this.

# Test Cases

The following cases need to be considered and tested:

That during creation of a brand new contract, within the constructor, the penalty should not be applied for calls concerning the self-address.
TBD: How the penalty is applied in the case of a contract which has performed a selfdestruct
- a) previously in the same call-context,
- b) previously in the same transaction,
- c) previously in the same block, For any variant of EXTCODEHASH(destructed), CALL(destructed), CALLCODE(destructed) etc.
The effects on a transaction with 0 value going to a non-existent account.

# Security Considerations

See 'Backwards Compatibility'

# Implementation

Not yet available.

# Alternative variants

# Alt 1: Insta-refunds

Bump all trie accesses with penalty. EXTCODEHASH becomes 2700 instead of 700.

If a trie access hit an existing item, immediately refund penalty (2K )

Upside:

This eliminates the 'shielded relay' attack

Downside:

This increases the up-front cost of many ops (CALL/EXTCODEHASH/EXTCODESIZE/STATICCALL/EXTCODESIZE etc)
- Which may break many contracts.

# Alt 2: Parent bail

Use penalty as described, but if a child context goes OOG on the penalty, then the remainder is subtracted from the parent context (recursively).