proposer-based time: address implementation concerns

Question

proposer-based time: address implementation concerns

Closed this issue 3 years ago · 12 comments

Currently and ADR for PBTS is drafted and the implementation is following. We need to keep spec and code aligned. This issue tracks necessary changes.

separate hashes for value and time
clarify how v and t are written in the blocks. Clarify the one-off confusion

Answer 1 · 2021-07-20T15:04:42.000Z

To add some more context to these problems (as far as I understand them), the one-off problem is that in BFT time, the timestamp in the header, h, corresponds to the time derived from the votes of the previous block, h - 1. In PBTS, validators vote for a (v, t) combination. According to the rule here, a validator that has locked on (v1, t1), can also vote on (v1, t2) and (v1, tn), i.e. any other timestamp proposed in later rounds without needing to change lock so long as that timestamp is still considered timely. The implication of this is that, 2/3+ may agree on a value v (which can be finalized in height h), but the canonical time, may not be agreed upon until h + 1 when the proposer chooses which one of the rounds to add to the last commit.

Does this mean that the timestamp that a proposer proposes in the header is that of the previous block? Do we want the time reported to the application to be delayed by a block (like it was before) or would we prefer instead to not allow proposals in later rounds for the same block to be able to increment the timestamp? Take into consideration that the chance of multiple rounds happening is very seldom anyway. This also means that to verify the commit for a block at height h you also need to get the timestamp in the header at h + 1

Answer 2 · 2021-07-20T15:16:12.000Z

As an auxiliary thought I had whilst scrolling through the code. Vote is currently:

type Vote struct {
	Type             tmproto.SignedMsgType `json:"type"`
	Height           int64                 `json:"height"`
	Round            int32                 `json:"round"`    // assume there will not be greater than 2_147_483_647 rounds
	BlockID          BlockID               `json:"block_id"` // zero if vote is nil.
	Timestamp        time.Time             `json:"timestamp"`
	ValidatorAddress Address               `json:"validator_address"`
	ValidatorIndex   int32                 `json:"validator_index"`
	Signature        []byte                `json:"signature"`
}

But seeing that there can only be one proposal per round, it seems that a lot of this information is gossiped around that other nodes can already deduce. We can keep all this information around if it serves as cache but for the over the wire message, I would propose only having the following:

type Vote struct {
	Type             tmproto.SignedMsgType `json:"type"`
	Height           int64                 `json:"height"`
	Round            int32                 `json:"round"` 
        ProposalRound    int32                 `json:"proposal_round"`
	ValidatorIndex   int32                 `json:"validator_index"`
	Signature        []byte                `json:"signature"`
}

Answer 3 · 2021-07-20T16:04:47.000Z

To add some more context to these problems (as far as I understand them), the one-off problem is that in BFT time, the timestamp in the header, h, corresponds to the time derived from the votes of the previous block, h - 1.

Does this mean 'the timestamp for the header for block at height h'?

a validator that has locked on (v1, t1), can also vote on (v1, t2) and (v1, tn), i.e. any other timestamp proposed in later rounds without needing to change lock so long as that timestamp is still considered timely.

The exception here from the spec [PBTS-ALG-DECIDE.0] is that if it sees greater than 2/3 precommits for a block, it will ignore timely and precommit either way.

I think what you're saying here makes sense @cmwaters. If I'm understanding correctly, it seems the correct thing to do is change so that the timestamp being proposed at height h is written into the block at height h. BFTTime wrote the timestamp for height h-1 into the block at height h. It did this by gathering +2/3 precommits from the previous height. These +2/3 precommits for height h-1 were also written into the block at height h in the last_commit field. So, despite them representing information for height h-1 they were both present in the block of height h. In this way, the timestamp field in BFTtime did not require maintaining header information across heights (happy to be corrected on this). Because the information would no longer come from the last_commit, if we maintain this off-by-one timestamp scheme, validators would therefore have to maintain header information across rounds which seems cumbersome.

Answer 4 · 2021-07-22T15:54:33.000Z

Does this mean 'the timestamp for the header for block at height h'?

yup

The exception here from the spec [PBTS-ALG-DECIDE.0] is that if it sees greater than 2/3 precommits for a block, it will ignore timely and precommit either way.

Ah yeah I remember discussing this. In some areas of the spec, if 2/3 precommit an invalid block, for example, with a different state hash, a node will just refuse it and shutdown. I wondered if we'd do the same if the time was out and it seems like we agreed to just go with the flow if 2/3+ precommit an untimely block.

In this way, the timestamp field in BFTtime did not require maintaining header information across heights (happy to be corrected on this)

Correct

if we maintain this off-by-one timestamp scheme, validators would therefore have to maintain header information across rounds which seems cumbersome.

do you mean across heights? I guess actually it doesn't matter because a node running fast sync or lagging behind in consensus won't verify the time at all (i.e. no timely check) but just take it as correct (so long as it is monotonically increasing). Even then, I think there is more value that the time on header h is for header h (and not h - 1). Not allowing to vote on proposals with the same block but different timestamp also solves the issue of splitting up the hashes

Answer 5 · 2021-07-22T16:41:28.000Z

do you mean across heights?

Yup!

I think a very closely related issue to this is which timestamp is chosen in the precommit logic? The logic in the spec does not disambiguate between the proposed timestamp, the precommited timestamp and the prevoted timestamp. This can be seen in [pbts-alg-new-prevote.0]

Finally, I think I'm still not clear on why the PREVOTE message needs a timestamp at all. It's not used to change a locked value and it's not used in the precommit so it appears to me that it can just be dropped?

Answer 6 · 2021-08-04T10:47:44.000Z

Figure out lines: unlocking and sending vote without proposal.
@milosevic will have a look at spec/code discrepancies

Answer 7 · 2021-08-04T10:49:33.000Z

@cezarad can generate traces to analyze code/protocol changes

Answer 8 · 2021-08-05T12:32:11.000Z

I just want to enumerate what I currently don't know in regards to proposer based timestamp spec:

Say I prevote (v1, t1) and lock on it. If in the following round I receive a proposal for (v1, t2) where t2 is timely, I can also prevote/commit (v1, t2). What happens if t2 is not timely. Do I prevote (v1, t1) again or prevote nil?
Is there any circumstance in which I am in the second round and I prevote for the proposal in the first round (v1, t1)? If not this can simplify some of the consensus mechanics because therefore I can only vote for or against the proposal in my round only.
In the implementation, if we timeout during the propose phase (i.e. we never got a proposal) and we are locked on a block from a prior round, we will prevote that. Is this behavior correct in the context of proposer based timestamps. Should we instead be prevoting nil. For extra context, if we timeout in the prevote phase and don't reach 2/3+ prevotes of any block we will precommit nil

Answer 9 · 2021-08-05T19:32:51.000Z

Say I prevote (v1, t1) and lock on it. If in the following round I receive a proposal for (v1, t2) where t2 is timely, I can also prevote/commit (v1, t2). What happens if t2 is not timely. Do I prevote (v1, t1) again or prevote nil?

Is there any circumstance in which I am in the second round and I prevote for the proposal in the first round (v1, t1)? If not this can simplify some of the consensus mechanics because therefore I can only vote for or against the proposal in my round only.

Looking over the prevote cases from the spec

upon timely(⟨PROPOSAL, h_p, round_p, (v, tprop), vr⟩) from proposer(h_p, round_p) AND 2f + 1 ⟨PREVOTE, h_p, vr, id((v, tvote)⟩ 
while step_p = propose ∧ (vr ≥ 0 ∧ vr < round_p) do {
  if valid(v) ∧ (lockedRound_p ≤ vr ∨ lockedValue_p = v) {
    broadcast ⟨PREVOTE, h_p, roundp, id(v, tprop)⟩
  }
  else {
    broadcast ⟨PREVOTE, hp, roundp, nil⟩
  }
  step_p ← prevote
}

@cmwaters If I'm reading this correctly, round_p in the PROPOSAL must match the validator's round and the PROPOSAL must be timely for this rule to fire. That means if a timely PROPOSAL is not received in round_p, either because the message was not received by the timeout or because the message was received but timestamp was too far off of the validator's, this upon rule is not triggered for the round. If this upon rule is never triggered by timeoutPropose time, then the spec dictates we should run onTimeoutPropose and PREVOTE nil for that round.

Answer 10 · 2021-08-06T11:37:39.000Z

Say I prevote (v1, t1) and lock on it. If in the following round I receive a proposal for (v1, t2) where t2 is timely, I can also prevote/commit (v1, t2). What happens if t2 is not timely. Do I prevote (v1, t1) again or prevote nil?

According to PBTS spec you shoudl prevote nil.

Is there any circumstance in which I am in the second round and I prevote for the proposal in the first round (v1, t1)? If not this can simplify some of the consensus mechanics because therefore I can only vote for or against the proposal in my round only.

Neither in the PBTS spec nor in the arXiv paper, but...

In the implementation, if we timeout during the propose phase (i.e. we never got a proposal) and we are locked on a block from a prior round, we will prevote that. Is this behavior correct in the context of proposer based timestamps. Should we instead be prevoting nil. For extra context, if we timeout in the prevote phase and don't reach 2/3+ prevotes of any block we will precommit nil

... it is indeed like that in the implementation. We had a discussion with @milosevic, and in the process of code/spec alignment, the current plan is to remove this behavior (prevote for round 1 in round 2) from the implementation. We will have to check interlocking with another rule, though, that also differs in the implementation (release lock on 2/3 prevote nil)

Answer 11 · 2021-08-06T15:32:08.000Z

There is now a pull request for the ADR in tendermint/tendermint#6799. I suggest we move some of this discussion there where applicable.

Answer 12 · 2021-10-13T16:56:40.000Z

BFTTime wrote the timestamp for height h-1 into the block at height h. It did this by gathering +2/3 precommits from the previous height. These +2/3 precommits for height h-1 were also written into the block at height h in the last_commit field.

Hi guys, joining this discussion. If you consider that the timestamp of a block is the time at which it was assembled, the current solution uses for block at height H a timestamp that is actually closer to what will be the timestamp (according to my definition above mentioned) of block H+1. This happens because Precommit is the last phase of a round, which starts two communication delays after the blocking being assembled. In other words, by retrieving a timestamp from the median of the Precommit timestamps, we have a timestamp that is closer to the Commit time of a block, than to the Propose time of a block.