[CORE-435] Prevote yes on recent valid POL Proposal by BrendanChou · Pull Request #14 · dydxprotocol/cometbft

BrendanChou · 2023-07-26T22:38:34Z

Description

If a proposal with a proof-of-lock (POL) is proposed, validate both of the following two lines:

That this validator has seen +2/3 prevotes for this block in the given POL Round (Line 28 of whitepaper algorithm)
That Proposed Block = Locked Block OR POL Round >= Locked Round (Line 29 of whitepaper algorithm)

If these two things both evaluate to true, then prevote the block without consulting the Application (i.e. without calling ProcessProposal) to determine the validity of the block.

If either of these two checks evaluate to false, then prevote nil. Even if the block is valid, we don't prevote for the block. (Line 29/31 of whitepaper algorithm)

This change is aimed at fixing the liveness issue experienced in public testnet 1.

Implementation

Unfortunately it looks more complicated than necessary primarily because we need the Debug statements to say different things in different cases, so there are two places to prevote the block and two places to prevote nil (rather than just having one each).

Justification

It should be fine to not consult the Application to validate the block in the above case. To show this, let us first state that ProcessProposal may have both deterministic and non-deterministic validation.

In order to proceed with consensus, we choose to ignore any non-deterministic checks. This is the same logic as in the PBTS implementation (i.e. ignore the timely check for POL proposals).
For deterministic checks, we know that at least one honest validator has validated the block. This is because we validate that +2/3 of validators have prevoted the block in a previous round. On the lowest round this is true for the block (assuming that we do not have +2/3 Byzantine validators) ProcessProposal (and therefore its deterministic checks) MUST have passed at least one honest validator. Therefore, there no need to run the deterministic checks locally.

References

Based on some logic added for the PBTS here

This logic is also largely the same as lines 28-32 on page 6 of the Tendermint whitepaper, however we do not validate the block with the Application (i.e. ProcessProposal) to determine valid(v). As I have justified above, this check to valid(v) is unnecessary assuming <2/3 Byzantine validators.

teddyding · 2023-07-27T13:58:27Z

consensus/state.go

 	}

+	// Determine if the proposed block has a sane, non-nil proof-of-lock.
+	if cs.Proposal.POLRound >= 0 && cs.Proposal.POLRound < cs.Round {


This new case only takes effect when LockedBlock == nil, due to line 1275

This is a conscious choice to bring minimal code changes to current CometBFT implementation in this PR

We only merge the LockedBlock fix above in a follow-up PR. See https://linear.app/dydx/issue/CORE-434/merge-locked-block-logic-fix

teddyding · 2023-07-27T14:01:40Z

consensus/state.go

+			}
+
+			// Validate the proposed block is equal to our locked block.
+			if cs.ProposalBlock.HashesTo(cs.LockedBlock.Hash()) {


Currently this line won't be true due to line 1275

ttl33 · 2023-07-27T14:45:10Z

Can you help me understand Proposed Block = Locked Block part? IIUC, this is coming from the Tendermint white paper's consensus algorithm line 29 valid(v). Shouldn't valid(v) be interpretted as Proposed Block = Valid Block?

Nvm, you explained this here:

I have one novel claim: the check for valid(v) on line 29 of the whitepaper algorithm can be dropped and the algorithm will still fully function but allow for non-deterministic (but eventually consistent) ProcessProposal results.

teddyding · 2023-07-27T15:46:41Z

Nit on PR title: recent valid POL Proposal may be more accurate than any valid POL Proposal

ttl33 · 2023-07-28T17:47:01Z

It should be fine to not consult the Application to validate the block in the above case. To show this, let us first state that PrepareProposal may have both deterministic and non-deterministic validation.

nit: In the PR description's justification, should it read ProcessProposal instead of PrepareProposal?

linear · 2023-07-28T18:20:36Z

CORE-435 Prevote yes on recent valid POL Proposal

AI for chain halt outage

teddyding · 2023-07-28T18:30:08Z

consensus/state.go

+		if ok && cs.ProposalBlock.HashesTo(blockID.Hash) {
+			// Validate the proof-of-lock round is at least as new as the possible locked round.
+			// (vr >= 0, vr > round_p, 2f+1 prevotes at round vr, lockedRound_p <= vr) execute 30.
+			if cs.Proposal.POLRound >= cs.LockedRound {


Before we merge the locked block fix, we will only reach here when LockedRound == -1 and LockedBlock == nil .

In the context of the recent liveness outage, this means that at round 1:

validators who precommited and locked during round 0 will continue to vote for B0 (duet to line 1275)

validators who are not locked will also prevote for B0 since they will verify at POLRound == 0, they also witnessed 2/3+ prevotes

teddyding · 2023-07-28T18:32:24Z

TODO(CORE-436): Add unit test for logic change in a follow PR. The unit test setup is quite complicated and it should not block trying out the change in dev environments

consensus/state.go

ttl33 · 2023-07-28T19:00:19Z

consensus/state.go

+		if ok && cs.ProposalBlock.HashesTo(blockID.Hash) {
+			// Validate the proof-of-lock round is at least as new as the possible locked round.
+			// (vr >= 0, vr > round_p, 2f+1 prevotes at round vr, lockedRound_p <= vr) execute 30.
+			if cs.Proposal.POLRound >= cs.LockedRound {


can we add a comment that we are skipping valid(v) here?

ttl33 · 2023-07-28T19:46:56Z

consensus/state.go

 	logger := cs.Logger.With("height", height, "round", round)

 	// If a block is locked, prevote that.
+	// TODO(CORE-434): Incorporate fix from Proposer-based Timestamp.


nit: do we have TODOs or tickets for unit tests?

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

BrendanChou requested a review from teddyding July 26, 2023 22:38

BrendanChou changed the title ~~prevote any valid POL Proposal~~ Proof-of-Concept: Prevote yes on any valid POL Proposal Jul 26, 2023

prevote any valid POL Proposal

ddcc8d6

BrendanChou force-pushed the bc/prevote-pol branch from d5a6ff2 to ddcc8d6 Compare July 26, 2023 23:09

teddyding reviewed Jul 27, 2023

View reviewed changes

BrendanChou changed the title ~~Proof-of-Concept: Prevote yes on any valid POL Proposal~~ Proof-of-Concept: Prevote yes on recent valid POL Proposal Jul 27, 2023

teddyding changed the title ~~Proof-of-Concept: Prevote yes on recent valid POL Proposal~~ Proof-of-Concept: Prevote yes on recent valid POL Proposal. Do not blindly prevote LockedBlock Jul 28, 2023

teddyding force-pushed the bc/prevote-pol branch from 6250a78 to ddcc8d6 Compare July 28, 2023 17:58

teddyding changed the title ~~Proof-of-Concept: Prevote yes on recent valid POL Proposal. Do not blindly prevote LockedBlock~~ Proof-of-Concept: Prevote yes on recent valid POL Proposal Jul 28, 2023

teddyding changed the title ~~Proof-of-Concept: Prevote yes on recent valid POL Proposal~~ [CORE-435] Prevote yes on recent valid POL Proposal Jul 28, 2023

add docmentation and reference to paper

390fd75

teddyding marked this pull request as ready for review July 28, 2023 18:24

teddyding reviewed Jul 28, 2023

View reviewed changes

ttl33 approved these changes Jul 28, 2023

View reviewed changes

add nits

64aabe8

teddyding approved these changes Jul 28, 2023

View reviewed changes

ttl33 reviewed Jul 28, 2023

View reviewed changes

teddyding merged commit 23effc2 into dydx-fork-v0.37.2 Jul 28, 2023

teddyding deleted the bc/prevote-pol branch July 28, 2023 19:50

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

ed4345a

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

406742d

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

2f6394d

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

8506269

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

d827ebc

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

870b5bf

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

8545fdd

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 30, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

a4a0797

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

7dd5bb8

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

0643572

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

2feb10f

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

bda4292

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

a99e550

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Aug 31, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

65a7cee

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

teddyding mentioned this pull request Sep 6, 2023

Backport #1203, #1231: Avoid process proposal when correct nodes validated it; prevote nil when proposal != locked block #21

Merged

lcwik pushed a commit that referenced this pull request Dec 4, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

fdef896

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Dec 4, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

09f2700

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Dec 4, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

cd89b9a

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

lcwik pushed a commit that referenced this pull request Dec 4, 2023

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

5e6c4b6

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

roy-dydx pushed a commit that referenced this pull request Feb 20, 2024

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

e704122

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

roy-dydx pushed a commit that referenced this pull request Apr 9, 2024

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

6d0767b

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

roy-dydx pushed a commit that referenced this pull request Apr 9, 2024

[CORE-435] Prevote yes on recent valid POL Proposal (#14)

f565ae1

* prevote any valid POL Proposal * add docmentation and reference to paper * add nits --------- Co-authored-by: Teddy Ding <teddy@dydx.exchange>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[CORE-435] Prevote yes on recent valid POL Proposal#14

[CORE-435] Prevote yes on recent valid POL Proposal#14
teddyding merged 3 commits intodydx-fork-v0.37.2from
bc/prevote-pol

BrendanChou commented Jul 26, 2023 •

edited by teddyding

Loading

Uh oh!

teddyding Jul 27, 2023 •

edited

Loading

Uh oh!

teddyding Jul 27, 2023 •

edited

Loading

Uh oh!

ttl33 commented Jul 27, 2023 •

edited

Loading

Uh oh!

teddyding commented Jul 27, 2023

Uh oh!

ttl33 commented Jul 28, 2023 •

edited

Loading

Uh oh!

linear bot commented Jul 28, 2023

Uh oh!

teddyding Jul 28, 2023

Uh oh!

teddyding commented Jul 28, 2023 •

edited

Loading

Uh oh!

Uh oh!

ttl33 Jul 28, 2023

Uh oh!

ttl33 Jul 28, 2023

Uh oh!

Reviewers

Assignees

Labels

Milestone

Development

Uh oh!

3 participants

Conversation

BrendanChou commented Jul 26, 2023 • edited by teddyding Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

Implementation

Justification

References

Uh oh!

teddyding Jul 27, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

teddyding Jul 27, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ttl33 commented Jul 27, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

teddyding commented Jul 27, 2023

Uh oh!

ttl33 commented Jul 28, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

linear bot commented Jul 28, 2023

Uh oh!

teddyding Jul 28, 2023

Choose a reason for hiding this comment

Uh oh!

teddyding commented Jul 28, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

ttl33 Jul 28, 2023

Choose a reason for hiding this comment

Uh oh!

ttl33 Jul 28, 2023

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Milestone

Development

Uh oh!

3 participants

BrendanChou commented Jul 26, 2023 •

edited by teddyding

Loading

teddyding Jul 27, 2023 •

edited

Loading

teddyding Jul 27, 2023 •

edited

Loading

ttl33 commented Jul 27, 2023 •

edited

Loading

ttl33 commented Jul 28, 2023 •

edited

Loading

teddyding commented Jul 28, 2023 •

edited

Loading