1  # Ethereum 2.0 Phase 0 -- Beacon Chain Fork Choice
  2  
  3  **NOTICE**: This document is a work in progress for researchers and implementers.
  4  
  5  ## Table of contents
  6  <!-- TOC -->
  7  
  8  - [Ethereum 2.0 Phase 0 -- Beacon Chain Fork Choice](#ethereum-20-phase-0----beacon-chain-fork-choice)
  9      - [Table of contents](#table-of-contents)
 10      - [Introduction](#introduction)
 11      - [Prerequisites](#prerequisites)
 12      - [Constants](#constants)
 13          - [Time parameters](#time-parameters)
 14      - [Beacon chain processing](#beacon-chain-processing)
 15          - [Beacon chain fork choice rule](#beacon-chain-fork-choice-rule)
 16  
 17  <!-- /TOC -->
 18  
 19  ## Introduction
 20  
 21  This document represents is the specification for the beacon chain fork choice rule, part of Ethereum 2.0 phase 0.
 22  
 23  ## Prerequisites
 24  
 25  All terminology, constants, functions, and protocol mechanics defined in the [Phase 0 -- The Beacon Chain](./0_beacon-chain.md) doc are requisite for this document and used throughout. Please see the Phase 0 doc before continuing and use as a reference throughout.
 26  
 27  ## Constants
 28  
 29  ### Time parameters
 30  
 31  | Name | Value | Unit | Duration |
 32  | - | - | :-: | :-: |
 33  | `SECONDS_PER_SLOT` | `6` | seconds | 6 seconds |
 34  
 35  ## Beacon chain processing
 36  
 37  Processing the beacon chain is similar to processing the Ethereum 1.0 chain. Clients download and process blocks and maintain a view of what is the current "canonical chain", terminating at the current "head". For a beacon block, `block`, to be processed by a node, the following conditions must be met:
 38  
 39  * The parent block with root `block.previous_block_root` has been processed and accepted.
 40  * An Ethereum 1.0 block pointed to by the `state.latest_eth1_data.block_hash` has been processed and accepted.
 41  * The node's Unix time is greater than or equal to `state.genesis_time + block.slot * SECONDS_PER_SLOT`.
 42  
 43  Note: Leap seconds mean that slots will occasionally last `SECONDS_PER_SLOT + 1` or `SECONDS_PER_SLOT - 1` seconds, possibly several times a year.
 44  
 45  Note: Nodes needs to have a clock that is roughly (i.e. within `SECONDS_PER_SLOT` seconds) synchronized with the other nodes.
 46  
 47  ### Beacon chain fork choice rule
 48  
 49  The beacon chain fork choice rule is a hybrid that combines justification and finality with Latest Message Driven (LMD) Greediest Heaviest Observed SubTree (GHOST). At any point in time a validator `v` subjectively calculates the beacon chain head as follows.
 50  
 51  * Abstractly define `Store` as the type of storage object for the chain data and `store` be the set of attestations and blocks that the validator `v` has observed and verified (in particular, block ancestors must be recursively verified). Attestations not yet included in any chain are still included in `store`.
 52  * Let `finalized_head` be the finalized block with the highest epoch. (A block `B` is finalized if there is a descendant of `B` in `store` the processing of which sets `B` as finalized.)
 53  * Let `justified_head` be the descendant of `finalized_head` with the highest epoch that has been justified for at least 1 epoch. (A block `B` is justified if there is a descendant of `B` in `store` the processing of which sets `B` as justified.) If no such descendant exists set `justified_head` to `finalized_head`.
 54  * Let `get_ancestor(store: Store, block: BeaconBlock, slot: Slot) -> BeaconBlock` be the ancestor of `block` with slot number `slot`. The `get_ancestor` function can be defined recursively as:
 55  
 56  ```python
 57  def get_ancestor(store: Store, block: BeaconBlock, slot: Slot) -> BeaconBlock:
 58      """
 59      Get the ancestor of ``block`` with slot number ``slot``; return ``None`` if not found.
 60      """
 61      if block.slot == slot:
 62          return block
 63      elif block.slot < slot:
 64          return None
 65      else:
 66          return get_ancestor(store, store.get_parent(block), slot)
 67  ```
 68  
 69  * Let `get_latest_attestation(store: Store, index: ValidatorIndex) -> Attestation` be the attestation with the highest slot number in `store` from the validator with the given `index`. If several such attestations exist, use the one the validator `v` observed first.
 70  * Let `get_latest_attestation_target(store: Store, index: ValidatorIndex) -> BeaconBlock` be the target block in the attestation `get_latest_attestation(store, index)`.
 71  * Let `get_children(store: Store, block: BeaconBlock) -> List[BeaconBlock]` returns the child blocks of the given `block`.
 72  * Let `justified_head_state` be the resulting `BeaconState` object from processing the chain up to the `justified_head`.
 73  * The `head` is `lmd_ghost(store, justified_head_state, justified_head)` where the function `lmd_ghost` is defined below. Note that the implementation below is suboptimal; there are implementations that compute the head in time logarithmic in slot count.
 74  
 75  ```python
 76  def lmd_ghost(store: Store, start_state: BeaconState, start_block: BeaconBlock) -> BeaconBlock:
 77      """
 78      Execute the LMD-GHOST algorithm to find the head ``BeaconBlock``.
 79      """
 80      validators = start_state.validator_registry
 81      active_validator_indices = get_active_validator_indices(validators, slot_to_epoch(start_state.slot))
 82      attestation_targets = [(i, get_latest_attestation_target(store, i)) for i in active_validator_indices]
 83  
 84      # Use the rounded-balance-with-hysteresis supplied by the protocol for fork
 85      # choice voting. This reduces the number of recomputations that need to be
 86      # made for optimized implementations that precompute and save data
 87      def get_vote_count(block: BeaconBlock) -> int:
 88          return sum(
 89              start_state.validator_registry[validator_index].effective_balance
 90              for validator_index, target in attestation_targets
 91              if get_ancestor(store, target, block.slot) == block
 92          )
 93  
 94      head = start_block
 95      while 1:
 96          children = get_children(store, head)
 97          if len(children) == 0:
 98              return head
 99          # Ties broken by favoring block with lexicographically higher root
100          head = max(children, key=lambda x: (get_vote_count(x), hash_tree_root(x)))
101  ```