Stellar 백서

Stellar

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 4쪽

y 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]. The nomination protocol 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 confirmed the statement nominate x—i.e., v has ratified accept .nominate x/. 20 D. Mazi`eres So long as node v has no candidate values, v may vote in favor of nominate x for any value x that passes application-level validity checks (such as timestamps not being in the future). In fact, v should generally re-nominate any values that it sees other nodes nominate, with some rate-limiting discussed below to avoid an explosion of can- didates. As soon asv has a candidate value, however, it must cease voting tonominate x for any new values x. It should still continue to accept nominate statements for new values (when accepted by a v-blocking set) and confirm new nominate statements as prescribed by the federated voting procedure. The nomination protocol enjoys several properties when a system has intact nodes (meaning it has avoided complete failure). Specifically, for each slot: (1) Intact nodes can produce at least one candidate value. (2) At some point, the set of possible candidate values stops growing. (3) If any intact node considers x to be a candidate value, then eventually every intact node will consider x to be a candidate value. Now consider how the nomination protocol achieves its three properties. Property 1 is achieved because nominate statements are irrefutable. Nodes never vote against nominating a particular value, and until the first candidate value is confirmed, intact nodes can vote to nominate any value. So long as any value x passes application-level validity checks, intact nodes can vote for and confirm nominate x. Property 2 is en- sured because once each intact node confirms at least one candidate value—which will happen in a finite amount of time—no intact nodes will vote to nominate any new val- ues. Hence, the only values that can become candidates are those that already have votes from intact nodes. Property 3 is a direct consequence of Theorem 11. The nomination process will be more efficient if fewer combinations of values are in play. Hence, we assign nodes a temporary priority and have each node, when pos- sible, nominate the same values as a higher-priority node. More concretely, let H be a cryptographic hash function whose range can be interpreted as a set of integers ^0; § ; hmax * 1‘. (H might be SHA-256 [National Institute of Standards and Technol- ogy 2012], in which case hmax = 2 256.) Let Gi.m/ = H.i; xi*1; m/ be a slot-specific hash function for slot i, where xi*1 is the value chosen for the slot preceding i (or the sorted set of values of all immediate dependencies of slot i when slots are governed by a par- tial order). Given a sloti and a round number n, each nodev computes a set ofneighbors and a priority for each neighbor as follows: weight .v; v¤/ = óóó^ q Ý q ¸ Q.v/ Æ v¤ ¸ q ‘óóó óóóQ.v/óóó neighbors.v; n/ = v¤ Ý Gi.N; n; v¤/ < hmax weight .v; v¤/ priority.n; v¤/ = Gi.P; n; v¤/ N and P are constants to produce two different hash functions. The function weight .v; v¤/ returns the fraction of slices in Q.v/ containing v¤. By using weight as the probability over n that v¤ appears in neighbors.v; n/, we also reduce the chance that nodes without a lot of trust will dominate a round. Each node v should initially find a node v0 ¸ neighbors.v; 0/ that maximizes priority.0; v0/ among nodes it can communicate with, then vote to nominate the same values as v0. Only if v = v0 should v introduce a new value to nominate. v should use timeouts to decide on new nominate statements to vote for. After n timeouts, v should The Stellar Consensus Protocol 21 Variable Meaning X The set of values node v has voted to nominate Y The set of values node v has accepted as nominated Z The set of values that node v considers candidate values N The set of the latest NOMINATE message received from each node Fig. 14. Nomination state maintained by node v for each slot NOMINATE v i X Y 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: — ^ nominate x Ý x ¸ X ‘ (votes to nominate each value in X) — ^ accept .nominate x/ Ý x ¸ Y ‘ (votes to confirm nominations in Y ) Fig. 15. Message in nomination protocol find a node vn ¸ neighbors.v; n/ maximizing priority.n; vn/ and vote to nominate every- thing vn has voted to nominate. THEOREM 12. Eventually, all intact 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. Such values will need to have garnered votes from well-behaved nodes, however, which limits them to a finite set. Eventually, ill-behaved nodes will either stop perturbing the system or run out of new candidate values to inject, in which case intact 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 asD does not change mid-nomination (orD 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 must cope with different composite values at different nodes. As an optimization, then, 22 D. Mazi`eres nodes can attempt to predict the final composite value before they even have a candi- date value. To do this, the composite value can be taken as combine.Z/ when Z ‘ ç, otherwise combine.Y / when Y ‘ ç, otherwise combine.X/ when X ‘ ç. This means the highest-priority node can optimistically initiate balloting at the same time as nom- ination, piggybacking its first ballot message PREPARE (described below) on its first NOMINATE message. 6.2. Ballot protocol Once nodes have a composite value, they engage in the ballot protocol, though nomi- nation may continue to update the composite value in parallel. A ballot b is a pair of the form b = Œn; xº, where x ‘ ò is a value and b is a referendum on externalizing x for the slot in question. The value n g 1 is a counter to ensure higher ballot numbers are always available. We use C-like notation b:n and b:x to denote the counter and value fields of ballot b, so that b = Œb:n; b:xº. Ballots are totally ordered, with b:n more signif- icant than b:x. For convenience, a special invalid null ballot 0 = Œ0; òº is less than all other ballots, and a special counter value Ø is greater than all other counters. We speak of committing and aborting a ballot b as a shorthand for using federated voting to agree on the statementscommit b and abort b, respectively. For a given ballot, commit and abort are contradictory, so a well-behaved node may vote for at most one of them. In the notation of Section 5, the opposite of commit b would be “ commit b;” but abort b is a more intuitive notation. Because at most one value can be chosen for a given slot, all committed and stuck ballots must contain the same value. Roughly speaking, this meanscommit statements are invalid if they conflict with lower-numbered unaborted ballots. Definition .compatible/. Two ballots b1 and b2 are compatible, written b1 í b2, iff b1:x = b2:x and incompatible, written b1 ò b2, iff b1:x ‘ b2:x. We also write b1 ¿ b 2 or b2 À b 1 iff b1 f b2 (or equivalently b2 g b1) and b1 í b2. Similarly, b1 , b2 or b2 - b1 means b1 f b2 (or equivalently b2 g b1) and b1 ò b2. Definition .prepared/. A ballot b is prepared iff every statement in the following set is true: ^ abort bold Ý bold, b ‘. More precisely, then, commit b is valid to vote for only if b is confirmed prepared, which nodes ensure through federated voting on the corresponding abort statements. It is convenient to vote on these statements en masse, so wherever we write “ b is prepared,” the surrounding context applies to the whole set of abort statements. In particular, a node votes, accepts, or confirms that b is prepared iff it votes for, accepts, or confirms, respectively, all of theseaborts. To commit a ballotb and externalize its value b:x, SCP nodes first accept and confirm b is prepared, then accept and confirm commit b. Before the first intact node votes for commit b, the prepare step, through federated voting, ensures all intact nodes can eventually confirm b is prepared. When an intact node v accepts commit b, it means b:x will eventually be chosen. However, as discussed in Section 5.4.1, v must confirm commit before acting on it in case v is befouled. 6.2.1. Concrete ballot protocol. Figure 16 illustrates the per-slot state maintained by each node. A nodev stores: its current phase ’; its current ballot b; the two most recent incompatible ballots it has prepared (p; p¤); the lowest (c) and highest (h) ballot, if any, it has voted to commit and for which it has not subsequently accepted an abort (or for which it has accepted or confirmed a commit in later phases); a next value z to try if the current ballot fails; and the latest message received from each node (M). Ballots b, p, p¤, and h are non-decreasing within a phase. In addition, if c ‘ 0—meaning v may The Stellar Consensus Protocol 23 Variable Meaning ’ Current phase: one of PREPARE , CONFIRM , or EXTERNALIZE b Current ballot that node v is attempting to prepare and commit (b ‘ 0) p¤; p The two highest ballots accepted as prepared such that p¤, p, where p¤ = 0 or p = p¤ = 0 if there are no such ballots c; h In PREPARE : h is the highest ballot confirmed as prepared, or 0 if none; if c ‘ 0, then c is lowest and h the highest ballot for which v has voted commit and not accepted abort. In CONFIRM : lowest, highest ballot for which v accepted commit In EXTERNALIZE : lowest, highest ballot for which v confirmed commit Invariant: if c ‘ 0, then c ¿ h ¿ b . z Value to use in next ballot. If h = 0, then z is the composite value (see Section 6.1); otherwise, z = h:x. M Set of the latest ballot message seen from each node Fig. 16. Ballot state maintained by each node v for each slot PREPARE v i b p p ¤ c:n h:n D This is a message from node v about slot i. D specifies Q.v/. The other fields reflect v’s state. Values c:x and h:x are elided as c:x = h:x = b:x when c:n ‘ 0. This concrete message encodes a host of conceptual statements, as follows: — ^ abort b¤ â accept .abort b¤/ Ý b¤, b ‘ (a vote to prepare b) — ^ accept .abort b¤/ Ý b¤, p ‘ (a vote to confirm p is prepared) — ^ accept .abort b¤/ Ý b¤, p¤ ‘ (a vote to confirm p¤ is prepared) — ^ commit b¤ Ý c:n ‘ 0 Æ c ¿ b ¤ ¿ h ‘ (a vote to commit c; § ; h if c ‘ 0) CONFIRM v i b p:n c:n h:n D Sent by v to try to externalize b:x for slot i after accepting a commit. Implies p:x = c:x = h:x = b:x in v’s state. For convenience, we also say p¤ = 0 (p¤ is irrelevant after accepting commit). D specifies Q.v/ as above. Encodes: — Everything implied by PREPARE v i ŒØ; b:xº p 0 c:n Ø D — ^ accept .commit b¤/ Ý c ¿ b ¤ ¿ h ‘ (a vote to confirm commit c; § ; h) EXTERNALIZE v i x c:n h:n D After v confirms commit Œc:n; xº for slot i and externalizes value x, this mes- sage helps other nodes externalize x. Implies c = Œc:n; xº and h = Œh:n; xº. For convenience, we also say b = p = h = ŒØ; xº, and p¤ = 0. Encodes: — Everything implied by CONFIRM v i ŒØ; xº Ø c:n Ø D — Everything implied by CONFIRM v i ŒØ; xº Ø c:n h:n ^^v‘‘ Fig. 17. Messages in SCP’s ballot protocol have participated in ratifying commit c—code must ensure c ¿ h ¿ b . This invariant guarantees a node can always legally vote to prepare its current ballot b. Figure 17 shows the three ballot protocol messages, with ’ determining which one of the three a node can send. Ballot messages may overlap with nomination messages, so that, when h = 0, a node may update z in response to a NOMINATE message. Note 24 D. Mazi`eres that “ a â accept .a/” is what each node must assert for a quorum to accept a under condition 1 of the definition of accept. For convenience, when comparing state across nodes, we will identify fields belong- ing to particular nodes with subscripts. If v is a node, then we write bv; pv; p¤v; § to denote the values of b; p; p¤; § in node v’s state as described in Figure 16. Similarly, we let vm denote message m’s sender, and bm; pm; p¤m; § denote the corresponding values of b; p; p¤; § in vm’s state as implied by m. Each node initializes its ballot state for a slot by setting ’ } PREPARE , z } ò, b } Œ0; zº, M } ç, and all other fields ( p; p¤; c; h) to the invalid ballot 0. While z = ò, a node can receive but not send ballot messages. Once z ‘ ò, if b:n = 0 , a node reinitializes b } Œ1; zº to start sending messages. Nodes then repeatedly exchange messages with peers, sending whichever ballot message is indicated by’. Upon adding a newly received message m to Mv, a node v updates its state as follows: (1) If ’ = PREPARE and m lets v accept new ballots as prepared, update p and p¤. Afterwards, if either p- h or p¤- h, then set c } 0. (2) If ’ = PREPARE and m lets v confirm new higher ballots prepared, then raise h to the highest such ballot and set z } h:x. (3) If ’ = PREPARE , c = 0, b f h, and neither p- h nor p¤- h, then set c to the lowest ballot satisfying b f c ¿ h . (4) If ’ = PREPARE and v accepts commit for one or more ballots, set c to the lowest such ballot, then set h to the highest ballot such that v accepts all ^ commit b¤ Ý c ¿ b ¤ ¿ h ‘, and set ’ } CONFIRM . Also set z } h:x after updating h, and unless h ¿ b , set b } h. (5) If ’ = CONFIRM and the received message lets v accept new ballots prepared, raise p to the highest accepted prepared ballot such that p í c. (6) If ’ = CONFIRM and v accepts more commit messages or raises b, then let h¤ be the highest ballot such that v accepts all ^ commit b¤ Ý b ¿ b ¤ ¿ h ¤ ‘ (if any). If there exists such an h¤ and h¤ > h , then set h } h¤, and, if necessary, raise c to the lowest ballot such that v accepts all ^ commit b¤ Ý c ¿ b ¤ ¿ h ‘. (7) If ’ = CONFIRM and v confirms commit c¤ for any c¤, set c and h to the lowest and highest such ballots, set ’ } EXTERNALIZE , externalize c:x, and terminate. (8) If ’ ¸ ^PREPARE ; CONFIRM ‘ and b < h , then set b } h. (9) If ’ ¸ ^ PREPARE ; CONFIRM ‘ and ˙S Ó M v such that the set of senders ^ vm¤ Ý m¤ ¸ S ‘ is v-blocking and ¯m¤ ¸ S, bm¤ :n > b v:n, then set b } Œn; zº, where n is the lowest counter for which no such S exists. Repeat the previous steps after updating b. While c = 0, the above protocol implements federated voting to confirmb is prepared. Once c ‘ 0, the protocol implements federated voting on commit c¤ for every c ¿ c ¤ ¿ h. For the CONFIRM phase, once a well-behaved node accepts commit c, the node never accepts, and hence never attempts to confirm, commit c¤ for any c¤ ò c. Once a commit is confirmed, the value of its ballot is safe to externalize assuming quorum intersection. All messages sent by a particular node are totally ordered by Œ’; b; p; p¤; hº, with ’ the most significant and h the least significant field. The values of these fields can be determined from messages, as described in Figure 17. All PREPARE messages precede all CONFIRM messages, which in turn precede the single EXTERNALIZE message for a given slot. The ordering makes it possible to ensure M contains only the latest ballot The Stellar Consensus Protocol 25 from each node without relying on timing to order the messages, since the network may re-order messages. A few details of the protocol merit explanation. The statements implied byPREPARE of the form “ abort b¤ â accept .abort b¤/” do not specify whether v is voting for or con- firming abort b¤. The distinction is unimportant for the definition of accept. Glossing over the distinction allows v to forget about old ballots it voted to commit (and hence cannot vote to abort), so long as it accepted an abort message for them. Indeed, the only time v modifies c when c ‘ 0 is to set it back to 0 after accepting abort for every ballot it is voting to commit in step 1 on the preceding page. Conversely, the only time v modifies c when c = 0 is to set it to a value c g b in step 3. Because nodes never vote abort c for any c g b, no past abort votes can conflict with commit c. Theorem 11 requires that nodes rebroadcast what they have accepted. It follows from the definition of prepare that the two highest incompatible ballots a node has accepted as prepared subsume all ballots the node has accepted as prepared. Hence, including p and p¤ in every message ensures that nodes converge on h—a confirmed prepared ballot. Note further that the ballots a node accepts as prepared must be a superset of the ballots the node confirms as prepared; hence, step 2 can never set h such that h ò c ‘ 0, as step 1 will set c } 0 if the new h is incompatible with the old c. At the time v sends an EXTERNALIZE message, it has accepted ^ commit b¤ Ý b¤ À c ‘. More importantly, however, it has confirmed ^ commit b¤ Ý c ¿ b ¤ ¿ h ‘. v can assert its acceptance of confirmed statements without regard to Q.v/, because it has already checked that one of its slices unanimously agrees; this explains the appearance of ^^v‘‘ in place of D for the second implicit CONFIRM message in the description of EXTERNAL
프로젝트로 돌아가기