# Consensus for Validator-set-updating Blocks

## Motivation

Consensus protocol for non-validator-set-updating blocks proceeds according to the pipelined HotStuff protocol. However, pipelined HotStuff does not guarantee immediacy and when applied to validator-set-updating blocks, would force us to possibly consider multiple validator-set-updating blocks at a time.

However, for validator-set-updating blocks we additionally need the following properties to hold:
1. **Immediacy:** the block is committed immediately on seeing a `commitQC` for it.
- For example, as opposed to pipelined HotStuff where a block can be committed only once either the block, or a higher block in the block's branch, satisfies the *commit rule*.
2. **Uniqueness:** Only one validator-set-updating block can be considered at a time.
- In other words, there is no interleaving of consensus processes for two validator-set-updating blocks. A proposal for a validator-set-updating block is under consideration for some consecutive views, after which it is either committed or abandoned.

This leads us to adopt a version of non-pipelined HotStuff, since it guarantees **uniqueness**, with the following two modifications:
1. We **keep the "1 leader, 1 view, 1 voting phase" principle** for the sake of consistency with pipelined HotStuff.
- We ensure this is safe by adopting a **commit rule for validator-set-updating blocks**, which effectively forces replicas to drop a proposal once the chain of consecutive views in which the validators vote for the proposal is discontinued or interrupted by another proposal.
2. We **do not allow an uncommitted** (in fact undecided) **validator-set-updating block to be extended** for the sake of immediacy.
- We compensate for the potential loss of liveness by letting replicas **re-propose a locked block**.

## The protocol

We refer to the current protocol with the following updates.

First, commit rule states that a block can be committed only if its `prepareQC`, `precommitQC`, and `commitQC` are such that:
- `prepareQC.view + 1 = precommitQC.view`, and
- `precommitQC.view + 1 = commitQC.view`.

We enforce that the rule is satisfied, and that its violations do not lead to liveness problems, through the following rules:
- *safe-qc* rule (modified`safe_qc` method):
- Enforces that only QCs that satisfy the commit rule can be considered valid, and
- *live-qc* rule (new `live_qc` method):
- Asserts that voting for or broadcasting (via nudge) a `Prepare` or `Precommit` QC that is not from the previous view will not lead to any progress (because the resulting QC will not satisfy the *safe-qc rule*), and hence shall be avoided, for the sake of liveness.

Secondly, we introduce **new locking rules and locking behaviour** that are aimed at:
- Protecting the safety of a commit, and
- Preserving liveness, in particular when even though replicas are locked, a `commitQC` satisfying the *commit rule* cannot be collected.

### *Safe-qc rule*

By the *commit rule*:
- a `precommitQC` where `prepareQC.view + 1` $\neq$ `precommitQC.view` can never lead the block to being eventually committed, and
- a `commitQC` where `precommitQC.view + 1` $\neq$ `commitQC.view` can never lead the block to being eventually committed.

Therefore, such QCs should not be considered safe and should never become an honest replica's `highest_qc`.

Therefore, we embed the *commit rule* requirement in the `safe_qc` method as follows:

pub fn safe_qc(&self, qc: &QuorumCertificate, chain_id: ChainID) -> bool {
        /* 1 */
        (qc.chain_id == chain_id || qc.is_genesis_qc()) &&
        /* 2 */
        (self.contains(&qc.block) || qc.is_genesis_qc()) &&
        /* 3 */ qc.view >= self.locked_view() &&
        /* 4 */ (((qc.phase.is_prepare() || qc.phase.is_precommit() || qc.phase.is_commit() || qc.phase.is_decide()) && self.pending_validator_set_updates(&qc.block).is_some()) ||
        /* 5 */ (qc.phase.is_generic() && self.pending_validator_set_updates(&qc.block).is_none())) && 
        /* 6 Commit Rule */
        qc.phase.match {
            Precommit(prepare_qc_view) => qc.view = prepare_qc_view + 1,
            Commit(precommit_qc_view) => qc.view = precommit_qc_view + 1,
        }
}

Note that on receiving a `commitQC` it is sufficient to check if its view is one bigger than the `precommitQC`, without checking if it is bigger than the `prepareQC` by 2. This is because by the *live-qc rule* described below honest replicas would not have voted "commit" on seeing a `Nudge(precommitQC)` where `prepareQC.view + 1` $\neq$ `precommitQC.view`, hence a `commitQC` would not have been collected.

### *Live-qc rule*

This ensures that:
1. A validator only votes for nudges and proposals that can succeed, i.e., do not violate the *commit rule*.
2. A leader only broadcasts nudges and proposals that can succeed, i.e., do not violate the *commit rule*.

A `qc` satisfies the *live-qc rule* if:
1. If the `qc` is a `Prepare` or `Precommit` QC and `qc.justify.view + 1 = cur_view`, or
2. If the qc is a `Commit`, `Decide`, or `Generic` QC.

Hence, this should be checked:
1. Before a replica votes for a nudge, and
2. Before a leader nudges for a given QC. In case the *live-qc rule* is not satisfied the leader should propose instead.

### *Locking rules*

We introduce the following *locking rules*:
1. A replica locks a validator-set-updating block `B` on seeing a (`is_correct`, `safe_qc`, and `live_qc`) `precommitQC` for `B` (or on seeing a `commitQC`, if it didn't receive `precommitQC`), and
2. A replica unlocks `B` on:
- Seeing a `prepareQC` for another block `B` with `prepareQC.view` higher than the view of the `prepareQC` for `B`, or
- Seeing a `commitQC` for `B`.

Note that we are locking a block, concretely a block hash, not the view of its `prepareQC`.

Additionally, on seeing a `commitQC` for a validator-set-updating block B, `locked-view` should be set to `commitQC.view`. This is for the sake of safety of the pipelined protocol.

### Locking behaviour

If a validator-set-updating block is locked for a replica, i.e, if `block_tree.locked_block() = Some(b)`, then:
1. If the replica becomes a leader, it can only propose or nudge `b`, but no other block.
2. The replica can only vote for a nudge or proposal for `b`, but no other block.
3. Only `b` can be committed, but no other block, even if there is a valid commitQC for it.

Note that unlike in pipelined HotStuff, **a leader can re-propose a locked block, and a voter can vote "prepare" for a locked block** even though a `prepareQC` has been collected in the past. This is to ensure liveness: sometimes a block is locked but commit rule cannot be satisfied because a `commitQC` is not collected in the next view, in which case the only way to continue making safe progress is to re-propose the block.

### Required `BlockTree` changes

The following extra fields are required:
- `locked_vsu_block`: currently locked validator-set-updating block. Can be `None` in case no validator-set-updating block is locked.
- `locked_vsu_view`: the view of the most recent `PrepareQC` for the `locked_vsu_block`. Can be `None` in case no validator-set-updating block is locked. Required to check if a higher `Prepare` or `Generic` QC was seen.
- `highest_block_justify`: highest-viewed `Decide` or `Generic` phase QC seen. This should be stored in case the leader's `highest_qc` does not satisfy the *live-qc rule*, and hence a new block should be proposed with the `highest_block_justify` as the `justify`.

### Broadcast rules

This summarizes the above-mentioned rules regarding what a replica should broadcast when it becomes the leader:
1. If a replica is blocked on a validator-set-updating block `B`:
- if `highest_qc` satisfies `live_qc`, then Nudge with `nudge.justify = highest_qc`,
- else Re-Propose `B`.
2. Else:
- if `highest_qc` satisfies `live_qc`, then Propose or Nudge with `justify = highest_qc`,
- else Re-Propose `highest_qc.block` (with `highest_block_justify` as `B.justify`).

**Note:** `highest_block_justify` may not be required, since we can get the entire `Block`, together with its `justify`, from the `BlockTree` given a block's hash.

### Safety and Liveness arguments

These are by no means conclusive arguments, just ideas about safety and liveness that motivated this design, and in the future should be developed into rigorous proofs.

#### Safety

If a quorum is locked on `B`, a quorum of votes can only be collected for `B`.

#### Liveness

1. If a quorum is locked on `B`, eventually `B` shall be committed, and unlocked.
2. Otherwise, other blocks can be proposed and locked (including `B`).

### Relevant properties

<!-- #### #1 *If a block B is deleted from the `BlockTree` through pruning, then it is not locked.*

**Note:** if this property doesn't hold, it might lead to violations of liveness, since proposing a locked block that conflicts with a committed block could never succeed. -->

#### #1 If B' is committed, it does not conflict with the locked block.

**Proof (sketch) by contradiction:**

Let B be the locked block.

Suppose B' is committed in some view v''. Then the prepareQC, and precommitQC, and commitQC that led to B' being committed (the QCs don't have to be for B', for example if B' becomes committed only because a higher block is committed) were collected in views v, v+1, v+2, where v+2 < v''. Suppose these QCs were for a block B''. Since B'' is higher in the same branch as B' (or B'' = B'), if B' conflicts with B, so does B''.

Now since as of view v'' B is locked, either:
1. PrepareQC and PrecommitQC for B were collected in v' and v'+1 respectively, and B was locked in v'+2, where v' > v+2, and v'+2 < v''.
- In this case, since v' > v+2, and hence also v' > v, `locked_view = v` when B was proposed. Hence, `B.justify.view > v`, and B.justify.view > v+2. But the B.justify.block can't conflict with B'', and so B can't conflict with B''. Contradiction.
2. PrepareQC and PrecommitQC for B were collected in v' and v'+1 respectively, and B was locked in v'+2, where v'+2 < v.
- Then B can't be locked in `v''`, since on seeing a prepareQC for conflicting B'' in v > v' B must have been unlocked. Contradiction.

Q.E.D

### Notes on implementation

1. We must ensure that unlocking on seeing a new QC happens before committing some block.
2. Order of events on seeing `decideQC` for B: first set `locked_view = DecideQC.view` and unlock B, then vote for the new proposal.
3. A vs-updating block **must be locked** to be committed (unless via sync).
4. For consistency, we might need to update locked_view on seeing a prepareQC for a validator-set-updating block. This is motivated by the principle that a lock is always "dropped" after seeinga higher prepareQC. The issue is that we don't know how to update the locked_view when a validator-set-updating block is considered, since it cannot be set to the view of the prepareQC, because the block might be re-proposed. Rather, we might need to set it to the view of the justify of the validator-set-updating block. This would be useful in cases when less than a quorum has locked_view incompatible with the proposal for the validator-set-updating block, and if progress is made on the proposal, the lock should be dropped.