forkChoice.ts

import {ChainForkConfig} from "@lodestar/config";
import {ForkSeq, SLOTS_PER_EPOCH, SLOTS_PER_HISTORICAL_ROOT} from "@lodestar/params";
import {
  DataAvailabilityStatus,
  EffectiveBalanceIncrements,
  IBeaconStateView,
  ZERO_HASH,
  computeEpochAtSlot,
  computeSlotsSinceEpochStart,
  computeStartSlotAtEpoch,
  getAttesterSlashableIndices,
  isExecutionBlockBodyType,
} from "@lodestar/state-transition";
import {
  AttesterSlashing,
  BeaconBlock,
  Epoch,
  IndexedAttestation,
  Root,
  RootHex,
  Slot,
  ValidatorIndex,
  isGloasBeaconBlock,
  phase0,
  ssz,
} from "@lodestar/types";
import {Logger, MapDef, fromHex, toRootHex} from "@lodestar/utils";
import {ForkChoiceMetrics} from "../metrics.js";
import {computeDeltas} from "../protoArray/computeDeltas.js";
import {ProtoArrayError, ProtoArrayErrorCode} from "../protoArray/errors.js";
import {
  ExecutionStatus,
  HEX_ZERO_HASH,
  LVHExecResponse,
  MaybeValidExecutionStatus,
  NULL_VOTE_INDEX,
  PayloadStatus,
  ProtoBlock,
  ProtoNode,
  VoteIndex,
  isGloasBlock,
} from "../protoArray/interface.js";
import {ProtoArray} from "../protoArray/protoArray.js";
import {ForkChoiceError, ForkChoiceErrorCode, InvalidAttestationCode, InvalidBlockCode} from "./errors.js";
import {
  AncestorResult,
  AncestorStatus,
  EpochDifference,
  IForkChoice,
  NotReorgedReason,
  ShouldOverrideForkChoiceUpdateResult,
} from "./interface.js";
import {CheckpointWithPayloadStatus, IForkChoiceStore, JustifiedBalances, toCheckpointWithPayload} from "./store.js";

export type ForkChoiceOpts = {
  proposerBoost?: boolean;
  proposerBoostReorg?: boolean;
  computeUnrealized?: boolean;
};

export enum UpdateHeadOpt {
  GetCanonicalHead = "getCanonicalHead", // Skip getProposerHead
  GetProposerHead = "getProposerHead", // With getProposerHead
  GetPredictedProposerHead = "getPredictedProposerHead", // With predictProposerHead
}

export type UpdateAndGetHeadOpt =
  // When slot is provided, it overrides fcStore.currentSlot for Gloas FULL vs EMPTY tie-breaker logic
  | {mode: UpdateHeadOpt.GetCanonicalHead; slot?: Slot}
  | {mode: UpdateHeadOpt.GetProposerHead; secFromSlot: number; slot: Slot}
  | {mode: UpdateHeadOpt.GetPredictedProposerHead; secFromSlot: number; slot: Slot};

// the initial vote epoch for all validators
const INIT_VOTE_SLOT: Slot = 0;

/**
 * Provides an implementation of "Ethereum Consensus -- Beacon Chain Fork Choice":
 *
 * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#fork-choice
 *
 * ## Detail
 *
 * This class wraps `ProtoArray` and provides:
 *
 * - Management of validators latest messages and balances
 * - Management of the justified/finalized checkpoints as seen by fork choice
 * - Queuing of attestations from the current slot
 *
 * This class MUST be used with the following considerations:
 *
 * - Time is not updated automatically, updateTime MUST be called every slot
 */
export class ForkChoice implements IForkChoice {
  irrecoverableError?: Error;
  /**
   * Votes currently tracked in the protoArray. Instead of tracking a VoteTracker of currentIndex, nextIndex and epoch,
   * we decompose the struct and track them in separate arrays for performance reason.
   *
   * For Gloas (ePBS), LatestMessage tracks slot instead of epoch and includes payload_present flag.
   * Spec: gloas/fork-choice.md#modified-latestmessage
   *
   * IMPORTANT: voteCurrentIndices and voteNextIndices point to the EXACT variant node index.
   * The payload status is encoded in the node index itself (different variants have different indices).
   * For example, if a validator votes for the EMPTY variant, voteNextIndices[i] points to that specific EMPTY node.
   */
  private readonly voteCurrentIndices: VoteIndex[];
  private readonly voteNextIndices: VoteIndex[];
  private readonly voteNextSlots: Slot[];

  /**
   * Attestations that arrived at the current slot and must be queued for later processing.
   * NOT currently tracked in the protoArray
   *
   * Modified for Gloas to track PayloadStatus per validator.
   * Maps: Slot -> BlockRoot -> ValidatorIndex -> PayloadStatus
   */
  private readonly queuedAttestations: MapDef<Slot, MapDef<RootHex, Map<ValidatorIndex, PayloadStatus>>> = new MapDef(
    () => new MapDef(() => new Map())
  );

  /**
   * It's inconsistent to count number of queued attestations at different intervals of slot.
   * Instead of that, we count number of queued attestations at the previous slot.
   */
  private queuedAttestationsPreviousSlot = 0;

  // Note: as of Jun 2022 Lodestar metrics show that 100% of the times updateHead() is called, synced = false.
  // Because we are processing attestations from gossip, recomputing scores is always necessary
  // /** Avoid having to compute deltas all the times. */
  // private synced = false;

  /** Cached head */
  private head: ProtoBlock;
  /**
   * Only cache attestation data root hex if it's tree backed since it's available.
   **/
  private validatedAttestationDatas = new Set<string>();
  /** Boost the entire branch with this proposer root as the leaf */
  private proposerBoostRoot: RootHex | null = null;
  /** Score to use in proposer boost, evaluated lazily from justified balances */
  private justifiedProposerBoostScore: number | null = null;
  /** The current effective balances */
  private balances: EffectiveBalanceIncrements;
  /**
   * Instantiates a Fork Choice from some existing components
   *
   * This is useful if the existing components have been loaded from disk after a process restart.
   */
  constructor(
    private readonly config: ChainForkConfig,
    private readonly fcStore: IForkChoiceStore,
    /** The underlying representation of the block DAG. */
    private readonly protoArray: ProtoArray,
    validatorCount: number,
    readonly metrics: ForkChoiceMetrics | null,
    private readonly opts?: ForkChoiceOpts,
    private readonly logger?: Logger
  ) {
    // initialize votes, they will grow in addLatestMessage() function below
    this.voteCurrentIndices = new Array(validatorCount).fill(NULL_VOTE_INDEX);
    this.voteNextIndices = new Array(validatorCount).fill(NULL_VOTE_INDEX);
    // when compute deltas, we ignore epoch if voteNextIndex is NULL_VOTE_INDEX anyway

    this.voteNextSlots = new Array(validatorCount).fill(0);

    this.head = this.updateHead();
    this.balances = this.fcStore.justified.balances;

    metrics?.forkChoice.votes.addCollect(() => {
      metrics.forkChoice.votes.set(this.voteNextSlots.length);
      metrics.forkChoice.queuedAttestations.set(this.queuedAttestationsPreviousSlot);
      metrics.forkChoice.validatedAttestationDatas.set(this.validatedAttestationDatas.size);
      metrics.forkChoice.balancesLength.set(this.balances.length);
      metrics.forkChoice.nodes.set(this.protoArray.nodes.length);
      metrics.forkChoice.indices.set(this.protoArray.indices.size);
    });
  }

  /**
   * Returns the block root of an ancestor of `blockRoot` at the given `slot`.
   * (Note: `slot` refers to the block that is *returned*, not the one that is supplied.)
   *
   * NOTE: May be expensive: potentially walks through the entire fork of head to finalized block
   *
   * ### Specification
   *
   * Equivalent to:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#get_ancestor
   */
  getAncestor(blockRoot: RootHex, ancestorSlot: Slot): ProtoNode {
    return this.protoArray.getAncestor(blockRoot, ancestorSlot);
  }

  /**
   * Get the cached head root
   */
  getHeadRoot(): RootHex {
    return this.getHead().blockRoot;
  }

  /**
   * Get the cached head
   */
  getHead(): ProtoBlock {
    return this.head;
  }

  /**
   *
   * A multiplexer to wrap around the traditional `updateHead()` according to the scenario
   * Scenarios as follow:
   *    Prepare to propose in the next slot: getHead() -> predictProposerHead()
   *    Proposing in the current slot: updateHead() -> getProposerHead()
   *    Others eg. initializing forkchoice, importBlock: updateHead()
   *
   * Only `GetProposerHead` returns additional field `isHeadTimely` and `notReorgedReason` for metrics purpose
   */
  updateAndGetHead(opt: UpdateAndGetHeadOpt): {
    head: ProtoBlock;
    isHeadTimely?: boolean;
    notReorgedReason?: NotReorgedReason;
  } {
    const {mode} = opt;

    const canonicalHeadBlock =
      mode === UpdateHeadOpt.GetPredictedProposerHead ? this.getHead() : this.updateHead(opt.slot);
    switch (mode) {
      case UpdateHeadOpt.GetPredictedProposerHead:
        return {head: this.predictProposerHead(canonicalHeadBlock, opt.secFromSlot, opt.slot)};
      case UpdateHeadOpt.GetProposerHead: {
        const {
          proposerHead: head,
          isHeadTimely,
          notReorgedReason,
        } = this.getProposerHead(canonicalHeadBlock, opt.secFromSlot, opt.slot);
        return {head, isHeadTimely, notReorgedReason};
      }
      case UpdateHeadOpt.GetCanonicalHead:
        return {head: canonicalHeadBlock};
      default:
        return {head: canonicalHeadBlock};
    }
  }

  // Called by `predictProposerHead` and `importBlock`. If the result is not same as blockRoot's block, return true else false
  // See https://github.com/ethereum/consensus-specs/blob/v1.5.0/specs/bellatrix/fork-choice.md#should_override_forkchoice_update
  // Return true if the given block passes all criteria to be re-orged out
  // Return false otherwise.
  // Note when proposer boost reorg is disabled, it always returns false
  shouldOverrideForkChoiceUpdate(
    headBlock: ProtoBlock,
    secFromSlot: number,
    currentSlot: Slot
  ): ShouldOverrideForkChoiceUpdateResult {
    if (headBlock === null) {
      // should not happen because this block just got imported. Fall back to no-reorg.
      return {shouldOverrideFcu: false, reason: NotReorgedReason.HeadBlockNotAvailable};
    }
    const {proposerBoost, proposerBoostReorg} = this.opts ?? {};
    // Skip re-org attempt if proposer boost (reorg) are disabled
    if (!proposerBoost || !proposerBoostReorg) {
      this.logger?.verbose("Skip shouldOverrideForkChoiceUpdate check since the related flags are disabled", {
        slot: currentSlot,
        proposerBoost,
        proposerBoostReorg,
      });
      return {shouldOverrideFcu: false, reason: NotReorgedReason.ProposerBoostReorgDisabled};
    }

    const parentBlock = this.protoArray.getBlock(
      headBlock.parentRoot,
      this.protoArray.getParentPayloadStatus(headBlock)
    );
    const proposalSlot = headBlock.slot + 1;

    // No reorg if parentBlock isn't available
    if (parentBlock === undefined) {
      return {shouldOverrideFcu: false, reason: NotReorgedReason.ParentBlockNotAvailable};
    }

    const {prelimProposerHead, prelimNotReorgedReason} = this.getPreliminaryProposerHead(
      headBlock,
      parentBlock,
      proposalSlot
    );

    if (prelimProposerHead === headBlock) {
      return {shouldOverrideFcu: false, reason: prelimNotReorgedReason ?? NotReorgedReason.Unknown};
    }

    const currentTimeOk =
      headBlock.slot === currentSlot ||
      (proposalSlot === currentSlot && this.isProposingOnTime(secFromSlot, currentSlot));
    if (!currentTimeOk) {
      return {shouldOverrideFcu: false, reason: NotReorgedReason.ReorgMoreThanOneSlot};
    }

    this.logger?.verbose("Block is weak. Should override forkchoice update", {
      blockRoot: headBlock.blockRoot,
      slot: currentSlot,
    });
    return {shouldOverrideFcu: true, parentBlock};
  }

  /**
   * Get the proposer boost root
   */
  getProposerBoostRoot(): RootHex {
    return this.proposerBoostRoot ?? HEX_ZERO_HASH;
  }

  /**
   * To predict the proposer head of the next slot. That is, to predict if proposer-boost-reorg could happen.
   * Reason why we can't be certain is because information of the head block is not fully available yet
   * since the current slot hasn't ended especially the attesters' votes.
   *
   * There is a chance we mispredict.
   *
   * By calling this function, we assume we are the proposer of next slot
   *
   */
  predictProposerHead(headBlock: ProtoBlock, secFromSlot: number, currentSlot: Slot): ProtoBlock {
    const {proposerBoost, proposerBoostReorg} = this.opts ?? {};
    // Skip re-org attempt if proposer boost (reorg) are disabled
    if (!proposerBoost || !proposerBoostReorg) {
      this.logger?.verbose("No proposer boost reorg prediction since the related flags are disabled", {
        slot: currentSlot,
        proposerBoost,
        proposerBoostReorg,
      });
      return headBlock;
    }

    const blockRoot = headBlock.blockRoot;
    const result = this.shouldOverrideForkChoiceUpdate(headBlock, secFromSlot, currentSlot);

    if (result.shouldOverrideFcu) {
      this.logger?.verbose("Current head is weak. Predicting next block to be built on parent of head.", {
        slot: currentSlot,
        proposerHead: result.parentBlock.blockRoot,
        weakHead: blockRoot,
      });
      return result.parentBlock;
    }

    this.logger?.verbose("Current head is strong. Predicting next block to be built on head", {
      slot: currentSlot,
      head: headBlock.blockRoot,
      reason: result.reason,
    });

    return headBlock;
  }

  /**
   *
   * This function takes in the canonical head block and determine the proposer head (canonical head block or its parent)
   * https://github.com/ethereum/consensus-specs/pull/3034 for info about proposer boost reorg
   * This function should only be called during block proposal and only be called after `updateHead()` in `updateAndGetHead()`
   *
   * Same as https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#get_proposer_head
   */
  getProposerHead(
    headBlock: ProtoBlock,
    secFromSlot: number,
    slot: Slot
  ): {proposerHead: ProtoBlock; isHeadTimely: boolean; notReorgedReason?: NotReorgedReason} {
    const isHeadTimely = headBlock.timeliness;
    let proposerHead = headBlock;

    // Skip re-org attempt if proposer boost (reorg) are disabled
    const {proposerBoost, proposerBoostReorg} = this.opts ?? {};
    if (!proposerBoost || !proposerBoostReorg) {
      this.logger?.verbose("No proposer boost reorg attempt since the related flags are disabled", {
        slot,
        proposerBoost,
        proposerBoostReorg,
      });
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.ProposerBoostReorgDisabled};
    }

    const parentBlock = this.protoArray.getBlock(
      headBlock.parentRoot,
      this.protoArray.getParentPayloadStatus(headBlock)
    );

    // No reorg if parentBlock isn't available
    if (parentBlock === undefined) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.ParentBlockNotAvailable};
    }

    const {prelimProposerHead, prelimNotReorgedReason} = this.getPreliminaryProposerHead(headBlock, parentBlock, slot);

    if (prelimProposerHead === headBlock && prelimNotReorgedReason !== undefined) {
      return {proposerHead, isHeadTimely, notReorgedReason: prelimNotReorgedReason};
    }

    // Only re-org if we are proposing on-time
    if (!this.isProposingOnTime(secFromSlot, slot)) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.NotProposingOnTime};
    }

    // No reorg if attempted reorg is more than a single slot
    // Half of single_slot_reorg check in the spec is done in getPreliminaryProposerHead()
    const currentTimeOk = headBlock.slot + 1 === slot;
    if (!currentTimeOk) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.ReorgMoreThanOneSlot};
    }

    // No reorg if proposer boost is still in effect
    const isProposerBoostWornOff = this.proposerBoostRoot !== headBlock.blockRoot;
    if (!isProposerBoostWornOff) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.ProposerBoostNotWornOff};
    }

    // No reorg if headBlock is "not weak" ie. headBlock's weight exceeds (REORG_HEAD_WEIGHT_THRESHOLD = 20)% of total attester weight
    // https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#is_head_weak
    const reorgThreshold = getCommitteeFraction(this.fcStore.justified.totalBalance, {
      slotsPerEpoch: SLOTS_PER_EPOCH,
      committeePercent: this.config.REORG_HEAD_WEIGHT_THRESHOLD,
    });
    const headNode = this.protoArray.getNode(headBlock.blockRoot, headBlock.payloadStatus);
    // If headNode is unavailable, give up reorg
    if (headNode === undefined || headNode.weight >= reorgThreshold) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.HeadBlockNotWeak};
    }

    // No reorg if parentBlock is "not strong" ie. parentBlock's weight is less than or equal to (REORG_PARENT_WEIGHT_THRESHOLD = 160)% of total attester weight
    // https://github.com/ethereum/consensus-specs/blob/v1.6.1/specs/phase0/fork-choice.md#is_parent_strong
    const parentThreshold = getCommitteeFraction(this.fcStore.justified.totalBalance, {
      slotsPerEpoch: SLOTS_PER_EPOCH,
      committeePercent: this.config.REORG_PARENT_WEIGHT_THRESHOLD,
    });
    const parentNode = this.protoArray.getNode(parentBlock.blockRoot, parentBlock.payloadStatus);
    // If parentNode is unavailable, give up reorg
    if (parentNode === undefined || parentNode.weight <= parentThreshold) {
      return {proposerHead, isHeadTimely, notReorgedReason: NotReorgedReason.ParentBlockNotStrong};
    }

    // Reorg if all above checks fail
    this.logger?.verbose("Performing single-slot reorg to remove current weak head", {
      slot,
      proposerHead: parentBlock.blockRoot,
      weakHead: headBlock.blockRoot,
    });
    proposerHead = parentBlock;

    return {proposerHead, isHeadTimely};
  }

  /**
   * Run the fork choice rule to determine the head.
   * Update the head cache.
   *
   * Very expensive function (400ms / run as of Aug 2021). Call when the head really needs to be re-calculated.
   *
   * ## Specification
   *
   * Is equivalent to:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#get_head
   *
   * @param slot - If provided, overrides fcStore.currentSlot for Gloas FULL vs EMPTY tie-breaker logic
   */
  updateHead(slot?: Slot): ProtoBlock {
    // balances is not changed but votes are changed

    // NOTE: In current Lodestar metrics, 100% of forkChoiceRequests this.synced = false.
    // No need to cache computeDeltas()
    //
    // TODO: In current Lodestar metrics, 100% of forkChoiceRequests result in a changed head.
    // No need to cache the head anymore

    // Check if scores need to be calculated/updated
    const oldBalances = this.balances;
    const newBalances = this.fcStore.justified.balances;
    const computeDeltasMetrics = this.metrics?.forkChoice.computeDeltas;

    const timer = computeDeltasMetrics?.duration.startTimer();
    const {
      deltas,
      equivocatingValidators,
      oldInactiveValidators,
      newInactiveValidators,
      unchangedVoteValidators,
      newVoteValidators,
    } = computeDeltas(
      this.protoArray.nodes.length,
      this.voteCurrentIndices,
      this.voteNextIndices,
      oldBalances,
      newBalances,
      this.fcStore.equivocatingIndices
    );
    timer?.();

    computeDeltasMetrics?.deltasCount.set(deltas.length);
    computeDeltasMetrics?.zeroDeltasCount.set(deltas.filter((d) => d === 0).length);
    computeDeltasMetrics?.equivocatingValidators.set(equivocatingValidators);
    computeDeltasMetrics?.oldInactiveValidators.set(oldInactiveValidators);
    computeDeltasMetrics?.newInactiveValidators.set(newInactiveValidators);
    computeDeltasMetrics?.unchangedVoteValidators.set(unchangedVoteValidators);
    computeDeltasMetrics?.newVoteValidators.set(newVoteValidators);

    this.balances = newBalances;
    /**
     * The structure in line with deltas to propagate boost up the branch
     * starting from the proposerIndex
     */
    let proposerBoost: {root: RootHex; score: number} | null = null;
    if (this.opts?.proposerBoost && this.proposerBoostRoot) {
      const proposerBoostScore =
        this.justifiedProposerBoostScore ??
        getCommitteeFraction(this.fcStore.justified.totalBalance, {
          slotsPerEpoch: SLOTS_PER_EPOCH,
          committeePercent: this.config.PROPOSER_SCORE_BOOST,
        });
      proposerBoost = {root: this.proposerBoostRoot, score: proposerBoostScore};
      this.justifiedProposerBoostScore = proposerBoostScore;
    }

    // When preparing for the next slot, pass slot as currentSlot + 1 to choose FULL vs EMPTY
    // This is important for Gloas tie-breaker logic
    const currentSlot = slot ?? this.fcStore.currentSlot;
    this.protoArray.applyScoreChanges({
      deltas,
      proposerBoost,
      justifiedEpoch: this.fcStore.justified.checkpoint.epoch,
      justifiedRoot: this.fcStore.justified.checkpoint.rootHex,
      finalizedEpoch: this.fcStore.finalizedCheckpoint.epoch,
      finalizedRoot: this.fcStore.finalizedCheckpoint.rootHex,
      currentSlot,
    });

    // findHead returns the ProtoNode representing the head
    const head = this.protoArray.findHead(this.fcStore.justified.checkpoint.rootHex, currentSlot);

    this.head = head;
    return this.head;
  }

  /**
   * An iteration over protoArray to get present slots, to be called preemptively
   * from prepareNextSlot to prevent delay on produceBlindedBlock
   * @param windowStart is the slot after which (excluding) to provide present slots
   */
  getSlotsPresent(windowStart: number): number {
    return this.protoArray.nodes.filter((node) => node.slot > windowStart).length;
  }

  /** Very expensive function, iterates the entire ProtoArray. Called only in debug API */
  getHeads(): ProtoBlock[] {
    return this.protoArray.nodes.filter((node) => node.bestChild === undefined);
  }

  /** This is for the debug API only */
  getAllNodes(): ProtoNode[] {
    return this.protoArray.nodes;
  }

  getFinalizedCheckpoint(): CheckpointWithPayloadStatus {
    return this.fcStore.finalizedCheckpoint;
  }

  getJustifiedCheckpoint(): CheckpointWithPayloadStatus {
    return this.fcStore.justified.checkpoint;
  }

  /**
   * Add `block` to the fork choice DAG.
   *
   * ## Specification
   *
   * Approximates:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#on_block
   *
   * It only approximates the specification since it does not run the `state_transition` check.
   * That should have already been called upstream and it's too expensive to call again.
   *
   * ## Notes:
   *
   * The supplied block **must** pass the `state_transition` function as it will not be run here.
   *
   * `justifiedBalances` balances of justified state which is updated synchronously.
   * This ensures that the forkchoice is never out of sync.
   */
  onBlock(
    block: BeaconBlock,
    state: IBeaconStateView,
    blockDelaySec: number,
    currentSlot: Slot,
    executionStatus: MaybeValidExecutionStatus,
    dataAvailabilityStatus: DataAvailabilityStatus
  ): ProtoBlock {
    const {parentRoot, slot} = block;
    const parentRootHex = toRootHex(parentRoot);
    // Parent block must be known because state_transition would have failed otherwise.
    const parentHashHex = isGloasBeaconBlock(block)
      ? toRootHex(block.body.signedExecutionPayloadBid.message.parentBlockHash)
      : null;
    const parentBlock = this.protoArray.getParent(parentRootHex, parentHashHex);
    if (!parentBlock) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_BLOCK,
        err: {
          code: InvalidBlockCode.UNKNOWN_PARENT,
          root: parentRootHex,
          hash: parentHashHex,
        },
      });
    }

    // Blocks cannot be in the future. If they are, their consideration must be delayed until
    // the are in the past.
    //
    // Note: presently, we do not delay consideration. We just drop the block.
    if (slot > this.fcStore.currentSlot) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_BLOCK,
        err: {
          code: InvalidBlockCode.FUTURE_SLOT,
          currentSlot: this.fcStore.currentSlot,
          blockSlot: slot,
        },
      });
    }

    // Check that block is later than the finalized epoch slot (optimization to reduce calls to
    // get_ancestor).
    const finalizedSlot = computeStartSlotAtEpoch(this.fcStore.finalizedCheckpoint.epoch);
    if (slot <= finalizedSlot) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_BLOCK,
        err: {
          code: InvalidBlockCode.FINALIZED_SLOT,
          finalizedSlot,
          blockSlot: slot,
        },
      });
    }

    // Check block is a descendant of the finalized block at the checkpoint finalized slot.
    const blockAncestorNode = this.getAncestor(parentRootHex, finalizedSlot);
    const fcStoreFinalized = this.fcStore.finalizedCheckpoint;
    if (
      blockAncestorNode.blockRoot !== fcStoreFinalized.rootHex ||
      blockAncestorNode.payloadStatus !== fcStoreFinalized.payloadStatus
    ) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_BLOCK,
        err: {
          code: InvalidBlockCode.NOT_FINALIZED_DESCENDANT,
          finalizedRoot: fcStoreFinalized.rootHex,
          blockAncestor: blockAncestorNode.blockRoot,
        },
      });
    }

    const blockRoot = this.config.getForkTypes(slot).BeaconBlock.hashTreeRoot(block);
    const blockRootHex = toRootHex(blockRoot);

    // Assign proposer score boost if the block is timely
    // before attesting interval = before 1st interval
    const isTimely = this.isBlockTimely(block, blockDelaySec);
    if (
      this.opts?.proposerBoost &&
      isTimely &&
      // only boost the first block we see
      this.proposerBoostRoot === null
    ) {
      this.proposerBoostRoot = blockRootHex;
    }

    // Get justified checkpoint with payload status for Gloas
    const justifiedPayloadStatus = getCheckpointPayloadStatus(
      this.config,
      state,
      state.currentJustifiedCheckpoint.epoch
    );
    const justifiedCheckpoint = toCheckpointWithPayload(state.currentJustifiedCheckpoint, justifiedPayloadStatus);
    const stateJustifiedEpoch = justifiedCheckpoint.epoch;

    // Get finalized checkpoint with payload status for Gloas
    const finalizedPayloadStatus = getCheckpointPayloadStatus(this.config, state, state.finalizedCheckpoint.epoch);
    const finalizedCheckpoint = toCheckpointWithPayload(state.finalizedCheckpoint, finalizedPayloadStatus);

    // Justified balances for `justifiedCheckpoint` are new to the fork-choice. Compute them on demand only if
    // the justified checkpoint changes
    this.updateCheckpoints(justifiedCheckpoint, finalizedCheckpoint, () =>
      this.fcStore.justifiedBalancesGetter(justifiedCheckpoint, state)
    );

    const blockEpoch = computeEpochAtSlot(slot);

    // same logic to compute_pulled_up_tip in the spec, making it inline because of reusing variables
    // If the parent checkpoints are already at the same epoch as the block being imported,
    // it's impossible for the unrealized checkpoints to differ from the parent's. This
    // holds true because:
    //
    // 1. A child block cannot have lower FFG checkpoints than its parent.
    // 2. A block in epoch `N` cannot contain attestations which would justify an epoch higher than `N`.
    // 3. A block in epoch `N` cannot contain attestations which would finalize an epoch higher than `N - 1`.
    //
    // This is an optimization. It should reduce the amount of times we run
    // `process_justification_and_finalization` by approximately 1/3rd when the chain is
    // performing optimally.
    let unrealizedJustifiedCheckpoint: CheckpointWithPayloadStatus;
    let unrealizedFinalizedCheckpoint: CheckpointWithPayloadStatus;
    if (this.opts?.computeUnrealized) {
      if (
        parentBlock.unrealizedJustifiedEpoch === blockEpoch &&
        parentBlock.unrealizedFinalizedEpoch + 1 >= blockEpoch
      ) {
        // reuse from parent, happens at 1/3 last blocks of epoch as monitored in mainnet
        // Get payload status for unrealized justified checkpoint
        const unrealizedJustifiedPayloadStatus = getCheckpointPayloadStatus(
          this.config,
          state,
          parentBlock.unrealizedJustifiedEpoch
        );
        unrealizedJustifiedCheckpoint = {
          epoch: parentBlock.unrealizedJustifiedEpoch,
          root: fromHex(parentBlock.unrealizedJustifiedRoot),
          rootHex: parentBlock.unrealizedJustifiedRoot,
          payloadStatus: unrealizedJustifiedPayloadStatus,
        };
        // Get payload status for unrealized finalized checkpoint
        const unrealizedFinalizedPayloadStatus = getCheckpointPayloadStatus(
          this.config,
          state,
          parentBlock.unrealizedFinalizedEpoch
        );
        unrealizedFinalizedCheckpoint = {
          epoch: parentBlock.unrealizedFinalizedEpoch,
          root: fromHex(parentBlock.unrealizedFinalizedRoot),
          rootHex: parentBlock.unrealizedFinalizedRoot,
          payloadStatus: unrealizedFinalizedPayloadStatus,
        };
      } else {
        // compute new, happens 2/3 first blocks of epoch as monitored in mainnet
        const unrealized = state.computeUnrealizedCheckpoints();
        // Get payload status for unrealized justified checkpoint
        const unrealizedJustifiedPayloadStatus = getCheckpointPayloadStatus(
          this.config,
          state,
          unrealized.justifiedCheckpoint.epoch
        );
        unrealizedJustifiedCheckpoint = toCheckpointWithPayload(
          unrealized.justifiedCheckpoint,
          unrealizedJustifiedPayloadStatus
        );
        // Get payload status for unrealized finalized checkpoint
        const unrealizedFinalizedPayloadStatus = getCheckpointPayloadStatus(
          this.config,
          state,
          unrealized.finalizedCheckpoint.epoch
        );
        unrealizedFinalizedCheckpoint = toCheckpointWithPayload(
          unrealized.finalizedCheckpoint,
          unrealizedFinalizedPayloadStatus
        );
      }
    } else {
      unrealizedJustifiedCheckpoint = justifiedCheckpoint;
      unrealizedFinalizedCheckpoint = finalizedCheckpoint;
    }

    // Un-realized checkpoints
    // Update best known unrealized justified & finalized checkpoints
    this.updateUnrealizedCheckpoints(unrealizedJustifiedCheckpoint, unrealizedFinalizedCheckpoint, () =>
      this.fcStore.justifiedBalancesGetter(unrealizedJustifiedCheckpoint, state)
    );

    // If block is from past epochs, try to update store's justified & finalized checkpoints right away
    if (blockEpoch < computeEpochAtSlot(currentSlot)) {
      this.updateCheckpoints(unrealizedJustifiedCheckpoint, unrealizedFinalizedCheckpoint, () =>
        this.fcStore.justifiedBalancesGetter(unrealizedJustifiedCheckpoint, state)
      );
    }

    const targetSlot = computeStartSlotAtEpoch(blockEpoch);
    const targetRoot = slot === targetSlot ? blockRoot : state.getBlockRootAtSlot(targetSlot);

    // This does not apply a vote to the block, it just makes fork choice aware of the block so
    // it can still be identified as the head even if it doesn't have any votes.
    const protoBlock: ProtoBlock = {
      slot: slot,
      blockRoot: blockRootHex,
      parentRoot: parentRootHex,
      targetRoot: toRootHex(targetRoot),
      stateRoot: toRootHex(block.stateRoot),
      timeliness: isTimely,

      justifiedEpoch: stateJustifiedEpoch,
      justifiedRoot: toRootHex(state.currentJustifiedCheckpoint.root),
      finalizedEpoch: finalizedCheckpoint.epoch,
      finalizedRoot: toRootHex(state.finalizedCheckpoint.root),
      unrealizedJustifiedEpoch: unrealizedJustifiedCheckpoint.epoch,
      unrealizedJustifiedRoot: unrealizedJustifiedCheckpoint.rootHex,
      unrealizedFinalizedEpoch: unrealizedFinalizedCheckpoint.epoch,
      unrealizedFinalizedRoot: unrealizedFinalizedCheckpoint.rootHex,

      ...(isGloasBeaconBlock(block)
        ? {
            executionPayloadBlockHash: toRootHex(block.body.signedExecutionPayloadBid.message.parentBlockHash), // post-gloas, we don't know payload hash until we import execution payload. Set to parent payload hash for now
            executionPayloadNumber: (() => {
              // Determine parent's execution payload number based on which variant the block extends
              const parentBlockHashFromBid = toRootHex(block.body.signedExecutionPayloadBid.message.parentBlockHash);

              // If parent is pre-merge, return 0
              if (parentBlock.executionPayloadBlockHash === null) {
                return 0;
              }

              // If parent is pre-Gloas, it only has FULL variant
              if (parentBlock.parentBlockHash === null) {
                return parentBlock.executionPayloadNumber;
              }

              // Parent is Gloas: get the variant that matches the parentBlockHash from bid
              const parentVariant = this.getBlockHexAndBlockHash(parentRootHex, parentBlockHashFromBid);
              if (parentVariant && parentVariant.executionPayloadBlockHash !== null) {
                return parentVariant.executionPayloadNumber;
              }
              // Fallback to parent block's number (we know it's post-merge from check above)
              return parentBlock.executionPayloadNumber;
            })(),
            executionStatus: this.getPostGloasExecStatus(executionStatus),
            dataAvailabilityStatus,
          }
        : isExecutionBlockBodyType(block.body) && state.isExecutionStateType && state.isExecutionEnabled(block)
          ? {
              executionPayloadBlockHash: toRootHex(block.body.executionPayload.blockHash),
              executionPayloadNumber: block.body.executionPayload.blockNumber,
              executionStatus: this.getPreGloasExecStatus(executionStatus),
              dataAvailabilityStatus,
            }
          : {
              executionPayloadBlockHash: null,
              executionStatus: this.getPreMergeExecStatus(executionStatus),
              dataAvailabilityStatus: this.getPreMergeDataStatus(dataAvailabilityStatus),
            }),

      payloadStatus: isGloasBeaconBlock(block) ? PayloadStatus.PENDING : PayloadStatus.FULL,
      parentBlockHash: parentHashHex,
    };

    this.protoArray.onBlock(protoBlock, currentSlot, this.proposerBoostRoot);

    return protoBlock;
  }

  /**
   * Register `attestation` with the fork choice DAG so that it may influence future calls to `getHead`.
   *
   * ## Specification
   *
   * Approximates:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#on_attestation
   *
   * It only approximates the specification since it does not perform
   * `is_valid_indexed_attestation` since that should already have been called upstream and it's
   * too expensive to call again.
   *
   * ## Notes:
   *
   * The supplied `attestation` **must** pass the `in_valid_indexed_attestation` function as it
   * will not be run here.
   */
  onAttestation(attestation: IndexedAttestation, attDataRoot: string, forceImport?: boolean): void {
    // Ignore any attestations to the zero hash.
    //
    // This is an edge case that results from the spec aliasing the zero hash to the genesis
    // block. Attesters may attest to the zero hash if they have never seen a block.
    //
    // We have two options here:
    //
    //  1. Apply all zero-hash attestations to the genesis block.
    //  2. Ignore all attestations to the zero hash.
    //
    // (1) becomes weird once we hit finality and fork choice drops the genesis block. (2) is
    // fine because votes to the genesis block are not useful; all validators implicitly attest
    // to genesis just by being present in the chain.
    const attestationData = attestation.data;
    const {slot, beaconBlockRoot} = attestationData;
    const blockRootHex = toRootHex(beaconBlockRoot);
    const targetEpoch = attestationData.target.epoch;
    if (ssz.Root.equals(beaconBlockRoot, ZERO_HASH)) {
      return;
    }

    this.validateOnAttestation(attestation, slot, blockRootHex, targetEpoch, attDataRoot, forceImport);

    // Pre-gloas: payload is always present
    // Post-gloas:
    // - always add weight to PENDING
    // - if message.slot > block.slot, it also add weights to FULL or EMPTY
    let payloadStatus: PayloadStatus;

    // We need to retrieve block to check if it's Gloas and to compare slot
    // https://github.com/ethereum/consensus-specs/blob/v1.7.0-alpha.1/specs/gloas/fork-choice.md#new-is_supporting_vote
    const block = this.getBlockHexDefaultStatus(blockRootHex);

    if (block && isGloasBlock(block)) {
      // Post-Gloas block: determine FULL/EMPTY/PENDING based on slot and committee index
      // If slot > block.slot, we can determine FULL or EMPTY. Else always PENDING
      if (slot > block.slot) {
        if (attestationData.index === 1) {
          payloadStatus = PayloadStatus.FULL;
        } else if (attestationData.index === 0) {
          payloadStatus = PayloadStatus.EMPTY;
        } else {
          throw new ForkChoiceError({
            code: ForkChoiceErrorCode.INVALID_ATTESTATION,
            err: {
              code: InvalidAttestationCode.INVALID_DATA_INDEX,
              index: attestationData.index,
            },
          });
        }
      } else {
        payloadStatus = PayloadStatus.PENDING;
      }
    } else {
      // Pre-Gloas block or block not found: always FULL
      payloadStatus = PayloadStatus.FULL;
    }

    if (slot < this.fcStore.currentSlot) {
      for (const validatorIndex of attestation.attestingIndices) {
        if (!this.fcStore.equivocatingIndices.has(validatorIndex)) {
          this.addLatestMessage(validatorIndex, slot, blockRootHex, payloadStatus);
        }
      }
    } else {
      // The spec declares:
      //
      // ```
      // Attestations can only affect the fork choice of subsequent slots.
      // Delay consideration in the fork choice until their slot is in the past.
      // ```
      const byRoot = this.queuedAttestations.getOrDefault(slot);
      const validatorVotes = byRoot.getOrDefault(blockRootHex);
      for (const validatorIndex of attestation.attestingIndices) {
        if (!this.fcStore.equivocatingIndices.has(validatorIndex)) {
          validatorVotes.set(validatorIndex, payloadStatus);
        }
      }
    }
  }

  /**
   * Small different from the spec:
   * We already call is_slashable_attestation_data() and is_valid_indexed_attestation
   * in state transition so no need to do it again
   */
  onAttesterSlashing(attesterSlashing: AttesterSlashing): void {
    // TODO: we already call in in state-transition, find a way not to recompute it again
    const intersectingIndices = getAttesterSlashableIndices(attesterSlashing);
    for (const validatorIndex of intersectingIndices) {
      this.fcStore.equivocatingIndices.add(validatorIndex);
    }
  }

  /**
   * Process a PTC (Payload Timeliness Committee) message
   * Updates the PTC votes for multiple validators attesting to a block
   * Spec: gloas/fork-choice.md#new-on_payload_attestation_message
   */
  notifyPtcMessages(blockRoot: RootHex, ptcIndices: number[], payloadPresent: boolean): void {
    this.protoArray.notifyPtcMessages(blockRoot, ptcIndices, payloadPresent);
  }

  /**
   * Notify fork choice that an execution payload has arrived (Gloas fork)
   * Creates the FULL variant of a Gloas block when the payload becomes available
   * Spec: gloas/fork-choice.md#new-on_execution_payload
   */
  onExecutionPayload(
    blockRoot: RootHex,
    executionPayloadBlockHash: RootHex,
    executionPayloadNumber: number,
    executionPayloadStateRoot: RootHex
  ): void {
    this.protoArray.onExecutionPayload(
      blockRoot,
      this.fcStore.currentSlot,
      executionPayloadBlockHash,
      executionPayloadNumber,
      executionPayloadStateRoot,
      this.proposerBoostRoot
    );
  }

  /**
   * Call `onTick` for all slots between `fcStore.getCurrentSlot()` and the provided `currentSlot`.
   * This should only be called once per slot because:
   *   - calling this multiple times in the same slot does not update `votes`
   *     - new attestations in the current slot must stay in the queue
   *     - new attestations in the old slots are applied to the `votes` already
   *   - also side effect of this function is `validatedAttestationDatas` reseted
   */
  updateTime(currentSlot: Slot): void {
    if (this.fcStore.currentSlot >= currentSlot) return;
    while (this.fcStore.currentSlot < currentSlot) {
      const previousSlot = this.fcStore.currentSlot;
      // Note: we are relying upon `onTick` to update `fcStore.time` to ensure we don't get stuck in a loop.
      this.onTick(previousSlot + 1);
    }

    this.queuedAttestationsPreviousSlot = 0;
    // Process any attestations that might now be eligible.
    this.processAttestationQueue();
    this.validatedAttestationDatas = new Set();
  }

  getTime(): Slot {
    return this.fcStore.currentSlot;
  }

  /** Returns `true` if the block is known **and** a descendant of the finalized root. */
  hasBlock(blockRoot: Root): boolean {
    return this.hasBlockHex(toRootHex(blockRoot));
  }
  /** Returns a `ProtoBlock` if the block is known **and** a descendant of the finalized root. */
  getBlock(blockRoot: Root, payloadStatus: PayloadStatus): ProtoBlock | null {
    return this.getBlockHex(toRootHex(blockRoot), payloadStatus);
  }

  getBlockDefaultStatus(blockRoot: Root): ProtoBlock | null {
    return this.getBlockHexDefaultStatus(toRootHex(blockRoot));
  }

  /**
   * Returns `true` if the block is known **and** a descendant of the finalized root.
   * Uses default variant (PENDING for Gloas, FULL for pre-Gloas).
   */
  hasBlockHex(blockRoot: RootHex): boolean {
    const defaultStatus = this.protoArray.getDefaultVariant(blockRoot);
    const node = defaultStatus !== undefined ? this.protoArray.getNode(blockRoot, defaultStatus) : undefined;
    if (node === undefined) {
      return false;
    }

    return this.protoArray.isFinalizedRootOrDescendant(node);
  }

  /**
   * Same to hasBlock but without checking if the block is a descendant of the finalized root.
   */
  hasBlockUnsafe(blockRoot: Root): boolean {
    return this.hasBlockHexUnsafe(toRootHex(blockRoot));
  }

  /**
   * Same to hasBlockHex but without checking if the block is a descendant of the finalized root.
   */
  hasBlockHexUnsafe(blockRoot: RootHex): boolean {
    return this.protoArray.hasBlock(blockRoot);
  }

  /**
   * Returns a MUTABLE `ProtoBlock` if the block is known **and** a descendant of the finalized root.
   */
  getBlockHex(blockRoot: RootHex, payloadStatus: PayloadStatus): ProtoBlock | null {
    const node = this.protoArray.getNode(blockRoot, payloadStatus);
    if (!node) {
      return null;
    }

    if (!this.protoArray.isFinalizedRootOrDescendant(node)) {
      return null;
    }

    return {
      ...node,
    };
  }

  /**
   * Returns a `ProtoBlock` with the default variant for the given block root
   * - Pre-Gloas blocks: returns FULL variant (only variant)
   * - Gloas blocks: returns PENDING variant
   *
   * Use this when you need the canonical block reference regardless of payload status.
   * For searching by execution payload hash and variant-specific info, use `getBlockHexAndBlockHash` instead.
   */
  getBlockHexDefaultStatus(blockRoot: RootHex): ProtoBlock | null {
    const defaultStatus = this.protoArray.getDefaultVariant(blockRoot);
    if (defaultStatus === undefined) {
      return null;
    }

    return this.getBlockHex(blockRoot, defaultStatus);
  }

  /**
   * Returns EMPTY or FULL `ProtoBlock` that has matching block root and block hash
   */
  getBlockHexAndBlockHash(blockRoot: RootHex, blockHash: RootHex): ProtoBlock | null {
    return this.protoArray.getBlockHexAndBlockHash(blockRoot, blockHash);
  }

  getJustifiedBlock(): ProtoBlock {
    const {rootHex, payloadStatus} = this.fcStore.justified.checkpoint;
    const block = this.getBlockHex(rootHex, payloadStatus);
    if (!block) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.MISSING_PROTO_ARRAY_BLOCK,
        root: rootHex,
      });
    }
    return block;
  }

  getFinalizedBlock(): ProtoBlock {
    const {rootHex, payloadStatus} = this.fcStore.finalizedCheckpoint;
    const block = this.getBlockHex(rootHex, payloadStatus);
    if (!block) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.MISSING_PROTO_ARRAY_BLOCK,
        root: rootHex,
      });
    }
    return block;
  }

  getFinalizedCheckpointSlot(): Slot {
    const finalizedEpoch = this.fcStore.finalizedCheckpoint.epoch;
    return computeStartSlotAtEpoch(finalizedEpoch);
  }

  /**
   * Returns true if the `descendantRoot` has an ancestor with `ancestorRoot`.
   *
   * Always returns `false` if either input roots are unknown.
   * Still returns `true` if `ancestorRoot===descendantRoot` (and the roots are known)
   */
  isDescendant(
    ancestorRoot: RootHex,
    ancestorPayloadStatus: PayloadStatus,
    descendantRoot: RootHex,
    descendantPayloadStatus: PayloadStatus
  ): boolean {
    return this.protoArray.isDescendant(ancestorRoot, ancestorPayloadStatus, descendantRoot, descendantPayloadStatus);
  }

  /**
   * All indices in votes are relative to proto array so always keep it up to date
   */
  prune(finalizedRoot: RootHex): ProtoBlock[] {
    const prunedNodes = this.protoArray.maybePrune(finalizedRoot);
    const prunedCount = prunedNodes.length;
    for (let i = 0; i < this.voteNextSlots.length; i++) {
      const currentIndex = this.voteCurrentIndices[i];

      if (currentIndex !== NULL_VOTE_INDEX) {
        if (currentIndex >= prunedCount) {
          this.voteCurrentIndices[i] = currentIndex - prunedCount;
        } else {
          // the vote was for a pruned proto node
          this.voteCurrentIndices[i] = NULL_VOTE_INDEX;
        }
      }

      const nextIndex = this.voteNextIndices[i];

      if (nextIndex !== NULL_VOTE_INDEX) {
        if (nextIndex >= prunedCount) {
          this.voteNextIndices[i] = nextIndex - prunedCount;
        } else {
          // the vote was for a pruned proto node
          this.voteNextIndices[i] = NULL_VOTE_INDEX;
        }
      }
    }
    return prunedNodes;
  }

  setPruneThreshold(threshold: number): void {
    this.protoArray.pruneThreshold = threshold;
  }

  /**
   * Iterates backwards through block summaries, starting from a block root.
   * Return only the non-finalized blocks.
   */
  iterateAncestorBlocks(blockRoot: RootHex, payloadStatus: PayloadStatus): IterableIterator<ProtoBlock> {
    return this.protoArray.iterateAncestorNodes(blockRoot, payloadStatus);
  }

  /**
   * Returns all blocks backwards starting from a block root.
   * Return only the non-finalized blocks.
   */
  getAllAncestorBlocks(blockRoot: RootHex, payloadStatus: PayloadStatus): ProtoBlock[] {
    const blocks = this.protoArray.getAllAncestorNodes(blockRoot, payloadStatus);
    // the last node is the previous finalized one, it's there to check onBlock finalized checkpoint only.
    return blocks.slice(0, blocks.length - 1);
  }

  /**
   * The same to iterateAncestorBlocks but this gets non-ancestor nodes instead of ancestor nodes.
   */
  getAllNonAncestorBlocks(blockRoot: RootHex, payloadStatus: PayloadStatus): ProtoBlock[] {
    return this.protoArray.getAllNonAncestorNodes(blockRoot, payloadStatus);
  }

  /**
   * Returns both ancestor and non-ancestor blocks in a single traversal.
   */
  getAllAncestorAndNonAncestorBlocks(
    blockRoot: RootHex,
    payloadStatus: PayloadStatus
  ): {ancestors: ProtoBlock[]; nonAncestors: ProtoBlock[]} {
    const {ancestors, nonAncestors} = this.protoArray.getAllAncestorAndNonAncestorNodes(blockRoot, payloadStatus);

    return {
      // the last node is the previous finalized one, it's there to check onBlock finalized checkpoint only.
      ancestors: ancestors.slice(0, ancestors.length - 1),
      nonAncestors,
    };
  }

  getCanonicalBlockByRoot(blockRoot: Root): ProtoBlock | null {
    const blockRootHex = toRootHex(blockRoot);
    if (blockRootHex === this.head.blockRoot) {
      return this.head;
    }

    for (const block of this.protoArray.iterateAncestorNodes(this.head.blockRoot, this.head.payloadStatus)) {
      if (block.blockRoot === blockRootHex) {
        return block;
      }
    }

    return null;
  }

  getCanonicalBlockAtSlot(slot: Slot): ProtoBlock | null {
    if (slot > this.head.slot) {
      return null;
    }

    if (slot === this.head.slot) {
      return this.head;
    }

    for (const block of this.protoArray.iterateAncestorNodes(this.head.blockRoot, this.head.payloadStatus)) {
      if (block.slot === slot) {
        return block;
      }
    }
    return null;
  }

  getCanonicalBlockClosestLteSlot(slot: Slot): ProtoBlock | null {
    if (slot >= this.head.slot) {
      return this.head;
    }

    for (const block of this.protoArray.iterateAncestorNodes(this.head.blockRoot, this.head.payloadStatus)) {
      if (slot >= block.slot) {
        return block;
      }
    }
    return null;
  }

  /** Very expensive function, iterates the entire ProtoArray. TODO: Is this function even necessary? */
  forwarditerateAncestorBlocks(): ProtoBlock[] {
    return this.protoArray.nodes;
  }

  *forwardIterateDescendants(blockRoot: RootHex, payloadStatus: PayloadStatus): IterableIterator<ProtoBlock> {
    const rootsInChain = new Set([blockRoot]);
    const blockIndex = this.protoArray.getNodeIndexByRootAndStatus(blockRoot, payloadStatus);
    if (blockIndex === undefined) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.MISSING_PROTO_ARRAY_BLOCK,
        root: blockRoot,
      });
    }

    for (let i = blockIndex + 1; i < this.protoArray.nodes.length; i++) {
      const node = this.protoArray.nodes[i];
      if (rootsInChain.has(node.parentRoot)) {
        rootsInChain.add(node.blockRoot);
        yield node;
      }
    }
  }

  /** Very expensive function, iterates the entire ProtoArray. TODO: Is this function even necessary? */
  getBlockSummariesByParentRoot(parentRoot: RootHex): ProtoBlock[] {
    return this.protoArray.nodes.filter((node) => node.parentRoot === parentRoot);
  }

  /** Very expensive function, iterates the entire ProtoArray. TODO: Is this function even necessary? */
  getBlockSummariesAtSlot(slot: Slot): ProtoBlock[] {
    const nodes = this.protoArray.nodes;
    const blocksAtSlot: ProtoBlock[] = [];
    for (let i = 0, len = nodes.length; i < len; i++) {
      const node = nodes[i];
      if (node.slot === slot) {
        blocksAtSlot.push(node);
      }
    }
    return blocksAtSlot;
  }

  /** Returns the distance of common ancestor of nodes to the max of the newNode and the prevNode. */
  getCommonAncestorDepth(prevBlock: ProtoBlock, newBlock: ProtoBlock): AncestorResult {
    const prevNode = this.protoArray.getNode(prevBlock.blockRoot, prevBlock.payloadStatus);
    const newNode = this.protoArray.getNode(newBlock.blockRoot, newBlock.payloadStatus);
    if (!prevNode || !newNode) {
      return {code: AncestorStatus.BlockUnknown};
    }

    const commonAncestor = this.protoArray.getCommonAncestor(prevNode, newNode);
    // No common ancestor, should never happen. Return null to not throw
    if (!commonAncestor) {
      return {code: AncestorStatus.NoCommonAncenstor};
    }

    // If common node is one of both nodes, then they are direct descendants, return null
    if (commonAncestor.blockRoot === prevNode.blockRoot || commonAncestor.blockRoot === newNode.blockRoot) {
      return {code: AncestorStatus.Descendant};
    }

    return {code: AncestorStatus.CommonAncestor, depth: Math.max(newNode.slot, prevNode.slot) - commonAncestor.slot};
  }

  /**
   * Optimistic sync validate till validated latest hash, invalidate any descendant
   * branch if invalidate till hash provided
   *
   * Proxies to protoArray's validateLatestHash and could run extra validations for the
   * justified's status as well as validate the terminal conditions if terminal block
   * becomes valid
   */
  validateLatestHash(execResponse: LVHExecResponse): void {
    try {
      this.protoArray.validateLatestHash(execResponse, this.fcStore.currentSlot);
    } catch (e) {
      if (e instanceof ProtoArrayError && e.type.code === ProtoArrayErrorCode.INVALID_LVH_EXECUTION_RESPONSE) {
        this.irrecoverableError = e;
      }
    }
  }

  /**
   * A dependent root is the block root of the last block before the state transition that decided a specific shuffling
   *
   * For proposer shuffling with 0 epochs of lookahead = previous immediate epoch transition
   * For attester shuffling with 1 epochs of lookahead = last epoch's epoch transition
   *
   * ```
   *         epoch: 0       1       2       3       4
   *                |-------|-------|=======|-------|
   * dependent root A -------------^
   * dependent root B -----^
   * ```
   * - proposer shuffling for a block in epoch 2: dependent root A (EpochDifference = 0)
   * - attester shuffling for a block in epoch 2: dependent root B (EpochDifference = 1)
   */
  getDependentRoot(block: ProtoBlock, epochDifference: EpochDifference): RootHex {
    // The navigation at the end of the while loop will always progress backwards,
    // jumping to a block with a strictly less slot number. So the condition `blockEpoch < atEpoch`
    // is guaranteed to happen. Given the use of target blocks for faster navigation, it will take
    // at most `2 * (blockEpoch - atEpoch + 1)` iterations to find the dependent root.

    const beforeSlot = block.slot - (block.slot % SLOTS_PER_EPOCH) - epochDifference * SLOTS_PER_EPOCH;

    // Special case close to genesis block, return the genesis block root
    if (beforeSlot <= 0) {
      const genesisBlock = this.protoArray.nodes[0];
      if (genesisBlock === undefined || genesisBlock.slot !== 0) {
        throw Error("Genesis block not available");
      }
      return genesisBlock.blockRoot;
    }

    const finalizedSlot = this.getFinalizedBlock().slot;
    while (block.slot >= finalizedSlot) {
      // Dependant root must be in epoch less than `beforeSlot`
      if (block.slot < beforeSlot) {
        return block.blockRoot;
      }

      // Skip one last jump if there's no skipped slot at first slot of the epoch
      if (block.slot === beforeSlot) {
        return block.parentRoot;
      }

      // For the first slot of the epoch, a block is it's own target
      const nextRoot = block.blockRoot === block.targetRoot ? block.parentRoot : block.targetRoot;
      // Use default variant (PENDING for Gloas, FULL for pre-Gloas)
      // For Gloas: we search for PENDING blocks because dependent root is determined by the block itself,
      // not the payload. In state-transition, block parentage is independent of payload status,
      // so linking by PENDING block in fork-choice is correct.
      const defaultStatus = this.protoArray.getDefaultVariant(nextRoot);
      if (defaultStatus === undefined) {
        throw Error(`No block for root ${nextRoot}`);
      }
      block = this.protoArray.getBlockReadonly(nextRoot, defaultStatus);
    }

    throw Error(`Not found dependent root for block slot ${block.slot}, epoch difference ${epochDifference}`);
  }

  /**
   * Return true if the block is timely for the current slot.
   * Child class can overwrite this for testing purpose.
   */
  protected isBlockTimely(block: BeaconBlock, blockDelaySec: number): boolean {
    const fork = this.config.getForkName(block.slot);
    const isBeforeLateBlockCutoff = blockDelaySec * 1000 < this.config.getAttestationDueMs(fork);
    return this.fcStore.currentSlot === block.slot && isBeforeLateBlockCutoff;
  }

  /**
   * https://github.com/ethereum/consensus-specs/blob/v1.5.0/specs/phase0/fork-choice.md#is_proposing_on_time
   */
  private isProposingOnTime(secFromSlot: number, slot: Slot): boolean {
    const fork = this.config.getForkName(slot);
    const proposerReorgCutoff = this.config.getProposerReorgCutoffMs(fork);
    return secFromSlot * 1000 <= proposerReorgCutoff;
  }

  private getPreMergeExecStatus(executionStatus: MaybeValidExecutionStatus): ExecutionStatus.PreMerge {
    if (executionStatus !== ExecutionStatus.PreMerge)
      throw Error(`Invalid pre-merge execution status: expected: ${ExecutionStatus.PreMerge}, got ${executionStatus}`);
    return executionStatus;
  }

  private getPreMergeDataStatus(dataAvailabilityStatus: DataAvailabilityStatus): DataAvailabilityStatus.PreData {
    if (dataAvailabilityStatus !== DataAvailabilityStatus.PreData)
      throw Error(
        `Invalid pre-merge data status: expected: ${DataAvailabilityStatus.PreData}, got ${dataAvailabilityStatus}`
      );
    return dataAvailabilityStatus;
  }

  private getPreGloasExecStatus(
    executionStatus: MaybeValidExecutionStatus
  ): ExecutionStatus.Valid | ExecutionStatus.Syncing {
    if (executionStatus === ExecutionStatus.PreMerge || executionStatus === ExecutionStatus.PayloadSeparated)
      throw Error(
        `Invalid post-merge execution status: expected: ${ExecutionStatus.Syncing} or ${ExecutionStatus.Valid}, got ${executionStatus}`
      );
    return executionStatus;
  }

  private getPostGloasExecStatus(executionStatus: MaybeValidExecutionStatus): ExecutionStatus.PayloadSeparated {
    if (executionStatus !== ExecutionStatus.PayloadSeparated)
      throw Error(
        `Invalid post-gloas execution status: expected: ${ExecutionStatus.PayloadSeparated}, got ${executionStatus}`
      );
    return executionStatus;
  }

  /**
   * Why `getJustifiedBalances` getter?
   * - updateCheckpoints() is called in both on_block and on_tick.
   * - Our cache strategy to get justified balances is incomplete, it can't regen all possible states.
   * - If the justified state is not available it will get one that is "closest" to the justified checkpoint.
   * - As a last resort fallback the state that references the new justified checkpoint is close or equal to the
   *   desired justified state. However, the state is available only in the on_block handler
   * - `getJustifiedBalances` makes the dynamics of justified balances cache easier to reason about
   *
   * **`on_block`**:
   * May need the justified balances of:
   * - justifiedCheckpoint
   * - unrealizedJustifiedCheckpoint
   * These balances are not immediately available so the getter calls a cache fn `() => cache.getBalances()`
   *
   * **`on_tick`**
   * May need the justified balances of:
   * - unrealizedJustified: Already available in `CheckpointWithPayloadAndBalance`
   * Since this balances are already available the getter is just `() => balances`, without cache interaction
   */
  private updateCheckpoints(
    justifiedCheckpoint: CheckpointWithPayloadStatus,
    finalizedCheckpoint: CheckpointWithPayloadStatus,
    getJustifiedBalances: () => JustifiedBalances
  ): void {
    // Update justified checkpoint.
    if (justifiedCheckpoint.epoch > this.fcStore.justified.checkpoint.epoch) {
      this.fcStore.justified = {checkpoint: justifiedCheckpoint, balances: getJustifiedBalances()};
      this.justifiedProposerBoostScore = null;
    }

    // Update finalized checkpoint.
    if (finalizedCheckpoint.epoch > this.fcStore.finalizedCheckpoint.epoch) {
      this.fcStore.finalizedCheckpoint = finalizedCheckpoint;
      this.justifiedProposerBoostScore = null;
    }
  }

  /**
   * Update unrealized checkpoints in store if necessary
   */
  private updateUnrealizedCheckpoints(
    unrealizedJustifiedCheckpoint: CheckpointWithPayloadStatus,
    unrealizedFinalizedCheckpoint: CheckpointWithPayloadStatus,
    getJustifiedBalances: () => JustifiedBalances
  ): void {
    if (unrealizedJustifiedCheckpoint.epoch > this.fcStore.unrealizedJustified.checkpoint.epoch) {
      this.fcStore.unrealizedJustified = {
        checkpoint: unrealizedJustifiedCheckpoint,
        balances: getJustifiedBalances(),
      };
    }
    if (unrealizedFinalizedCheckpoint.epoch > this.fcStore.unrealizedFinalizedCheckpoint.epoch) {
      this.fcStore.unrealizedFinalizedCheckpoint = unrealizedFinalizedCheckpoint;
    }
  }

  /**
   * Validates the `indexed_attestation` for application to fork choice.
   *
   * ## Specification
   *
   * Equivalent to:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#validate_on_attestation
   */
  private validateOnAttestation(
    indexedAttestation: IndexedAttestation,
    slot: Slot,
    blockRootHex: string,
    targetEpoch: Epoch,
    attDataRoot: string,
    // forceImport attestation even if too old, mostly used in spec tests
    forceImport?: boolean
  ): void {
    // There is no point in processing an attestation with an empty bitfield. Reject
    // it immediately.
    //
    // This is not in the specification, however it should be transparent to other nodes. We
    // return early here to avoid wasting precious resources verifying the rest of it.
    if (!indexedAttestation.attestingIndices.length) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.EMPTY_AGGREGATION_BITFIELD,
        },
      });
    }

    if (!this.validatedAttestationDatas.has(attDataRoot)) {
      this.validateAttestationData(indexedAttestation.data, slot, blockRootHex, targetEpoch, attDataRoot, forceImport);
    }
  }

  private validateAttestationData(
    attestationData: phase0.AttestationData,
    slot: Slot,
    beaconBlockRootHex: string,
    targetEpoch: Epoch,
    attDataRoot: string,
    // forceImport attestation even if too old, mostly used in spec tests
    forceImport?: boolean
  ): void {
    const epochNow = computeEpochAtSlot(this.fcStore.currentSlot);
    const targetRootHex = toRootHex(attestationData.target.root);

    // Attestation must be from the current of previous epoch.
    if (targetEpoch > epochNow) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.FUTURE_EPOCH,
          attestationEpoch: targetEpoch,
          currentEpoch: epochNow,
        },
      });
    }

    if (!forceImport && targetEpoch + 1 < epochNow) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.PAST_EPOCH,
          attestationEpoch: targetEpoch,
          currentEpoch: epochNow,
        },
      });
    }

    if (targetEpoch !== computeEpochAtSlot(slot)) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.BAD_TARGET_EPOCH,
          target: targetEpoch,
          slot,
        },
      });
    }

    // Attestation target must be for a known block.
    //
    // We do not delay the block for later processing to reduce complexity and DoS attack
    // surface.
    if (!this.protoArray.hasBlock(targetRootHex)) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.UNKNOWN_TARGET_ROOT,
          root: targetRootHex,
        },
      });
    }

    // Load the block for `attestation.data.beacon_block_root`.
    //
    // This indirectly checks to see if the `attestation.data.beacon_block_root` is in our fork
    // choice. Any known, non-finalized block should be in fork choice, so this check
    // immediately filters out attestations that attest to a block that has not been processed.
    //
    // Attestations must be for a known block. If the block is unknown, we simply drop the
    // attestation and do not delay consideration for later.
    // We don't care which variant it is, just need to find the block
    const defaultStatus = this.protoArray.getDefaultVariant(beaconBlockRootHex);
    const block = defaultStatus !== undefined ? this.protoArray.getBlock(beaconBlockRootHex, defaultStatus) : undefined;
    if (!block) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.UNKNOWN_HEAD_BLOCK,
          beaconBlockRoot: beaconBlockRootHex,
        },
      });
    }

    // If an attestation points to a block that is from an earlier slot than the attestation,
    // then all slots between the block and attestation must be skipped. Therefore if the block
    // is from a prior epoch to the attestation, then the target root must be equal to the root
    // of the block that is being attested to.
    const expectedTargetHex = targetEpoch > computeEpochAtSlot(block.slot) ? beaconBlockRootHex : block.targetRoot;

    if (expectedTargetHex !== targetRootHex) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.INVALID_TARGET,
          attestation: targetRootHex,
          local: expectedTargetHex,
        },
      });
    }

    // Attestations must not be for blocks in the future. If this is the case, the attestation
    // should not be considered.
    if (block.slot > slot) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.ATTESTS_TO_FUTURE_BLOCK,
          block: block.slot,
          attestation: slot,
        },
      });
    }

    // For Gloas blocks, attestation index must be 0 or 1
    if (isGloasBlock(block) && attestationData.index !== 0 && attestationData.index !== 1) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INVALID_ATTESTATION,
        err: {
          code: InvalidAttestationCode.INVALID_DATA_INDEX,
          index: attestationData.index,
        },
      });
    }

    this.validatedAttestationDatas.add(attDataRoot);
  }

  /**
   * Add a validator's latest message to the tracked votes.
   * Always sync voteCurrentIndices and voteNextIndices so that it'll not throw in computeDeltas()
   *
   * Modified for Gloas to accept slot and payloadPresent.
   * Spec: gloas/fork-choice.md#modified-update_latest_messages
   *
   * For backward compatibility with Fulu (pre-Gloas):
   * - Accepts both epoch-derived and slot parameters
   * - payloadPresent defaults to true for Fulu (payloads embedded in blocks)
   */
  private addLatestMessage(
    validatorIndex: ValidatorIndex,
    nextSlot: Slot,
    nextRoot: RootHex,
    nextPayloadStatus: PayloadStatus
  ): void {
    // should not happen, attestation is validated before this step
    // Get the node index for the voted block
    const nextIndex = this.protoArray.getNodeIndexByRootAndStatus(nextRoot, nextPayloadStatus);
    if (nextIndex === undefined) {
      throw new Error(`Could not find proto index for nextRoot ${nextRoot} with payloadStatus ${nextPayloadStatus}`);
    }

    // ensure there is no undefined entries in Votes arrays
    if (this.voteNextSlots.length < validatorIndex + 1) {
      for (let i = this.voteNextSlots.length; i < validatorIndex + 1; i++) {
        this.voteNextSlots[i] = INIT_VOTE_SLOT;
        this.voteCurrentIndices[i] = this.voteNextIndices[i] = NULL_VOTE_INDEX;
      }
    }

    const existingNextSlot = this.voteNextSlots[validatorIndex];
    if (existingNextSlot === INIT_VOTE_SLOT || computeEpochAtSlot(nextSlot) > computeEpochAtSlot(existingNextSlot)) {
      // nextIndex is transfered to currentIndex in computeDeltas()
      this.voteNextIndices[validatorIndex] = nextIndex;
      this.voteNextSlots[validatorIndex] = nextSlot;
    }
    // else its an old vote, don't count it
  }

  /**
   * Processes and removes from the queue any queued attestations which may now be eligible for
   * processing due to the slot clock incrementing.
   */
  private processAttestationQueue(): void {
    const currentSlot = this.fcStore.currentSlot;
    for (const [slot, byRoot] of this.queuedAttestations.entries()) {
      if (slot < currentSlot) {
        this.queuedAttestations.delete(slot);
        for (const [blockRoot, validatorVotes] of byRoot.entries()) {
          const blockRootHex = blockRoot;
          for (const [validatorIndex, payloadStatus] of validatorVotes.entries()) {
            // equivocatingIndices was checked in onAttestation
            this.addLatestMessage(validatorIndex, slot, blockRootHex, payloadStatus);
          }

          if (slot === currentSlot - 1) {
            this.queuedAttestationsPreviousSlot += validatorVotes.size;
          }
        }
      } else {
        break;
      }
    }
  }

  /**
   * Called whenever the current time increases.
   *
   * ## Specification
   *
   * Equivalent to:
   *
   * https://github.com/ethereum/consensus-specs/blob/v1.1.10/specs/phase0/fork-choice.md#on_tick
   */
  private onTick(time: Slot): void {
    const previousSlot = this.fcStore.currentSlot;

    if (time > previousSlot + 1) {
      throw new ForkChoiceError({
        code: ForkChoiceErrorCode.INCONSISTENT_ON_TICK,
        previousSlot,
        time,
      });
    }

    // Update store time
    this.fcStore.currentSlot = time;
    // Reset proposer boost if this is a new slot.
    if (this.proposerBoostRoot) {
      // Since previous weight was boosted, we need would now need to recalculate the scores without the boost
      this.proposerBoostRoot = null;
    }

    // Not a new epoch, return.
    if (computeSlotsSinceEpochStart(time) !== 0) {
      return;
    }

    // If a new epoch, pull-up justification and finalization from previous epoch
    this.updateCheckpoints(
      this.fcStore.unrealizedJustified.checkpoint,
      this.fcStore.unrealizedFinalizedCheckpoint,
      () => this.fcStore.unrealizedJustified.balances
    );
  }

  /**
   *
   * Common logic of get_proposer_head() and should_override_forkchoice_update()
   * No one should be calling this function except these two
   *
   */
  private getPreliminaryProposerHead(
    headBlock: ProtoBlock,
    parentBlock: ProtoBlock,
    slot: Slot
  ): {prelimProposerHead: ProtoBlock; prelimNotReorgedReason?: NotReorgedReason} {
    let prelimProposerHead = headBlock;
    // No reorg if headBlock is on time
    // https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#is_head_late
    const isHeadLate = !headBlock.timeliness;
    if (!isHeadLate) {
      return {prelimProposerHead, prelimNotReorgedReason: NotReorgedReason.HeadBlockIsTimely};
    }

    // No reorg if we are at epoch boundary where proposer shuffling could change
    // https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#is_shuffling_stable
    const isShufflingStable = slot % SLOTS_PER_EPOCH !== 0;
    if (!isShufflingStable) {
      return {prelimProposerHead, prelimNotReorgedReason: NotReorgedReason.NotShufflingStable};
    }

    // No reorg if headBlock and parentBlock are not ffg competitive
    // https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#is_ffg_competitive
    const {unrealizedJustifiedEpoch: headBlockCpEpoch, unrealizedJustifiedRoot: headBlockCpRoot} = headBlock;
    const {unrealizedJustifiedEpoch: parentBlockCpEpoch, unrealizedJustifiedRoot: parentBlockCpRoot} = parentBlock;
    const isFFGCompetitive = headBlockCpEpoch === parentBlockCpEpoch && headBlockCpRoot === parentBlockCpRoot;
    if (!isFFGCompetitive) {
      return {prelimProposerHead, prelimNotReorgedReason: NotReorgedReason.NotFFGCompetitive};
    }

    // No reorg if chain is not finalizing within REORG_MAX_EPOCHS_SINCE_FINALIZATION
    // https://github.com/ethereum/consensus-specs/blob/v1.4.0-beta.4/specs/phase0/fork-choice.md#is_finalization_ok
    const epochsSinceFinalization = computeEpochAtSlot(slot) - this.getFinalizedCheckpoint().epoch;
    const isFinalizationOk = epochsSinceFinalization <= this.config.REORG_MAX_EPOCHS_SINCE_FINALIZATION;
    if (!isFinalizationOk) {
      return {prelimProposerHead, prelimNotReorgedReason: NotReorgedReason.ChainLongUnfinality};
    }

    // No reorg if this reorg spans more than a single slot
    const parentSlotOk = parentBlock.slot + 1 === headBlock.slot;
    if (!parentSlotOk) {
      return {prelimProposerHead, prelimNotReorgedReason: NotReorgedReason.ParentBlockDistanceMoreThanOneSlot};
    }

    prelimProposerHead = parentBlock;

    return {prelimProposerHead};
  }
}

// Approximate https://github.com/ethereum/consensus-specs/blob/v1.6.1/specs/phase0/fork-choice.md#calculate_committee_fraction
// Calculates proposer boost score when committeePercent = config.PROPOSER_SCORE_BOOST
export function getCommitteeFraction(
  justifiedTotalActiveBalanceByIncrement: number,
  config: {slotsPerEpoch: number; committeePercent: number}
): number {
  const committeeWeight = Math.floor(justifiedTotalActiveBalanceByIncrement / config.slotsPerEpoch);
  return Math.floor((committeeWeight * config.committeePercent) / 100);
}

/**
 * Get the payload status for a checkpoint.
 *
 * Pre-Gloas: always FULL (payload embedded in block)
 * Gloas: determined by state.execution_payload_availability
 *
 * @param state - The state to check execution_payload_availability
 * @param checkpointEpoch - The epoch of the checkpoint
 */
export function getCheckpointPayloadStatus(
  config: ChainForkConfig,
  state: IBeaconStateView,
  checkpointEpoch: number
): PayloadStatus {
  // Compute checkpoint slot first to determine the correct fork
  const checkpointSlot = computeStartSlotAtEpoch(checkpointEpoch);
  const fork = config.getForkSeq(checkpointSlot);

  // Pre-Gloas: always FULL
  if (fork < ForkSeq.gloas) {
    return PayloadStatus.FULL;
  }

  // For Gloas, check state.execution_payload_availability
  // - For non-skipped slots at checkpoint: returns false (EMPTY) since payload hasn't arrived yet
  // - For skipped slots at checkpoint: returns the actual availability status from state
  const payloadAvailable = state.executionPayloadAvailability.get(checkpointSlot % SLOTS_PER_HISTORICAL_ROOT);

  return payloadAvailable ? PayloadStatus.FULL : PayloadStatus.EMPTY;
}