Ethereum Yellow Paper Deciphered | Part 4: Transaction Execution
December 3, 2022
Note that this post is updated till the Shanghai version of the ethereum yellow paper.
This part of the series dives into section 6 of the Yellow Paper that describes the execution of transactions.
If you haven't yet, go through Part 0 of this series to get conventions right.
Transaction Execution
We have already learnt about what forms a transaction in Part 2 of this series. This part covers the deep dive details of how a given transaction, is executed leading to the final state change.
Before a transaction is executed, it must go through an initial tests for validity. These tests are described by below in later section. First, lets make sense of execution parameters so that we define this validity better.
Remember from Part 1 that transaction execution in Ethereum is defined by the state transition function, . The transaction is executed at current state to get to next state :
is referred as post-transactional state or the final state.
Accrued Transaction Substate
The next world state is finalized only when a block a finalized with all of the transactions in it are executed, not when a single transaction is executed. The transactions in a block are executed one by one taking the world state through multiple states, until all of the transactions are executed and a new world state is finalized.
Furthermore, execution of a single transaction is divided between 4 phases. In each such the original state is updated until the final state is reached completing execution.
Throughout this execution involving multiple phases certain information is accrued called accrued transaction substate or accrued substate, . It includes:
Self-destruct set, : Set of accounts that will be discarded after this transaction completes. This could be contract whose selfdestruct was called.
Log series, : Logged data such as emitted events during transaction execution.
Set of touched accounts, : Accounts that are accessed during transaction execution. See this.
Refund balance, : Any excess fee to be refunded to fee payer.
Set of accessed accounts, : Account addresses accessed during execution of transaction. The precompiled addresses are in this set by default.
Accessed storage keys, : Set of accessed contract storage keys, each represented by tuple of address and storage slot accessed there.
An empty substate, consists of no self-destructs, no logs, no touched accounts, zero refund balance, no accessed storage and only precompiled contract addresses (i.e. set ) in accessed addresses.
The substate is cleared after transaction execution completes.
Here we limit our scope to transition (via ) the world state at to final state . Do not confuse the state as when after block is finalized, it is the state after a transaction is executed successfully.
Validation
Before laying out formal validation of transaction that we talked about earlier, let's defined some related parameters.
Intrinsic gas,
First, intrinsic gas which is denoted by . is the amount of gas required to be paid for before any transaction execution occurs. So, will not account for any gas spent on computation (with contract code) in a transaction.
and is sum of multiple gas fragments. These are:
Transaction data costs: These are influenced by the initialization code () bytes and calldata bytes (). Regardless of or bytes, the gas required of each zero byte is and each non-zero bytes is . Summing gas for all bytes data gives:
Contract creation costs: Recall that new contract creation transaction is specified by setting to address to null i.e. . If transaction is contract creation, the gas is plus additional cost, times number of words (32-bytes) in the initialization code .
where is initcode cost function:
Transaction cost: Fixed gas cost paid for every transaction (21000).
Access entries warm up cost: For each access entry from list of access entries of a transaction , there are two costs. First, cost for warming up an account at its address. Second, cost for warming up all storage slots accessed at that address i.e. .
Note that represents number of accessed storage slots of entry at index in access entries list and is cost for one storage slot access. So cost for all such items in access entries is:
Finally, summing up all costs in terms of gas, we get:
as defined in paper.
Effective Gas Price,
The effective gas price is the actual price (in wei) paid per unit of gas by the transaction signer. The transaction signer controls it and sets it to some sane value that is enough to incentivize the validator to include its transaction. The signer controls it by specifying gas price for type-0 and type-1 transactions. For type-2 transactions, it is controlled by specifying the max fee per gas and max priority fee per gas .
where is priority fee.
Priority Fee,
As evident from used to be simply () of type-0 and type-1 transactions.
For type-2 transaction, with introduction of and it became sum two fees. First, , the block's - the amount that will be burned per unit of gas. And second, the priority fee which is amount of wei that is sent to validator as reward per unit of total gas consumed during transaction execution.
Since is the reward (in wei) per gas given to validator after whatever left from burning according to parameter, it is simply the difference between and for type-0 and type-1 transactions.
For type-2 this difference is calculated between and instead. Additionally, for type-2 this reward is capped by () of course. With this information, can be concisely calculated as:
Up-front Cost,
Up-front cost is the total gas cost plus any ether value () sent with the transaction. The total gas cost calculation depends of transaction type. For type-0 and type-1 transactions it is gas price times the gas limit i.e . For type-2 transactions specified max fee per gas times the gas limit i.e. :
accounts for the price of gas that will be consumed for execution of the transaction.
Validity Check
Now we come back to the validity check pre-transaction execution. The checks include:
Sender of transaction, denoted by must not be empty:
The code at sender account must be empty i.e. it should be EOA:
Transaction nonce must be equal to sender account nonce:
Intrinsic gas must be less than or equal to gas limit since gas limit is max allowed to use in the transaction:
The transaction gas price must be greater than or equal to block's base fee per gas.
where,
The initialization code, if any (for contract creation), must be less than 49152 bytes:
where,
The block's gas limit must not be exceeded during successive execution of transactions in it. Therefore, the sum of gas consumed in current block by execution of transactions up to prior to current transaction () represented by, and current transaction's gas limit () must be less current block's gas limit ():
or,
Combining all constraints we get:
For type-2 transactions additional constraint is that must not exceed :
Execution
As told earlier, the execution of a transaction occurs through 4 phases to finally reach a final state after which any change is irrevocable.
The four phases in the process to execution of transaction are:
From current state, to checkpoint state,
From checkpoint state, to post-execution provisional state,
From post-execution provisional state, to pre-final state,
From pre-final state, to final state
Let's go through each phase one by one.
1.
The transition from current state to modifies only two properties of the current state - sender balance and sender nonce. All else remains same i.e.:
except, the balance of sender account is deducted by only a part of the up-front cost () which is the gas cost in wei covering all gas specified as gas limit. This part is simply :
and nonce of sender account is increased by 1:
Note that even though we deduct cost covering all of the gas limit () at this point, not all gas is necessarily exhausted. A part of it refunded later. Also note there is no computation performed in this phase.
At this point the gas available, from the gas limit is since we only deduct intrinsic gas before doing any computation/execution.
2.
The state is reached by performing the execution (including any computation with contract code) on the sent transaction. The computation involved can either be contract creation whose result is given by contract creation function . Or, it can be a message call whose result is given by message call function .
Whether or is used depends on whether transaction is contract creation () or message call. Along with giving as output, these functions also output remaining gas after computation , accrued state and status code :
The outputs of the and are actually 5-element tuple instead of 4. We used and here to denote that only 4 elements from the output are taken. The fifth element is actually represents message-call output bytes (, the returndata) which we have omitted here as it is not required in this context.
(Note: We will see more about functions and in detail in next parts.)
is the accrued substate after reaching previous state . It has same elements as empty substate i.e:
except accessed storage keys and accessed account addresses from previous state. is set of all entries (each entry denoted by ) in transaction access list :
and contains accessed addresseses that include:
Accessed addresses in a zero substate i.e. . This is simply all precompiled contract addresses (denoted by in in )
Transaction sender address
Beneficiary address of the block
All accesses addresses in transaction access list i.e.
If, it is not a contract creation (), the address where transactions executed at
In set notation this is same as saying:
where,
We've already defined remaining gas at state in above. Do not confuse with , is the remaining gas after the computation or execution of transaction - at state .
The state is finalized the amount of refunded gas . This is sum of remaining gas plus some allowance:
3.
In the pre-final state only two fields of the provisional state, are updated. All other fields reamins same as , i.e:
except the account balance of sender is increased by refunded gas cost (remaining gas times the effective price):
and account balance of beneficiary address (validator that includes that transaction in block) is increased w.r.t. priority fee :
4.
The final state does some final cleanups. It delets all accounts (contracts) that appear in self-destruct set, or are touched and empty from pre-final state .
The final state is same as pre-final state :
except all accounts in pre-final state are deleted (set to null) that are in set :
and same with touched accounts:
And, that concludes the process of execution of a transaction.
Transaction Receipt
Now that transaction has been executed the receipt of that transaction can be created. For that we define additional three parameters:
Total gas used in transaction, which is simply difference between provided gas limit and actual gas used:
Logs (a.k.a events) that are created in this transaction execution. This is simply accumulated logs in substate:
Status code of transaction, . is 1 for successfully executed transactions and 0 for reverted transactions:
And that concludes this part! Next up we see Contract Creation.