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