New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposer priority value is not carried over after round skips #3044

Open
Slamper opened this Issue Dec 18, 2018 · 10 comments

Comments

Projects
None yet
7 participants
@Slamper
Copy link
Contributor

Slamper commented Dec 18, 2018

We are seeing proposers being reselected for a few blocks in a row in the game_of_stakes network

image

Here is what we were able to see:

Proposer Round of polka Height Proposer Priority of proposer
703 DF8C99E762662D4D575E3709C96B1A0FDC81B27D 0 -1001008
702 DA80EAEC28CB97523FCD34EAC3A48F3591338129 0 -965470
701 2B8ABD3EE563B006D71156784DB4D539E691C812 0 -955206
700 2B8ABD3EE563B006D71156784DB4D539E691C812 1 1828306
699 83AB321E012C57746689FED3A6064DF331F81007 0 -937074
698 83AB321E012C57746689FED3A6064DF331F81007 1 1832205
697 50C18305F49BE332E4C6BCDE0DEECD4A22B1D6A4 0 -931810
696 FBC7F1617ADECC38BEF6329F01F7E0123689C2CD 0 -939515
695 FBC7F1617ADECC38BEF6329F01F7E0123689C2CD 1 1820486
694 FBC7F1617ADECC38BEF6329F01F7E0123689C2CD 2 1810486
693 FBC7F1617ADECC38BEF6329F01F7E0123689C2CD 3 1800486
692 B2971B2E464209C6A925649252E5D2848B0A20AF 0 -992613
691 B2971B2E464209C6A925649252E5D2848B0A20AF 1 1776443
690 B2971B2E464209C6A925649252E5D2848B0A20AF 2 1761344
689 B2971B2E464209C6A925649252E5D2848B0A20AF 3 1746245
688 CD8EC884F2A65119F1AA953DE5BFCAF2C3A8B4DE 0 -1033338
687 B4D271B369B728E0A716300193E16DF68010B062 0 -1035199
686 B4D271B369B728E0A716300193E16DF68010B062 1 1733793
685 B4D271B369B728E0A716300193E16DF68010B062 2 1718814
684 B4D271B369B728E0A716300193E16DF68010B062 3 1687937
683 B4D271B369B728E0A716300193E16DF68010B062 4 1672959
682 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 0 -1070297
681 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 1 1688521
680 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 2 1678521
679 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 3 1668521
678 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 4 1658521
677 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 5 1648521
676 6B275FFA0571EEFC4482CD7A6CAE836F5785CB4E 6 1652793

This looks like that in rounds > 0 the proposer priority is not decremented for the actual proposer. This is most likely a bug in the proposer selection.

What is actually happening is:

Block 1 R0: Val C: round skip <- prio decremented
Block 1 R1: Val B: round skip
Block 1 R2: Val A: Proposes

Block 2 R0: Val B: round skip <- prio decremented
Block 2 R1: Val C: propose

Block 3 R0: Val C: propose <- prio decremented

==

I would expect the following:

Block 1 R0: Val C: round skip <- prio decremented
Block 1 R1: Val B: round skip <- prio decremented
Block 1 R2: Val A: Proposes <- prio decremented

Block 2 R1: Val D: propose <- prio decremented

==

NextValidators is already specified 1 block ahead so any updates to the proposer priority at the previous height are ignored (e.g. round skips).

In updateState instead of nValSet.IncrementProposerPriority(1) we could do nValSet.IncrementProposerPriority(n_rounds_prev_block)

CC: @ebuchman @zmanian @jaekwon @ValarDragon @milosevic @melekes

@Slamper Slamper changed the title Possible bug in proposer selection in GoS Proposer priority value is not carried over after round skips Dec 18, 2018

@jaekwon jaekwon removed the bug label Dec 18, 2018

@jaekwon

This comment has been minimized.

Copy link
Contributor

jaekwon commented Dec 18, 2018

This is working as designed, for round incrementAccums to not carry over into the next height. And, the proposer for (H,R) is the same as (H+1,R-1) in the absence of validator set changes.

The main problem with any round data carrying over is that there actually isn't a canonical round for a commit until it is agreed upon by inserting it into the blockchain. So, a commit might happen at (H,R), but it's possible that the other validators didn't see (H,R) but rather only a commit at (H,R+1) and so on. What's guaranteed by safety is that the decided block will be the same (given assumptions about the number of byzantine validators), not that everyone agrees on which round it happened.

So carrying over rounds potentially introduces an additional degree of freedom for exploitation by a chain of proposers. Comparatively, the current proposer algorithm is more deterministic. It's probably worth considering alternative implementations for a public blockchain setting, though I'm not sure what would be simplest. It may get exploited for GoS but it doesn't seem like a pressing issue for mainnet just yet. Lets consider many alternatives and pick the simplest alternative, it looks like the solution space is large.

@dlguddus

This comment has been minimized.

Copy link

dlguddus commented Dec 18, 2018

for round incrementAccums to not carry over into the next height. OK.

Then, doesn't the priority still should decrease by number of proposed blocks multiplied by total power somewhere after that?

Fair proposing logics should possess the rule that at any given circumstances, every proposing of a block should result in decreasing priority by total-power no matter reason behind.

If the logic should choose straight consecutive proposer, it is fine. However current sdk is lack of appropriate priority decreasing process existence.

Or, if the consecutive proposings are not punished by decreasing priority, the proposings should not result in proposer bonus rewards too. Two of them should always be together.

@zmanian

This comment has been minimized.

Copy link
Contributor

zmanian commented Dec 18, 2018

My sense of things is that there may be no alternative to eventually sticking a Verifiable Random Function into the proposer selection algorithm.

@dlguddus

This comment has been minimized.

Copy link

dlguddus commented Dec 18, 2018

proposer selection and decreasing priority are two independent different issues, isnt it??
Can't we leave the first issue as now, and solve only the later issue?

@ValarDragon

This comment has been minimized.

Copy link
Member

ValarDragon commented Dec 18, 2018

I agree as well Zaki. I don't see a clear way to prove that a deterministic proposer election has the properties we want (#2890) whereas its fairly trivial with randomness. (I see two possibilities VRF from sometime in the last blocks, or VDFs. VRF's are quite well understood, so may not be too far out)

@zmanian

This comment has been minimized.

Copy link
Contributor

zmanian commented Dec 19, 2018

So when IncrementProposerPriority was implemented, we did not have the proposer in the Block Header so it naively just moves the the proposer 1 position forward.

I think we have option now the looking the proposer of the block when we apply changes and rotate the validator pool until we rotate pass the proposer once.

https://github.com/tendermint/tendermint/blob/master/types/validator_set.go#L76-L94

@ValarDragon

This comment has been minimized.

Copy link
Member

ValarDragon commented Dec 19, 2018

I think your right @zmanian (Though it doesn't actually need the proposer address, it just needs the round number in the header)

I also agree that this may not be a huge problem for mainnet, but my sense of how using round number appearing in the header is as follows (I also think its what @zmanian is implying, thought it would be useful to write below for concreteness):

The hash of the block committed (which everyone is voting on) depends on the block header. The block header contains the round number.

Once a validator sees enough precommits to be a commit in the round which they are at, they would calculate a 'candidate-next-proposer' and see if it is themself. If so, propose the next block. Everyone else upon receiving the 'next block' would then learn which the round the prior commit was in (as that is in the block header), and can consequently verify the current proposer is correct. This should give us sufficient flexibility to decrement proposer priorities as we so choose for rounds [0, round used in commit].

The DOS potential does increase now, as when you receive the newly proposed block's header, you first have to parse its round, then derive the correct proposer, and see if it matches. Whereas previously figuring out the correct proposer for the subsequent block was super easy, since it was round-independent. This cost should be fairly cheap by just caching the candidate-next-proposer for all rounds you've entered though.


Is the above right, and is the additional cost sufficiently cheap for us to implement? Lite clients would also have to do this sort of replay to determine the proposer priorities based off of the round, but this is a trivial amount of computation as compared to signature verification. (I definitely think its a #postlaunch thing to do though. I'd also suggest only decrementing the proposer, what hendrik was originally suggesting as well)

bshang added a commit to bshang/tendermint that referenced this issue Dec 20, 2018

Skip missed proposer to current proposer in NextValidators(tendermint…
…#3044)

	1. skip missed proposers if it has two or more
	2. differ its position in next round
@bshang

This comment has been minimized.

Copy link

bshang commented Dec 20, 2018

This patch would be the following:

Block 1 R0: Val C: round skip <- prio decremented (with slashFactor decreased)
Block 1 R1: Val B: round skip <- prio decremented (with slashFactor decreased)
Block 1 R2: Val A: Proposes <- prio decremented

Block 2 R0: Val A: propose <- prio decremented

AND NEXT VALIDATOR ROUND WOULD BE:

Block 1xx R0: Val C: round skip <- prio decremented (with slashFactor decreased)
Block 1xx R1: Val B: round skip <- prio decremented (with slashFactor decreased)
Block 1xx R2: Val Z: Proposes <- prio decremented

Block 1xx+1 R0: Val Z: propose <- prio decremented

AND Z WOULD BE different every VALIDATOR ROUND

is this workable?

CC: @ebuchman @zmanian @jaekwon @ValarDragon @milosevic @melekes @dlguddus @Slamper

@dlguddus

This comment has been minimized.

Copy link

dlguddus commented Dec 21, 2018

+200% if it is possible!

@zmanian

This comment has been minimized.

Copy link
Contributor

zmanian commented Dec 21, 2018

This is possible. I have some work in progress code on it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment