# Locked view and 3-chains

## The safety-threatening scenario

Here is a scenario that may lead to two honest replica committing two conflicting blocks B1 and B3:

graph TD;
    B1-->B0;
    B2-->B1;
    B3-->B0;
    B4-->B3;
    B5-->B2;
    B6-->B4;
    B7-->B5;
    B7'-->B6;

Suppose the number in the block name corresponds to the view in which it was proposed. Suppose a block B0 was voted for and inserted by all honest nodes.

Then the scenario goes as follows (numbering according to view numbers):
1. An honest leader $l_{1}$ proposes B1. All honest replicas vote for it and insert it into their blockchains. Another honest leader $l_{2}$ collects the QC for B1 ($QC_{B1}$).
2. Honest $l_{2}$ proposes B2 with $QC_{B1}$ as *justify*. All honest replicas vote and insert. A byzantine leader $l_{3}$ collects the votes into $QC_{B2}$. All honest replicas set `locked_view = 0`.
3. Byzantine $l_{3}$ proposes B3 with $QC_{B0}$ as *justify*. B3 passes the `safe_block` check, since `justify.view` = 0 is equal to locked view 0. All honest replicas vote for it and insert. An honest leader $l_{4}$ collects the votes into $QC_{B3}$.
4. Honest $l_{4}$ proposes B4 with $QC_{B3}$ as *justify*. All honest replicas vote for it and insert. A byzantine leader $l_{5}$ collects the votes into $QC_{B4}$.
5. Byzantine $l_{5}$ proposes B5 with $QC_{B2}$ as *justify* (this is possible since it can learn about the QC from another byzantine leader $l_{3}$ that collected it). All honest replicas vote for B5 and insert it. They also set `locked_view = 1`. Another byzantine leader $l_{6}$ collects the votes into $QC_{B5}$.
6. Byzantine $l_{6}$ proposes B6 with $QC_{B4}$ as *justify* (this is possible since it could learn about the QC from byzantine $l_{5}$ that collected it). All honest replicas vote for it and insert it. They also set `locked_view = 3`. Byzantine $l_{7}$ collects the votes into $QC_{B6}$.
7. Byzantine $l_{7}$ proposes (1) B7 with $QC_{B5}$ as *justify* to an honest replica r, and (2) B7' with $QC_{B6}$ as *justify* to all other honest replicas. All honest replicas vote for the proposal they received. Hence, also (1) R commits B1, and (2) all other honest replicas commit B3.

## Discussion

The safety violation is caused by the branch-switching behaviour of 4 byzantine leaders, and because we automatically commit the great-grandparent of a newly-inserted block.

The chained HotStuff from the original paper has an extra requirement according to which for the great-grandparent to be committed, there must be a "3-chain" starting from the great-grandparent. The original paper equates heights with views, so the exact requirement does not apply to our design, but I'd translate the requirement as folllows:

> For any $v \in \mathbb{N}$, any $k \geq v+3$, inserting $B_{k}$ can lead to committing $B_{v}$ if:
> 1. $B_{v+1}$*.justify.block* = $B_{v}$, and
> 2. $B_{v+2}$*.justify.block* = $B_{v+1}$,
> 3. $B_{k}$*.justify.block* = $B_{v+2}$.

graph TD;
    B1-->B0;
    B2-->B1;
    BK-->B2;

Indeed, introducing this requirement would avoid the issue above, because switching to a new branch before forming a 3-chain means the starting block of the previous branch cannot be committed.

The original paper equates heights with views, and inserts an empty block for a view with no or an unseccessful proposal. Therefore, a 3-chain is quite literally a sequence of 3 blocks, on subsequent heights, hence subsequent views, such that they are linked to each other by the *justify* relation. But our blocks are only linked by the *justify* relation, so additionally we need to require that the subsequent blocks come from subsequent views.

However, introducing this requirement would break a lot of nice properties of our design, for instance:
1. The property that a block gets committed once it has a chain of 3 ancestors.
2. The property that all blocks lower than `highest_committed_block_height` are committed.

Moreover, there would be gaps in the blockchain, not so easy to prune and determine what is committed and what isn't.

Here is the original [HotStuff paper](https://dl.acm.org/doi/pdf/10.1145/3293611.3331591), details of the chained version can be found on pages 8-9.

As an alternative, we can explore modifying the SAFENODE (`safe_block`) predicate, and/or locked view. For instance, we could require that a block to be committed extends the locked block (i.e. is in the branch starting from the locked block). But this could lead to some liveness violations, I need to think about this.

## Locked view

The "locking" behaviour in our implementation should be equivalent to the on from the paper.

Intuitively, is because:
* We lock the first block in a 3-chain, same as in HotStuff.
* The SAFENODE safety predicate from HotStuff says that to get a "safe" new block, such that inserting it leads to committig the same block that everyone agreed on committing (the locked block), it must extend the locked block. In our implementation, this corresponds to inserting a block to the branch starting from the locked block, hence with the inserted block's justify having a view greater or equal to the locked view.
* The SAFENODE liveness predicate from HotStuff says that if a safe block cannot be inserted, e.g., because some replicas don't know about the locked branch, then any other block can be inserted, as long as the block's justify has view greater or equal to the locked view (in HotStufv view = height). In our implementation this corresponds to inserting a block to a different branch than the one of the locked block, but the inserted block's justify having a view greater or equal to the locked view.

More rigorously:

### #1 `locked_view` is reset under the same condition as $b_{lock}$

Both are reset when:
1. A block b is inserted, and
2. The view (in the paper: height) of b's grandparent is greater than the current locked view (in the paper: $b_{lock}.view$)

### #2 The *SAFENODE* requirement on $b_{lock}$ is equivalent to the `safe_qc` requirement on `locked_view`

According to the paper $b_{new}$ is *SAFENODE* iff:
1. (SAFETY) $b_{new}$ extends $b_{lock}$, **or**
2. (LIVENESS) $b_{new}.justify.node.height > b_{lock}.height$.

For us the equivalent requirement is:
1'. (SAFETY AND LIVENESS) $b_{new}.justify.node.view \geq v_{locked}$.

**Proof (sketch) of equivalence:**

First, I interpret "(1) (SAFETY) $b_{new}$ extends $b_{lock}$" as $b_{new}$ being in the branch starting from $b_{lock}$, i.e., connected to $b_{lock}$ via a chain of *justify* relations. In our case, this implies "(1') $b_{new}.justify.view \geq v_{lock}$". The implication does not work the other way around, but:
* "$b_{new}.justify.view > v_{lock}$" implies (2) (LIVENESS) as discussed below, and
* "$b_{new}.justify.view = v_{lock}$" implies $b_{new}.justify = b_{lock}$ (since there is a unique proposal per view), which is a particular case of b_{new}$ extending $b_{lock}$.

Second, because in the paper height = view, clearly "(2) (LIVENESS) $b_{new}.justify.node.height > b_{lock}.height$" is equivalent to "(1') (SAFETY AND LIVENESS) $b_{new}.justify.node.view > v_{locked}$".

Hence, overall we have equivalence.

More intuitively, (1) from the paper requires that we propose a block in the branch extending from $b_{lock}$, thus eventually creating a 3-chain and committing $b_{lock}$. This is called "safety", because here the lock guards the safety of a commit in case a quorum of replicas locked and hence has a 3-chain that shall be committed.

If (1) doesn't hold, a proposal can still be valid because of (2), i.e., if the proposed block is proposed in a higher view (same as height in the paper) than $b_{lock}$. This is useful in case only a few (but not a quorum) of replicas locked $b_{lock}$, and others do not know about the lock (yet, they will eventually find out about the lock).