consensus: Rolling Finality: implement vote-accumulation quorum

[fed-franz]

Summary

As described in #1118, the new consensus protocol will use a "naive" definition of rolling finality: after N Attested blocks, we finalize all previous non-finalized blocks.

This approach, while simple, could effectively ensure blocks finalized by the rolling finality won't be replaced with overwhelming probability. However, since this has not been yet demonstrated, and could turn to be wrong, we should evaluate in the future a different approach.
This is the original proposal for rolling finality: instead of counting blocks, we count the cumulative weight of Provisioner's votes for blocks added on top of a non-final block.

Detailed Description

As per the original definition in #1118:

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.

(also see here)

Footnotes

1. https://github.com/dusk-network/rusk/issues/1118#user-content-fn-3-ce52005fafca99689b3d36def91895f8 ↩

[goshawk-3]

the new consensus protocol will use a "naive" definition of rolling finality: after N Attested blocks, we finalize all previous non-finalized blocks.

Do you mean N Attested Blocks in a row or not?

Let's assume that N=3

Example_1:

Block 1 - Final
Block 2 - Accepted
Block 3 - Attested
Block 4 - Accepted
Block 5 - Attested
Block 6 - Accepted
Block 7- Attested

Question: Would we consider any of the blocks after Block 1 a Final? @fed-franz

[fed-franz]

the new consensus protocol will use a "naive" definition of rolling finality: after N Attested blocks, we finalize all previous non-finalized blocks.

Do you mean N Attested Blocks in a row or not?

Let's assume that N=3

Example_1:

Block 1 - Final Block 2 - Accepted Block 3 - Attested Block 4 - Accepted Block 5 - Attested Block 6 - Accepted Block 7- Attested

Question: Would we consider any of the blocks after Block 1 a Final? @fed-franz

N in a row.

PS: please note this is the issue for the "improved" version

[fed-franz]

Adding a couple of sidenotes for improving the current Rolling Finality:

• we should consider an "hybrid" approach where we still consider only consecutive Attested blocks but instead of merely counting them, we count the number of Attestations (Certificates) in them. That is, instead of waiting 5 consecutive Attested blocks, we wait for, e.g., 10 Certificates included in consecutive Attested blocks.
  This allow to take into account all failed iterations (where provisioners still "confirm" the Accepted block with their vote).
  In this view, Attested blocks with more iterations would contribute more to the rolling finality, because there are more votes in it.

• we should set the threshold (5 blocks/10 certificates) depending on the size of the provisioner set (this is akin to, and can coincide with, the proposal in this PR, where we wait for reaching the 67% of the total stake).

[autholykos]

Before being able to work on this, specs need to be finalized

[HDauven]

@fed-franz @goshawk-3 @herr-seppia is this still relevant?

[herr-seppia]

@fed-franz @goshawk-3 @herr-seppia is this still relevant?

Probably not, but we should close it only when superseded by a new tracking issue explaining our direction on the topic

[fed-franz]

I think we should keep it around, if not here, somewhere else, as a reminder of at least evaluate a more "meaningful" rolling finality design.
Once the block-accumulation based rolling finality is shown to be secure as is, we can make this obsolete (assuming this solution is by any means more complex)