consensus: update state to prevote nil when proposal block does not match locked block. by williambanfield · Pull Request #6986 · tendermint/tendermint

williambanfield · 2021-09-23T21:46:31Z

This change updates state.go to modify the conditions under which a validator will issue prevote for a proposed block. This change attempts to bring the prevote logic in this go implementation more inline with the algorithm as described in the 2018 tendermint arXiv paper.

The change adds a condition under which this code will issue a prevote. The code will now prevote if +2/3 prevotes were seen for a block in a previous round and that block is proposed in current round. This matches the condition on line 28 of the arXiv paper. Prevoting in this condition must not update the locked block. The locked block should only be updated if +2/3 prevotes were seen within the same round as the proposal. TestState_PrevotePOLFromPreviousRound was added to check the correctness of this change.

This change also removes a condition under which the code will issue a prevote. Previously, the code issued for the validator's locked block regardless of what the proposal was for. The code will now only issue a prevote for its locked block if it matches the currently proposed block. TestStateLock_PrevoteNilWhenLockedAndMissProposal was added to check the correctness of this change.

Other tests were modified to ensure we correctly issue prevotes for nil or the locked block as a result of this change.

closes: #6850

ValarDragon · 2021-10-05T20:17:18Z

Left some comments on the docs as I tried to understand the new change / check correspondence. Plz don't block merge of this on me / these comments. Just thought I'd review try to understand more of the consensus code while its being touched!

internal/consensus/state.go

Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com>

cason · 2021-10-15T09:13:48Z

internal/consensus/state.go

+	*/
+	blockID, ok := cs.Votes.Prevotes(cs.Proposal.POLRound).TwoThirdsMajority()
+	if ok && cs.ProposalBlock.HashesTo(blockID.Hash) && cs.Proposal.POLRound >= 0 && cs.Proposal.POLRound < cs.Round {
+		if cs.LockedRound <= cs.Proposal.POLRound {


Why >= here? The log message states "round later than the locked round", so > will be more consistent with it.

Well, it is true that the ArXiv algorithm uses this condition: lockedRound_p ≤ v_r.

The code is implicitly assuming the following: if Proposal.POLRound == LockedRound AND Prevotes(Proposal.POLRound).TwoThirdsMajority() == id(ProposalBlock) THEN ProposalBlock == LockedBlock.

Which is very likely to be true. But since hashes are performed lots of times in this code, maybe is better to double check this in the following if.

The code is implicitly assuming the following: if Proposal.POLRound == LockedRound AND Prevotes(Proposal.POLRound).TwoThirdsMajority() == id(ProposalBlock) THEN ProposalBlock == LockedBlock.

I'm not totally sure we make that assumption. We have 2/3 prevotes from some round round_p. Given that we received 2/3 prevotes for the block in some round round_p, and round_p >= locked_round then we are safe to prevote that block, whether it matches our locked block or not.

If round_p == locked_round, then the block that received 2/3+ votes in round_p must be our locked block, mustn't it? I am assuming that <1/3 of the voting power is Byzantine... but I'm not sure if we should assume this.

Definitely, there is no reason for it not to match our locked block. I'm more saying that from the perspective of the correctness of the algorithm, seeing 2/3 prevotes in a round >= to our locked round is enough for us to prevote the block. It absolutely should match the locked block, and from the current implementation I'm not sure why it ever would not (happy to be corrected here), but I think that keeping it in this notation allows us to match the arXiv paper. I think keeping it in the same notation as the arXiv paper is preferable so that we can more easily know we're making safe changes to it as we go forward.

'v_r' is a round greater than our current locked round.

Agreed. But in this case I would make the comment consistent: v_r is not lesser/smaller than...

Good point, fixed.

internal/consensus/state.go

cason

Reviewed the implementation, not the tests yet.

cason

Tests reviewed, minor comments.

internal/consensus/state_test.go

williambanfield · 2021-10-15T18:35:22Z

Thanks @cason for the review! Looks like I missed a few comments while refactoring. Very appreciated.

williambanfield · 2021-10-15T18:40:41Z

Another situation in which POLRound > LockedRound is when POLRound = ValidRound > LockedRound. This happens when we receive a block and 2/3+ Prevotes for that block after the PrevoteStep of that round. This causes Valid{Block,BlockParts,Round} to be updated while Locked{} are not, as there is a contract that Locked{} should match the previous issued Prevote.

I see, so we would have missed 2/3 prevotes during the actual time that would have been actionable, but still retained them for a future POL check. Thanks for the info.

zeu5 · 2021-11-12T11:18:07Z

We ran a few test scenarios around this change.

We test if a replica unlocks on seeing 2f+1 nil votes to vote on a new proposal.
We test if a replica continues to vote on a locked block.
We test if a replica which has locked onto a value, is able to relock onto a new proposal when it receives 2f+1 votes for the new proposal.

The outcome was that the first test case fails and the other two pass. This was the expected behaviour.
We also ran other test cases that are not related to this change.

We test if we can skip rounds by not delivering enough votes and changing votes.
We test if we can skip rounds by not delivering the BlockPart messages.

As expected, the other two test cases were successful as well.

The test cases are described in more detail here - https://github.com/ds-test-framework/tendermint-test/blob/master/docs/report/Tendermint.md. Apologies for posting it late but please let me know if you have any comments or feedback.

josef-widder · 2021-11-12T14:24:45Z

Thanks a lot @zeu5!!
@williambanfield, @cmwaters: What do you think? Should we track these outcomes of the tests somehow within the repo? I am not sure a discussion in a closed PR is very visible in the future...

…atch locked block. (#6986) * add failing test * tweak comments in failing test * failing test comment * initial attempt at removing prevote locked block logic * comment out broken function * undo reset on prevotes * fixing TestProposeValidBlock test * update test for completed POL update * comment updates * further unlock testing * update comments * Update internal/consensus/state.go * spacing nit * comment cleanup * nil check in addVote * update unlock description * update precommit on relock comment * add ensure new timeout back * rename IsZero to IsNil and replace uses of block len check with helper * add testing.T to new assertions * begin removing unlock condition * fix TestStateProposerSelection2 to precommit for nil correctly * remove erroneous sleep * update TestStatePOL comment * update relock test to be more clear * add _ into test names * rename slashing * udpate no relock function to be cleaner * do not relock on old proposal test cleanup * con state name update * remove all references to unlock * update test comments to include new * add relock test * add ensureRelock to common_test * remove all event unlock * remove unlock checks * no lint add space * lint ++ * add test for nil prevote on different proposal * fix prevote nil condition * fix defaultDoPrevote * state_test.go fixes to accomodate prevoting for nil * add failing test for POL from previous round case * update prevote logic to prevote POL from previous round * state.go comment fixes * update validatePrevotes to correctly look for nil * update new test name and comment * update POLFromPreviousRound test * fixes post merge * fix spacing * make the linter happy * change prevote log message * update prevote nil debug line * update enterPrevote comment * lint * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * add english description of alg rules * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * comment fixes from review * fix comment * fix comment Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com>

…not match locked block (tendermint#1203) * consensus: update state to prevote nil when proposal block does not match locked block. (tendermint#6986) * add failing test * tweak comments in failing test * failing test comment * initial attempt at removing prevote locked block logic * comment out broken function * undo reset on prevotes * fixing TestProposeValidBlock test * update test for completed POL update * comment updates * further unlock testing * update comments * Update internal/consensus/state.go * spacing nit * comment cleanup * nil check in addVote * update unlock description * update precommit on relock comment * add ensure new timeout back * rename IsZero to IsNil and replace uses of block len check with helper * add testing.T to new assertions * begin removing unlock condition * fix TestStateProposerSelection2 to precommit for nil correctly * remove erroneous sleep * update TestStatePOL comment * update relock test to be more clear * add _ into test names * rename slashing * udpate no relock function to be cleaner * do not relock on old proposal test cleanup * con state name update * remove all references to unlock * update test comments to include new * add relock test * add ensureRelock to common_test * remove all event unlock * remove unlock checks * no lint add space * lint ++ * add test for nil prevote on different proposal * fix prevote nil condition * fix defaultDoPrevote * state_test.go fixes to accomodate prevoting for nil * add failing test for POL from previous round case * update prevote logic to prevote POL from previous round * state.go comment fixes * update validatePrevotes to correctly look for nil * update new test name and comment * update POLFromPreviousRound test * fixes post merge * fix spacing * make the linter happy * change prevote log message * update prevote nil debug line * update enterPrevote comment * lint * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * add english description of alg rules * Update internal/consensus/state.go Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * comment fixes from review * fix comment * fix comment Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> * Fix UTs * Addressed comments * Add changelog * Update consensus/state.go Co-authored-by: Hernán Vanzetto <15466498+hvanz@users.noreply.github.com> --------- Co-authored-by: William Banfield <4561443+williambanfield@users.noreply.github.com> Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com> Co-authored-by: Hernán Vanzetto <15466498+hvanz@users.noreply.github.com>

williambanfield and others added 30 commits September 16, 2021 17:04

add failing test

6e826f8

tweak comments in failing test

883bec8

failing test comment

fe84c0c

initial attempt at removing prevote locked block logic

72b8deb

comment out broken function

79469af

undo reset on prevotes

108eecf

fixing TestProposeValidBlock test

ec740a8

update test for completed POL update

abc07b4

comment updates

8bfedb6

further unlock testing

914a85e

update comments

3b0ecf7

Update internal/consensus/state.go

9cfa604

spacing nit

c741c1c

comment cleanup

41c3240

nil check in addVote

f94528b

update unlock description

afff87f

update precommit on relock comment

c69f933

add ensure new timeout back

51db3f8

rename IsZero to IsNil and replace uses of block len check with helper

dc12a19

Merge branch 'wb/proposer-based-timestamps' into wb/issue-6849

3f854d8

add testing.T to new assertions

0a2098e

begin removing unlock condition

cffe1fe

fix TestStateProposerSelection2 to precommit for nil correctly

6bc596f

remove erroneous sleep

bf90e1c

update TestStatePOL comment

2bb9ca2

update relock test to be more clear

b7d4381

add _ into test names

e47ef0f

rename slashing

00b758b

udpate no relock function to be cleaner

f559ece

do not relock on old proposal test cleanup

962ceef

ValarDragon reviewed Oct 5, 2021

View reviewed changes

internal/consensus/state.go Show resolved Hide resolved

ValarDragon reviewed Oct 5, 2021

View reviewed changes

internal/consensus/state.go Show resolved Hide resolved

williambanfield and others added 7 commits October 14, 2021 08:03

update prevote nil debug line

5935870

update enterPrevote comment

ba0bb1a

lint

c8e6d61

Update internal/consensus/state.go

57e79ec

Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com>

Update internal/consensus/state.go

aec17c6

Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com>

add english description of alg rules

bec293d

Update internal/consensus/state.go

0f4844a

Co-authored-by: Dev Ojha <ValarDragon@users.noreply.github.com>

cason reviewed Oct 15, 2021

View reviewed changes

internal/consensus/state_test.go Outdated Show resolved Hide resolved

internal/consensus/state_test.go Outdated Show resolved Hide resolved

internal/consensus/state_test.go Outdated Show resolved Hide resolved

internal/consensus/state_test.go Outdated Show resolved Hide resolved

williambanfield added 2 commits October 15, 2021 14:34

comment fixes from review

0db34a5

Merge remote-tracking branch 'origin/wb/issue-6850' into wb/issue-6850

da3b385

williambanfield added S:automerge Automatically merge PR when requirements pass and removed S:automerge Automatically merge PR when requirements pass labels Oct 15, 2021

williambanfield added 2 commits October 15, 2021 15:54

fix comment

8df0ab6

fix comment

5b9efdd

williambanfield merged commit fe2ed68 into wb/proposer-based-timestamps Oct 23, 2021

williambanfield deleted the wb/issue-6850 branch October 23, 2021 14:12

williambanfield restored the wb/issue-6850 branch September 9, 2022 16:12

sergio-mena mentioned this pull request Aug 3, 2023

Forward-port: update state to prevote nil when proposal block does not match locked block cometbft/cometbft#1203

Merged

3 tasks

Conversation

williambanfield commented Sep 23, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ValarDragon commented Oct 5, 2021

Uh oh!

Uh oh!

Uh oh!

cason Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

cason Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

cason Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

williambanfield Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

cason Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

williambanfield Oct 15, 2021 • 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!

cason Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

williambanfield Oct 15, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

cason left a comment

Choose a reason for hiding this comment

Uh oh!

cason left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

williambanfield commented Oct 15, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

williambanfield commented Oct 15, 2021

Uh oh!

zeu5 commented Nov 12, 2021

Uh oh!

josef-widder commented Nov 12, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

williambanfield commented Sep 23, 2021 •

edited

Loading

williambanfield Oct 15, 2021 •

edited

Loading

williambanfield commented Oct 15, 2021 •

edited

Loading