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 is marked as final following these rules:

• if B is Attested, it is marked as Final after 1 successive Attested block
• if B is Accepted, it is marked as Final after PNI x 2, where PNI is the number of previous non-attested iterations

For instance, if B has Iteration=0 it will be finalized if the next block is Attested.
If B has Iteration=5 and there are 3 previous iterations whose result is unknown (not attested), then it is finalized after 3 x 2 = 6 consecutive Attested blocks.

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