Proposal: Incremental Rolling Finality

[fed-franz]

Summary

Current Rolling Finality (RF) marks a block as final after a fixed number of consecutive attested blocks.
However, this approach does not take into account the number of lower-iteration (hence higher-priority) candidates that might have reached quorum. A more appropriate approach would be to have the number of blocks for the RF depend on the number of non-attested lower iterations in the same round.

This issue defines an "incremental" RF, where a block is marked as final after a variable number of blocks that depends on the number of previous non-attested iterations. Specifically, the higher the iteration number of such iterations, the more the consecutive attested blocks to wait.

At the same time, this new RF eliminates the concept of instant finality for attested blocks following a final block and replaces it with a 1-block RF. This means an attested block is marked as final when receiving its attested successor.

Relevant Context

Rationale
We can't give unconditional priority to lower-iteration blocks, since these can be withheld and published at a later time, forcing the network to rollback to a previous state, even when RF has already been achieved. This withholding attack can be disruptive for the network and lead to double-spending attacks.
Due to the above, priority is given to the RF and instant finality is removed.
In particular, requiring a successor block to finalize attested blocks prevents an attacker from forcing the network to rollback by simply withholding the vote determining the quorum.

Possible Solution

Incremental RF
A block B will be labeled following these rules:

• if B is Attested, it is marked as Confirmed after 1 successive Attested or Confirmed block;
• if B is Accepted, it is marked as Confirmed after PNI x 2 Attested or Confirmed Blocks, where PNI is the number of previous non-attested iterations;
• if B is Confirmed and its parent is Final, B is marked as Final

For instance, if B has Iteration=0 it will be confirmed if the next block is Attested or Confirmed.
If B has Iteration=5 and there are 3 previous non-attested iterations, then it is confirmed after 3 x 2 = 6 consecutive Attested or Confirmed blocks.
Once B is marked as Confirmed it will become Final as soon as its parent is marked Final.

Branch selection
When a node detects two competing branches, it acts as follows:
- between two non-finalized branches, choose the one based on the lowest-iteration block
- between a non-finalized and a finalized branch, choose the finalized branch
- in the event of two finalized branches (which should never occur), choose the one with the lowest iteration

Sync
When a node N receives from a block B from a peer P:

• if B has higher priority than the block at the same height in the local chain, N switches to B and requests following blocks, if any
• if B has lower priority than the corresponding block in the local chain:
  • N asks P if B is Final (it reached RF); this information could also be included in the Block or Quorum messages to save the request)
  • If B reached the RF, N requests P the blocks determining the RF. Then, if all blocks are received, the node switches to the new branch
  • If B is not Final, N sends its higher-priority block to P, which in turn should switch to this branch