EIP-7557: Block-level Warming with fair cost savings

Block-level warming of addresses and slots with access lists

Abstract

A mechanism for a fair distribution of the gas costs associated with access to addresses and storage slots among multiple transactions with shared items in their accessList.

Motivation

EIP-2929: Gas cost increases for state access opcodes introduced a new gas cost model that differentiates between “cold” and “warm” access to accounts and storage slots.

However, the cost of every cold access is borne by each transaction separately, even though the validator only needs to fetch the state object once for the entire block.

When multiple transactions access the same state object in the same block the fees charged for these transactions do not accurately reflect the computations that block builders and validators perform for the blockchain state access during transaction execution.

EIP-2930: Optional access lists made it possible for transactions to pre-specify and pre-pay for the accounts and storage slots that the transaction plans to access, however, the cost is still paid repeatedly by each transaction rather than once at the block level.

With the EIP-6800: Ethereum state using a unified verkle tree on the roadmap for inclusion, the cost of reading from the Ethereum state and especially the contract code is expected to increase.

Especially affected by this upcoming change will be transactions that involve smart contracts with a high code size.

Each such transaction in the block will be forced to pay the full “retail” price for loading smart contract bytecode during a transaction.

The validators, however, only have to perform the actual reading from the Ethereum state once per block, and all subsequent reads of the values that were already referenced are significantly more efficient.

If witnesses are introduced to Ethereum blocks, the same witness can be reused by multiple transactions. Requiring each transaction to pay regardless of the contents of the block is unfair and inefficient.

Another change that may be on the roadmap for Ethereum is Account Abstraction. This change will see a large share of transactions being initiated by smart contracts directly. It is reasonable to expect many of these Smart Contract Accounts to rely on the same core wallet implementations. If each Account Abstraction transaction is charged a full gas cost of loading the Smart Contract Account code repeatedly, such transactions would become significantly overpriced.

This difference is especially noticeable when compared to an EOA, which gets its validation logic loaded and executed for free.

In this scenario, the base gas fees would be taken from the senders and burned needlessly while block proposers would be enjoying an unjustified excessive earning of priority gas fees.

A major distinction between this proposal and alternatives, such as EIP-7863, lies in performing a fair distribution of gas savings between all participants - all transactions senders and the block builder.

Specification

The EIP-2930: Optional access lists already introduced the first part of the solution. Each transaction can specify an array of accessed_addresses and accessed_storage_keys to announce its intention to read those values during the execution of the transaction.

The sender of the transaction is then pre-charged with the cost of accessing this data but is given a small discount compared to unannounced access.

The missing component is a mechanism to aggregate the gas costs of the cold access and redistribute the resulting savings amongst the participating transactions.

Overview

During the transaction execution, the cost of all storage-related operations is not affected, and all rules from EIP-2929 and EIP-2930 continue to apply.

There are no changes to the block header or the transaction payload and receipt.

As the last operation of each block, the collected gas costs associated with storage access are redistributed among the senders of all transactions withing a block. This affects the balances of all these accounts in a way that only becomes observable in the next block.

This reimbursement’s amount is proportional to the amount paid for the access in the first place.

Participant transactions mapping

After the block builder finalizes the contents of the block, it iterates over all included transactions to read the accessList component of each supported transaction.

The block builder then constructs an array containing each accessed address and each accessed slot, and an array of transaction senders’ addresses that initiated at least one access to the given address or slot, as well as the priorityFeePerGas that was paid for such access.

A sample JSON representation of the data structure that represents such a structure and is used in the pseudocode below:

[
  {
    "address": "0xde0b295669a9fd93d5f28d9ec85e40f4cb697bae",
    "accessors": [
      {
        "sender": "0x90F8bf6A479f320ead074411a4B0e7944Ea8c9C1",
        "priorityFeePerGas": "1000"
      },
      {
        "sender": "0x90F8bf6A479f320ead074411a4B0e7944Ea8c9C1",
        "priorityFeePerGas": "2000"
      },
      {
        "sender": "0xFFcf8FDEE72ac11b5c542428B35EEF5769C409f0",
        "priorityFeePerGas": "1000"
      },
      {
        "sender": "0xFFcf8FDEE72ac11b5c542428B35EEF5769C409f0",
        "priorityFeePerGas": "2000"
      },
      {
        "sender": "0x22d491Bde2303f2f43325b2108D26f1eAbA1e32b",
        "priorityFeePerGas": "2000"
      },
      {
        "sender": "0x22d491Bde2303f2f43325b2108D26f1eAbA1e32b",
        "priorityFeePerGas": "3000"
      }
    ],
    "slots": [
      {
        "id": "0x0000000000000000000000000000000000000000000000000000000000000003",
        "accessors": [
          {
            "sender": "0x90F8bf6A479f320ead074411a4B0e7944Ea8c9C1",
            "priorityFeePerGas": "1000"
          },
          {
            "sender": "0x90F8bf6A479f320ead074411a4B0e7944Ea8c9C1",
            "priorityFeePerGas": "2000"
          },
          {
            "sender": "0x22d491Bde2303f2f43325b2108D26f1eAbA1e32b",
            "priorityFeePerGas": "2000"
          },
          {
            "sender": "0x22d491Bde2303f2f43325b2108D26f1eAbA1e32b",
            "priorityFeePerGas": "3000"
          }
        ]
      },
      {
        "id": "0x0000000000000000000000000000000000000000000000000000000000000007",
        "accessors": [
          {
            "sender": "0xFFcf8FDEE72ac11b5c542428B35EEF5769C409f0",
            "priorityFeePerGas": "1000"
          },
          {
            "sender": "0xFFcf8FDEE72ac11b5c542428B35EEF5769C409f0",
            "priorityFeePerGas": "2000"
          }
        ]
      }
    ]
  }
]

Calculating a reimbursement of the burned base fee

Considering that the same amount of computation is needed to access an address or a slot regardless of the number of transactions using one, it is reasonable for the protocol to only burn the gas cost of the cold access once. As all transactions in the same block pay exactly the same baseFeePerGas, the single cost of accessing a cold item is divided evenly among all transactions containing such access and the rest of the burned base fee is reimbursed.

Setting an absolute minimal cost of cold state access

If a large number of transactions all access the same addresses or slots, the cost of each cold access may get way too low which may represent a potential DoS attack vector.

In order to prevent that, the gas cost of including an entity in the access list cannot be lower than MIN_ACCESS_LIST_ENTRY_COST, which is set to 32 gas.

This value is equivalent to the calldata cost of including two bytes long identifier of entries in block_access_list.

Calculating a reimbursement of the charged priority fee

Each transaction pays an individual priorityFeePerGas value and redistributing this part of the cold access cost is more complex.

We propose the following approach to a fair reimbursement of the paid priorityFee:

1. The validator gets paid the priorityFee for each cold access only once, but according to the highest priorityFee among the transactions containing the said cold access.
2. The rest of the Ether that was charged by the validator as a priorityFee is redistributed back to all the senders of transactions containing the same cold access in proportion to their marginal contribution to the total gains of the transaction.
3. The block builder is only paid for access once and the remaining value is reimbursed. So the total reimbursement value is a difference between the sum of value charged and the block builder’s reward.
4. The total gains of the transaction is defined by a sum of the priorityFee paid out to the block builder and total reimbursement made to all participants.

5. Mathematically, the marginal contribution of a transaction to the total gains is defined as the difference between the sum total gains value calculated when all transactions in a block are included, and when all transactions are included except for this particular transaction. In practice this value always amounts to priorityFee * gasCost.

   𝑀𝐶𝑖 = 𝑣(𝑆 ∪ {𝑖}) − 𝑣(𝑆)

A single transaction accessing an address or a slot that is not shared by other transactions does not trigger a reimbursement, and therefore has a zero marginal contribution.

Efficiently storing the access lists in the block history

The contents of the accessList parameter are part of the Ethereum history and the potential cost of keeping this data in the blockchain must be accounted for when implementing this change. There is currently no additional charge applied to the accessList parameter, due to the cost of including an address or a storage slot in the accessList being a constant value that is significantly higher than the potential cost of storing the accessList at the cost of a dynamically sized calldata field.

With the block-level warming there is a change that makes it possible for a transaction sender to construct transactions with a large accessList that cost very little to be included, and this can be used to bloat the blockchain size.

This potential bloating of the block size also presents a challenge for the propagation of the block in a P2P network.

In order to minimize the cost of permanently storing access lists, we propose the following changes to the execution_payload structure:

1. Add a new block_access_list field.

The execution clients create a combined block-level “access list” that contains all unique entries from all transactions in the block.

1. All individual transaction accessList fields replace the full entries with a compact 2 bytes long reference to the block_access_list in the same order they appeared originally.

With this approach shared entries in the access lists cannot cause sufficient bloating of the block size.

There is no need to introduce any observable changes to the RPC API as this “compression” can be unwrapped by the clients in real time.

Pseudocode implementation of the reimbursement calculation algorithm

export function calculateBlockColdAccessReimbursement (
  baseFeePerGas: string,
  accessDetailsMap: AddressAccessDetails[]
): Map<string, reimbursement> {
  const reimbursements = new Map<string, Reimbursement>()
  for (const accessDetail of accessDetailsMap) {
    calculateItemColdAccessReimbursement(accessDetail.accessors, baseFeePerGas, COLD_ACCOUNT_ACCESS_COST, reimbursements)
    for (const slot of accessDetail.slots) {
      calculateItemColdAccessReimbursement(slot.accessors, baseFeePerGas, COLD_SLOAD_COST, reimbursements)
    }
  }
  return reimbursements
}

function calculateItemColdAccessReimbursement (
  unsortedAccessors: AccessDetails[],
  baseFeePerGas: string,
  accessGasCost: string,
  reimbursements: Map<string, Reimbursement>
): void {
  const sortedAccessDetails = unsortedAccessors.sort((a, b) => { return parseInt(b.priorityFeePerGas) - parseInt(a.priorityFeePerGas) })
  const addressAccessN = sortedAccessDetails.length
  const reimbursementPercent = (addressAccessN - 1) / addressAccessN
  const reimbursementsFromCoinbase = calculatePriorityFeeReimbursements(sortedAccessDetails, accessGasCost)
  for (let i = 0; i < sortedAccessDetails.length; i++) {
    const accessor = sortedAccessDetails[i]
    const reimbursement = reimbursements.get(accessor.sender) ?? { reimbursementFromBurn: 0n, reimbursementFromCoinbase: 0n }
    const adjustedAccessGasCost = Math.max(MIN_ACCESS_LIST_ENTRY_COST, parseInt(accessGasCost) * reimbursementPercent)
    reimbursement.reimbursementFromBurn += BigInt(adjustedAccessGasCost * parseInt(baseFeePerGas))
    reimbursement.reimbursementFromCoinbase += BigInt(reimbursementsFromCoinbase[i])
    reimbursements.set(accessor.sender, reimbursement)
  }
}

export function calculatePriorityFeeReimbursements (sortedAccesses: AccessDetails[], accessGasCost: string) {
  // Validator charge is based on the highest paid priority fee per gas
  const validatorFee = parseInt(sortedAccesses[0].priorityFeePerGas) * parseInt(accessGasCost)

  // Accumulate the sum of all "contributions", at least the top transaction contribution
  let totalContributions = validatorFee
  // Accumulate cost of gas paid to validator for accessing the same address/slot/chunk
  let totalSendersCharged = parseInt(sortedAccesses[0].priorityFeePerGas) * parseInt(accessGasCost)
  // Starting with `1` as element at `0` is explicitly shown here to be used as `validatorFee`
  for (let i = 1; i < sortedAccesses.length; i++) {
    const charge = parseInt(sortedAccesses[i].priorityFeePerGas) * parseInt(accessGasCost)
    totalContributions += charge
    totalSendersCharged += charge
  }

  // Calculate the total amount of ether to be reimbursed for this access
  const totalReimbursement = totalSendersCharged - validatorFee
  if (totalReimbursement == 0) {
    // possible if only single transaction or if all priority fees are 0
    return Array(sortedAccesses.length).fill(0)
  }

  // Calculate actual charges and reimbursements
  const reimbursements = [Math.floor(totalReimbursement * topTransactionContribution / totalContributions)]
  for (let i = 1; i < sortedAccesses.length; i++) {
    const charge = parseInt(sortedAccesses[i].priorityFeePerGas) * parseInt(accessGasCost)
    const calldataCharge = parseInt(sortedAccesses[i].priorityFeePerGas) * MIN_ACCESS_LIST_ENTRY_COST
    const reimbursementToCalldata = charge - calldataCharge
    const reimbursementToContribution = Math.floor(totalReimbursement * charge / totalContributions)
    reimbursements.push(Math.min(reimbursementToCalldata, reimbursementToContribution))
  }
  return reimbursements
}

Note that two accumulating values, reimbursementFromBurn and reimbursementFromCoinbase, are necessary in light of EIP-1559: Fee market change for ETH 1.0 chain in order to differentiate between the Ether reimbursement that is originating from a reduced block gas burn, and from the reduced block proposer priority fee per gas reward.

Future EIP-6800 gas reform support

Once EIP-6800 is active, the cost of accessing a contract code for a cold address is expected to change.

Instead of being a constant value of COLD_ACCOUNT_ACCESS_COST (currently 2600 gas), the total cost will be determined by the number of 31-byte “chunks” the code consists of. Each “chunk” of code will have a cost of CODE_CHUNK_ACCESS_COST (currently 200 gas).

For a maximum contract size of 24576 bytes defined by EIP-170 the cost of accessing this contract surges from 2600 to 158600 gas.

This change will likely require the accessList parameter of transactions to be adjusted for transactions to be able to specify which code chunks will be accessed.

In such case the changes are reflected in the reimbursement function as well, which is updated by adding the following code in order to redistribute the shared cost of accessing the same code chunk in multiple transactions:

const reimbursementsFromCoinbase = calculatePriorityFeeReimbursements(sortedCodeChunkAccessDetails, CHUNK_ACCESS_COST)
for (let i = 0; i < sortedAccessDetails.length; i++) {
  const reimbursement = reimbursements.get(accessor.sender)
  reimbursement.reimbursementFromBurn += CHUNK_ACCESS_COST * block.baseFeePerGas * reimbursementPercent
  reimbursement.reimbursementFromCoinbase += reimbursementsFromCoinbase[i]
}

Cost redistribution system operation

The EIP-4895: Beacon chain push withdrawals as operations sets a precedent by introducing a concept of a system-level withdrawal operation.

We propose the introduction of yet another system-level operation called cost redistribution. The redistributions in an execution payload are processed after any user-level transactions are applied.

The block builder or a validator prepares a list of reimbursement information.

For each redistribution in the list, the implementation increases the balance of the address specified by the amount reimbursementFromBurn + reimbursementFromCoinbase.

The balance of the coinbase is reduced by a sum of all reimbursementFromCoinbase values.

Rationale

Current cold storage gas cost is unfair

As described in the Motivation section, the amount of gas that users spend on accessing the contract code does not reflect the actual cost of this access for the block builder or a validator.

The more popular the contract code or a storage slot is, the more transactions in each block should share the cost. However, the current system multiplies the cost for the users instead of dividing it.

Issuing a regular gas refund after a transaction is not possible

There exists a list of EVM instructions that trigger both a gas charge and a gas refund. A notable example of such operations is the 0x55 SSTORE opcode as defined in EIP-1283: Net gas metering for SSTORE without dirty maps. Intuitively it seems reasonable to issue the gas reimbursements for the shared cold storage access in the same fashion.

However, this approach significantly complicates the block-building process. In this case, the inclusion or exclusion of a transaction at the end of the block triggers observable effects in transactions included at the beginning of the block, and this makes the job of finding a valid set of transactions for a block potentially computationally unsolvable.

Therefore, we propose performing the reimbursements at the end of the block, where it cannot change the behavior of any transaction in the block.

Weighting priority fee reimbursement

A common game-theoretical answer to the problem of calculating a fair redistribution of the payoff of the results of the participants’ cooperation is the use of Shapley values.

However, we argue that the proposed distribution of the priorityFee reimbursements is sufficiently fair while being a lot easier to compute or articulate.

Backwards Compatibility

This proposal does not introduce a change to any behavior that can be observed by a smart contract during its execution. The only effect this change has is a lower effective gas cost for the transaction senders.

Security Considerations

The upper limit of storage reads in one block is not affected by this change as the gas charge is done with the full cost of COLD_ACCOUNT_ACCESS_COST or COLD_SLOAD_COST.

The maximum amount of memory and computation required to calculate the reimbursements according to the specified algorithm is insignificant.

It appears that this change does not have any negative security implications.

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Yoav Weiss (@yoavw), Alex Forshtat (@forshtat), Dror Tirosh (@drortirosh), Shahaf Nacson (@shahafn), "EIP-7557: Block-level Warming with fair cost savings [DRAFT]," Ethereum Improvement Proposals, no. 7557, October 2023. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7557.