TheStellar Consensus Protocol 21 Variable Meaning X Thesetofvaluesnodevhasvotedtonominate Y Thesetofvalues node v has accepted as nominated Z Thesetofvaluesthatnodevconsiderscandidatevalues N Thesetofthelatest NOMINATE messagereceivedfromeachnode Fig. 14. Nomination state maintained by node v for each slot NOMINATEviXY D This is a message from node v nominating values for slot i. D is v’s quorum slice Q(v) or a collision-resistant hash of Q(v). X and Y are from v’s state. The concrete message encodes the following conceptual messages: — {nominatex∣x∈X} (votes to nominate each value in X) — {accept(nominate x) ∣ x ∈ Y } (votes to confirm nominations in Y) Fig. 15. Messageinnominationprotocol findanodev ∈neighbors(v,n)maximizingpriority(n,v ) and vote to nominate every- n n thing v has voted to nominate. n THEOREM12. Eventually,allintact nodes will have the same composite value. PROOF. The theorem follows from the three properties of the nomination protocol. Each intact node will only ever vote to nominate a finite number of ballots. In the absence of action by ill-behaved nodes, intact nodes will converge on the same set of candidate values, call it Z. To forestall this convergence, ill-behaved nodes may introduce new candidate values, which for a period may be candidates at some but not all intact nodes. Suchvalueswillneedtohavegarneredvotesfromwell-behavednodes, however,whichlimitsthemtoafiniteset.Eventually,ill-behavednodeswilleitherstop perturbingthesystemorrunoutofnewcandidatevaluestoinject,inwhichcaseintact nodes will converge on Z. 6.1.1. Concrete nomination protocol. Figure 14 lists the nomination protocol state a node v must maintain for each slot. X is the set of values x for which v has voted nominate x, Y is the set of values for which v has accepted nominate x, and Z is the set of candidate values—i.e., all values for which a quorum including v has stated accept(nominate x). Finally, v maintains N, the latest concrete message from each node. (Technically, X, Y, and Z can all be recomputed from N, but it is convenient to be able to reference them directly.) All four fields are initialized to the empty set. Note that all three of X, Y, and Z are growing over time—nodes never remove a value from these sets. Figure 15 shows the concrete message that constitutes the nomination protocol. Be- cause X and Y grow monotonically over time, it is possible to determine which of mul- tiple NOMINATE messages from the same node is the latest, independent of network delivery order, so long as D does not change mid-nomination (or D has to be versioned). Only one remote procedure call (RPC) is needed for nomination—the argument is the sender’s latest NOMINATE message and the return value is the receiver’s. If D or the nominated values are cryptographic hashes, a second RPC should permit retrieval of uncached hash preimages as needed. Because nodes cannot tell when the nomination protocol is complete anyway, SCP mustcopewithdifferentcompositevaluesatdifferentnodes.Asanoptimization,then,

The Stellar Consensus Protocol - Page 22 The Stellar Consensus Protocol Page 21 Page 23