ethereum.london.fork

   1"""
   2Ethereum Specification
   3^^^^^^^^^^^^^^^^^^^^^^
   4
   5.. contents:: Table of Contents
   6    :backlinks: none
   7    :local:
   8
   9Introduction
  10------------
  11
  12Entry point for the Ethereum specification.
  13"""
  14
  15from dataclasses import dataclass
  16from typing import List, Optional, Set, Tuple, Union
  17
  18from ethereum.base_types import Bytes0
  19from ethereum.crypto.elliptic_curve import SECP256K1N, secp256k1_recover
  20from ethereum.crypto.hash import Hash32, keccak256
  21from ethereum.ethash import dataset_size, generate_cache, hashimoto_light
  22from ethereum.exceptions import InvalidBlock
  23from ethereum.utils.ensure import ensure
  24
  25from .. import rlp
  26from ..base_types import U64, U256, U256_CEIL_VALUE, Bytes, Uint
  27from . import FORK_CRITERIA, vm
  28from .bloom import logs_bloom
  29from .fork_types import (
  30    TX_ACCESS_LIST_ADDRESS_COST,
  31    TX_ACCESS_LIST_STORAGE_KEY_COST,
  32    TX_BASE_COST,
  33    TX_CREATE_COST,
  34    TX_DATA_COST_PER_NON_ZERO,
  35    TX_DATA_COST_PER_ZERO,
  36    AccessListTransaction,
  37    Address,
  38    Block,
  39    Bloom,
  40    FeeMarketTransaction,
  41    Header,
  42    LegacyTransaction,
  43    Log,
  44    Receipt,
  45    Root,
  46    Transaction,
  47    decode_transaction,
  48    encode_transaction,
  49)
  50from .state import (
  51    State,
  52    account_exists_and_is_empty,
  53    create_ether,
  54    destroy_account,
  55    get_account,
  56    increment_nonce,
  57    set_account_balance,
  58    state_root,
  59)
  60from .trie import Trie, root, trie_set
  61from .utils.message import prepare_message
  62from .vm.interpreter import process_message_call
  63
  64BLOCK_REWARD = U256(2 * 10**18)
  65BASE_FEE_MAX_CHANGE_DENOMINATOR = 8
  66ELASTICITY_MULTIPLIER = 2
  67GAS_LIMIT_ADJUSTMENT_FACTOR = 1024
  68GAS_LIMIT_MINIMUM = 5000
  69MINIMUM_DIFFICULTY = Uint(131072)
  70INITIAL_BASE_FEE = 1000000000
  71MAX_OMMER_DEPTH = 6
  72BOMB_DELAY_BLOCKS = 9700000
  73EMPTY_OMMER_HASH = keccak256(rlp.encode([]))
  74
  75
  76@dataclass
  77class BlockChain:
  78    """
  79    History and current state of the block chain.
  80    """
  81
  82    blocks: List[Block]
  83    state: State
  84    chain_id: U64
  85
  86
  87def apply_fork(old: BlockChain) -> BlockChain:
  88    """
  89    Transforms the state from the previous hard fork (`old`) into the block
  90    chain object for this hard fork and returns it.
  91
  92    When forks need to implement an irregular state transition, this function
  93    is used to handle the irregularity. See the :ref:`DAO Fork <dao-fork>` for
  94    an example.
  95
  96    Parameters
  97    ----------
  98    old :
  99        Previous block chain object.
 100
 101    Returns
 102    -------
 103    new : `BlockChain`
 104        Upgraded block chain object for this hard fork.
 105    """
 106    return old
 107
 108
 109def get_last_256_block_hashes(chain: BlockChain) -> List[Hash32]:
 110    """
 111    Obtain the list of hashes of the previous 256 blocks in order of
 112    increasing block number.
 113
 114    This function will return less hashes for the first 256 blocks.
 115
 116    The ``BLOCKHASH`` opcode needs to access the latest hashes on the chain,
 117    therefore this function retrieves them.
 118
 119    Parameters
 120    ----------
 121    chain :
 122        History and current state.
 123
 124    Returns
 125    -------
 126    recent_block_hashes : `List[Hash32]`
 127        Hashes of the recent 256 blocks in order of increasing block number.
 128    """
 129    recent_blocks = chain.blocks[-255:]
 130    # TODO: This function has not been tested rigorously
 131    if len(recent_blocks) == 0:
 132        return []
 133
 134    recent_block_hashes = []
 135
 136    for block in recent_blocks:
 137        prev_block_hash = block.header.parent_hash
 138        recent_block_hashes.append(prev_block_hash)
 139
 140    # We are computing the hash only for the most recent block and not for
 141    # the rest of the blocks as they have successors which have the hash of
 142    # the current block as parent hash.
 143    most_recent_block_hash = keccak256(rlp.encode(recent_blocks[-1].header))
 144    recent_block_hashes.append(most_recent_block_hash)
 145
 146    return recent_block_hashes
 147
 148
 149def state_transition(chain: BlockChain, block: Block) -> None:
 150    """
 151    Attempts to apply a block to an existing block chain.
 152
 153    All parts of the block's contents need to be verified before being added
 154    to the chain. Blocks are verified by ensuring that the contents of the
 155    block make logical sense with the contents of the parent block. The
 156    information in the block's header must also match the corresponding
 157    information in the block.
 158
 159    To implement Ethereum, in theory clients are only required to store the
 160    most recent 255 blocks of the chain since as far as execution is
 161    concerned, only those blocks are accessed. Practically, however, clients
 162    should store more blocks to handle reorgs.
 163
 164    Parameters
 165    ----------
 166    chain :
 167        History and current state.
 168    block :
 169        Block to apply to `chain`.
 170    """
 171    parent_header = chain.blocks[-1].header
 172    validate_header(block.header, parent_header)
 173    validate_ommers(block.ommers, block.header, chain)
 174    (
 175        gas_used,
 176        transactions_root,
 177        receipt_root,
 178        block_logs_bloom,
 179        state,
 180    ) = apply_body(
 181        chain.state,
 182        get_last_256_block_hashes(chain),
 183        block.header.coinbase,
 184        block.header.number,
 185        block.header.base_fee_per_gas,
 186        block.header.gas_limit,
 187        block.header.timestamp,
 188        block.header.difficulty,
 189        block.transactions,
 190        block.ommers,
 191        chain.chain_id,
 192    )
 193    ensure(gas_used == block.header.gas_used, InvalidBlock)
 194    ensure(transactions_root == block.header.transactions_root, InvalidBlock)
 195    ensure(state_root(state) == block.header.state_root, InvalidBlock)
 196    ensure(receipt_root == block.header.receipt_root, InvalidBlock)
 197    ensure(block_logs_bloom == block.header.bloom, InvalidBlock)
 198
 199    chain.blocks.append(block)
 200    if len(chain.blocks) > 255:
 201        # Real clients have to store more blocks to deal with reorgs, but the
 202        # protocol only requires the last 255
 203        chain.blocks = chain.blocks[-255:]
 204
 205
 206def calculate_base_fee_per_gas(
 207    block_gas_limit: Uint,
 208    parent_gas_limit: Uint,
 209    parent_gas_used: Uint,
 210    parent_base_fee_per_gas: Uint,
 211    is_fork_block: bool,
 212) -> Uint:
 213    """
 214    Calculates the base fee per gas for the block.
 215
 216    Parameters
 217    ----------
 218    block_gas_limit :
 219        Gas limit of the block for which the base fee is being calculated.
 220    parent_gas_limit :
 221        Gas limit of the parent block.
 222    parent_gas_used :
 223        Gas used in the parent block.
 224    parent_base_fee_per_gas :
 225        Base fee per gas of the parent block.
 226    is_fork_block :
 227        Whether the block is the fork block.
 228
 229    Returns
 230    -------
 231    base_fee_per_gas : `Uint`
 232        Base fee per gas for the block.
 233    """
 234    if is_fork_block:
 235        return Uint(INITIAL_BASE_FEE)
 236    parent_gas_target = parent_gas_limit // ELASTICITY_MULTIPLIER
 237
 238    ensure(
 239        check_gas_limit(block_gas_limit, parent_gas_limit),
 240        InvalidBlock,
 241    )
 242
 243    if parent_gas_used == parent_gas_target:
 244        expected_base_fee_per_gas = parent_base_fee_per_gas
 245    elif parent_gas_used > parent_gas_target:
 246        gas_used_delta = parent_gas_used - parent_gas_target
 247
 248        parent_fee_gas_delta = parent_base_fee_per_gas * gas_used_delta
 249        target_fee_gas_delta = parent_fee_gas_delta // parent_gas_target
 250
 251        base_fee_per_gas_delta = max(
 252            target_fee_gas_delta // BASE_FEE_MAX_CHANGE_DENOMINATOR,
 253            1,
 254        )
 255
 256        expected_base_fee_per_gas = (
 257            parent_base_fee_per_gas + base_fee_per_gas_delta
 258        )
 259    else:
 260        gas_used_delta = parent_gas_target - parent_gas_used
 261
 262        parent_fee_gas_delta = parent_base_fee_per_gas * gas_used_delta
 263        target_fee_gas_delta = parent_fee_gas_delta // parent_gas_target
 264
 265        base_fee_per_gas_delta = (
 266            target_fee_gas_delta // BASE_FEE_MAX_CHANGE_DENOMINATOR
 267        )
 268
 269        expected_base_fee_per_gas = (
 270            parent_base_fee_per_gas - base_fee_per_gas_delta
 271        )
 272
 273    return Uint(expected_base_fee_per_gas)
 274
 275
 276def validate_header(header: Header, parent_header: Header) -> None:
 277    """
 278    Verifies a block header.
 279
 280    In order to consider a block's header valid, the logic for the
 281    quantities in the header should match the logic for the block itself.
 282    For example the header timestamp should be greater than the block's parent
 283    timestamp because the block was created *after* the parent block.
 284    Additionally, the block's number should be directly following the parent
 285    block's number since it is the next block in the sequence.
 286
 287    Parameters
 288    ----------
 289    header :
 290        Header to check for correctness.
 291    parent_header :
 292        Parent Header of the header to check for correctness
 293    """
 294    ensure(header.gas_used <= header.gas_limit, InvalidBlock)
 295
 296    is_fork_block = header.number == FORK_CRITERIA.block_number
 297    expected_base_fee_per_gas = calculate_base_fee_per_gas(
 298        header.gas_limit,
 299        parent_header.gas_limit,
 300        parent_header.gas_used,
 301        parent_header.base_fee_per_gas,
 302        is_fork_block,
 303    )
 304
 305    ensure(expected_base_fee_per_gas == header.base_fee_per_gas, InvalidBlock)
 306
 307    parent_has_ommers = parent_header.ommers_hash != EMPTY_OMMER_HASH
 308    ensure(header.timestamp > parent_header.timestamp, InvalidBlock)
 309    ensure(header.number == parent_header.number + 1, InvalidBlock)
 310    ensure(len(header.extra_data) <= 32, InvalidBlock)
 311
 312    block_difficulty = calculate_block_difficulty(
 313        header.number,
 314        header.timestamp,
 315        parent_header.timestamp,
 316        parent_header.difficulty,
 317        parent_has_ommers,
 318    )
 319    ensure(header.difficulty == block_difficulty, InvalidBlock)
 320
 321    block_parent_hash = keccak256(rlp.encode(parent_header))
 322    ensure(header.parent_hash == block_parent_hash, InvalidBlock)
 323
 324    validate_proof_of_work(header)
 325
 326
 327def generate_header_hash_for_pow(header: Header) -> Hash32:
 328    """
 329    Generate rlp hash of the header which is to be used for Proof-of-Work
 330    verification.
 331
 332    In other words, the PoW artefacts `mix_digest` and `nonce` are ignored
 333    while calculating this hash.
 334
 335    A particular PoW is valid for a single hash, that hash is computed by
 336    this function. The `nonce` and `mix_digest` are omitted from this hash
 337    because they are being changed by miners in their search for a sufficient
 338    proof-of-work.
 339
 340    Parameters
 341    ----------
 342    header :
 343        The header object for which the hash is to be generated.
 344
 345    Returns
 346    -------
 347    hash : `Hash32`
 348        The PoW valid rlp hash of the passed in header.
 349    """
 350    header_data_without_pow_artefacts = [
 351        header.parent_hash,
 352        header.ommers_hash,
 353        header.coinbase,
 354        header.state_root,
 355        header.transactions_root,
 356        header.receipt_root,
 357        header.bloom,
 358        header.difficulty,
 359        header.number,
 360        header.gas_limit,
 361        header.gas_used,
 362        header.timestamp,
 363        header.extra_data,
 364        header.base_fee_per_gas,
 365    ]
 366
 367    return rlp.rlp_hash(header_data_without_pow_artefacts)
 368
 369
 370def validate_proof_of_work(header: Header) -> None:
 371    """
 372    Validates the Proof of Work constraints.
 373
 374    In order to verify that a miner's proof-of-work is valid for a block, a
 375    ``mix-digest`` and ``result`` are calculated using the ``hashimoto_light``
 376    hash function. The mix digest is a hash of the header and the nonce that
 377    is passed through and it confirms whether or not proof-of-work was done
 378    on the correct block. The result is the actual hash value of the block.
 379
 380    Parameters
 381    ----------
 382    header :
 383        Header of interest.
 384    """
 385    header_hash = generate_header_hash_for_pow(header)
 386    # TODO: Memoize this somewhere and read from that data instead of
 387    # calculating cache for every block validation.
 388    cache = generate_cache(header.number)
 389    mix_digest, result = hashimoto_light(
 390        header_hash, header.nonce, cache, dataset_size(header.number)
 391    )
 392
 393    ensure(mix_digest == header.mix_digest, InvalidBlock)
 394    ensure(
 395        Uint.from_be_bytes(result) <= (U256_CEIL_VALUE // header.difficulty),
 396        InvalidBlock,
 397    )
 398
 399
 400def check_transaction(
 401    tx: Transaction,
 402    base_fee_per_gas: Uint,
 403    gas_available: Uint,
 404    chain_id: U64,
 405) -> Tuple[Address, Uint]:
 406    """
 407    Check if the transaction is includable in the block.
 408
 409    Parameters
 410    ----------
 411    tx :
 412        The transaction.
 413    base_fee_per_gas :
 414        The block base fee.
 415    gas_available :
 416        The gas remaining in the block.
 417    chain_id :
 418        The ID of the current chain.
 419
 420    Returns
 421    -------
 422    sender_address :
 423        The sender of the transaction.
 424    effective_gas_price :
 425        The price to charge for gas when the transaction is executed.
 426
 427    Raises
 428    ------
 429    InvalidBlock :
 430        If the transaction is not includable.
 431    """
 432    ensure(tx.gas <= gas_available, InvalidBlock)
 433    sender_address = recover_sender(chain_id, tx)
 434
 435    if isinstance(tx, FeeMarketTransaction):
 436        ensure(tx.max_fee_per_gas >= tx.max_priority_fee_per_gas, InvalidBlock)
 437        ensure(tx.max_fee_per_gas >= base_fee_per_gas, InvalidBlock)
 438
 439        priority_fee_per_gas = min(
 440            tx.max_priority_fee_per_gas,
 441            tx.max_fee_per_gas - base_fee_per_gas,
 442        )
 443        effective_gas_price = priority_fee_per_gas + base_fee_per_gas
 444    else:
 445        ensure(tx.gas_price >= base_fee_per_gas, InvalidBlock)
 446        effective_gas_price = tx.gas_price
 447
 448    return sender_address, effective_gas_price
 449
 450
 451def make_receipt(
 452    tx: Transaction,
 453    error: Optional[Exception],
 454    cumulative_gas_used: Uint,
 455    logs: Tuple[Log, ...],
 456) -> Union[Bytes, Receipt]:
 457    """
 458    Make the receipt for a transaction that was executed.
 459
 460    Parameters
 461    ----------
 462    tx :
 463        The executed transaction.
 464    error :
 465        Error in the top level frame of the transaction, if any.
 466    cumulative_gas_used :
 467        The total gas used so far in the block after the transaction was
 468        executed.
 469    logs :
 470        The logs produced by the transaction.
 471
 472    Returns
 473    -------
 474    receipt :
 475        The receipt for the transaction.
 476    """
 477    receipt = Receipt(
 478        succeeded=error is None,
 479        cumulative_gas_used=cumulative_gas_used,
 480        bloom=logs_bloom(logs),
 481        logs=logs,
 482    )
 483
 484    if isinstance(tx, AccessListTransaction):
 485        return b"\x01" + rlp.encode(receipt)
 486    elif isinstance(tx, FeeMarketTransaction):
 487        return b"\x02" + rlp.encode(receipt)
 488    else:
 489        return receipt
 490
 491
 492def apply_body(
 493    state: State,
 494    block_hashes: List[Hash32],
 495    coinbase: Address,
 496    block_number: Uint,
 497    base_fee_per_gas: Uint,
 498    block_gas_limit: Uint,
 499    block_time: U256,
 500    block_difficulty: Uint,
 501    transactions: Tuple[Union[LegacyTransaction, Bytes], ...],
 502    ommers: Tuple[Header, ...],
 503    chain_id: U64,
 504) -> Tuple[Uint, Root, Root, Bloom, State]:
 505    """
 506    Executes a block.
 507
 508    Many of the contents of a block are stored in data structures called
 509    tries. There is a transactions trie which is similar to a ledger of the
 510    transactions stored in the current block. There is also a receipts trie
 511    which stores the results of executing a transaction, like the post state
 512    and gas used. This function creates and executes the block that is to be
 513    added to the chain.
 514
 515    Parameters
 516    ----------
 517    state :
 518        Current account state.
 519    block_hashes :
 520        List of hashes of the previous 256 blocks in the order of
 521        increasing block number.
 522    coinbase :
 523        Address of account which receives block reward and transaction fees.
 524    block_number :
 525        Position of the block within the chain.
 526    base_fee_per_gas :
 527        Base fee per gas of within the block.
 528    block_gas_limit :
 529        Initial amount of gas available for execution in this block.
 530    block_time :
 531        Time the block was produced, measured in seconds since the epoch.
 532    block_difficulty :
 533        Difficulty of the block.
 534    transactions :
 535        Transactions included in the block.
 536    ommers :
 537        Headers of ancestor blocks which are not direct parents (formerly
 538        uncles.)
 539    chain_id :
 540        ID of the executing chain.
 541
 542    Returns
 543    -------
 544    block_gas_used : `ethereum.base_types.Uint`
 545        Gas used for executing all transactions.
 546    transactions_root : `ethereum.fork_types.Root`
 547        Trie root of all the transactions in the block.
 548    receipt_root : `ethereum.fork_types.Root`
 549        Trie root of all the receipts in the block.
 550    block_logs_bloom : `Bloom`
 551        Logs bloom of all the logs included in all the transactions of the
 552        block.
 553    state : `ethereum.fork_types.State`
 554        State after all transactions have been executed.
 555    """
 556    gas_available = block_gas_limit
 557    transactions_trie: Trie[
 558        Bytes, Optional[Union[Bytes, LegacyTransaction]]
 559    ] = Trie(secured=False, default=None)
 560    receipts_trie: Trie[Bytes, Optional[Union[Bytes, Receipt]]] = Trie(
 561        secured=False, default=None
 562    )
 563    block_logs: Tuple[Log, ...] = ()
 564
 565    for i, tx in enumerate(map(decode_transaction, transactions)):
 566        trie_set(
 567            transactions_trie, rlp.encode(Uint(i)), encode_transaction(tx)
 568        )
 569
 570        sender_address, effective_gas_price = check_transaction(
 571            tx, base_fee_per_gas, gas_available, chain_id
 572        )
 573
 574        env = vm.Environment(
 575            caller=sender_address,
 576            origin=sender_address,
 577            block_hashes=block_hashes,
 578            coinbase=coinbase,
 579            number=block_number,
 580            gas_limit=block_gas_limit,
 581            base_fee_per_gas=base_fee_per_gas,
 582            gas_price=effective_gas_price,
 583            time=block_time,
 584            difficulty=block_difficulty,
 585            state=state,
 586            chain_id=chain_id,
 587            traces=[],
 588        )
 589
 590        gas_used, logs, error = process_transaction(env, tx)
 591        gas_available -= gas_used
 592
 593        receipt = make_receipt(
 594            tx, error, (block_gas_limit - gas_available), logs
 595        )
 596
 597        trie_set(
 598            receipts_trie,
 599            rlp.encode(Uint(i)),
 600            receipt,
 601        )
 602
 603        block_logs += logs
 604
 605    pay_rewards(state, block_number, coinbase, ommers)
 606
 607    block_gas_used = block_gas_limit - gas_available
 608
 609    block_logs_bloom = logs_bloom(block_logs)
 610
 611    return (
 612        block_gas_used,
 613        root(transactions_trie),
 614        root(receipts_trie),
 615        block_logs_bloom,
 616        state,
 617    )
 618
 619
 620def validate_ommers(
 621    ommers: Tuple[Header, ...], block_header: Header, chain: BlockChain
 622) -> None:
 623    """
 624    Validates the ommers mentioned in the block.
 625
 626    An ommer block is a block that wasn't canonically added to the
 627    blockchain because it wasn't validated as fast as the canonical block
 628    but was mined at the same time.
 629
 630    To be considered valid, the ommers must adhere to the rules defined in
 631    the Ethereum protocol. The maximum amount of ommers is 2 per block and
 632    there cannot be duplicate ommers in a block. Many of the other ommer
 633    constraints are listed in the in-line comments of this function.
 634
 635    Parameters
 636    ----------
 637    ommers :
 638        List of ommers mentioned in the current block.
 639    block_header:
 640        The header of current block.
 641    chain :
 642        History and current state.
 643    """
 644    block_hash = rlp.rlp_hash(block_header)
 645
 646    ensure(rlp.rlp_hash(ommers) == block_header.ommers_hash, InvalidBlock)
 647
 648    if len(ommers) == 0:
 649        # Nothing to validate
 650        return
 651
 652    # Check that each ommer satisfies the constraints of a header
 653    for ommer in ommers:
 654        ensure(1 <= ommer.number < block_header.number, InvalidBlock)
 655        ommer_parent_header = chain.blocks[
 656            -(block_header.number - ommer.number) - 1
 657        ].header
 658        validate_header(ommer, ommer_parent_header)
 659
 660    # Check that there can be only at most 2 ommers for a block.
 661    ensure(len(ommers) <= 2, InvalidBlock)
 662
 663    ommers_hashes = [rlp.rlp_hash(ommer) for ommer in ommers]
 664    # Check that there are no duplicates in the ommers of current block
 665    ensure(len(ommers_hashes) == len(set(ommers_hashes)), InvalidBlock)
 666
 667    recent_canonical_blocks = chain.blocks[-(MAX_OMMER_DEPTH + 1) :]
 668    recent_canonical_block_hashes = {
 669        rlp.rlp_hash(block.header) for block in recent_canonical_blocks
 670    }
 671    recent_ommers_hashes: Set[Hash32] = set()
 672    for block in recent_canonical_blocks:
 673        recent_ommers_hashes = recent_ommers_hashes.union(
 674            {rlp.rlp_hash(ommer) for ommer in block.ommers}
 675        )
 676
 677    for ommer_index, ommer in enumerate(ommers):
 678        ommer_hash = ommers_hashes[ommer_index]
 679        # The current block shouldn't be the ommer
 680        ensure(ommer_hash != block_hash, InvalidBlock)
 681
 682        # Ommer shouldn't be one of the recent canonical blocks
 683        ensure(ommer_hash not in recent_canonical_block_hashes, InvalidBlock)
 684
 685        # Ommer shouldn't be one of the uncles mentioned in the recent
 686        # canonical blocks
 687        ensure(ommer_hash not in recent_ommers_hashes, InvalidBlock)
 688
 689        # Ommer age with respect to the current block. For example, an age of
 690        # 1 indicates that the ommer is a sibling of previous block.
 691        ommer_age = block_header.number - ommer.number
 692        ensure(1 <= ommer_age <= MAX_OMMER_DEPTH, InvalidBlock)
 693
 694        ensure(
 695            ommer.parent_hash in recent_canonical_block_hashes, InvalidBlock
 696        )
 697        ensure(ommer.parent_hash != block_header.parent_hash, InvalidBlock)
 698
 699
 700def pay_rewards(
 701    state: State,
 702    block_number: Uint,
 703    coinbase: Address,
 704    ommers: Tuple[Header, ...],
 705) -> None:
 706    """
 707    Pay rewards to the block miner as well as the ommers miners.
 708
 709    The miner of the canonical block is rewarded with the predetermined
 710    block reward, ``BLOCK_REWARD``, plus a variable award based off of the
 711    number of ommer blocks that were mined around the same time, and included
 712    in the canonical block's header. An ommer block is a block that wasn't
 713    added to the canonical blockchain because it wasn't validated as fast as
 714    the accepted block but was mined at the same time. Although not all blocks
 715    that are mined are added to the canonical chain, miners are still paid a
 716    reward for their efforts. This reward is called an ommer reward and is
 717    calculated based on the number associated with the ommer block that they
 718    mined.
 719
 720    Parameters
 721    ----------
 722    state :
 723        Current account state.
 724    block_number :
 725        Position of the block within the chain.
 726    coinbase :
 727        Address of account which receives block reward and transaction fees.
 728    ommers :
 729        List of ommers mentioned in the current block.
 730    """
 731    miner_reward = BLOCK_REWARD + (len(ommers) * (BLOCK_REWARD // 32))
 732    create_ether(state, coinbase, miner_reward)
 733
 734    for ommer in ommers:
 735        # Ommer age with respect to the current block.
 736        ommer_age = U256(block_number - ommer.number)
 737        ommer_miner_reward = ((8 - ommer_age) * BLOCK_REWARD) // 8
 738        create_ether(state, ommer.coinbase, ommer_miner_reward)
 739
 740
 741def process_transaction(
 742    env: vm.Environment, tx: Transaction
 743) -> Tuple[Uint, Tuple[Log, ...], Optional[Exception]]:
 744    """
 745    Execute a transaction against the provided environment.
 746
 747    This function processes the actions needed to execute a transaction.
 748    It decrements the sender's account after calculating the gas fee and
 749    refunds them the proper amount after execution. Calling contracts,
 750    deploying code, and incrementing nonces are all examples of actions that
 751    happen within this function or from a call made within this function.
 752
 753    Accounts that are marked for deletion are processed and destroyed after
 754    execution.
 755
 756    Parameters
 757    ----------
 758    env :
 759        Environment for the Ethereum Virtual Machine.
 760    tx :
 761        Transaction to execute.
 762
 763    Returns
 764    -------
 765    gas_left : `ethereum.base_types.U256`
 766        Remaining gas after execution.
 767    logs : `Tuple[ethereum.fork_types.Log, ...]`
 768        Logs generated during execution.
 769    """
 770    ensure(validate_transaction(tx), InvalidBlock)
 771
 772    sender = env.origin
 773    sender_account = get_account(env.state, sender)
 774
 775    if isinstance(tx, FeeMarketTransaction):
 776        max_gas_fee = tx.gas * tx.max_fee_per_gas
 777    else:
 778        max_gas_fee = tx.gas * tx.gas_price
 779
 780    ensure(sender_account.nonce == tx.nonce, InvalidBlock)
 781    ensure(sender_account.balance >= max_gas_fee + tx.value, InvalidBlock)
 782    ensure(sender_account.code == bytearray(), InvalidBlock)
 783
 784    effective_gas_fee = tx.gas * env.gas_price
 785
 786    gas = tx.gas - calculate_intrinsic_cost(tx)
 787    increment_nonce(env.state, sender)
 788
 789    sender_balance_after_gas_fee = sender_account.balance - effective_gas_fee
 790    set_account_balance(env.state, sender, sender_balance_after_gas_fee)
 791
 792    preaccessed_addresses = set()
 793    preaccessed_storage_keys = set()
 794    if isinstance(tx, (AccessListTransaction, FeeMarketTransaction)):
 795        for address, keys in tx.access_list:
 796            preaccessed_addresses.add(address)
 797            for key in keys:
 798                preaccessed_storage_keys.add((address, key))
 799
 800    message = prepare_message(
 801        sender,
 802        tx.to,
 803        tx.value,
 804        tx.data,
 805        gas,
 806        env,
 807        preaccessed_addresses=frozenset(preaccessed_addresses),
 808        preaccessed_storage_keys=frozenset(preaccessed_storage_keys),
 809    )
 810
 811    output = process_message_call(message, env)
 812
 813    gas_used = tx.gas - output.gas_left
 814    gas_refund = min(gas_used // 5, output.refund_counter)
 815    gas_refund_amount = (output.gas_left + gas_refund) * env.gas_price
 816
 817    # For non-1559 transactions env.gas_price == tx.gas_price
 818    priority_fee_per_gas = env.gas_price - env.base_fee_per_gas
 819    transaction_fee = (
 820        tx.gas - output.gas_left - gas_refund
 821    ) * priority_fee_per_gas
 822
 823    total_gas_used = gas_used - gas_refund
 824
 825    # refund gas
 826    sender_balance_after_refund = (
 827        get_account(env.state, sender).balance + gas_refund_amount
 828    )
 829    set_account_balance(env.state, sender, sender_balance_after_refund)
 830
 831    # transfer miner fees
 832    coinbase_balance_after_mining_fee = (
 833        get_account(env.state, env.coinbase).balance + transaction_fee
 834    )
 835    if coinbase_balance_after_mining_fee != 0:
 836        set_account_balance(
 837            env.state, env.coinbase, coinbase_balance_after_mining_fee
 838        )
 839    elif account_exists_and_is_empty(env.state, env.coinbase):
 840        destroy_account(env.state, env.coinbase)
 841
 842    for address in output.accounts_to_delete:
 843        destroy_account(env.state, address)
 844
 845    for address in output.touched_accounts:
 846        if account_exists_and_is_empty(env.state, address):
 847            destroy_account(env.state, address)
 848
 849    return total_gas_used, output.logs, output.error
 850
 851
 852def validate_transaction(tx: Transaction) -> bool:
 853    """
 854    Verifies a transaction.
 855
 856    The gas in a transaction gets used to pay for the intrinsic cost of
 857    operations, therefore if there is insufficient gas then it would not
 858    be possible to execute a transaction and it will be declared invalid.
 859
 860    Additionally, the nonce of a transaction must not equal or exceed the
 861    limit defined in `EIP-2681 <https://eips.ethereum.org/EIPS/eip-2681>`_.
 862    In practice, defining the limit as ``2**64-1`` has no impact because
 863    sending ``2**64-1`` transactions is improbable. It's not strictly
 864    impossible though, ``2**64-1`` transactions is the entire capacity of the
 865    Ethereum blockchain at 2022 gas limits for a little over 22 years.
 866
 867    Parameters
 868    ----------
 869    tx :
 870        Transaction to validate.
 871
 872    Returns
 873    -------
 874    verified : `bool`
 875        True if the transaction can be executed, or False otherwise.
 876    """
 877    return calculate_intrinsic_cost(tx) <= tx.gas and tx.nonce < 2**64 - 1
 878
 879
 880def calculate_intrinsic_cost(tx: Transaction) -> Uint:
 881    """
 882    Calculates the gas that is charged before execution is started.
 883
 884    The intrinsic cost of the transaction is charged before execution has
 885    begun. Functions/operations in the EVM cost money to execute so this
 886    intrinsic cost is for the operations that need to be paid for as part of
 887    the transaction. Data transfer, for example, is part of this intrinsic
 888    cost. It costs ether to send data over the wire and that ether is
 889    accounted for in the intrinsic cost calculated in this function. This
 890    intrinsic cost must be calculated and paid for before execution in order
 891    for all operations to be implemented.
 892
 893    Parameters
 894    ----------
 895    tx :
 896        Transaction to compute the intrinsic cost of.
 897
 898    Returns
 899    -------
 900    verified : `ethereum.base_types.Uint`
 901        The intrinsic cost of the transaction.
 902    """
 903    data_cost = 0
 904
 905    for byte in tx.data:
 906        if byte == 0:
 907            data_cost += TX_DATA_COST_PER_ZERO
 908        else:
 909            data_cost += TX_DATA_COST_PER_NON_ZERO
 910
 911    if tx.to == Bytes0(b""):
 912        create_cost = TX_CREATE_COST
 913    else:
 914        create_cost = 0
 915
 916    access_list_cost = 0
 917    if isinstance(tx, (AccessListTransaction, FeeMarketTransaction)):
 918        for _address, keys in tx.access_list:
 919            access_list_cost += TX_ACCESS_LIST_ADDRESS_COST
 920            access_list_cost += len(keys) * TX_ACCESS_LIST_STORAGE_KEY_COST
 921
 922    return Uint(TX_BASE_COST + data_cost + create_cost + access_list_cost)
 923
 924
 925def recover_sender(chain_id: U64, tx: Transaction) -> Address:
 926    """
 927    Extracts the sender address from a transaction.
 928
 929    The v, r, and s values are the three parts that make up the signature
 930    of a transaction. In order to recover the sender of a transaction the two
 931    components needed are the signature (``v``, ``r``, and ``s``) and the
 932    signing hash of the transaction. The sender's public key can be obtained
 933    with these two values and therefore the sender address can be retrieved.
 934
 935    Parameters
 936    ----------
 937    tx :
 938        Transaction of interest.
 939    chain_id :
 940        ID of the executing chain.
 941
 942    Returns
 943    -------
 944    sender : `ethereum.fork_types.Address`
 945        The address of the account that signed the transaction.
 946    """
 947    r, s = tx.r, tx.s
 948
 949    ensure(0 < r and r < SECP256K1N, InvalidBlock)
 950    ensure(0 < s and s <= SECP256K1N // 2, InvalidBlock)
 951
 952    if isinstance(tx, LegacyTransaction):
 953        v = tx.v
 954        if v == 27 or v == 28:
 955            public_key = secp256k1_recover(
 956                r, s, v - 27, signing_hash_pre155(tx)
 957            )
 958        else:
 959            ensure(
 960                v == 35 + chain_id * 2 or v == 36 + chain_id * 2, InvalidBlock
 961            )
 962            public_key = secp256k1_recover(
 963                r, s, v - 35 - chain_id * 2, signing_hash_155(tx, chain_id)
 964            )
 965    elif isinstance(tx, AccessListTransaction):
 966        public_key = secp256k1_recover(
 967            r, s, tx.y_parity, signing_hash_2930(tx)
 968        )
 969    elif isinstance(tx, FeeMarketTransaction):
 970        public_key = secp256k1_recover(
 971            r, s, tx.y_parity, signing_hash_1559(tx)
 972        )
 973
 974    return Address(keccak256(public_key)[12:32])
 975
 976
 977def signing_hash_pre155(tx: LegacyTransaction) -> Hash32:
 978    """
 979    Compute the hash of a transaction used in a legacy (pre EIP 155) signature.
 980
 981    Parameters
 982    ----------
 983    tx :
 984        Transaction of interest.
 985
 986    Returns
 987    -------
 988    hash : `ethereum.crypto.hash.Hash32`
 989        Hash of the transaction.
 990    """
 991    return keccak256(
 992        rlp.encode(
 993            (
 994                tx.nonce,
 995                tx.gas_price,
 996                tx.gas,
 997                tx.to,
 998                tx.value,
 999                tx.data,
1000            )
1001        )
1002    )
1003
1004
1005def signing_hash_155(tx: LegacyTransaction, chain_id: U64) -> Hash32:
1006    """
1007    Compute the hash of a transaction used in a EIP 155 signature.
1008
1009    Parameters
1010    ----------
1011    tx :
1012        Transaction of interest.
1013    chain_id :
1014        The id of the current chain.
1015
1016    Returns
1017    -------
1018    hash : `ethereum.crypto.hash.Hash32`
1019        Hash of the transaction.
1020    """
1021    return keccak256(
1022        rlp.encode(
1023            (
1024                tx.nonce,
1025                tx.gas_price,
1026                tx.gas,
1027                tx.to,
1028                tx.value,
1029                tx.data,
1030                chain_id,
1031                Uint(0),
1032                Uint(0),
1033            )
1034        )
1035    )
1036
1037
1038def signing_hash_2930(tx: AccessListTransaction) -> Hash32:
1039    """
1040    Compute the hash of a transaction used in a EIP 2930 signature.
1041
1042    Parameters
1043    ----------
1044    tx :
1045        Transaction of interest.
1046
1047    Returns
1048    -------
1049    hash : `ethereum.crypto.hash.Hash32`
1050        Hash of the transaction.
1051    """
1052    return keccak256(
1053        b"\x01"
1054        + rlp.encode(
1055            (
1056                tx.chain_id,
1057                tx.nonce,
1058                tx.gas_price,
1059                tx.gas,
1060                tx.to,
1061                tx.value,
1062                tx.data,
1063                tx.access_list,
1064            )
1065        )
1066    )
1067
1068
1069def signing_hash_1559(tx: FeeMarketTransaction) -> Hash32:
1070    """
1071    Compute the hash of a transaction used in a EIP 1559 signature.
1072
1073    Parameters
1074    ----------
1075    tx :
1076        Transaction of interest.
1077
1078    Returns
1079    -------
1080    hash : `ethereum.crypto.hash.Hash32`
1081        Hash of the transaction.
1082    """
1083    return keccak256(
1084        b"\x02"
1085        + rlp.encode(
1086            (
1087                tx.chain_id,
1088                tx.nonce,
1089                tx.max_priority_fee_per_gas,
1090                tx.max_fee_per_gas,
1091                tx.gas,
1092                tx.to,
1093                tx.value,
1094                tx.data,
1095                tx.access_list,
1096            )
1097        )
1098    )
1099
1100
1101def compute_header_hash(header: Header) -> Hash32:
1102    """
1103    Computes the hash of a block header.
1104
1105    The header hash of a block is the canonical hash that is used to refer
1106    to a specific block and completely distinguishes a block from another.
1107
1108    ``keccak256`` is a function that produces a 256 bit hash of any input.
1109    It also takes in any number of bytes as an input and produces a single
1110    hash for them. A hash is a completely unique output for a single input.
1111    So an input corresponds to one unique hash that can be used to identify
1112    the input exactly.
1113
1114    Prior to using the ``keccak256`` hash function, the header must be
1115    encoded using the Recursive-Length Prefix. See :ref:`rlp`.
1116    RLP encoding the header converts it into a space-efficient format that
1117    allows for easy transfer of data between nodes. The purpose of RLP is to
1118    encode arbitrarily nested arrays of binary data, and RLP is the primary
1119    encoding method used to serialize objects in Ethereum's execution layer.
1120    The only purpose of RLP is to encode structure; encoding specific data
1121    types (e.g. strings, floats) is left up to higher-order protocols.
1122
1123    Parameters
1124    ----------
1125    header :
1126        Header of interest.
1127
1128    Returns
1129    -------
1130    hash : `ethereum.crypto.hash.Hash32`
1131        Hash of the header.
1132    """
1133    return keccak256(rlp.encode(header))
1134
1135
1136def check_gas_limit(gas_limit: Uint, parent_gas_limit: Uint) -> bool:
1137    """
1138    Validates the gas limit for a block.
1139
1140    The bounds of the gas limit, ``max_adjustment_delta``, is set as the
1141    quotient of the parent block's gas limit and the
1142    ``GAS_LIMIT_ADJUSTMENT_FACTOR``. Therefore, if the gas limit that is
1143    passed through as a parameter is greater than or equal to the *sum* of
1144    the parent's gas and the adjustment delta then the limit for gas is too
1145    high and fails this function's check. Similarly, if the limit is less
1146    than or equal to the *difference* of the parent's gas and the adjustment
1147    delta *or* the predefined ``GAS_LIMIT_MINIMUM`` then this function's
1148    check fails because the gas limit doesn't allow for a sufficient or
1149    reasonable amount of gas to be used on a block.
1150
1151    Parameters
1152    ----------
1153    gas_limit :
1154        Gas limit to validate.
1155
1156    parent_gas_limit :
1157        Gas limit of the parent block.
1158
1159    Returns
1160    -------
1161    check : `bool`
1162        True if gas limit constraints are satisfied, False otherwise.
1163    """
1164    max_adjustment_delta = parent_gas_limit // GAS_LIMIT_ADJUSTMENT_FACTOR
1165    if gas_limit >= parent_gas_limit + max_adjustment_delta:
1166        return False
1167    if gas_limit <= parent_gas_limit - max_adjustment_delta:
1168        return False
1169    if gas_limit < GAS_LIMIT_MINIMUM:
1170        return False
1171
1172    return True
1173
1174
1175def calculate_block_difficulty(
1176    block_number: Uint,
1177    block_timestamp: U256,
1178    parent_timestamp: U256,
1179    parent_difficulty: Uint,
1180    parent_has_ommers: bool,
1181) -> Uint:
1182    """
1183    Computes difficulty of a block using its header and parent header.
1184
1185    The difficulty is determined by the time the block was created after its
1186    parent. The ``offset`` is calculated using the parent block's difficulty,
1187    ``parent_difficulty``, and the timestamp between blocks. This offset is
1188    then added to the parent difficulty and is stored as the ``difficulty``
1189    variable. If the time between the block and its parent is too short, the
1190    offset will result in a positive number thus making the sum of
1191    ``parent_difficulty`` and ``offset`` to be a greater value in order to
1192    avoid mass forking. But, if the time is long enough, then the offset
1193    results in a negative value making the block less difficult than
1194    its parent.
1195
1196    The base standard for a block's difficulty is the predefined value
1197    set for the genesis block since it has no parent. So, a block
1198    can't be less difficult than the genesis block, therefore each block's
1199    difficulty is set to the maximum value between the calculated
1200    difficulty and the ``GENESIS_DIFFICULTY``.
1201
1202    Parameters
1203    ----------
1204    block_number :
1205        Block number of the block.
1206    block_timestamp :
1207        Timestamp of the block.
1208    parent_timestamp :
1209        Timestamp of the parent block.
1210    parent_difficulty :
1211        difficulty of the parent block.
1212    parent_has_ommers:
1213        does the parent have ommers.
1214
1215    Returns
1216    -------
1217    difficulty : `ethereum.base_types.Uint`
1218        Computed difficulty for a block.
1219    """
1220    offset = (
1221        int(parent_difficulty)
1222        // 2048
1223        * max(
1224            (2 if parent_has_ommers else 1)
1225            - int(block_timestamp - parent_timestamp) // 9,
1226            -99,
1227        )
1228    )
1229    difficulty = int(parent_difficulty) + offset
1230    # Historical Note: The difficulty bomb was not present in Ethereum at the
1231    # start of Frontier, but was added shortly after launch. However since the
1232    # bomb has no effect prior to block 200000 we pretend it existed from
1233    # genesis.
1234    # See https://github.com/ethereum/go-ethereum/pull/1588
1235    num_bomb_periods = ((int(block_number) - BOMB_DELAY_BLOCKS) // 100000) - 2
1236    if num_bomb_periods >= 0:
1237        difficulty += 2**num_bomb_periods
1238
1239    # Some clients raise the difficulty to `MINIMUM_DIFFICULTY` prior to adding
1240    # the bomb. This bug does not matter because the difficulty is always much
1241    # greater than `MINIMUM_DIFFICULTY` on Mainnet.
1242    return Uint(max(difficulty, MINIMUM_DIFFICULTY))