Stellar 백서

Stellar

원문

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

¯q ¸ Q.v/; q ª B ‘ ç. THEOREM 7. Let B Ó V be a set of nodes in FBAS ŒV; Qº. ŒV; Qº enjoys quorum availability despite B iff B is not v-blocking for any v ¸ V ä B. PROOF. “ ¯v ¸ V ä B; B is not v-blocking” is equivalent to “¯v ¸ V ä B; ˙q ¸ Q.v/ such that q Ó V ä B.” By the definition of quorum, the latter holds iff V ä B is a quorum or B = V, the exact definition of quorum availability despite B. As a corollary, the DSet of befouled nodes is not v-blocking for any intact v. 5.3. Accepting statements When an intact node v learns that it has ratified a statement, Theorem 6 tells v that other intact nodes will not ratify contradictory statements. This condition is sufficient for v to accept a, but we cannot make it necessary. Ratifying a statement requires vot- ing for it, and some nodes may have voted for contradictory statements. In Figure 9, for example, v4 votes for „ abefore learning that the other three nodes ratified the contra- dictory statement a. Though v4 cannot now vote for a, we would still like it to accept a to be consistent with the other nodes. A key insight is that if a nodev is intact, then no v-blocking set B can consist entirely of befouled nodes. Now suppose B is a v-blocking set and every member of B claims to accept statement a. If v is intact, at least one member of B must be, too. The intact member will not lie about accepting a; hence, a is true and v can accept it. Of course, if v is befouled, then a might not be true. But a befouled node can accept anything and vacuously not affect the correctness of intact nodes. Definition .accept/. An FBAS node v accepts a statement a iff it has never accepted a statement contradicting a and it determines that either (1) There exists a quorum U such that v ¸ U and each member of U either voted for a or claims to accept a, or (2) Each member of a v-blocking set claims to accept a. Though a well-behaved node cannot vote for contradictory statements, condition 2 above allows a node to vote for one statement and later accept a contradictory one. 14 D. Mazi`eres v1 vote a accept v2 vote a v4 vote „ a v3 vote a 3/4 Slice is 3 nodes,including self a) v2 vote a v3 vote „a accept v4 vote „ a v1 vote a vote „a 3/4 b) Fig. 10. Scenarios indistinguishable to v2 when v2 does not see bold messages THEOREM 8. Two intact nodes in an FBAS that enjoys quorum intersection cannot accept contradictory statements. PROOF. Let ŒV; Qº be an FBAS with quorum intersection and letB be its DSet of be- fouled nodes (which exists by Theorem 3). Suppose an intact node accepts statementa. Let v be the first intact node to accept a. At the point v accepts a, only befouled nodes in B can claim to accept it. Since by the corollary to Theorem 7,B cannot be v-blocking, it must be that v accepted a through condition 1. Thus, v identified a quorum U such that every node claimed to vote for or accepta, and since v is the first intact node to ac- cept a, it must mean all nodes inU äB voted for a. In other words,v ratified a inŒV; QºB. Generalizing, any statement accepted by an intact node in ŒV; Qº must be ratified in ŒV; QºB. Because B is a DSet, ŒV; QºB enjoys quorum intersection. Because addition- ally B contains all ill-behaved nodes, Theorem 4 rules out ratification of contradictory statements. 5.4. Accepting is not enough Unfortunately, for nodes to assume the truth of accepted statements would yield sub- optimal safety and liveness guarantees in a federated consensus protocol. We discuss the issues with safety and liveness in turn. To provide some context, we then explain why these issues are thornier in FBA than in centralized Byzantine agreement. 5.4.1. Safety. Consider an FBAS ŒV; Qº in which the only quorum is unanimous consent—i.e., ¯v; Q.v/ = ^ V‘. This ought to be a conservative choice for safety—don’t do anything unless everyone agrees. Yet since every node isv-blocking for every v, any node can single-handedly convince any other node to accept arbitrary statements. The problem is that accepted statements are only safe among intact nodes. But as discussed in Section 4.1, the only condition necessary to guarantee safety is quorum intersection of well-behaved nodes, which might hold even in the case that some well- behaved nodes are befouled. In particular, whenQ.v/ = ^ V‘, the only DSets areç and V, meaning any node failure befouls the whole system. By contrast, quorum intersection holds despite every B Ó V. 5.4.2. Liveness. Another limitation of accepted statements is that other intact nodes may be unable to accept them. This possibility makes reliance on accepted statements The Stellar Consensus Protocol 15 problematic for liveness. If a node proceeds to act on a statement because it accepted the statement, other nodes could be unable to proceed in a similar fashion. Consider Figure 10a, in which node v3 crashes after helping v1 ratify and accept statement a. Though v1 accepts a, v2 and v4 cannot. In particular, fromv2’s perspective, the situation depicted is indistinguishable from Figure 10b, in whichv3 voted for „ aand is well-behaved but slow to respond, while v1 is ill-behaved and sent v3 a vote for „ a (thereby causing v3 to accept „ a) while illegally also sending v2 a vote for a. To support a protocol-level notion of liveness in cases like Figure 10a,v1 needs a way to ensure every other intact node can eventually accept a before v1 acts on a. Once this is the case, it makes sense to say the system agrees on a. Definition .agree/. An FBAS ŒV; Qº agrees on a statement a iff, regardless of what subsequently transpires, once sufficient messages are delivered and processed, every intact node will accept a. 5.4.3. Comparison to centralized voting. To understand why the above issues arise in fed- erated voting, consider a centralized Byzantine agreement system of N nodes with quorum size T . Such a system enjoys quorum availability with fL = N * T or fewer node failures. Since any two quorums share at least2T * N nodes, quorum intersection of well-behaved nodes holds up to fS = 2T * N * 1 Byzantine failures. Centralized Byzantine agreement systems typically set N = 3 f + 1 and T = 2 f + 1 to yield fL = fS = f, the equilibrium point at which safety and liveness have the same fault tolerance. If safety is more important than liveness, some protocols increase T so that fS > f L [Li and Mazi `eres 2007]. In FBA, because quorums arise organically, systems are unlikely to find themselves at equilibrium, making it far more important to protect safety in the absence of liveness. Now consider a centralized system in which, because of node failure and contradic- tory votes, some node v cannot ratify statement a that was ratified by other nodes. If v hears fS + 1 nodes claim a was ratified, v knows that either one of them is well- behaved or all safety guarantees have collapsed. Either way,v can act on a with no loss of safety. The FBA equivalent would be to hear from a set B where B, if deleted, un- dermines quorum intersection of well-behaved nodes. Identifying such a B is hard for three reasons: one, quorums are discovered dynamically; two, ill-behaved nodes may lie about slices; and three, v does not know which nodes are well-behaved. Instead, we defined federated voting to accept a when a v-blocking set does. The v-blocking prop- erty has the advantage of being easily checkable, but is equivalent to hearing from fL + 1 nodes in a centralized system when we really want fS + 1. To guarantee agreement among all well-behaved nodes in a centralized system, one merely needs fL + fS + 1 nodes to acknowledge that a statement was ratified. If more than fL of them fail, we do not expect liveness anyway. If fL or fewer fail, then we know fS + 1 nodes remain willing to attest to ratification, which will in turn convince all other well-behaved nodes. The reliance on fS has no easy analogue in the FBA model. Interestingly, however, fL + fS + 1 = T , the quorum size, suggesting a similar approach might work with a more complex justification. Put another way, at some point nodes need to believe a statement strongly enough to depend on its truth for safety. A centralized system offers two ways to reach this point for a statement a: ratify a first-hand, or reason backwards from fS + 1 nodes claiming a was ratified, figuring safety is hopeless if they have all lied. FBA lacks the latter approach; the only tool it has for safety among well-behaved nodes is first-hand ratification. Since nodes still need a way to overcome votes against ratified statements, we introduced a notion of accepting, but it provides a weaker consistency guarantee limited to intact nodes. 16 D. Mazi`eres 5.5. Statement confirmation Both limitations of accepted statements stem from complications when a set of intact nodes S votes against a statement a that is nonetheless ratified. Particularly in light of FBA’s non-uniform quorums, S may prevent some intact node from ever ratifying v. To provide v a means of accepting a despite votes against it, the definition ofaccept has a second criterion based on v-blocking sets. But the second criterion is weaker than ratification, offering no guarantees to befouled nodes that enjoy quorum intersection. Now suppose a statement a has the property that no intact node ever votes against it. Then we have no need to accept a and can instead insist that nodes directly ratify a before acting on it. We call such statements irrefutable. Definition .irrefutable/. A statement a is irrefutable in an FBAS if no intact node can ever vote against it. Theorem 8 tells us that two intact nodes cannot accept contradictory statements. Thus, while some intact nodes may vote against a statement a that was accepted by an intact node, the statement “an intact node accepted a” is irrefutable. This suggests holding a second vote to ratify the fact that an intact node accepted a. Definition .confirm/. A quorum Ua in an FBAS confirms a statement a iff ¯v ¸ Ua, v claims to accept a. A node confirms a iff it is in such a quorum. Nodes express that they have accepted statement a by stating “ accept .a/,” an ab- breviation of the statement, “An intact node accepted a.” To confirm a means to ratify accept .a/. A well-behaved node v can vote for accept .a/ only after accepting a, as v cannot assume any particular other nodes are intact. If v itself is befouled, accept .a/ might be false, in which case voting for it may cost v liveness, but a befouled node has no guarantee of liveness anyway. The next theorem shows that nodes can rely on confirmed statements without losing optimal safety. Theorem 11 then shows that confirmed statements meet the defini- tion of agreement from Section 5.4.2, meaning nodes can rely on confirmed statements without endangering the liveness of intact nodes. THEOREM 9. Let ŒV; Qº be an FBAS enjoying quorum intersection despite B, and suppose B contains all ill-behaved nodes. Let v1 and v2 be two nodes not in B. Let a and „ abe contradictory statements. If v1 confirms a, then v2 cannot confirm „ a. PROOF. First note that accept .a/ contradicts accept . „ a/—no well-behaved node can vote for both. Note further that v1 must ratify accept .a/ to confirm a. By Theorem 5, v2 cannot ratify accept . „ a/ and hence cannot confirm „ a. THEOREM 10. Let B be the set of befouled nodes in an FBAS ŒV; Qº with quorum intersection. Let U be a quorum containing an intact node (U Õ B ), and let S be any set such that U Ó S Ó V. Let S+ = S äB be the set of intact nodes inS, and let S* = .VäS/äB be the set of intact nodes not in S. Either S* = ç, or ˙v ¸ S* such that S+ is v-blocking. PROOF. If S+ is v-blocking for some v ¸ S*, then we are done. Otherwise, we must show S* = ç. If S+ is not v-blocking for any v ¸ S*, then, by Theorem 7, either S* = ç or S* is a quorum in ŒV; QºB. In the former case we are done, while in the latter we get a contradiction: By Theorem 1, U ä B is a quorum in ŒV; QºB. Since B is a DSet (by Theorem 3),ŒV; QºB must enjoy quorum intersection, meaning S* ª .U ä B/ ‘ ç. This is impossible, since .U ä B/ Ó S and S* ª S = ç. THEOREM 11. If an intact node in an FBAS ŒV; Qº with quorum intersection con- firms a statement a, then, whatever subsequently transpires, once sufficient messages are delivered and processed, every intact node will accept and confirm a. The Stellar Consensus Protocol 17 quorum satisfying v each votes or accepts a quorum satisfying v confirms a a is valid v-blocking set accepts a uncommitted voted a accepted a confirmed a voted „ a Fig. 11. Possible states of an accepted statement a at a single node v bivalent a-valent „ a-valent stuck a agreed „ aagreed Fig. 12. Possible system-wide status of a statement a PROOF. Let B be the DSet of befouled nodes and let U Õ B be the quorum through which an intact node confirmeda. Let nodes in U äB broadcast accept .a/. By definition, any node v, regardless of how it has voted, accepts a after receiving accept .a/ from a v-blocking set. Hence, these messages may convince additional nodes to accept a. Let these additional nodes in turn broadcast accept .a/ until a point is reached at which, regardless of future communication, no further intact nodes can ever accept a. At this point let S be the set of nodes that claim to accept a (where U Ó S ), let S+ be the set of intact nodes in S, and let S* be the set of intact nodes not inS. S+ cannot be v-blocking for any node in S*, or else more nodes could come to accept a. By Theorem 10, then, S* = ç, meaning every intact node has accepted a. Figure 11 summarizes the paths an intact node v can take to confirm a. Given no knowledge, v might vote for either a or the contradictory „ a. If v votes for „ a, it cannot later vote for a, but can nonetheless accepta if a v-blocking set accepts it. A subsequent quorum of confirmation messages allows v to confirm a, which by Theorem 11 means the system agrees on a. 5.6. Liveness and neutralization The main challenge of distributed consensus, whether centralized or not, is that a statement can get stuck in a permanently indeterminate state before the system reaches agreement on it. Hence, a protocol must not attempt to ratify externalized values directly. Should the statement “The value of slot i is x” get stuck, the system will be forever unable to agree on slot i, losing liveness. The solution is to craft the statements in votes carefully. It must be possible to break a stuck statement’s hold on the question we really care about, namely slot contents. We call the process of obsolet- ing a stuck statement neutralization. 18 D. Mazi`eres Local state System-wide status of a uncommitted unknown (any) voted a unknown (any) voted „ a unknown (any) accepted a stuck, a-valent, or a agreed confirmed a a agreed Fig. 13. What an intact node knows about the status of statement a More concretely, Figure 12 depicts the potential status a statement a can have system-wide. Initially, the system isbivalent, by which we mean there is one sequence of possible events through which all intact nodes will accept a, and another sequence through which all intact nodes will reject a (i.e., accept a statement „ acontradicting a). At some point, one of these two outcomes may cease to be possible. If no intact node can ever reject a, we say the system is a-valent; conversely, if no intact node can ever accept a, we say the system is „ a-valent. At the time an FBAS transitions from bivalent to a-valent, there is a possible out- come in which all intact nodes accept a. However, this might not remain the case. Consider a PBFT-like four-node system^v1; § ; v4‘ in which any three nodes constitute a quorum. If v1 and v2 vote for a, the system becomes a-valent; no three nodes can ratify a contradictory statement. However, if v3 and v4 subsequently vote for „ acontra- dicting a, it also becomes impossible to ratify a. In this case, a’s state is permanently indeterminate, or stuck. As seen in Figure 10a, even once an intact node accepts a, the system may still fail to reach system-wide agreement on a. However, by Theorem 11, once an intact node confirms a, all intact nodes can eventually come to accept it; hence the system has agreed upon a. Figure 13 summarizes what intact nodes know about the global state of a statement from their own local state. To preserve the possibility of consensus, a protocol must ensure that every statement is either irrefutable, and hence cannot get stuck, or neutralizable, and hence cannot block progress if stuck. There are two popular approaches to crafting neutralizable statements: the view-based approach, pioneered by viewstamped replication [Oki and Liskov 1988] and favored by PBFT [Castro and Liskov 1999]; and the ballot-based ap- proach, invented by Paxos [Lamport 1998]. The ballot-based approach may be harder to understand [Ongaro and Ousterhout 2014]. Compounding confusion, people often call viewstamped replication “Paxos” or assert that the two algorithms are the same when they are not [van Renesse et al. 2014]. View-based protocols associate the slots in votes with monotonically increasing view numbers. Should consensus get stuck on the ith slot in view n, nodes recover by agree- ing that view n had fewer than i meaningful slots and moving to a higher view number. Ballot-based protocols associate the values in votes with monotonically increasing bal- lot numbers. Should a ballot get stuck, nodes retry the same slot with a higher ballot, taking care never to select values that would contradict prior stuck ballots. This work takes a ballot-based approach, as doing so makes it easier to do away with the notion of a distinguished primary node or leader. For example, leader behavior can be emulated [Lamport 2011b]. 6. SCP: A FEDERATED BYZANTINE AGREEMENT PROTOCOL This section presents the Stellar Consensus Protocol, SCP. At a high level, SCP con- sists of two sub-protocols: a nomination protocol and a ballot protocol. The nomination The Stellar 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 a finite 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 and ballots 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 partiall
프로젝트로 돌아가기