Change block's finality definition

[herr-seppia]

Summary

A final block is a block that can never be replaced during the fallback mechanism.
Currently, a block is considered final if it's accepted at first iteration.
This lead to some edge case where consensus halt.

Possible solution design or implementation

Change finality as per following

Instant finality:

A block can achieve instant finality if one of the following conditions is met:

• A block at iteration 0 is accepted on top of an already finalized block.
• A block at iteration I is accepted on top of an already finalized block, and all iterations lower than I have timed out. ¹

Rolling finality:

If the tip of the blockchain is not finalized, the concept of rolling finality comes into play.

The aim of rolling finality is to deterministically identify a new block that can be considered final.
This block is sought within the range between the last finalized block and the most recently accepted block.

The process involves retracing steps from the last accepted block TIP to the last finalized block (FINALIZED) while counting the stakes of the provisioners involved in timeout certificates or winning certificates. ²
If, at a specific block H (where FINALIZED < H < TIP), the sum³ of stakes reaches 67% of the total stake, block H is considered final. ⁴

Additional context

This issue requires the following issue to be implemented

• Single vote for iteration #1109
• Add Deterministic winning certificate #1115
• Add failed_iterations fields #1116

Tracking:

• consensus: Add Instant Finality #1188
• consensus: Add Rolling Finality #1189

Footnotes

1. Blocks accepted with iteration greater than RELAX_ITERATION_THRESHOLD are exempt from instant finality ↩

2. Blocks accepted with iteration greater than RELAX_ITERATION_THRESHOLD are not taken into account ↩

3. It should be verified whether the first vote found for each provisioner needs to be discarded ↩

4. Since instant finality can be applied on top of rolling finality, this mechanism ensures recovery from non final blocks. ↩

[fed-franz]

I have a couple of comments on Rolling finality.

First, the current definition is problematic: I can't deem any block H as final if its predecessor is not final (because the predecessor can change). Also, it goes without saying, that if block H "accumulated" 67% of stake confirmation, so will have its predecessor.
So I think the definition of rolling finality should regard block at height FINALIZED+1.

Second, I'm a bit concerned about assuming that accumulated confirmations are immutable.
In fact, we are accumulating confirmations for a non-final block, which can be replaced by a higher-priority one.
Let's consider this case:

• the last received block TIP makes me reach the "finalization threshold" of 67% so I make H final.
• meanwhile, an lower-iteration H' is spread and reaches a quorum (maybe this block was already voted by other provisioners).
• part of the network (including part of the 67% confirming H) receives H' before TIP and replaces H with it the one that we made final.
  Now you have two branches: one with H and one with H'. If the branch with H' becomes the main chain, our node gets stuck because it considers H as final.
  Maybe this is an edge case, but we should rule out any risk before deeming something as "final".

[fed-franz]

As per recent discussions, we are going for a "naive" implementation of Rolling Finality:

• After N consecutive ATTESTED blocks [see consensus: Introduce block "Consensus State" labels #1158], we finalize all previous non-FINAL blocks

An Issue will be filed to discuss a more complex design that considers a cumulative weight of votes confirming the non-finalized block.

[fed-franz]

Can we close this? @goshawk-3 @herr-seppia