EIP1087 - Net gas metering for SSTORE operations

# Abstract

This EIP proposes a change to how gas is charged for EVM SSTORE operations, in order to reduce excessive gas costs in situations where these are unwarranted, and to enable new use-cases for contract storage.

# Motivation

Presently, SSTORE (0x55) operations are charged as follows:

20,000 gas to set a slot from 0 to non-0
5,000 gas for any other change
A 10,000 gas refund when a slot is set from non-0 to 0. Refunds are applied at the end of the transaction.

In situations where a single update is made to a storage value in a transaction, these gas costs have been determined to fairly reflect the resources consumed by the operation. However, this results in excessive gas costs for sequences of operations that make multiple updates.

Some examples to illustrate the problem:

If a contract with empty storage sets slot 0 to 1, then back to 0, it will be charged 20000 + 5000 - 10000 = 15000 gas, despite this sequence of operations not requiring any disk writes.
A contract with empty storage that increments slot 0 5 times will be charged 20000 + 5 * 5000 = 45000 gas, despite this sequence of operations requiring no more disk activity than a single write, charged at 20000 gas.
A balance transfer from account A to account B followed by a transfer from B to C, with all accounts having nonzero starting and ending balances, will cost 5000 * 4 = 20000 gas.

Addressing this issue would also enable new use-cases that are currently cost-prohibitive, where a sequence of operations results in no net change to storage at the end of the transaction. For instance, mutexes to prevent reentrancy, or context information passed between multiple calls to the same contract. One such example is an approveAndCall operation, which would permit sending to and calling a contract in a single transaction, without that contract having to be updated for a new token standard.

# Specification

The following changes are made to the EVM:

A 'dirty map' for each transaction is maintained, tracking all storage slots in all contracts that have been modified in the current transaction. The dirty map is scoped in the same manner as updates to storage, meaning that changes to the dirty map in a call that later reverts are not retained.
When a storage slot is written to with the value it already contains, 200 gas is deducted.
When a storage slot's value is changed for the first time, the slot is marked as dirty. If the slot was previously set to 0, 20000 gas is deducted; otherwise, 5000 gas is deducted.
When a storage slot that is already in the dirty map is written to, 200 gas is deducted.
At the end of the transaction, for each slot in the dirty map:
- If the slot was 0 before the transaction and is 0 now, refund 19800 gas.
- If the slot was nonzero before the transaction and its value has not changed, refund 4800 gas.
- If the slot was nonzero before the transaction and is 0 now, refund 15000 gas.

After these changes, transactions that make only a single change to a storage slot will retain their existing costs. However, contracts that make multiple changes will see significantly reduced costs. Repeating the examples from the Motivation section:

If a contract with empty storage sets slot 0 to 1, then back to 0, it will be charged 20000 + 200 - 19800 = 400 gas, down from 15000.
A contract with empty storage that increments slot 0 5 times will be charged 20000 + 5 * 200 = 21000 gas, down from 45000.
A balance transfer from account A to account B followed by a transfer from B to C, with all accounts having nonzero starting and ending balances, will cost 5000 * 3 + 200 - 4800 = 10400 gas, down from 20000.

# Rationale

We believe the proposed mechanism represents the simplest way to reduce storage gas costs in situations where they do not reflect the actual costs borne by nodes. Several alternative designs were considered and dismissed:

Charging a flat 200 gas for SSTORE operations, and an additional 19800 / 4800 at the end of a transaction for new or modified values is simpler, and removes the need for a dirty map, but pushes a significant source of gas consumption out of the EVM stack and applies it at the end of the transaction, which is likely to complicate debugging and reduces contracts' ability to limit the gas consumption of callees, as well as introducing a new mechanism to the EVM.
Keeping a separate refund counter for storage gas refunds would avoid the issue of refunds being limited to half the gas consumed (not necessary here), but would introduce additional complexity in tracking this value.
Refunding gas each time a storage slot is set back to its initial value would introduce a new mechanism (instant refunds) and complicate gas accounting for contracts calling other contracts; it would also permit the possibility of a contract call with negative execution cost.

# Backwards Compatibility

This EIP requires a hard fork to implement.

No contract should see an increase in gas cost for this change, and many will see decreased gas consumption, so no contract-layer backwards compatibility issues are anticipated.

# Test Cases

Writing x to a storage slot that contains 0, where x != 0 (20k gas, no refund)
Writing y to a storage slot that contained x, where x != y and x != 0 (5k gas, no refund)
Writing 0 to a storage slot that contains x, where x != 0 (5k gas, 10k refund)
Writing 0 to a storage slot that already contains zero (200 gas, no refund)
Writing x to a storage slot that already contains x, where x != 0 (200 gas, no refund)
Writing x, then y to a storage slot that contains 0, where x != y (20200 gas, no refund)
Writing x, then y to a storage slot that contains 0, where x != y != z and x != 0 (5200 gas, no refund)
Writing x, then 0 to a storage slot that contains 0, where x != 0 (20200 gas, 19800 refund)
Writing x, then y to a storage slot that contains y, where x != y != 0 (5200 gas, 4800 refund)
Writing x, then 0 to a storage slot that contains 0, then reverting the stack frame in which the writes occurred (20200 gas, no refund)
Writing x, then y to a storage slot that contains y, then reverting the stack frame in which the writes occurred (5200 gas, no refund)
In a nested frame, writing x to a storage slot that contains 0, then returning, and writing 0 to that slot (20200 gas, 19800 refund)

# Implementation

TBD