TheStellar Consensus Protocol 27 PROOF. LetS ={v∣bv ≥n}bethesetofnodeswithcountersatleastn.Byassump- tion, S contains an intact node. Furthermore, because that intact node armed its timer, S must also encompass a quorum. Let S+ be the intact subset of S, and S− be the set of intact nodes not in S. By Theorem 10, either S− = ç (in which case the theorem is trivial), or S+ is v-blocking for some v ∈ S. By step 9 on page 24, v will adjust its ballot so b .n ≥ n. At this point, repeat the argument with S ← S ∪ {v} until such point as − v S =ç. THEOREM15. Given long enough timeouts, if an intact node has reached the CON- FIRM phase with b.x = x, then eventually all intact nodes will terminate. PROOF. If an intact node has reached the EXTERNALIZE phase, it has confirmed commit c for some ballot c. By Theorem 11, all intact nodes will confirm commit c, after which they will terminate in step 7 on page 24. Otherwise, an intact node in the CONFIRM phase has accepted commit c where c = ⟨n,x⟩. Beforehand, an intact node confirmed c was prepared. By Theorem 11, all intact nodes will eventually have ℎ ≥ c. Moreover, by Theorem 8, no intact node v can accept abort c, so no intact node can accept as prepared any ballot p such that p ⋧ c. Hence, after sufficient communication, every intact node will permanently have ℎ ≳ c. The intact node or nodes with the lowest b will, by Theorem 14, raise their ballots until such point as all intact nodes with armed timers have the same ballot counter. Since they also have identical z = ℎ.x = x, they will all have the same ballot. If they cannot complete the protocol because one or more intact nodes have higher ballots, the nodes with higher numbered ballots will not have timers set. Hence, the nodes with lower- numberedballots will after a timeout set set b ← ⟨b.n+1,x⟩ until eventually all intact nodes are on the same ballot and can complete the protocol THEOREM16. Regardlessofpastill-behavior, given long enough timeouts and peri- ods in which ill-behaved nodes do not send new messages, intact nodes running SCP will terminate. PROOF. By Theorem 12, all intact nodes will eventually have identical sets Z of candidate values. Assume this point has passed and every intact node v has the same composite value z = combine(Z). If no intact node ever confirms any ballot b prepared without b.x = z, then after at most one timeout, all new ballots of intact nodes will have value z and, given a sufficient timeout, complete the protocol. By Theorem 15, nodeswill also complete if any intact node has progressed beyond the PREPARE phase. The remaining case is that an intact node has ℎ ≠ 0 and all intact nodes have ' = PREPARE.ByTheorem14,whentheintactnodeornodeswiththehighestb.narmtheir timers, if timers are long enough, other nodes will catch up. Moreover, by Theorem 11, if timers are long enough, nodes will converge on the value of ℎ (the highest confirmed prepared ballot) before the next timeout, at which point all intact nodes will raise b to the same value and complete the protocol. Theorem 16 assures us there are no dead-end states in SCP. However, a set of ill- behaved nodes with very good timing could perpetually preempt an SCP system by delaying messages so that some fraction of intact nodes update ℎ right before timers fire and the remaining update it after, preventing intact nodes from converging on the nextballot. Nodescanrecoverfromsuchanattackbyremovingill-behavednodesfrom their slices. An alternative would be to add randomness to the protocol, for instance changing step 2 on page 24 to update z with probability 1∕2 (or even with probability propor- tional to the fraction of the timer remaining). Such an approach would terminate with