RFC 100: ABCI Vote Extension Propagation

Changelog

11-Apr-2022: Initial draft (@sergio-mena).
15-Apr-2022: Addressed initial comments. First complete version (@sergio-mena).
09-May-2022: Addressed all outstanding comments (@sergio-mena).
09-May-2022: Add section on upgrade path (@wbanfield)
02-Mar-2023: Migrated to CometBFT RFCs. New number: RFC 100 (@sergio-mena).
03-Mar-2023: Added "changes needed" to solutions in upgrade path section (@sergio-mena)

Abstract

According to the [ABCI 2.0 specification][abci-2-0], a validator MUST provide a signed vote extension for each non-nil precommit vote of height h that it uses to propose a block in height h+1. When a validator is up to date, this is easy to do, but when a validator needs to catch up this is far from trivial as this data cannot be retrieved from the blockchain.

This RFC presents and compares the different options to address this problem, which have been proposed in several discussions by the CometBFT team.

Document Structure

The RFC is structured as follows. In the Background section, subsections Problem Description and Cases to Address explain the problem at hand from a high level perspective, i.e., abstracting away from the current CometBFT implementation. In contrast, subsection Current Catch-up Mechanisms delves into the details of the current CometBFT code.

In the Discussion section, subsection Solutions Proposed is also worded abstracting away from implementation details, whilst subsections Feasibility of the Proposed Solutions and Current Limitations and Possible Implementations analyze the viability of one of the proposed solutions in the context of CometBFT's architecture based on reactors. Subsection Upgrade Path discusses how a CometBFT node can upgrade from a version predating vote extensions, to one featuring it. Finally, Formalization Work briefly discusses the work still needed to demonstrate the correctness of the chosen solution.

The high level subsections are aimed at readers who are familiar with consensus algorithms, in particular with the Tendermint algorithm described here, but who are not necessarily acquainted with the details of the CometBFT codebase. The other subsections, which go into implementation details, are best understood by engineers with deep knowledge of the implementation of CometBFT's blocksync and consensus reactors.

Background

Basic Definitions

This document assumes that all validators have equal voting power for the sake of simplicity. This is done without loss of generality.

There are two types of votes in the Tendermint algorithm: prevotes and precommits. Votes can be nil or refer to a proposed block. This RFC focuses on precommits, also known as precommit votes. In this document we sometimes call them simply votes.

Validators send precommit votes to their peer nodes in precommit messages. According to the [ABCI 2.0 specification][abci-2-0], a precommit message MUST also contain a vote extension. This mandatory vote extension can be empty, but MUST be signed with the same key as the precommit vote (i.e., the sending validator's). Nevertheless, the vote extension is signed independently from the vote, so a vote can be separated from its extension. The reason for vote extensions to be mandatory in precommit messages is that, otherwise, a (malicious) node can omit a vote extension while still providing/forwarding/sending the corresponding precommit vote.

The validator set at height h is denoted valseth. A commit for height h consists of more than 2nh/3 precommit votes voting for a block b, where nh denotes the size of valseth. A commit does not contain nil precommit votes, and all votes in it refer to the same block. An extended commit is a commit where every precommit vote has its respective vote extension attached.

Problem Description

In [ABCI 1.0][abci-1-0] and previous versions (e.g. [ABCI 0.17.0][abci-0-17-0]), for any height h, a validator v MUST have the decided block b and a commit for height h in order to decide at height h. Then, v just needs a commit for height h to propose at height h+1, in the rounds of h+1 where v is a proposer.

In [ABCI 2.0][abci-2-0], the information that a validator v MUST have to be able to decide in h does not change with respect to pre-existing ABCI: the decided block b and a commit for h. In contrast, for proposing in h+1, a commit for h is not enough: v MUST now have an extended commit.

When a validator takes an active part in consensus at height h, it has all the data it needs in memory, in its consensus state, to decide on h and propose in h+1. Things are not so easy in the cases when v cannot take part in consensus because it is late (e.g., it falls behind, it crashes and recovers, or it just starts after the others). If v does not take part, it cannot actively gather precommit messages (which include vote extensions) in order to decide. Before ABCI 2.0, this was not a problem: full nodes are supposed to persist past blocks in the block store, so other nodes would realise that v is late and send it the missing decided block at height h and the corresponding commit (kept in block h+1) so that v can catch up. However, we cannot apply this catch-up technique for ABCI 2.0, as the vote extensions, which are part of the needed extended commit are not part of the blockchain.

Cases to Address

Before we tackle the description of the possible cases we need to address, let us describe the following incremental improvement to the ABCI 2.0 logic. Upon decision, a full node persists (e.g., in the block store) the extended commit that allowed the node to decide. For the moment, let us assume the node only needs to keep its most recent extended commit, and MAY remove any older extended commits from persistent storage. This improvement is so obvious that all solutions described in the Discussion section use it as a building block. Moreover, it completely addresses by itself some of the cases described in this subsection.

We now describe the cases (i.e. possible runs of the system) that have been raised in different discussions and need to be addressed. They are (roughly) ordered from easiest to hardest to deal with.

(a) Happy path: all validators advance together, no crash.

This case is included for completeness. All validators have taken part in height h. Even if some of them did not manage to send a precommit message for the decided block, they all receive enough precommit messages to be able to decide. As vote extensions are mandatory in precommit messages, every validator v trivially has all the information, namely the decided block and the extended commit, needed to propose in height h+1 for the rounds in which v is the proposer.

No problem to solve here.
(b) All validators advance together, then all crash at the same height.

This case has been raised in some discussions, the main concern being whether the vote extensions for the previous height would be lost across the network. With the improvement described above, namely persisting the latest extended commit at decision time, this case is solved. When a crashed validator recovers, it recovers the last extended commit from persistent storage and handshakes with the Application. If need be, it also reconstructs messages for the unfinished height (including all precommits received) from the WAL. Then, the validator can resume where it was at the time of the crash. Thus, as extensions are persisted, either in the WAL (in the form of received precommit messages), or in the latest extended commit, the only way that vote extensions needed to start the next height could be lost forever would be if all validators crashed and never recovered (e.g. disk corruption). Since a correct node MUST eventually recover, this violates the assumption of more than 2nh/3 correct validators for every height h.

No problem to solve here.
(c) Lagging majority.

Let us assume the validator set does not change between h and h+1. It is not possible by the nature of the Tendermint algorithm, which requires more than 2nh/3 precommit votes for some round of height h in order to make progress. So, only up to nh/3 validators can lag behind.

On the other hand, for the case where there are changes to the validator set between h and h+1 please see case (d) below, where the extreme case is discussed.
(d) Validator set changes completely between h and h+1.

If sets valseth and valseth+1 are disjoint, more than 2nh/3 of validators in height h should have actively participated in consensus in h. So, as of height h, only a minority of validators in h can be lagging behind, although they could all lag behind from h+1 on, as they are no longer validators, only full nodes. This situation falls under the assumptions of case (h) below.

As for validators in valseth+1, as they were not validators as of height h, they could all be lagging behind by that time. However, by the time h finishes and h+1 begins, the chain will halt until more than 2nh+1/3 of them have caught up and started consensus at height h+1. If set valseth+1 does not change in h+2 and subsequent heights, only up to nh+1/3 validators will be able to lag behind. Thus, we have converted this case into case (h) below.
(e) Enough validators crash to block the rest.

In this case, blockchain progress halts, i.e. surviving full nodes keep increasing rounds indefinitely, until some of the crashed validators are able to recover. Those validators that recover first will handshake with the Application and recover at the height they crashed, which is still the same the nodes that did not crash are stuck in, so they don't need to catch up. Further, they had persisted the extended commit for the previous height. Nothing to solve.

For those validators recovering later, we are in case (h) below.
(f) Some validators crash, but not enough to block progress.

When the correct processes that crashed recover, they handshake with the Application and resume at the height they were at when they crashed. As the blockchain did not stop making progress, the recovered processes are likely to have fallen behind with respect to the progressing majority.

At this point, the recovered processes are in case (h) below.
(g) A new full node starts.

The reasoning here also applies to the case when more than one full node are starting. When the full node starts from scratch, it has no state (its current height is 0). Ignoring statesync for the time being, the node just needs to catch up by applying past blocks one by one (after verifying them).

Thus, the node is in case (h) below.
(h) Advancing majority, lagging minority

In this case, some nodes are late. More precisely, at the present time, a set of full nodes, denoted Lhp, are falling behind (e.g., temporary disconnection or network partition, memory thrashing, crashes, new nodes) an arbitrary number of heights: between hs and hp, where hs < hp, and hp is the highest height any correct full node has reached so far.

The correct full nodes that reached hp were able to decide for hp-1. Therefore, less than nhp-1/3 validators of hp-1 can be part of Lhp, since enough up-to-date validators needed to actively participate in consensus for hp-1.

Since, at the present time, no node in Lhp took part in any consensus between hs and hp-1, the reasoning above can be extended to validator set changes between hs and hp-1. This results in the following restriction on the full nodes that can be part of Lhp.
- ∀ h, where hs ≤ h < hp, | valseth ∩ Lhp | < nh/3
So, full nodes that are validators at some height h between hs and hp-1 can be in Lhp, but not more than 1/3 of those acting as validators in the same height. If this property does not hold for a particular height h, where hs ≤ h < hp, CometBFT could not have progressed beyond h and therefore no full node could have reached hp (a contradiction).

These lagging nodes in Lhp need to catch up. They have to obtain the information needed to make progress from other nodes. For each height h between hs and hp-2, this includes the decided block for h, and the precommit votes also for deciding h (which can be extracted from the block at height h+1).

At a given height hc (where possibly hc << hp), a full node in Lhp will consider itself caught up, based on the (maybe out of date) information it is getting from its peers. Then, the node needs to be ready to propose at height hc+1, which requires having received the vote extensions for hc. As the vote extensions are not stored in the blocks, and it is difficult to have strong guarantees on when a late node considers itself caught up, providing the late node with the right vote extensions for the right height poses a problem.

At this point, we have described and compared all cases raised in discussions leading up to this RFC. The list above aims at being exhaustive. The analysis of each case included above makes all of them converge into case (h).

Current Catch-up Mechanisms

We now briefly describe the current catch-up mechanisms in the reactors concerned in CometBFT.

Statesync

Full nodes optionally run statesync just after starting, when they start from scratch. If statesync succeeds, an Application snapshot is installed, and CometBFT jumps from height 0 directly to the height the Application snapshot represents, without applying the block of any previous height. Some light blocks are received and stored in the block store for running light-client verification of all the skipped blocks. Light blocks are incomplete blocks, typically containing the header and the canonical commit but, e.g., no transactions. They are stored in the block store as "signed headers".

The statesync reactor is not really relevant for solving the problem discussed in this RFC. We will nevertheless mention it when needed; in particular, to understand some corner cases.

Blocksync

The blocksync reactor kicks in after start up or recovery. At startup, if statesync is enabled, blocksync starts just after statesync and sends the following messages to its peers:

StatusRequest to query the height its peers are currently at, and
BlockRequest, asking for blocks of heights the local node is missing.

Using BlockResponse messages received from peers, the blocksync reactor validates each received block using the block of the following height, saves the block in the block store, and sends the block to the Application for execution (it effectively simulates the node deciding on that height).

If blocksync has validated and applied the block for the height previous to the highest seen in a StatusResponse message, or if no progress has been made after a timeout, the node considers itself as caught up and switches to the consensus reactor.

Consensus Reactor

The consensus reactor runs the full Tendermint algorithm. For a validator this means it has to propose blocks, and send/receive prevote/precommit messages, as mandated by the algorithm, before it can decide and move on to the next height.

If a full node that is running the consensus reactor falls behind at height h, when a peer node realises this it will retrieve the canonical commit of h+1 from the block store, and convert it into a set of precommit votes and will send those to the late node.

Discussion

Solutions Proposed

These are the solutions proposed in discussions leading up to this RFC.

Solution 0. Vote extensions are made best effort in the specification.

This is the simplest solution, considered as a way to provide vote extensions in a simple enough way so that it can be a first available version in ABCI 2.0. It consists in changing the specification so as to not require that precommit votes used upon PrepareProposal contain their corresponding vote extensions. In other words, we render vote extensions optional. There are strong implications stemming from such a relaxation of the original specification.
- As a vote extension is signed separately from the vote it is extending, an intermediate node can now remove (i.e., censor) vote extensions from precommit messages at will.
- Further, there is no point anymore in the spec requiring the Application to accept a vote extension passed via VerifyVoteExtension to consider a precommit message valid in its entirety. Remember this behavior of VerifyVoteExtension is adding a constraint to CometBFT's conditions for liveness. In this situation, it is better and simpler to just drop the vote extension rejected by the Application via VerifyVoteExtension, but still consider the precommit vote itself valid as long as its signature verifies.
Solution 1. Include vote extensions in the blockchain.

Another obvious solution, which has somehow been considered in the past, is to include the vote extensions and their signatures in the blockchain. The blockchain would thus include the extended commit, rather than a regular commit, as the structure to be canonicalized in the next block. With this solution, the current mechanisms implemented both in the blocksync and consensus reactors would still be correct, as all the information a node needs to catch up, and to start proposing when it considers itself as caught-up, can now be recovered from past blocks saved in the block store.

This solution has two main drawbacks.
- As the block format must change, upgrading a chain requires a hard fork. Furthermore, all existing light client implementations will stop working until they are upgraded to deal with the new format (e.g., how certain hashes calculated and/or how certain signatures are checked). For instance, let us consider IBC, which relies on light clients. An IBC connection between two chains will be broken if only one chain upgrades.
- The extra information (i.e., the vote extensions) that is now kept in the blockchain is not really needed at every height for a late node to catch up.
  - This information is only needed to be able to propose at the height the validator considers itself as caught-up. If a validator is indeed late for height h, it is useless (although correct) for it

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

← Back to Documentation