Audit Suggestion 5: Unnecessary checks increase complexity

Overview

We changed the isProposalJustification function according to the QBFT formal specification (Audit suggestion 5).

To compare the changes, follow up the QBFT formal spec isProposalJustification and validRoundChange functions.

Basically, we used to:

Verify all Round-Change messages and their nested prepare messages.
Take one of the highest prepared Round-Change messages and compare its data to the attached prepare messages

Now, we:

Verify all Round-Change messages without verifying their justifications.
Check if one of the highest-prepared Round-Change messages is in accordance with the attached prepare messages. To be "in accordance" means to have the same proposed data.

Dependency

This PR is built upon the Fix - Misaligned terms PR's branch.

Discussion topics

If a proposal has no prepared round-change messages but includes a justification of prepare messages, it will be accepted. This is due to the fact that, if there's no prepared round-change, the validation will return nil without checking the prepare messages. Should we add a check to ensure that the prepare messages should be empty in this case?
A correctly signed prepared round-change message without justification is:
- valid if it's included in the justification of a proposal msg
- invalid as a single RC message. We could add a quorum check in the validation of the proposal justification, but what would be the point if we don't inspect the contents of the RC justification?

Performance implications

All times are in milliseconds.

Max processing time for the Proposal message

	Round 1	Round 2	Round 3
Old	1.5	18	18
New	1.5	8	8

Max processing time for a consensus round

	1st round	2nd round	3rd round
Old	13	64	64
New	13	44	44

The difference is 20ms (not 10ms as one could expect) because, once a quorum of Round-Change messages is received, the isReceivedProposalJustification function is called.

Namely, look at the break-down times of each phase for round 2:

	Round-Changes	Proposal	Prepares	Commits
Old	4, 9, 21	18	1, 1, 1, 1	1, 1, 1, 1
New	4, 9, 11	8	1, 1, 1, 1	1, 1, 1, 1

Tests

In the following, we list existing and added tests for the proposal phase.

The existing tests are listed for one to check the test coverage.

Valid

Existing:

[x] Valid proposal for rounds 1 and 2 (with prepared data)
[x] Valid proposal for round 5 with no preparation
[x] Proposal for a future round
[x] Proposal for a future round not prepared
[x] Proposal for the first round

Proposal fields

Message{
        MsgType(ProposalMsgType),
        Height,
        Round,
        Identifier,
        Root,
        RoundChangeJustification,
        ProposalJustification,
    }
SignedMessage{
        Signature,
        Signers([]types.OperatorID{state.Share.OperatorID}),
        Message,
        FullData,
    }

Existing:

[x] Wrong height
[x] Old round
[x] Old round with no preparation
[x] Round 15
[x] Invalid identifier
[x] Wrong signature
[x] Non-leader
[x] Unknown signer (not in committee)
[x] Multi-signers
[x] Full-data: nil
[x] Full-data: doesn't pass the value check

Added:

[x] No Root
[x] Wrong full data

Message time or multiplicity

Existing:

[x] A second proposal with the same data
[x] A second proposal with different data
[x] A second proposal with the same data
[x] A second proposal after the preparation phase
[x] A second proposal after the commit phase
[x] A proposal after force-stop

Justification - Quorum checks

Existing:

[x] No quorum of prepare msgs (2 messages)
[x] No quorum of RC msgs (2 messages)
[x] Duplicate RC msg in 4 msgs -> Valid
[x] Duplicate RC msg in 3 msgs -> No quorum
[x] Duplicate Prepare msg in 4 msgs -> Valid
[x] Duplicate Prepare msg in 3 msgs -> No quorum
[x] No quorum of RC msgs (3 messages, one with wrong signer -> no quorum)
[x] No quorum of RC msgs (3 messages, one with wrong signer -> no quorum)
[x] Duplicate RC msg (no quorum)
[x] No quorum of RC msgs (2 messages)

Justification - Logic

Existing:

[x] Invalid proposal with highest prepared RC with diff data round than prepare msg justification
[x] Invalid proposal with a prepare msg with a root value that differs from others
[x] Invalid proposal with a prepare msg with a round value that differs from others

Added:

[x] One RC message with different round
[x] All RC messages with different round
[x] Prepare messages with round > highest prepared RC round
[x] Prepare messages but no prepared RC
[x] Single prepared RC with data != prepare msgs data
[x] Single prepared RC with data == prepare msgs data
[x] All RC prepared but all with data != prepare msg data
[x] All RC prepared, only one with data == prepare msg data
[x] RC messages with invalid justification (should pass since it's not checked anymore)
[x] RC messages with empty justification (should pass since it's not checked anymore)

ssvlabs / ssv-spec