TheStellar Consensus Protocol 19 protocol produces candidate values for a slot. If run long enough, it eventually pro- duces the same set of candidate values at every intact node, which means nodes can combine the candidate values in a deterministic way to produce a single composite value for the slot. There are two huge caveats, however. First, nodes have no way of knowing when the nomination protocol has reached the point of convergence. Second, even after convergence, ill-behaved nodes may be able to reset the nomination process afinite number of times. When nodes guess that the nomination protocol has converged, they execute the ballot protocol, which employs federated voting to commit and abort ballots associated with composite values. When intact nodes agree to commit a ballot, the value associ- ated with the ballot will be externalized for the slot in question. When they agree to abort a ballot, the ballot’s value becomes irrelevant. If a ballot gets stuck in a state where one or more intact nodes cannot commit or abort it, then nodes try again with a higher ballot; they associate the new ballot with the same value as the stuck one in case any node believes the stuck ballot was committed. Intuitively, safety results from ensuring that all stuck and committed ballots are associated with the same value. Liveness follows from the fact that a stuck ballot can be neutralized by moving to a higher ballot. The remainder of this section presents the nomination and ballot protocols. Each is described first in terms of conceptual statements, then as a concrete protocol with messages representing sets of conceptual statements. Finally, Section 6.3 shows the correctness of the protocol. SCP treats each slot completely independently and can be viewed as many separate instances of a single-slot consensus protocol (akin to the “single-decree synod” in Paxos [Lamport 1998]). Concepts such as candidate values andballots must always be interpreted in the context of a particular slot even if much of the discussion leaves the slot implicit. 6.1. Nomination protocol Because slots need only be partially ordered, some applications of SCP will have only one plausible ballot per slot. For example, in certificate transparency, each CA may have its own series of slots and sign exactly one certificate tree per slot. However, other applications admit many plausible values per slot, in which case it is helpful to narrow down the possible input values. Our strategy is to begin with a synchronous nomination protocol that achieves consensus under certain timing assumptions, and feed the output of the nomination protocol into an asynchronous ballot protocol whose safety does not depend on timing [Lamport 2011a]. Such an initial synchronous phase is sometimes called a conciliator [Aspnes 2010]. Thenominationprotocol works by converging on a set of candidate values for a slot. Nodes then deterministically combine these candidates into a single composite value for the slot. Exactly how to combine values depends on the application. By way of example, the Stellar network uses SCP to choose a set of transactions and a ledger timestamp for each slot. To combine candidate values, Stellar takes the union of their transaction sets and the maximum of their timestamps. (Values with invalid times- tamps will not receive enough nominations to become candidates.) Other possible ap- proaches include combining sets by intersection or simply picking the candidate value with the highest hash. Nodes produce a candidate value x through federated voting on the statement nominate x. Definition (candidate). A node v considers a value x to be a candidate when v has confirmedthestatementnominatex—i.e., v has ratified accept(nominate x).