consensus: Implement new Validation and Ratification logic

[fed-franz]

Summary

The current implementation of the Validation and Ratification steps is not aligned with the intended design of #1177.
Additionally, the original design does not align with slashing, which has been later introduced with #1257.

This Issue describes in detail how the Validation and Ratification steps should work in the new protocol.

Detailed Description

Nomenclature Update:

• We will use quorum to refer to two quantities:

  • The supermajority 2/3
  • The simple majority 1/2+1

• Target Quorum will refer to the quorum threshold depending on the type of vote

• NoQuorum: represent the vote casted if the amount of votes is insufficient to reach a conclusion on the step; it is only casted in the Ratification step

VALIDATION

• Votes:

  • Valid: a candidate block has been received and it's valid
  • Invalid: a candidate block has been received but it's invalid
  • NoCandidate: no candidate block has been received

• Validation message:

  • Header:
    • Prev_Hash
    • Round
    • Iteration
    • StepNum (= "Validation")
  • Payload:
    • Vote: Valid, Invalid, NoCandidate
    • Candidate_Hash: empty if Vote=NoCandidate
    • Signature: Sign(Hash(Header || Vote || Candidate_Hash))

• ValidationResults:

• Valid: a Supermajority of Valid votes has been received

• Invalid: a Majority of Invalid votes has been received

• NoCandidate: a Majority of NoCandidate votes has been received

• NoQuorum: the timeout expired

RATIFICATION
The Ratification vote corresponds to the local Validation Result and is accompanied by the SV of the Validation votes that produced the result.

• Votes

  • Valid
  • Invalid
  • NoCandidate
  • NoQuorum

• Ratification message:

  • Header:
    • Prev_Hash
    • Round
    • Iteration
    • StepNum (= "Ratification")
  • Payload:
    • Vote: Valid, Invalid, NoCandidate, NoQuorum
    • Candidate_Hash: empty if Vote=NoCandidate or Vote=NoQuorum
    • Signature: Sign(Hash(Header || Vote || Candidate_Hash))
    • Validation_Votes: StepVotes of the Validation votes that determined the Ratification Vote; empty if Vote=NoQuorum

Each Ratification vote is verified against Validation_Votes. Therefore, a NoCandidate vote is only valid with a SV containing a MajorityQuorum of NoCandidate votes for Validation.

• Ratification Results:
  • Success (Valid): a Supermajority Quorum of Valid votes has been received -> broadcast Quorum message
  • Fail (Invalid): a Majority Quorum of Invalid votes has been received -> broadcast Quorum message
  • Fail (NoCandidate): a Majority Quorum of NoCandidate votes has been received -> broadcast Quorum message
  • Fail(NoQuorum): a Majority Quorum of NoQuorum votes has been received -> broadcast Quorum message
  • Timeout: -> no output

Quorum messages with Fail results are used to attest failed iterations. Invalid and NoCandidate fails are additionally used for slashing.

• Quorum message:
  • Header:
    • Prev_Hash
    • Round
    • Iteration
    • StepNum: not necessary
  • Payload:
    • Result: Success, Fail (Invalid), Fail (NoCandidate), Fail(NoQuorum)
    • Candidate_Hash: empty if Vote=NoCandidate or Vote=NoQuorum
    • Validation_Votes
    • Ratification_Votes

Votes are checked against the Result's vote (Valid,Invalid,NoCandidate,NoQuorum), which must be the same vote for both Validation and Ratification. An exception to this is NoQuorum, which can differ from the Validation result.

ProcessQuorum

• Success: accept candidate
• Fail (Invalid): add to FailedIterations; slash for invalid block
• Fail (NoCandidate): add to FailedIterations; slash for missed block
• Fail (NoQuorum): add to FailedIterations

Relevant Context

• Waiting for a majority of Invalid/NoCandidate votes in Validation allows to mutually exclude these votes in the Ratification step (since there can't be a Ratification vote NoCandidate if there was a majority of Invalid votes in Validation)
• In Ratification:
• we wait for a Supermajority of Valid in order to be sure most provisioners are accepting the new block (i.e., they are aligned with the other provisioners)
• we wait for a Majority of Invalid/NoCandidate for the same reason as for Valid: we want a large portion of provisioners to be aligned on the iteration as failed.
• While a single NoQuorum result on Validation is not a definitive result (there might have been a Quorum seen by other provisioners), a majority of NoQuorum in the Ratification step ensure no other result is possible, hence we produce the Quorum message that can be used to attest the iteration as failed.

Implementation

• Consensus messages are being updated by consensus: add support for Invalid vote #1264

Notes

• $NoCandidate$ and $NoQuorum$ votes should be disabled in Emergency Mode, since step timeouts do not interrupt the step itself.