ADR 112: Proposer-Based Timestamps

Changelog

July 15 2021: Created by @williambanfield
Aug 4 2021: Draft completed by @williambanfield
Aug 5 2021: Draft updated to include data structure changes by @williambanfield
Aug 20 2021: Language edits completed by @williambanfield
Oct 25 2021: Update the ADR to match updated spec from @cason by @williambanfield
Nov 10 2021: Additional language updates by @williambanfield per feedback from @cason
Feb 2 2022: Synchronize logic for timely with latest version of the spec by @williambanfield
Feb 1 2024: Renamed to ADR 112 as basis for its adoption (#1731) in CometBFT v1.0 by @cason
Feb 7 2024: Multiple revisions, fixes, and backwards compatibility discussion by @cason
Feb 12 2024: More detailed backwards compatibility discussion by @cason
Feb 22 2024: Consensus parameters for backwards compatibility by @cason

Status

Accepted

Context

CometBFT currently provides a monotonically increasing source of time known as [BFT Time][bfttime]. This mechanism for producing a source of time is reasonably simple. Each validator adds a timestamp to each Precommit message it sends. The timestamp a correct validator sends is either the validator's current known Unix time or one millisecond greater than the previous block time, depending on which value is greater. When a block is produced, the proposer chooses the block timestamp as the weighted median of the times in all of the Precommit messages the proposer received. The weighting is defined by the amount of voting power, or stake, each validator has on the network. This mechanism for producing timestamps is both deterministic and Byzantine fault tolerant.

This current mechanism for producing timestamps has a few drawbacks. Validators do not have to agree at all on how close the selected block timestamp is to their own currently known Unix time. Additionally, any amount of voting power >1/3 may control the block timestamp. As a result, it is quite possible that the timestamp is not particularly meaningful.

These drawbacks present issues in CometBFT. Timestamps are used by light clients to verify blocks. Light clients rely on correspondence between their own currently known Unix time and the block timestamp to verify blocks they see. However, their currently known Unix time may be greatly divergent from the block timestamp as a result of the limitations of BFT Time.

The [Proposer-Based Timestamps specification (PBTS)][pbts-spec] suggests an alternative approach for producing block timestamps that remedies these issues. Proposer-based timestamps alter the current mechanism for producing block timestamps in two main ways:

The block proposer is amended to offer up its currently known Unix time as the timestamp for the next block instead of the BFT Time.
Correct validators are assumed to be equipped with synchronized clocks and only approve the proposed block timestamp if it is close enough to their own currently known Unix time.

The result of these changes is a more meaningful timestamp that cannot be controlled by <= 2/3 of the validator voting power. This document outlines the necessary code changes in CometBFT to implement the corresponding [specification][pbts-spec].

Alternative Approaches

Remove timestamps altogether

Computer clocks are bound to skew for a variety of reasons. Using timestamps in our protocol means either accepting the timestamps as not reliable or impacting the protocol’s liveness guarantees. This design requires impacting the protocol’s liveness in order to make the timestamps more reliable. An alternate approach is to remove timestamps altogether from the block protocol. BFT Time is deterministic but may be arbitrarily inaccurate. However, having a reliable source of time is quite useful for applications and protocols built on top of a blockchain.

We therefore decided not to remove the timestamp. Applications often wish for some transactions to occur on a certain day, on a regular period, or after some time following a different event. All of these require some meaningful representation of agreed upon time. The following protocols and application features require a reliable source of time:

Light Clients rely on correspondence between their known time and the block time for block verification.
Evidence validity is determined either in terms of heights or in terms of time.
Unbonding of staked assets in the Cosmos Hub occurs after a period of 21 days.
IBC packets can use either a timestamp or a height to timeout packet delivery

Finally, inflation distribution in the Cosmos Hub uses an approximation of time to calculate an annual percentage rate. This approximation of time is calculated using block heights with an estimated number of blocks produced in a year. Proposer-based timestamps will allow this inflation calculation to use a more meaningful and accurate source of time.

Decision

Implement Proposer-Based Timestamps while maintaining backwards compatibility with BFT Time.

Detailed Design

Overview

Implementing Proposer-Based Timestamps (PBTS) will require a few changes to CometBFT’s code. These changes will be to the following components:

The consensus parameters.
The internal/consensus/ package.
The internal/state/ package.

The original version of this document ([ADR 071][original-adr]) dir not consider that the introduced PBTS and the previous method BFT Time could be adopted in the same chain/network. The backwards compatibility section below was thus added to address topic.

Backwards compatibility

In order to ensure backwards compatibility, PBTS should be enabled using a consensus parameter. The proposed approach is similar to the one adopted to enable vote extensions via VoteExtensionsEnableHeight.

In summary, the network will migrate from the BFT Time method for assigning and validating timestamps to the new method for assigning and validating timestamps adopted by PBTS from a given, configurable height. Once PBTS is activated, there are no provisions for the network to revert back to BFT Time (see [issue 2063][issue2063]).

Moreover, when compared to the original ([ADR 071][original-adr]), we will NOT:

Update CommitSigs and Vote types, removing the Timestamp field
Remove the MedianTime method used by BFT Time to produce and validate the block's time
Remove the voteTime method used by BFT Time to set timestamps to precommits
Remove the validation logic used by BFT Time

New consensus parameters

The PBTS specification includes some new parameters that must be the same among across all validators. The set of consensus parameters will be updated to include new fields as follows:

type ConsensusParams struct {
        Block     BlockParams     `json:"block"`
        Evidence  EvidenceParams  `json:"evidence"`
        Validator ValidatorParams `json:"validator"`
        Version   VersionParams   `json:"version"`
        ABCI      ABCIParams      `json:"abci"`
++      Synchrony SynchronyParams `json:"synchrony"`
++      Feature   FeatureParams   `json:"feature"`
}

Synchrony parameters

The PRECISION and MSGDELAY parameters are used to determine if the proposed timestamp is acceptable. A validator will only Prevote a proposal if the proposal timestamp is considered timely. A proposal timestamp is considered timely if it is within PRECISION and MSGDELAY of the Unix time known to the validator. More specifically, the timestamp of a proposal received at proposalReceiveTime is timely if

proposalTimestamp - PRECISION ≤ proposalReceiveTime ≤ proposalTimestamp + PRECISION + MSGDELAY

PRECISION and MSGDELAY will be added to the consensus synchrony parameters as durations:

type SynchronyParams struct {
        Precision    time.Duration `json:"precision,string"`
        MessageDelay time.Duration `json:"message_delay,string"`
}

Compatibility parameters

In order to ensure backwards compatibility, PBTS should be enabled using a consensus parameter:

type FeatureParams struct {
        PbtsEnableHeight int64 `json:"pbts_enable_height"`
        ...
}

The semantics are similar to the ones adopted to enable vote extensions via VoteExtensionsEnableHeight. The PBTS algorithm is enabled from FeatureParams.PbtsEnableHeight, when this parameter is set to a value greater than zero, and greater to the height at which it was set. Until that height, the BFT Time algorithm is used.

For more discussion of this, see [issue 2197][issue2197].

Changes to the block proposal step

Proposer selects block timestamp

CometBFT currently uses the BFT Time algorithm to produce the block's Header.Timestamp. The block production logic sets the weighted median of the times in the LastCommit.CommitSigs as the proposed block's Header.Timestamp. This method will be preserved, but it is only used while operating in BFT Time mode.

In PBTS, the proposer will still set a timestamp into the Header.Timestamp. The timestamp the proposer sets into the Header will change depending on whether the block has previously received 2/3+ prevotes in a previous round. Receiving +2/3 prevotes in a round is frequently referred to as a 'Polka' and we will use this term for simplicity.

Proposal of a block that has not previously received a Polka

If a proposer is proposing a new block then it will set the Unix time currently known to the proposer into the Header.Timestamp field. The proposer will also set this same timestamp into the Timestamp field of the Proposal message that it issues.

Re-proposal of a block that has previously received a Polka

If a proposer is re-proposing a block that has previously received a Polka on the network, then the proposer does not update the Header.Timestamp of that block. Instead, the proposer simply re-proposes the exact same block. This way, the proposed block has the exact same block ID as the previously proposed block and the nodes that have already received that block do not need to attempt to receive it again.

The proposer will set the re-proposed block's Header.Timestamp as the Proposal message's Timestamp.

Proposer waits

Block timestamps must be monotonically increasing. In BFT Time, if a validator’s clock was behind, the validator added 1 millisecond to the previous block’s time and used that in its vote messages. A goal of adding PBTS is to enforce some degree of clock synchronization, so having a mechanism that completely ignores the Unix time of the validator time no longer works. Validator clocks will not be perfectly in sync. Therefore, the proposer’s current known Unix time may be less than the previous block's Header.Time. If the proposer’s current known Unix time is less than the previous block's Header.Time, the proposer will sleep until its known Unix time exceeds it.

This change will require amending the defaultDecideProposal method. This method should now schedule a timeout that fires when the proposer’s time is greater than the previous block's Header.Time. When the timeout fires, the proposer will finally issue the Proposal message.

Changes to proposal validation rules

The rules for validating a proposed block will be modified to implement PBTS. We will change the validation logic to ensure that a proposal is timely. The timely verification is adopted once the node enabled PBTS.

Per the PBTS spec, timely only needs to be checked if a block has not received a Polka in a previous round. If a block previously received a +2/3 majority of prevotes in a round, then +2/3 of the voting power considered the block's timestamp near enough to their own currently known Unix time in that round.

The validation logic will be updated to check timely for blocks that did not previously receive a Polka in a round.

Timestamp validation when a block has not received a Polka

The POLRound in the Proposal message indicates which round the block received a Polka. A negative value in the POLRound field indicates that the block has not previously been proposed on the network. Therefore the validation logic will check for timely when POLRound == -1.

When a node receives a Proposal message, it records it proposalReceiveTime as the current Unix time known to the node. The node will check that the Proposal.Timestamp is at most PRECISION greater than proposalReceiveTime, and at maximum PRECISION + MSGDELAY less than proposalReceiveTime. If the timestamp is not within these bounds, the proposed block will not be considered timely. A validator prevotes nil when the proposed block is not considered timely.

Once a full block matching the Proposal message is received, the node will also check that the timestamp in the Header.Timestamp of the block matches this Proposal.Timestamp. Using the Proposal.Timestamp to check timely allows for the MSGDELAY parameter to be more finely tuned since Proposal messages do not change sizes and are therefore faster to gossip than full blocks across the network.

A node will also check that the proposed timestamp is greater than the timestamp of the block for the previous height. If the timestamp is not greater than the previous block's timestamp, the block will not be considered valid, which is the same as the current logic.

Timestamp validation when a block has received a Polka

When a block is re-proposed that has already received a +2/3 majority of Prevotes (i.e., a Polka) on the network, the Proposal message for the re-proposed block is created with a POLRound that is >= 0. A node will not check that the Proposal is timely if the proposal message has a non-negative POLRound. If the POLRound is non-negative, each node (although this is only relevant for validators) will simply ensure that it received the Prevote messages for the proposed block in the round indicated by POLRound.

If the node is a validator and it does not receive Prevote messages for the proposed block before the proposal timeout, then it will prevote nil. Validators already check that +2/3 prevotes were seen in POLRound, so this does not represent a change to the prevote logic.

Additionally, this validation logic can be updated to check that the Proposal.Timestamp matches the Header.Timestamp of the proposed block, but it is less relevant since checking that votes were received is sufficient to ensure the block timestamp is correct.

Relaxation of the 'Timely' check

The Synchrony parameters, MessageDelay and Precision provide a means to bound the timestamp of a proposed block. Selecting values that are too small presents a possible liveness issue for the network. If a CometBFT network selects a MessageDelay parameter that does not accurately reflect the time to broadcast a proposal message to all of the validators on the network, validators will begin rejecting proposals from otherwise correct proposers because these proposals will appear to be too far in the past.

MessageDelay and Precision are planned to be configured as ConsensusParams. A very common way to update ConsensusParams is by executing a transaction included in a block that specifies new values for them. However, if the network is unable to produce blocks because of this liveness issue, no such transaction may be executed. To prevent this dangerous condition, we will add a relaxation mechanism to the Timely predicate.

The chosen solution for this issue is to adopt the configured MessageDelay for the first round (0) of consensus. Then, as more rounds are needed to commit a value, we increase the adopted value for MessageDelay, at a rate of 10% per additional round. More precisely, the

Excerpt (19991 of 28164 characters). Read the whole page on CometBFT ADRs and RFCs ↗

← Back to Documentation