Q: When do we trigger it?
Q: Describe the algorithm

Relevant Spec

engine_forkchoiceUpdatedV1

https://github.com/ethereum/execution-apis/blob/main/src/engine/paris.md#specification-1

1. Client software MAY initiate a sync process if forkchoiceState.headBlockHash references an unknown payload or a payload that can't be validated because data that are requisite for the validation is missing. The sync process is specified in the Sync section.

engine_newPayloadV1

https://github.com/ethereum/execution-apis/blob/main/src/engine/paris.md#specification

2. Client software MAY initiate a sync process if requisite data for payload validation is missing. Sync process is specified in the Sync section.

Sync

https://github.com/ethereum/execution-apis/blob/main/src/engine/paris.md#sync

In the context of this specification, the sync is understood as the process of obtaining data required to validate a payload. The sync process may consist of the following stages:

1. Pulling data from remote peers in the network.
2. Passing ancestors of a payload through the Payload validation and obtaining a parent state.

Note: Each of these stages is optional. Exact behavior of client software during the sync process is implementation dependent.

Message ordering

https://github.com/ethereum/execution-apis/blob/main/src/engine/common.md#message-ordering

Consensus Layer client software MUST respect the order of the corresponding fork choice update events when making calls to the engine_forkchoiceUpdated method.

Execution Layer client software MUST process engine_forkchoiceUpdated method calls
in the same order as they have been received.

Besu Trigger

We start a new backwards sync (BWS) session on both engine_forkchoiceUpdated (fCU) and engine_newPayload (nP).

AbstractEngineForkchoiceUpdated.java

final Optional<BlockHeader> maybeNewHead =
  mergeCoordinator.getOrSyncHeadByHash(forkChoice.getHeadBlockHash(), 
    forkChoice.getFinalizedBlockHash());

if (maybeNewHead.isEmpty()) {
  return syncingResponse(requestId, forkChoice);
}

AbstractEngineNewPayload.java

final Optional<BlockHeader> maybeParentHeader =
  protocolContext.getBlockchain().getBlockHeader(blockParam.getParentHash());

// ...

if (maybeParentHeader.isEmpty()) {
  LOG.atDebug()
    .setMessage("Parent of block {} is not present, append it to backward sync")
    .addArgument(block::toLogString)
    .log();
  mergeCoordinator.appendNewPayloadToSync(block);

  return respondWith(reqId, blockParam, null, SYNCING);
}

MergeCoordinator.java

  @Override
  public Optional<BlockHeader> getOrSyncHeadByHash(final Hash headHash, final Hash finalizedHash) {
    final var chain = protocolContext.getBlockchain();
    final var maybeHeadHeader = chain.getBlockHeader(headHash);

    if (maybeHeadHeader.isPresent()) {
      LOG.atDebug()
          .setMessage("BlockHeader {} is already present")
          .addArgument(maybeHeadHeader.get()::toLogString)
          .log();
    } else {
      LOG.atDebug()
          .setMessage("Appending new head block hash {} to backward sync")
          .addArgument(headHash::toHexString)
          .log();
      backwardSyncContext.maybeUpdateTargetHeight(headHash);
      backwardSyncContext
          .syncBackwardsUntil(headHash)
          .thenRun(() -> updateFinalized(finalizedHash));
    }
    return maybeHeadHeader;
  }

  @Override
  public CompletableFuture<Void> appendNewPayloadToSync(final Block newPayload) {
    return backwardSyncContext.syncBackwardsUntil(newPayload);
  }

Algorithm and Structure Design

• BackwardSyncContext is the entry point and manages the session.
• BackwardChain is the data structure, where chainHead is the oldest block.
• BlockHeaders, Blocks and Hashes are stored on disk, keyed by Hash.
• Also sessionData is stored on disk.
• hashesToAppend is Deque representing the work queue (one per session?)
• isTrusted means "do we have it stored?" (Maybe "trust" is because it came from the CL).
• BackwardSyncAlgorithm consists of CompletableFuture Steps composed recursively in a State Pattern.

Initial Sync BWS INFO Logs

(WorldStateDownload || FastImportBlocks) -> WorldStateHeal -> BWS

BackwardSyncContext | Starting a new backward sync session
BackwardSyncStep | Backward sync phase 1 of 2 completed, downloaded a total of 200 headers. Peers: 8
BackwardSyncContext | Backward sync phase 2 of 2, 2.63% completed, imported 1 blocks of at least 38 (current head 3743023, target head 3743060). Peers: 2
BackwardSyncContext | Backward sync phase 2 of 2, 43.59% completed, imported 17 blocks of at least 39 (current head 3743039, target head 3743061). Peers: 2
BackwardSyncContext | Backward sync phase 2 of 2, 97.50% completed, imported 39 blocks of at least 40 (current head 3743061, target head 3743062). Peers: 3
BackwardSyncContext | Backward sync phase 2 of 2 completed, imported a total of 40 blocks. Peers: 2
BackwardSyncAlgorithm | Current backward sync session is done