I'm trying to understand the proof of correctness for Hot-Stuff algorithm.
My question is about the Lemma 1 (page 7), there the authors state that
"By assumption, event $e_j$ must occur before $e_k$.",
but the definitions given allow for $k=j+1$, for $e_j$ denotes a $<COMMIT: cmd(j)>$ which is an indication that $r$ votes for a $PROPOSE$ carrying a certificate for a direct parent aka $cmd(j)$. That is the voting happens on level $j+1$, and then $e_j$ and $e_k$ happen on the same level, hence we can't actually see which one came first.
Another confusing part is the following statement from Corollary 1 (same page): they find $h$ (which holds some specific qualities) such that $j<h\leq k$, yet by an assumption $k$ is the minimal number which has these qualities - that makes a contradiction, from their perspective. But what's wrong with $h$ being equal $k$?
Great questions!
On the first one: We were being a little terse/sloppy here, but the lemma is correct. Replica $r$ votes only once per level. Hence, if $k=j+1$, the same message is carrying $CC(cmd(j))$ and the $j+1$ proposal. First, the CC is processed, and recorded as the highest CC. Then, when $e_k$ occurs, it is indeed already known to replica r.
Note that in this case, the PROPOSE message could be filtered upon receipt when it is verified, since the proposal and the CC are on conflicting branches.
On the second question: This is in fact a contradiction even if $h = k$. The proof says: A prepare for $cmd(k)$ requires $2f+1$ prepares to already exist on the $cmd(k)$ branch. This is a circular prerequisite, to have one vote you need to already have $2f+1$ votes.