# Commit Rule and Lock Rule

## Commit Rule

In simple terms, a block can only be committed if its `prepareQC`, `precommitQC`, and `commitQC` were formed in 3 consecutive views.

This rule ensures safety, preventing the situation in which two conflicting blocks are committed due to their voting phases becoming intertwined.

## Commit rule for generic blocks

### Rationale

The need for the commit rule is explained [here](https://hackmd.io/GEUgjB54RS6JGM5LlhOfFg) by invoking a safety-threatening scenario for the current implementation of HotStuff-rs without the commit rule.

Moreover, the commit rule for non-validator-set-updating blocks is mentioned in the chained HotStuff protocol specification from the [HotStuff paper](https://arxiv.org/pdf/1803.05069.pdf).

### Implementation

The following method of the `BlockTree` should return true if the given block's great-grandparent should be committed, possibly triggering commit on some uncommitted ancestors of the great-grandparent:

fn commit_rule(self, b: Block) -> bool {
    let parent = b.justify.block;
    let grandparent = self.block_justify(parent).block;
    b.justify.view = self.block_justify(parent).view + 1
    && self.block_justify(parent).view = self.block_justify(grandparent).view + 1
}

It should be invoked in the `insert_block` method, on the inserted block.

## Commit rule for validator-set-updating blocks

### Rationale

In the following graph, each proposal or nudge is prefixed by the view number of the view in which it is broadcasted:

graph RL;
    id2(2: B2, genericQC) --> id0(0: B0, genericQC)
    id1(1: B1, genericQC) --> id0(0: B0, genericQC)
    id3[[3: Nudge prepareQC]] --> id1(1: B1, genericQC)
    id6[[6: Nudge precommitQC]] --> id3[[3: Nudge prepareQC]]
    id7[[7: Nudge commitQC]] --> id6[[6: Nudge precommitQC]] 
    id4[[4: Nudge prepareQC]] --> id2(2: B2, genericQC)
    id5[[5: Nudge precommitQC]] --> id4[[4: Nudge prepareQC]]
    id8[[7: Nudge commitQC]] --> id5[[5: Nudge precommitQC]]

Where a byzantine leader sends a Nudge for a commitQC for B1 to some replicas, and a Nudge for a commitQC for B2 to other replicas.

In this scenario:
* Without the commit rule, both B1 and B2 can be committed, causing a safety violation, and
* With the commit rule (applied before committing a block), neither branch can be committed since neither satisfies the commit rule, and no new branch can be created, causing a liveness threat. This is because:
- most replicas have either of the commitQCs as their `highest_qc`, hence will try to nudge their commitQC, but that will never succeed since it doesn't satisfy the commit rule, and also
- `locked_view` = 2, so no new blocks can be proposed.

This points to the fact that for validator-set-updating blocks we should check the ability of the QCs to satisfy the commit rule as we go, rather than only just before committing.

Such design would be more consistent with the non-pipelined HotStuff protocol, where a single leader drives one block proposal from propose to commit in a single view, thus eliminating the possibility of two different blocks being voted for in one such view.

On the other hand, in HotStuff-rs non-pipelined protocol for validator-set-updating blocks we have one voting phase per view. This is fine, as long as we make sure that:
- it is clear from where the next honest leader should take off, and
- where it takes off can always lead to an eventual commit, and
- malicious leaders can't exploit the multiple views and leaders to cause a safety violation.

### Implementation

Unlike in pipelined HotStuff, in non-pipelined HotStuff:
- 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 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.

### Limitation

If a leader of `cur_view` has a `precommitQC` (that passed the `safe_qc` check) as its `highest_qc`, but suppose `precommitQC.view < cur_view - 1`, the leader will not be able to collect a `commitQC` that will pass the `safe_qc` check.

In such case, the leader should go back to re-broadcasting the proposal for the `precommit_qc.block` (or another proposal for a sibling block).

**TODO:** define a mechanism for this.

Idea: If `cur_view > highest_qc.view + 1` (when `highest_qc` is for a validator-set-updating block) then re-broadcast the proposal for `highest_qc.block`. But what if some replicas have already locked the view of the prepareQC? In such case they will not vote for the re-broadcast. This points to the fact that `lockedQC` or `locked_block` is more appropriate for phased HotStuff than `locked_view`.

### Solution idea

#### Definitions

Suppose, in addition to `highest_qc`, we store the following field in the `BlockTree`:

highest_block_justify: QuorumCertificate

Which corresponds to the highest justify of a block seen so far. In particular, this means that `highest_block_justify` must be in `Generic` or `Decide` phase.

**Note (implementation):** For greater type safety, we can create a new type `Justify`, which is the same as `QuorumCertificate`, except that its phase must be `Generic` or `Decide`. Then we can define `TryFrom` instances to convert between the two.

Then define the following method on the `QuorumCertificate`:

fn live_qc(self, cur_view: ViewNumber) -> bool {
    self.phase match {
        Prepare(_) | Precommit(_) => self.view = cur_view - 1,
        _ => true,
    }
}

This predicate enforces that proposals or nudges that are deemed to fail are not broadcasted or voted for (else, they might cause a liveness problem).

#### Protocol updates

The following updates are in addition to the commit rule reflected in the `safe_qc`, as described above.

As a leader of `cur_view`:
* if `highest_qc = highest_block_justify || !highest_qc.live_qc(cur_view)` broadcast a proposal with the `highest_block_justify` as the `justify`,
* otherwise broadcast a nudge with the `highest_qc` as the `justify`.

As a voter, on receiving a `nudge`:
* if `nudge.justify.live_qc(cur_view)` then vote for the `nudge`,
* else don't vote for the `nudge`.

Also, before locking `live_qc` check must pass for the `precommitQC`.

Finally, **the block hash should be locked**, rather than the view in which the block was proposed. Otherwise, if a replica votes "commit" and locks, yet no commitQC is collected in that view, the replica should be able to vote for a new proposal for the same block.

## Lock rule update

### Rationale

**Lock Rule in HotStuff:**
>`lockedQC` is defined as *the last `prepareQC` for which a replica voted "commit"*.

On the other hand, the current implementation seems to maintain the invariant that on seeing a valid QC, its "parent QC" becomes the `lockedQC`, or equivalently the "parent QC"'s view becomes the `locked_view`. This is consistent with the lock rule for the pipelined consensus, where every QC is a `prepareQC` for some block, but not for the non-pipelined consensus, where some QCs (`precommitQC`, `commitQC`, `decideQC`) are not `prepareQC`s.

For example, consider the following sequence of block proposals and nudges, labelled with the view in which they were broadcasted (and assuming the broadcast resulted in collecting a QC in the same view):

graph TD;
    id1(1: B1, genericQC)--> id2(2: B2, genericQC)
    id2(2: B2, genericQC)--> id3(3: B3, genericQC)
    id3(3: B3, genericQC)--> id4(4: B4, genericQC)
    id4(4: B4, genericQC) -- 5: Nudge(prepareQC) - 6: Nudge(precommitQC) - 7: Nudge(commitQC) --> id8(8: B8, decideQC)
    id8(8: B8, decideQC) --> id9(9: B9, genericQC)
    id9(9: B9, decideQC) --> id10(10: B10, genericQC)

The **correct** locking behaviour would be as follows, proceeding by view number:
1. No view becomes locked,
2. No view becomes locked,
3. Lock 1, since voting "prepare" for B3 implies voting "commit" for B1.
4. Lock 2, since voting "prepare" for B4 implies voting "commit" for B2.
5. Lock 3, since voting "precommit" for B4 implies voting "commit" for B3.
6. Lock 4, since we vote "commit" for B4.
7. No lock, since we don't vote "commit" for any new block.
8. No lock, since we don't vote "commit" for any new block.
9. No lock, since we don't vote "commit" for any new block.
10. Lock 8, since voting "prepare" for B10 implies voting "commit" for B8.

Whereas **currently** (in hotstuff-rs 0.3 + validator set speculation mechanism):
- In view 7 we lock 5, i.e., the view of the precommitQC, which is incorrect because in this view we do not vote "commit" for any block (we vote "decide" for B4), and `locked_view` must be a view of a prepareQC, not a precommitQC.
- In view 8 we lock 6, the view of the commitQC for B4, which is incorrect.
- In view 9 we lock 7, the view of the decideQC for B4, which is incorrect.

Note: in the current implementation there is no "decide" phase, but if we were to abstract the current implementation to work for the decide phase, this is what it would look like.

### Implementation

Before updating the `locked_view` check if the target qc is in `Prepare` or `Generic` phase, for example:

if parent_justify_view > self.locked_view() && 
    (parent_justify_phase.is_generic() || parent_justify_phase.is_prepare()) {
                    wb.set_locked_view(parent_justify_view);
                    update_locked_view = Some(parent_justify_view);
}