IF: Update fork-choice rule for fork database

[arhag]

Depends on https://github.com/AntelopeIO/leap/issues/2244.

Update index for picking the best branch (rename by_lib_block_num to by_best_branch) to order based on the computed fields derived from data in block_state.

This issue assumes the following structures exist:

struct qc_claim
{
   uint32_t  block_num;
   bool      is_strong_qc;

   auto operator<=>(const qc_claim&) const = default;
};

struct core_metadata
{
   uint32_t  last_final_block_num;
   uint32_t  final_on_strong_qc_block_num;
   uint32_t  latest_qc_claim_block_num;
};

And that there is a member function next_metadata in the block header state core with the following function signature:

   /**
    *  @pre this->latest_qc_claim().block_num <= most_recent_ancestor_with_qc.block_num <= this->current_block_num()
    *  @pre this->latest_qc_claim() <= most_recent_ancestor_with_qc
    *
    *  @post returned core_metadata has last_final_block_num <= final_on_strong_qc_block_num <= latest_qc_claim_block_num
    *  @post returned core_metadata has latest_qc_claim_block_num == most_recent_ancestor_with_qc.block_num
    *  @post returned core_metadata has final_on_strong_qc_block_num >= this->final_on_strong_qc_block_num
    *  @post returned core_metadata has last_final_block_num >= this->last_final_block_num()
    */
   core_metadata next_metadata(const qc_claim& most_recent_ancestor_with_qc) const;

The idea is to keep a cache of a qc_claim called most_recent_ancestor_with_qc within each block_state in the fork database which makes a QC claim on its most recent ancestor that has a valid QC. And in addition to keep a cache of the next_core_metadata that is derived from the core of that block_state by calling core.next_metadata(most_recent_ancestor_with_qc). Any time most_recent_ancestor_with_qc is mutated for a block_state, the corresponding next_core_metadata should also be recomputed.

If a new QC (weak of strong) is achieved on a block_state, Leap must not only update the most_recent_ancestor_with_qc of that block_state but it must also traverse to the descendant blocks to determine whether their corresponding most_recent_ancestor_with_qcs should also be updated. If a block_state has a better qc_claim (as determined by operator<) then its most_recent_ancestor_with_qc should not be updated nor should those of any of its descendant blocks.

An index should be maintained in the new fork database to allow the best head to be quickly selected.

Computed fields for index (in order):

1. next_core_metadata.last_final_block_num
2. next_core_metadata.latest_qc_claim_block_num
3. block timestamp
4. block ID (as final tie breaker to ensure uniqueness)

Between blocks, the best head (as determined by the index) can be checked to determine if a fork switch is necessary.

[arhag]

Simpler version:

An index should be maintained in the new fork database to allow the best head to be quickly selected.

Computed fields for index (in order):

1. core.last_final_block_num
2. core.latest_qc_claim_block_num
3. block timestamp
4. block ID (as final tie breaker to ensure uniqueness)

In this case, the core is the immutable one. There would be no next_core_metadata anymore.

Also, we need to vote on blocks that are not yet validated. The rule for now is:

1. Get the core.final_on_strong_qc_block_num for the block you are considering to vote on and use that to find the actual block ID of the ancestor block that has that block number.
2. If that block ID is not an ancestor of the current head block, then do not vote for that block.
3. Otherwise, consider voting for that block according to the decide_vote rules.

[heifner]

Keeping open until the following is done:

Also, we need to vote on blocks that are not yet validated. The rule for now is:

1. Get the core.final_on_strong_qc_block_num for the block you are considering to vote on and use that to find the actual block ID of the ancestor block that has that block number.
2. If that block ID is not an ancestor of the current head block, then do not vote for that block.
3. Otherwise, consider voting for that block according to the decide_vote rules.

[heifner]

https://github.com/AntelopeIO/leap/pull/2275/files#diff-42e9f97eed543dd784b1b77a536c50ff8e2403d5bbd3b1fb7f5dd90201391061R3427

This needs to search the branch of bsp->id() which is not necessarily the head branch. Then it should verify the found block state is validated.