# GA-based SSF ## Building a practical, 1/2-resilient TOB ### 1/2-resilient GA with single round of voting, $5\Delta$ rounds **Model** Honest validators can be put to sleep and corrupted. Byzantine validators are always awake after being corrupted. Let $H$ be the honest validators which are awake at time $t = 0$ (beginning of the $GA$), let $h = |H|$, and let $f$ be the number of byzantine validators at $t = 5\Delta$ (end of the $GA$). We require that $h > f$. **GA definition** We work with a three-valued graded agreement protocol. Each validator has an input log $\Lambda$, and validators can output *graded logs* $(\Lambda, g)$ with grade $g \in \{0,1,2\}$. We say that an honest validator *participates in the output phase for grade $g$*, if it is awake when the outputs with grade $g$ are computed, and if it chooses to do so. Each instantion of this $GA$ can specify what this requires. We want the protocol to satisfy these properties: *Graded consistency*: If an honest validator outputs $(\Lambda, g)$ for $g \in \{1,2\}$, then any honest validator which participates in the output phase for grade $g-1$ outputs $(\Lambda, g-1)$ *Validity:* If all validators in $H$ input an extension of $\Lambda$, all honest validators which participate in the output phase for grade $g$ output $(\Lambda, g)$. *Integrity:* If an honest validator outputs $(\Lambda, 0)$, then at least one honest validator has input $\Lambda$. *No-divergence:* An honest validator does not output $(\Lambda, 0)$ and $(\Lambda', 0)$ for $\Lambda$ conflicting with $\Lambda'$. Note that no-divergence for grade $0$, together with graded consistency, also implies no-divergence for all grades. Moreover, no-divergence for all grades and graded consistency imply the following property: *Uniqueness:* If an honest validator outputs $(\Lambda, g)$ for $g \in \{1,2\}$, then no honest validator outputs $(\Lambda', g)$ for $\Lambda'$ conflicting with $\Lambda$. **Execution:** Given a set of inputs $V$ and a log $\Lambda$, we let $V_{\Lambda} = \{\Lambda' \in V: \Lambda' \succeq \Lambda\}$. Honest validators participate in the output phase for grade 1 if they were also awake at time $t = 2\Delta$, and in the output phase for grade $2$ if they were also awake at time $t = \Delta$. Besides that, honest validators execute this logic whenever awake: 1. **(Input phase, $t = 0$)** Input log $\Lambda$ 2. ($t = \Delta$) Store $V = \{\text{inputs}\}$ 3. ($t = 2\Delta$) Store $V' = \{\text{inputs}\}$ 4. **(Output phase for grade $0$, $t = 3\Delta$)** Let $V'' = \{\text{inputs}\}$, $E = \{\text{inputs from equivocators}\}$, $S = |\{\text{unique input senders}\}|$. Output $(\Lambda, 0)$ if $v''_{\Lambda} = |V''_{\Lambda} \setminus E| > S/2$. 7. **(Output phase for grade $1$, $t = 4\Delta$)** Let $E' = \{\text{inputs from equivocators}\}$, $S' = |\{\text{unique input senders}\}|$. Output $(\Lambda, 1)$ if $v'_{\Lambda} = |V'_{\Lambda} \setminus E'| > S'/2$. 8. **(Output phase for grade $2$, $t = 5\Delta$)** Let $E'' = \{\text{inputs from equivocators}\}$, $S'' = |\{\text{unique input senders}\}|$. Output $(\Lambda, 2)$ if $v_{\Lambda} = |V_{\Lambda} \setminus E''| > S''/2$ **Properties:** *Graded consistency:* Let $V,E'',S''$ resp. $V', E', S'$ resp. $V'', E, S$ be for three honest validators, participating to the output phase for grade 2 resp. 1 resp. 0. Then, the delays ensure that $V'' \supseteq V' \supseteq V$, $E'' \supseteq E' \supseteq E$. For any $\Lambda$ we then also have $V_{\Lambda}''\setminus E \supseteq V_{\Lambda}' \setminus E' \supseteq V_{\Lambda} \setminus E''$, so $v_{\Lambda}'' \ge v_{\Lambda}' \ge v_{\Lambda}$. Also, $S'' \ge S' \ge S$, so $v_{\Lambda} > S''/2$ (output $\Lambda$ with grade $2$) implies $v_{\Lambda}' > S'/2$ (output $\Lambda$ with grade $1$), and the latter implies $v_{\Lambda}'' > S/2$ (output $\Lambda$ with grade $0$) *Validity:* If all validators in $H$ input an extension of $\Lambda$, all such inputs are contained in the $V$ of any honest validator which was awake at $t=\Delta$, and no such inputs are contained in $E''$ of an honest validator awake in the output phase for grade $2$, since honest validators do not equivocate. Therefore, for any honest validator which participates in the output phase for grade $2$ (i.e., awake at $t=2\Delta$ and $t=5\Delta$), $v_{\Lambda} = |V_{\Lambda} \setminus E''| \ge |H| = h > f$. Moreover, $S'' \le h + f < 2h$, so $v_{\Lambda} > h > S''/2$, and thus the validator outputs $(\Lambda, 2)$. *Integrity:* Say an honest validator outputs $(\Lambda, 0)$, and suppose that there is no input $\Lambda' \succeq \Lambda$ in $V''$ which comes from a validator in $H$, so that $S \ge v''_{\Lambda} + h$. Note that $2h > h+f \ge S$. Then, $v''_{\Lambda} > S/2$ and $S \ge v''_{\Lambda} + h$ imply $S > S/2 + h > S/2 + S/2$ i.e., $S > S$, a contradiction. *No-divergence:* Note first that there's a natural injection of $V''_{\Lambda} \setminus E$ into $\{\text{unique input senders}\}$, since at most one input per validator is considered in the former, due to removing inputs from equivocators by subtracting $E$. Moreover, note that $V''_{\Lambda'}\setminus E$ and $V''_{\Lambda}\setminus E$ are disjoint for conflicting $\Lambda, \Lambda'$, so $v''_{\Lambda} + v''_{\Lambda'} = |V''_{\Lambda'}\setminus E \cup V''_{\Lambda}\setminus E| \leq |\{\text{unique input senders}\}| = S$. Therefore, $v''_{\Lambda} > S/2$ implies $v''_{\Lambda'} \leq S/2$ for any conflicting $\Lambda'$. ### TOB with instant decisions, $4\Delta$ rounds **Model:** Honest validators can be put to sleep and corrupted. Byzantine validators are always awake after being corrupted. For each time $t$, we let $H_t$ resp. $B_t$ be the honest resp. byzantine validators awake at time $t$, and we let $f_t = |B_t|$, $H_{t_1, t_2} = \bigcap_{t \in [t_1, t_2]} H_{t}$, $h_{t_1, t_2} = |H_{t_1, t_2}|$. For each time $t$, we require that $h_{t - \Delta, t + \Delta} > f_{t + 6\Delta}$, i.e., that the validators which are awake and honest throughout $[t - \Delta, t + \Delta]$ outnumber the byzantine validators at time $t + 6\Delta$. **Execution**: The protocol proceeds in slots of 4 rounds each, so of time $4\Delta$. We let $t_s = 4\Delta s$, the beginning of slot $s$. To each slot $s$ corresponds a graded agreement $GA_s$, which runs at time $[t_s + \Delta, t_{s+1} + 2\Delta] = [t_s + \Delta, t_s + 6\Delta]$. In slot $s$, an awake validator does the following, in addition to what is required by the $GA$s which are ongoing: 1. **[Propose, $t=t_s$]** If leader for slot $s$, propose $\Lambda'$ extending $\Lambda$, the highest log output with grade $0$ by $GA_{s-1}$ (*candidate*) 2. **[Vote, $t=t_s + \Delta]$** $GA_s$ starts. Let $L_s$ be the highest log output with grade $1$ by $GA_{s-1}$ (*lock*). Input to $GA_s$ a proposal extending $L_s$, or $L_s$ if no such proposal exists. 3. **[Decide, $t=t_s + 2\Delta]$** Decide the highest log $\Lambda$ output with grade $2$ by $GA_{s-1}$ (*commit*). $GA_{s-1}$ ends. 4. **[$t=t_s + 3\Delta$]** Do nothing (other than what is required by $GA_s$) Whenever an action requires a $GA$ output is not computed, because the validator chooses not to participate in the output phase due to not having been previously awake when required by it, the action is skipped. In particular, no decision is taken at time $t_s + 2\Delta$ and no input is broadcast at time $t_s + \Delta$. A proposal *may* anyway be broadcast at time $t_s$, but it is not necessary to do so. **Properties** Firstly, we map the assumptions of this TOB protocol to the $GA$ assumptions. $H_{t_s - \Delta, t_s + \Delta}$ are precisely the honest validators which input something to $GA_s$, because they participate in the output phase for grade $1$ of $GA_{s-1}$. This is because they are awake at time $t_s - \Delta$, which is time $2\Delta$ into $GA_{s-1}$, and moreover are awake at time $t_s + \Delta$, which is time $4\Delta$ in $GA_{s-1}$, i.e., when the output phase for grade $1$ happens, coinciding with the input phase of $GA_{s}$. Therefore, $H_{t_s - \Delta, t_s + \Delta}$ coincides precisely with $H$ of $GA_s$, from the $GA$ model. Moreover, $f_{t_s+6\Delta_s}$ coincides precisely with $f$ of $GA_s$, since $t_s + 6\Delta_s$ is time $t = 5\Delta$ of $GA_s$. Therefore, $h_{t_s - \Delta, t_s + \Delta} > f_{t_s + 5\Delta_s}$ implies that $h > f$ holds for $GA_s$, so all properties of $GA_s$ hold. *Lemma 1: If all validators $H_{t_s - \Delta, t_s + \Delta}$ output an extension of $\Lambda$ in $GA_{s-1}$, then all validators in $H_{t_{s+1} - \Delta, t_{s+1} + \Delta}$ output an extension of $\Lambda$ in $GA_s$. By induction, this then holds for all $s' \ge s-1$.* *Proof:* By no-divergence (for grade $1$), any honest validator in $H_{t_s - \Delta, t_s + \Delta}$ does not output something conflicting with grade $1$, so its lock $L_s$ extends $\Lambda$. Therefore, it inputs to $GA_s$ a proposal extending $\Lambda$. By validity of $GA_s$, all honest validators which participate to the output phase for grade $1$ of $GA_s$, precisely validators $H_{t_{s+1} - \Delta, t_{s+1} + \Delta}$, output $(\Lambda, 1)$. *Safety:* Suppose an honest validator decides log $\Lambda$ at time $t_s + 2\Delta$, by outputting $(\Lambda, 2)$ in $GA_{s-1}$. By graded consistency, any honest validator which participates to the output phase for grade $1$ of $GA_{s-1}$, i.e., any validator in $H_{t_s - \Delta, t_s + \Delta}$, outputs $(\Lambda, 1)$. By what we have just shown, extensions of $\Lambda$ will be output with grade 1 by (honest validators participating in the output phase for grade $1$ of) any $GA_{s'}$ for $s' \ge s-1$. Now, suppose that another honest validator decides a conflicting $\Lambda'$, and WLOG say it does so in slot $s'' \ge s$. Again, by graded consistency, every honest validator which participates in the output phase of $GA_{s''-1}$ outputs $(\Lambda', 1)$. Since $s''-1 \ge s-1$ we have shown that any such validator also output $(\Lambda, 1)$, which is a contradiction by no-divergence for grade $1$. *Lemma 2: Suppose slot $s$ has an honest leader which is awake at time $t_s$, and proposes $\Lambda$. Then, all honest validators $H_{t_s - \Delta, t_s + \Delta}$ input $\Lambda$ to $GA_s$*. *Proof:* Consider any honest validator $p \in H_{t_s - \Delta, t_s + \Delta}$, and its lock $L_s$, which it outputs with grade $1$ in $GA_{s-1}$. By graded consistency, the proposer outputs $(L_s, 0)$ in $GA_{s-1}$, at time $t_s$. Moreover, by no-divergence, it does not output any conflicting log with grade $0$, so its proposal $\Lambda$ extends $L_s$. The proposal is received by $p$ by time $t_s + \Delta$, and it inputs it to $GA_{s}$ since it extends $L_s$. *Liveness:* by Lemma 2, if the honest leader of slot $s$ is awake at time $t_s$ and proposes $\Lambda$, all honest validators $H_{t_s - \Delta, t_s + \Delta}$ input $\Lambda$ to $GA_s$. By validity, all validators $H_{t_{s+1} - \Delta, t_{s+1} + \Delta}$ then output $(\Lambda, 1)$ in $GA_s$. By Lemma 1, this then holds in $GA_{s'}$ for all $s' \ge s$. This also implies that honest validators $H_{t_{s'+1} - \Delta, t_{s'+1} + \Delta}$ input an extension of $\Lambda$ to $GA_{s'+1}$ for all $s' \ge s$. By validity, any honest validator, which participates to the output phase for grade $2$ of any such $GA$, i.e., any honest validator awake at $t= t_{s'+2} - 2\Delta$ and $t = t_{s'+2} + 2\Delta$, will decide $\Lambda$. **Explicit specification without $GA$**: We now expand the previous description, removing the use of the $GA$ as a blackbox and making all logic explicit. The protocol is the same, but the description might be clearer to some, and it is soon going to be helpful when modifying this protocol to be asynchrony resilient. Validators keep a local variable $\tilde{s}$, and, at any time, have $V = \{\text{votes from non equivocators, from slot } \tilde{s}\}$, $S = |\{\text{unique senders of votes from slot } \tilde{s}\}|$. 1. **[Propose, $t=t_s$]** If leader for slot $s$, propose $\Lambda'$ extending $C_s$, the highest log $\Lambda$ such that $|V_{\Lambda}| > S/2$. 3. **[Vote, $t=t_s + \Delta]$**: Vote for a proposal extending $L_s$, the highest log $\Lambda$ such that $|V'_{\Lambda} \cap V_{\Lambda}| > S/2$, or vote for $L_s$ if no such proposal exists. 5. **[Decide, $t=t_s + 2\Delta]$**: Decide $D_s$, the highest log $\Lambda$ such that $|V''_{\Lambda} \cap V_{\Lambda}| > S/2$. Set $\tilde{s} = s$, $V'' = V$, and store $V''$. 7. **[$t=t_s + 3\Delta$]** Set $V' = V$, and store $V'$. ### Adding RLMD and asynchrony resilience **Protocol changes**: We consider the latest input messages from the last $\eta \in [0, \infty]$ slots, at all points in the TOB, i.e., we use input messages from all $GA_{s'}$ for $s' \in [s - \eta, s]$ in $GA_s$. The protocol is exactly as in the last specification, except for these modified definitions for $V$ and $S$: $V = \{\text{latest votes from non equivocators, from slots } \in [\tilde{s}-\eta, \tilde{s}]\}$, $S = |\{\text{unique senders of votes from slots } [\tilde{s}-\eta, \tilde{s}]\}|$. **Model** Accordingly, we assume that, for all time $t$, $h_{t - \Delta, t + \Delta} > |\bigcup_{1 \le k \le \eta}H_{t - \Delta - 4k\Delta, t + \Delta - 4k\Delta}\cup B_{t + 6\Delta}|$. Alternatively, we can make the slightly stronger assumption that $h_{t - \Delta, t + \Delta} > |\bigcup_{t \in [t-\Delta - 4\eta\Delta, t-3\Delta]}H_{t}\cup B_{t + 6\Delta}|$. **Security under synchrony**: The fact that commit implies lock implies candidate still holds. Let's just consider the case of lock and candidate. If validator $i$ has $L_s = \Lambda$, take any vote $\in V'_{\Lambda} \cap V_{\Lambda}$ in the **Vote** phase for $i$. For this vote to be in $V_{\Lambda}$, it must still be a latest vote, and its sender must not be an equivocator, which implies that, if seen by the proposer by time $t_s$, $\Delta$ earlier, it would have also been considered a latest vote and from a non-equivocator, and it would be in $V_{\Lambda}$ of the proposer. In fact, it must have been seen by $i$ by time $t_s - \Delta$, in order to be in $V'$, so the proposer would have indeed seen it by $t_s$, and it would be in $V_{\Lambda}$ of the proposer at that time. That lock implies candidate then follows easily, and the argument that commit implies lock is analogous. Note that this argument is nothing but the graded consistency argument of the $GA$, except in that we need to take care to check that a vote which is used for locking is also seen as latest by the proposer, so that it can use it in its choice of a candidate. In other words, we rely on the fact that votes discarded by the proposer because not latest would also have been discarded by validators at voting time, much like an equivocating sender identified by the proposer is also identified by them. This aside, the normal functioning of the protocol is ensured by the usual reduction argument, centered around the fact that the senders of non-fresh latest messages can just be treated as adversarial, whereas the behavior of the validators in $H_{t_s - \Delta, t_s + \Delta}$ is unchanged, as their latest votes in $GA_s$ are always the inputs from $GA_s$ itself. This ensures validity, integrity and no-divergence. **Asynchrony resilience**: the argument is also the usual. Suppose we have a clique $H$, which all input an extension of $\Lambda$ to a synchronous $GA_s$, and that this clique is a majority in the following, potentially asynchronous, $GA$s, up to $GA_{s+\eta}$, which is again synchronous. Since $GA_s$ is synchronous, these inputs are observed by the clique, and are still unexpired in $GA_{s+\eta}$, so each validator in $H$ sees the latest input of other validators in $H$ as being from no earlier than $GA_s$, throughout slots $[s, s+\eta]$. Now, suppose all validators in $H$ have either input nothing or an extension of $\Lambda$ in all slots $< s'$ for $s' \in (s, s+\eta]$. Then, all latest inputs of validators of $H$, as seen by any validator in $H$ which inputs to $GA_{s'}$, are for extensions of $\Lambda$. Since $H$ is still a majority by assumption, this validator outputs $(\Lambda, 1)$ from $GA_{s'-1}$, and inputs an extension of $\Lambda$ to $GA_{s'}$. Therefore, all validators in $H$ input either nothing or an extension of $\Lambda$ in all $GA_{s'}$ for $s' \in [s, s+\eta]$. Since $GA_{s+\eta}$ is synchronous, all honest validators which participate in the output phase for grade $1$ of $GA_{s+\eta}$ are also now guaranteed to have seen messages of $H$ from $GA_s$, which are still unexpired in $GA_{s+\eta}$. In particular, they would have seen them by time $t_{s+\eta} + 3\Delta = t_{s+\eta+1 - \Delta}$, i.e., when storing $V'$. Therefore, they all output $(\Lambda, 1)$ and input an extension of $\Lambda$ to $GA_{s+\eta+1}$. Since synchrony has already been restored, this then implies that extensions of $\Lambda$ are always input by all honest validators in all subsequent $GA$s, as in Lemma 1. ## Building an SSF protocol Even in the original TOB, instant decisions are actually with a delay of one slot: a decision made at slot $s$ can at most decide something which was proposed in slot $s-1$. To build a simple SSF protocol, we would like to have instant confirmation, so that we can immediately justify and finalize a proposal. This is not only a question of speed of finality, but also of simplicity of the design, as it makes it incredibly simple to prevent interference of the finality gadget on the available chain. To get such instant guarantees, we can introduce an optimistic fast confirmation rule as in RLMD-GHOST. First, we take advantage of the fact that we do not require instant (non-optimistic) decisions anymore, to simplify the TOB itself. ### TOB with probabilistic-safety, 3$\Delta$ rounds If we desire to reduce the number of rounds in the TOB, we can choose to give up instant, deterministic safety for delayed, probabilistic safety. We start by simplifying the first GA, by removing the outputs of grade 2, and all rounds involving them, recovering a GA for grades $\{0,1\}$, requiring $3\Delta$ rounds: 1. **(Input phase, $t = 0$)** Input log $\Lambda$ 2. ($t = \Delta$) Store $V = \{\text{inputs}\}$ 3. **(Output phase for grade $0$, $t = 2\Delta$)** Let $V' = \{\text{inputs}\}$, $E = \{\text{inputs from non from equivocators}\}$, $S = |\{\text{unique input senders}\}|$, $v_{\Lambda}' = |V_{\Lambda}' \setminus E|$. Output $(\Lambda, 0)$ if $v_{\Lambda}' > S/2$. 4. **(Output phase for grade $1$, $t = 3\Delta$)** Let $E' = \{\text{inputs from equivocators}\}$, $S' = |\{\text{unique input senders}\}|$, $v_{\Lambda} = |V_{\Lambda} \setminus E'|$. Output $(\Lambda, 1)$ if $v > S'/2$. The same exact arguments made for the other GA show that all properties hold for this one. We can then also use it to construct a *probabilistic-safety* TOB where each proposal corresponds to a single $GA$. The key in doing so is realizing that decisions do not impact at all the behavior of participants in the previous TOB, they simply provide a confirmation rule for the protocol, and thus safety assurances. The **Decide** phase of slot $s$ in the previous TOB corresponds to time $5\Delta$ into $GA_{s-1}$, i.e., when $V$ is stored, to be later used in the output phase for grade 2, and $\Delta$ into $GA_{s}$, i.e., the output phase for grade 2. In other words, all events in the **Decide** phase are only relevant to grade 2 outputs. If we remove the **Decide** phase from the previous TOB, we are left with this: 1. **[Propose, $t=t_s$]** If leader for slot $s$, propose $\Lambda'$ extending $\Lambda$, the highest log output with grade $0$ by $GA_{s-1}$ (*candidate*) 2. **[Vote, $t=t_s + \Delta]$** $GA_s$ starts. Let $L_s$ be the highest log output with grade $1$ by $GA_{s-1}$ (*lock*). Input to $GA_s$ a proposal extending $L_s$, or $L_s$ if no such proposal exists. 3. **[$t=t_s + 2\Delta$]** Do nothing (other than what is required by $GA_s$) Crucially, we still have the guarantee that *candidates extend locks*, by graded consistency, and thus that all honest votes go to honest proposals. Much as in the other TOB, as well as in RLMD-GHOST through view-merge, this allows us to obtain reorg-resilience. In turn, reorg-resilience gives us probabilistic-safety for the $\kappa$-deep confirmation rule, exactly as in RLMD-GHOST. In the more explicit specification, this TOB is as follows: 1. **[Propose, $t=t_s$]** If leader for slot $s$, propose $\Lambda'$ extending $C_s$, the highest log $\Lambda$ such that $|V_{\Lambda}| > S/2$. 2. **[Vote, $t=t_s + \Delta]$**: Vote for a proposal extending $L_s$, the highest log $\Lambda$ such that $|V'_{\Lambda} \cap V_{\Lambda}| > S/2$, or vote for $L_s$ if no such proposal exists. 3. **[$t=t_s + 2\Delta$]** Set $\tilde{s} = s$, and $V' = V$. Store $V'$. ## Adding fast confirmations We introduce a fast confirmation rule, which immediately confirms a log whose subtree, in the current slot, has received 2/3 votes from the *whole* validator set. At any time between $(t_s + \Delta, t_{s+1} + \Delta]$, a validator keeps track of $\Lambda_C$, defined as the highest such log using votes from slot $s$, if there is one, and $\Lambda_C = Genesis$ otherwise. It keeps track also of a corresponding *quorum certificate* $Q_C$, consisting of the 2/3 votes for the subtree $\Lambda_C$ if such a quorum exists, or $Q_C = \bot$ otherwise. To ensure the safety of the confirmation rule, we modify the voting rule so that such logs are respected, as they are candidates for fast confirmation. Proposals now also include $\Lambda_C$ and $Q_C$. In order for a proposal to be valid, $Q_C$ must be a valid certificate for $\Lambda_C$, or $\Lambda_C = Genesis$. In all of the following, we always assume that $< 1/3$ of the whole validator set equivocates at any given slot, so that there are never quorum certificates for conflicting logs at the same slot. 1. **[Propose, $t=t_s$]:** If leader for slot $s$, propose $(\Lambda', \Lambda_C, Q_C)$ with $\Lambda'$ extending the highest log $\Lambda \succeq \Lambda_C$ such that $|V_{\Lambda}| > S/2$, if there is one, or $\Lambda'$ extending $\Lambda_C$ otherwise. 2. **[Vote, $t=t_s + \Delta$]:** - If a valid proposal $(\Lambda^p, \Lambda_{C}^p, Q_C^p)$ is received, and $\Lambda'_C \preceq \Lambda_C^p$, then let $\Lambda'_C = \Lambda_C^p$. - Let $L_s$ be the highest log $\Lambda \succeq \Lambda'_C$ such that $|V'_{\Lambda} \cap V_{\Lambda}| > S/2$, if there is one, or $L_s = \Lambda'_C$ otherwise. - Vote for a proposal extending $L_s$, if there is one, or for $L_s$ otherwise 3. **[Fast confirm, $t=t_s + 2\Delta]$:** Confirm $\Lambda_C$ 4. **[$t=t_s + 3\Delta$]:** Set $\tilde{s} = s$. Set $V' = V$, $\Lambda'_C = \Lambda_C$. Store $V', \Lambda'_C$. **Properties:** *Lemma 3: If all validators $H_{t_s - \Delta, t_s + \Delta}$ vote for an extension of $\Lambda$, then all validators in $H_{t_{s+1} - \Delta, t_{s+1} + \Delta}$ do so as well. By induction, all validators in $H_{t_s' - \Delta, t_s' + \Delta}$ vote for an extension of $\Lambda$ for all $s' \ge s.$* *Proof:* Since all honest validators which participate in the voting phase of slot $s$ vote for an extension of $\Lambda$, no quorum certificate of votes from slot $s$ can form for a log conflicting with $\Lambda$. Any honest validator voting in slot $s+1$ would then have either $\Lambda'_C \preceq \Lambda$ or $\Lambda \preceq \Lambda'_C$. If it updates it by setting $\Lambda'_C = \Lambda_C^p$, it first checks that either $\Lambda_C^p = Genesis$ or that $Q_C$ is a valid quorum certificate for $\Lambda_C^p$, so that in either case still $\Lambda'_C$ does not conflict with $\Lambda$. Therefore, $\Lambda'_C$ does not conflict with $\Lambda$ when used to compute $L_s$. If $\Lambda \preceq \Lambda'_C$ at this point, then clearly the validator votes for an extension of $\Lambda$, as it votes for an extension of $\Lambda'_C$. Otherwise, we use that $|V_{\Lambda}| \ge |H_{t_s - \Delta, t_s + \Delta}| > S/2$, so the validator votes for an extension of $\Lambda$. *Lemma 4:* Suppose slot $s$ has an honest proposer which is awake at time $t_s$, and proposes $(\Lambda^p, \Lambda^p_C, Q_C^p)$. Then, all honest validators $H_{t_s - \Delta, t_s + \Delta}$ vote for $\Lambda^p$. *Proof:* Consider an honest validator participating in the voting phase. Note that $\Lambda'_C \preceq \Lambda_C^p$, because there is a delay $\Delta$ between the time when $\Lambda_C'$ is set and when the proposal containing $\Lambda_C^p$ is made, so that the proposer observes a quorum for $\Lambda'_C$ or an extension of it, and does not observe a quorum for any conflicting log. Then, the honest validator sets $L_s$ to the highest log $\Lambda \succeq \Lambda_C^p$ such that $|V'_{\Lambda} \cap V_{\Lambda}| > S/2$, if there is one, or sets $L_s = \Lambda_C^p$ otherwise, and votes for $\Lambda^p$ as long as it extends $L_s$. If $L_s = \Lambda^p_C$, clearly $\Lambda^p$ extends $L_s$, since the proposer always extends $\Lambda^p_C$. If instead $L_s$ strictly extends $\Lambda_C^p$, than the proposer would also have extended $L_s$, because at proposal time it would have also observed $|V_{L_s}| > S/2$, by the usual time-shifted quorum argument. The honest validator therefore votes for $\Lambda^p$. *Reorg-resilience:* we apply Lemma 3 and Lemma 4. *Safety of fast confirmation*: if an honest validator fast confirms $\Lambda$ at slot $s$, any other honest validator $\in H_{t_{s+1} - \Delta, t_{s+1} + \Delta}$ sees the 2/3 quorum by time $t = t_s + 3\Delta$, and it does not see any conflicting 2/3 quorum from slot $s$. Therefore, $\Lambda \preceq \Lambda'_C$ for any such validator. The voting rule then ensures that it votes for a log extending $\Lambda'_C$, and thus $\Lambda$, at slot $s+1$. We can then apply Lemma 3. *Liveness of fast confirmation*: an honest proposal is voted by all honest validators by Lemma 4, so a 2/3 quorum forms whenever there are 2n/3 honest validators participating in a voting phase. The quorum is seen by all awake honest validators by the fast confirmation time, so they all fast confirm the proposal immediately. ## SSF protocol A checkpoint $\mathcal{C}$ is a pair $(\Lambda, s)$ with a log and a justification slot, and we write $\Lambda_\mathcal{C} = \Lambda, s_\mathcal{C} = s$. Each validator now keeps track of and of a set of justified checkpoint $\mathcal{J}$, the latest (of highest justification slot) of which we call $\mathcal{LJ}$. At any time between $(t_s + \Delta, t_{s+1} + \Delta]$, it also keeps track of $\Lambda_C$, redefined to be consistent with $\Lambda_{\mathcal{LJ}}$, as the highest log $\Lambda \succeq \Lambda_{\mathcal{LJ}}$ for which a quorum certificate from slot $s$ exists, if there is one, and as $\Lambda_C = \Lambda_{\mathcal{LJ}}$ otherwise. Proposals include $\mathcal{LJ}$ as well as $\Lambda_C$ and $Q_C$. 1. **[Propose, $t=t_s$]:** If leader for slot $s$, propose $(\Lambda', \Lambda_C, Q_C, \mathcal{LJ})$ with $\Lambda'$ extending the highest log $\Lambda \succeq \Lambda_C$ such that $|V_{\Lambda}| > S/2$, if there is one, or $\Lambda'$ extending $\Lambda_C$ otherwise. 2. **[Vote, $t=t_s + \Delta]$:** - If a valid proposal $(\Lambda^p, \Lambda_C^p, Q_C^p, \mathcal{LJ}^p)$ is received such that $\mathcal{LJ}^p \in \mathcal{J}$, $s_{\mathcal{LJ}^p} \ge s_{\mathcal{LJ}'}$, set $\mathcal{LJ'} = \mathcal{LJ}^p$, set $\Lambda'_C = \Lambda_{\mathcal{LJ}^p}$ if $\Lambda'_C \not \succeq \Lambda_{\mathcal{LJ}^p}$, and set $\Lambda'_C = \Lambda_C^p$ if $\Lambda_C^p \succeq \Lambda'_C$. - Let $L_s$ be the highest log $\Lambda \succeq \Lambda'_C$ such that $|V'_{\Lambda} \cap V_{\Lambda}| > S/2$, if there is one, or $L_s = \Lambda'_C$ otherwise. - Vote for a proposal extending $L_s$, if there is one, or for $L_s$ otherwise 3. **[Fast confirm and FFG-vote, $t=t_s + 2\Delta]$:** Confirm $\Lambda_C$. Cast the FFG vote $\mathcal{LJ}' \to (\Lambda_C, s)$ 4. **[$t=t_s + 3\Delta$]:** Set $\tilde{s} = s$, $V' = V$, $\Lambda'_C = \Lambda_C, \mathcal{LJ}' = \mathcal{LJ}$. Store $V', \Lambda'_C$, $\mathcal{LJ}'$. **Properties**: *Lemma 5: Suppose slot $s$ has an honest proposer which is awake at time $t_s$, and proposes $(\Lambda^p, \Lambda^p_C, Q_C^p, \mathcal{LJ}^p)$. Then, all honest validators $H_{t_s - \Delta, t_s + \Delta}$ vote for $\Lambda^p$.* *Proof:* An honest proposal is valid, and $\mathcal{LJ}^p \in J$, $s_{\mathcal{LJ}^p} \ge s_{\mathcal{LJ}'}$ all hold for it. Then, the honest validator receiving it first sets $\Lambda'_C = \mathcal{LJ}^p$ if $\Lambda'_C \not \succeq \mathcal{LJ}^p$, at which point it is the case that $\Lambda'_C \preceq \Lambda_C^p$. Therefore, it then sets $\Lambda'_C = \Lambda_C^p$. With that, we are left with the usual argument about time-shifted quorum. *Lemma 6: If all honest voters at slot $s$ vote for an extension of $\Lambda$, and no honest validator fast confirmed a conflicting log $\Lambda'$ at any slot $\le s$, then all honest voters at slot $s+1$ also vote for an extension of $\Lambda$*. *Proof:* There is also no justification of a checkpoint $(\Lambda', s')$ with $\Lambda'$ conflicting with $\Lambda$ and $s' \le s$, since it requires an honest validator to have fast confirmed $\Lambda'$ at slot $s'$, before casting an FFG vote with target $(\Lambda', s')$. Therefore, since no conflicting quorum certificate from slot $s$ nor justification from slots $\le s$ exist, all honest validators in the voting phase of slot $s+1$ have $\Lambda'_C$ not conflicting with $\Lambda$. Since they also see $|V'_{\Lambda} \cap V_{\Lambda}| \ge |H_{t_{s} - \Delta, t_{s} + \Delta}| > S/2$, they vote for an extension of $\Lambda$. *Lemma 7: if an honest validator fast confirms a log $\Lambda$ at slot $s$, then all honest voters in slots $> s$ vote for an extension of $\Lambda$. *Proof*: Suppose there is a counterexample, and let $\Lambda$ be of minimal fast confirmation slot $s$. By minimality of $s$, there cannot be any conflicting fast confirmation in a slot $< s$, because fast confirmation of $\Lambda$ in slot $s$ requires at least one honest vote for it. Moreover, there cannot be a conflicting fast confirmation in slot $s$, because conflicting quorum certificates cannot form in the same slot. Therefore, any conflicting confirmation must be in a slot $> s$. This moreover implies that any justification of a checkpoint $(\Lambda', s')$ with $\Lambda'$ conflicting with $\Lambda$ must have $s' > s$ as well, since it requires an honest validator to have fast confirmed $\Lambda'$ at slot $s'$, before casting an FFG vote with target $(\Lambda', s')$. Before the voting phase in slot $s+1$, all honest voters have $\Lambda'_C$ extending $\Lambda$, because they have all observed a quorum certificate for $\Lambda$ by time $t_s + 3\Delta$, and there is no justified checkpoint $\mathcal{C}$ with $\Lambda_{\mathcal{C}}$ conflicting with $\Lambda$. Also because no such justified checkpoint exists at this point, $\Lambda'_C$ can only be updated to an extension of itself during the voting phase, so that at the end all honest validators vote for an extension of $\Lambda$. We now show by induction that all honest voters in slots $> s$ vote for an extension of $\Lambda$. Suppose that this is the case for all slots $[s+1, s']$ as we have already shown to be the case for our base case $s' = s+1$. Then, no quorum certificate conflicting with $\Lambda$ could have formed in any slot $\in [s+1, s']$, and we already shown that no such quorum certificate could have formed in slots $\le s$ either, so that overall no conflicting quorum certificate could have formed in any slot $\le s'$. By Lemma 6, all honest voters at slot $s'+1$ vote for an extension of $\Lambda$, contradicting that $\Lambda$ is a counterexample, and thus the existence of one. *Safety of fast confirmations*: follows from Lemma 7 and the fact, if all honest voters at slot $s$ vote for an extension of $\Lambda$, no log conflicting with $\Lambda$ can be fast confirmed at slot $s$. *Reorg-resilience:* by Lemma 5, an honest proposal $\Lambda$ from slot $s$ is voted by all honest voters at slot $s$. Lemma 7 then implies that no conflicting log $\Lambda'$ has been fast confirmed at a slot $< s$, and moreover this also holds at slot $s$ since no log can be fast confirmed without any honest vote. We can then proceed by induction and show that all honest voters in subsequent slots vote for an extension of $\Lambda$. If this holds for slots $[s, s']$, then there cannot be any conflicting fast confirmation in slots $\le s'$, so it also holds in slot $s'+1$ by Lemma 6, completing the proof. *Lemma 8: if all honest validators are awake in a slot $s$ with an honest leader which proposes $(\Lambda, \Lambda_C, Q_C, \mathcal{LJ})$, then all honest validators cast an FFG vote for $\mathcal{LJ} \to (\Lambda, s)$, and all honest validators have $\mathcal{LJ} = (\Lambda, s)$ at $t = t_s + 3\Delta$* *Proof:* By Lemma 5, all honest validators vote for $\Lambda$, so they all see a quorum certificate consisting of honest votes by $t_s + 2\Delta$, and have $\Lambda_C = \Lambda$ then. Moreover, they all set $\mathcal{LJ}'$ to the proposed checkpoint $\mathcal{LJ}$, since the delay $\Delta$ between setting $\mathcal{LJ}$ at $t_s - \Delta$ and the proposal time $t_s$ ensures that $s_{\mathcal{LJ}} \geq s_{\mathcal{LJ}'}$. They then all cast an FFG vote for $\mathcal{LJ}' \to (\Lambda_C, s) = \mathcal{LJ} \to (\Lambda, s)$. *Liveness of finality: if all honest validators are awake in consecutive slots with honest leaders $s, s+1$, then the first proposal is finalized* *Proof*: By two repeated applications of Lemma 8, together with the fact that the second honest proposer extends the first proposal, since it sees it as justified, which also follows by Lemma 8.