Improve block import pipeline

[clangenb]

I was just analyzing what we have for #1587, and already see some follow up that we can do in order to improve efficiency after implementing it.

Status Quo of BlockImport

The current implementation of sidechain block import uses the ImportQueue. If there are competing blocks, aka forks, in this import queue, the first block (ordered by blockhash) of the competing ones is imported, which happens here. The queue has no notion of block ancestry, hence if there are competing blocks the chances are very high that we get an unrecoverable ancestry error, which is checked on step later. Something we have indeed observed in practice. Regardless, the suggestions here are actually almost independent of the fact that we have a ForkTree or the ImportQueue

Currently, the main entry point is process_queue there we enter the import_or_sync_block method. Here follows the pseudocode of the current state:

fn import_or_sync_block(
   sidechain_block (=sb),
   latest_imported_parentchain_header (=cph),
   maybe_sidechain_block_confirmation,
 ) {
   import_block(sb, cph)
      // If we get an ancestry error we try to fetch the missing blocks. If the ancestry error is due to a fork, we will never recover.
      // We will enter `import_block` again inside the `fetch_and_import_blocks_from_peer`.
      //-> ancestry_error -> fetch_and_import_blocks_from_peer.
      
      // confirm import aka send xt to parentchain.
}

The import_block pseudocode looks like this:

fn import_block(sb, cph) {
    // VERIFYING ----

    // pph will either have the value `cph` if the referenced parentchain header in `sb` equals `cph`.
    // Otherwise it will be some header from the queue
    let pph = peek_parentchain_header_from_queue()
    
    verify_sidechain_block(sb, pph, shard) {
       // we only need the `pph` because we have to get the current validateers, maybe we can optimise.
       authorities = ocall_api.current_validateers(pph).
       
       // verify block integrity, e.g., signature, ancestry etc.
    }
    
   // IMPORTING ------

    import_parentchain_blocks(cph +1 ... pph)

    appy_state_update()
    
    // CLEANUP ------
    // the following is not relevant for this task, but listed for completeness.
    cleanup {
       remove_applied_tops_from_pool
       set_block_height_metric
    }
    
    ocall_api.store_sidechain_blocks()
}  

Potential improvements

Inserting nodes into the fork tree might be expensive, navigating a fork tree is more expensive the more branches and nodes it contains. Hence, we should try to filter apriori what gets inserted in the first place. Further, if we run some check at insertion of a sidechain block into the fork tree, we don't have to run those chose at import aka during our precious block execution time. I argue that we can:

1. Verify block ancestry, block author, signature etc. upon insertion into the fork tree.
2. Fetch missing blocks in case of an ancestry error also upon insertoni into the fork tree.

If we do that, we can start at the importing phase directly when we actually import sidechain blocks from the fork tree. Especially when we rebuild the best state based on a snapshot, we will notice an increased speed as we don't have to fetch the authors via a network request during verification of the block authors.