Stellar 백서

Stellar

원문

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

s despite the presence of such ill-behaved nodes. There are two parts to this goal. First, we would like to prevent nodes from diverging and externalizing different values for the same slot. Second, we would like to ensure nodes can actually externalize values, as opposed to getting blocked in some dead-end state from which consensus is no longer possible. We introduce the following two terms for these prop- erties: Definition .safety/. A set of nodes in an FBAS enjoy safety if no two of them ever externalize different values for the same slot. Definition .liveness/. A node in an FBAS enjoys liveness if it can externalize new values without the participation of any failed (including ill-behaved) nodes. We call well-behaved nodes that enjoy both safety and liveness correct. Nodes that are not correct have failed. All ill-behaved nodes have failed, but a well-behaved node can fail, too, by waiting indefinitely for messages from ill-behaved nodes, or, worse, by having its state poisoned by incorrect messages from ill-behaved nodes. Figure 5 illustrates the possible kinds of node failure. To the left are Byzantine failures, meaning the ill-behaved nodes. To the right are two kinds of well-behaved but failed nodes. Nodes that lack liveness are termed blocked, while those that lack safety are termed divergent. An attack violating safety is strictly more powerful than one violating only liveness, so we classify divergent nodes as a subset of blocked ones. Our definition of liveness is weak in that it says a node can externalize new values, not that it will. Hence, it admits a state of perpetual preemption in which consensus remains forever possible, yet the network continually thwarts it by delaying or re- ordering critical messages in just the wrong way. Perpetual preemption is inevitable in a purely asynchronous, deterministic system that survives node failure [Fischer et al. 1985]. Fortunately, preemption is transient. It does not indicate node failure, be- cause the system can recover at any time. Protocols can mitigate the problem through randomness [Ben-Or 1983; Bracha and Toueg 1985] or through realistic assumptions about message latency [Dwork et al. 1988]. Latency assumptions are more practical when one would like to limit execution time or avoid the trusted dealers often re- quired by more efficient Randomized algorithms [ ?]. Of course, only termination and not safety should depend upon message timing. 4. OPTIMAL RESILIENCE Whether or not nodes enjoy safety and liveness depends on several factors: what quo- rum slices they have chosen, which nodes are ill-behaved, and of course the concrete consensus protocol and network behavior. As is common for asynchronous systems, we assume the network eventually delivers messages between well-behaved nodes, but can otherwise arbitrarily delay or reorder messages. 8 D. Mazi`eres v2 v1 v3 Q.v1/ = Q.v2/ = Q.v3/ = ^^v1; v2; v3‘‘ v5 v4 v6 Q.v4/ = Q.v5/ = Q.v6/ = ^^v4; v5; v6‘‘ Fig. 6. FBAS lacking quorum intersection v2 v1 v3 Q.v1/ = Q.v2/ = Q.v3/ = ^^v1; v2; v3; v7‘‘ v5 v4 v6 Q.v4/ = Q.v5/ = Q.v6/ = ^^v4; v5; v6; v7‘‘ v7 Q.v7/ = ^^ v7‘‘ Fig. 7. Ill-behaved node v7 can undermine quorum intersection. This section answers the following question: given a specific ŒV; Qº and particular subset of V that is ill-behaved, what are the best safety and liveness that any feder- ated Byzantine agreement protocol can guarantee regardless of the network? We first discuss quorum intersection, a property without which safety is impossible to guar- antee. We then introduce a notion of dispensable sets—sets of failed nodes in spite of which it is possible to guarantee both safety and liveness. 4.1. Quorum intersection A protocol can guarantee agreement only if the quorum slices represented by function Q satisfy a validity property we call quorum intersection. Definition .quorum intersection/. An FBAS enjoys quorum intersection iff any two of its quorums share a node—i.e., for all quorums U1 and U2, U1 ª U2 ‘ ç. Figure 6 illustrates a system lacking quorum intersection, where Q permits two quo- rums, ^v1; v2; v3‘ and ^v4; v5; v6‘, that do not intersect. Disjoint quorums can indepen- dently agree on contradictory statements, undermining system-wide agreement. When many quorums exist, quorum intersection fails if any two do not intersect. For exam- ple, the set of all nodes^v1; § ; v6‘ in Figure 6 is a quorum that intersects the other two, but the system still lacks quorum intersection because the other two do not intersect each other. No protocol can guarantee safety in the absence of quorum intersection, since such a configuration can operate as two different FBAS systems that do not exchange any messages. However, even with quorum intersection, safety may be impossible to guar- antee in the presence of ill-behaved nodes. Compare Figure 6, in which there are two disjoint quorums, to Figure 7, in which two quorums intersect at a single node v7, and v7 is ill-behaved. If v7 makes inconsistent statements to the left and right quorums, the effect is equivalent to disjoint quorums. In fact, since ill-behaved nodes contribute nothing to safety, no protocol can guaran- tee safety without the well-behaved nodes enjoying quorum intersection on their own. After all, in a worst-case scenario for safety, ill-behaved nodes can just always make any possible (contradictory) statement that completes a quorum. Two quorums over- lapping only at ill-behaved nodes will again be able to operate like two different FBAS The Stellar Consensus Protocol 9 systems thanks to the duplicity of the ill-behaved nodes. In short, FBAS ŒV; Qº can survive Byzantine failure by a set of nodes B Ó V iff ŒV; Qº enjoys quorum intersection after deleting the nodes in B from V and from all slices in Q. More formally: Definition .delete/. If ŒV; Qº is an FBAS and B Ó V is a set of nodes, then to delete B from ŒV; Qº, written ŒV; QºB, means to compute the modified FBAS ŒV ä B; QBº where QB.v/ = ^ q ä B Ý q ¸ Q.v/ ‘. It is the responsibility of each node v to ensure Q.v/ does not violate quorum inter- section. One way to do so is to pick conservative slices that lead to large quorums. Of course, a malicious v may intentionally pick Q.v/ to violate quorum intersection. But a malicious v can also lie about the value of Q.v/ or ignore Q.v/ to make arbitrary as- sertions. In short, Q.v/’s value is not meaningful when v is ill-behaved. This is why the necessary property for safety—quorum intersection of well-behaved nodes after deleting ill-behaved nodes—is unaffected by the slices of ill-behaved nodes. Suppose Figure 6 evolved from a three-node FBASv1; v2; v3 with quorum intersection to a six-node FBAS without. When v4; v5; v6 join, they maliciously choose slices that violate quorum intersection and no protocol can guarantee safety for V. Fortunately, deleting the bad nodes to yield ŒV; Qº^v4;v5;v6‘ restores quorum intersection, meaning at least ^v1; v2; v3‘ can enjoy safety. Note that deletion is conceptual, for the sake of describing optimal safety. A protocol should guarantee safety forv1; v2; v3 without their needing to know that v4; v5; v6 are ill-behaved. 4.2. Dispensable sets (DSets) We capture the fault tolerance of nodes’ slice selections through the notion of a dis- pensible set or DSet. Informally, the safety and liveness of nodes outside a DSet can be guaranteed regardless of the behavior of nodes inside the DSet. Put another way, in an optimally resilient FBAS, if a single DSet encompasses every ill-behaved node, it also contains every failed node, and conversely all nodes outside the DSet are correct. As an example, in a centralized PBFT system with 3f + 1 nodes and quorum size 2f + 1, any f or fewer nodes constitute a DSet. Since PBFT in fact survives up tof Byzantine failures, its robustness is optimal. In the less regular example of Figure 3, ^v1‘ is a DSet, since one top tier node can fail without affecting the rest of the system. ^v9‘ is also a DSet because no other node depends on v9 for correctness. ^v6; § ; v10‘ is a DSet, because neither v5 nor the top tier depend on any of those five nodes. ^v5; v6‘ is not a DSet, as it is a slice for v9 and v10 and hence, if entirely malicious, can lie to v9 and v10 and convince them of assertions inconsistent with each other or the rest of the system. To prevent a misbehaving DSet from affecting the correctness of other nodes, two properties must hold. For safety, deleting the DSet cannot undermine quorum inter- section. For liveness, the DSet cannot deny other nodes a functioning quorum. This leads to the following definition: Definition .DSet/. Let ŒV; Qº be an FBAS and B Ó V be a set of nodes. We say B is a dispensible set, or DSet, iff: (1) (quorum intersection despite B) ŒV; QºB enjoys quorum intersection, and (2) (quorum availability despite B) Either V ä B is a quorum in ŒV; Qº or B = V. Quorum availability despite B protects against nodes in B refusing to answer re- quests and blocking other nodes’ progress. Quorum intersection despite B protects against the opposite—nodes in B making contradictory assertions that enable other nodes to externalize inconsistent values for the same slot. Nodes must balance the two threats in slice selection. All else equal, bigger slices lead to bigger quorums with 10 D. Mazi`eres well-behaved / ill-behaved Local property of nodes, independent of other nodes (except for the validity of slice selection). intact / befouled Property of nodes given their quorum slices and a particular set of ill-behaved nodes. Befouled nodes are ill-behaved or depend, possibly indirectly, on too many ill-behaved nodes. correct / failed Property of nodes given their quorum slices, a concrete protocol, and actual network behavior. The goal of a consensus protocol is to guarantee correctness for all intact nodes. Fig. 8. Key properties of FBAS nodes greater overlap, meaning fewer failed node setsB will undermine quorum intersection when deleted. On the other hand, bigger slices are more likely to contain failed nodes, endangering quorum availability. The smallest DSet containing all ill-behaved nodes may encompass well-behaved nodes as well, reflecting the fact that a sufficiently large set of ill-behaved nodes can cause well-behaved nodes to fail. For instance, in Figure 3, the smallest DSet contain- ing v5 and v6 is ^v5; v6; v9; v10‘. The set of all nodes, V, is always a DSet, as an FBAS ŒV; Qº vacuously enjoys quorum intersection despite V and, by special case, also enjoys quorum availability despite V. The motivation for the special case is that given suffi- ciently many ill-behaved nodes, V may be the smallest DSet to contain all ill-behaved ones, indicating a scenario under which no protocol can guarantee anything better than complete system failure. The DSets in an FBAS are determined a priori by the quorum function Q. Which nodes are well- and ill-behaved depends on runtime behavior, such as machines getting compromised. The DSets we care about are those that encompass all ill-behaved nodes, as they help us distinguish nodes that should be guaranteed correct from ones for which such a guarantee is impossible. To this end, we introduce the following terms: Definition .intact/. A node v in an FBAS isintact iff there exists a DSetB containing all ill-behaved nodes and such that v Ì B. Definition .befouled/. A node v in an FBAS is befouled iff it is not intact. A befouled node v is surrounded by enough failed nodes to block its progress or poi- son its state, even ifv itself is well-behaved. No FBAS can guarantee the correctness of a befouled node. However, an optimal FBAS guarantees that every intact node remains correct. Figure 8 summarizes the key properties of nodes. The following theorems fa- cilitate analysis by showing that the set of befouled nodes is always a DSet in an FBAS with quorum intersection. THEOREM 1. Let U be a quorum in FBAS ŒV; Qº, let B Ó V be a set of nodes, and let U ¤ = U ä B. If U ¤ ‘ ç then U ¤ is a quorum in ŒV; QºB. PROOF. Because U is a quorum, every node v ¸ U has a q ¸ Q.v/ such that q Ó U . Since U ¤ Ó U , it follows that every v ¸ U ¤ has a q ¸ Q.v/ such that q ä B Ó U ¤. Rewriting with deletion notation yields ¯v ¸ U ¤; ˙q ¸ QB.v/ such that q Ó U ¤, which, because U ¤ Ó V ä B, means that U ¤ is a quorum in ŒV; QºB. THEOREM 2. If B1 and B2 are DSets in an FBAS ŒV; Qº enjoying quorum intersec- tion, then B = B1 ª B2 is a DSet, too. PROOF. Let U1 = V ä B1 and U2 = V ä B2. If U1 = ç, then B1 = V and B = B2 (a DSet), so we are done. Similarly, if U2 = ç , then B = B1, and we are done. Otherwise, note The Stellar Consensus Protocol 11 that by quorum availability despite DSets B1 and B2, U1 and U2 are quorums inŒV; Qº. It follows from the definition that the union of two quorums is also a quorum. Hence V ä B = U1 ä U2 is a quorum and we have quorum availability despite B. We must now show quorum intersection despite B. Let Ua and Ub be any two quorums in ŒV; QºB. Let U = U1 ª U2 = U2 ä B1. By quorum intersection of ŒV; Qº, U = U1 ª U2 ‘ ç. But then by Theorem 1, U = U2 ä B1 must be a quorum in ŒV; QºB1. Now consider that Ua ä B1 and Ua ä B2 cannot both be empty, or else Ua ä B = Ua would be. Hence, by Theorem 1, eitherUa ä B1 is a quorum inŒV; QºBB1 = ŒV; QºB1, or Ua ä B2 is a quorum inŒV; QºBB2 = ŒV; QºB2, or both. In the former case, note that ifUa ä B1 is a quorum in ŒV; QºB1, then by quorum intersection of ŒV; QºB1, .Ua ä B1/ ª U ‘ ç; since .Ua ä B1/ ª U = . Ua ä B1/ ä B2, it follows that Ua ä B2 ‘ ç, making Ua ä B2 a quorum in ŒV; QºB2. By a similar argument, Ub ä B2 must be a quorum in ŒV; QºB2. But then quo- rum intersection despite B2 tells us that .Ua ä B2/ ª .Ub ä B2/ ‘ ç, which is only possible if Ua ª Ub ‘ ç. THEOREM 3. In an FBAS with quorum intersection, the set of befouled nodes is a DSet. PROOF. Let Bmin be the intersection of every DSet that contains all ill-behaved nodes. It follows from the definition of intact that a node v is intact iff v Ì Bmin. Thus, Bmin is precisely the set of befouled nodes. By Theorem 2, DSets are closed under in- tersection, so Bmin is also a DSet. 5. FEDERATED VOTING This section develops a federated voting technique that FBAS nodes can use to agree on a statement. At a high level, the process for agreeing on some statement a involves nodes exchanging two sets of messages. First, nodes vote for a. Then, if the vote was successful, nodes confirm a, effectively holding a second vote on the fact that the first vote succeeded. From each node’s perspective, the two rounds of messages divide agreement on a statement a into three phases: unknown, accepted, and confirmed. (This pattern dates back to three-phase commit [Skeen and Stonebraker 1983].) Initially,a’s status is com- pletely unknown to a node v—a could end up true, false, or evenstuck in a permanently indeterminate state. If the first vote succeeds, v may come to accept a. No two intact nodes ever accept contradictory statements, so ifv is intact and acceptsa, then a cannot be false. For two reasons, however, v accepting a does not suffice for v to act on a. First, the fact that v accepted a does not mean all intact nodes can; a could be stuck for other nodes. Second, if v is befouled, then accepting a means nothing— a may be false at intact nodes. Yet even if v is befouled—which v does not know—the system may still enjoy quorum intersection of well-behaved nodes, in which case, for optimal safety, v needs greater assurance of a. Holding a second vote addresses both problems. If the second vote succeeds, v moves to the confirmed phase in which it can finally deem a true and act on it. The next few subsections detail the federated voting process. Because voting does not rule out the possibility of stuck statements, Section 5.6 discusses how to cope with them. Section 6 will turn federated voting into a consensus protocol that avoids the possibility of stuck slots for intact nodes. 12 D. Mazi`eres 5.1. Voting with open membership A correct node in a Byzantine agreement system acts on a statement a only when it knows that other correct nodes will never agree to statements contradicting a. Most protocols employ voting for this purpose. Well-behaved nodes vote for a statement a only if it is valid. Well-behaved nodes also never change their votes. Hence, in central- ized Byzantine agreement, it is safe to accept a if a quorum comprising a majority of well-behaved nodes has voted for it. We say a statement isratified once it has received the necessary votes. In a federated setting, we must adapt voting to accommodate open membership. One difference is that a quorum no longer corresponds to a majority of well-behaved nodes. However, the majority requirement primarily serves to ensure quorum intersection of well-behaved nodes, which Section 4.1 already adapted to FBA. Another implication of open membership is that nodes must discover what constitutes a quorum as part of the voting process. To implement quorum discovery, a protocol should specify Q.v/ in all messages from v. Definition .vote/. A node v votes for an (abstract) statement a iff (1) v asserts a is valid and consistent with all statements v has accepted, and (2) v asserts it has never voted against a—i.e., voted for a statement that contra- dicts a—and v promises never to vote against a in the future. Definition .ratify/. A quorum Ua ratifies a statement a iff every member of Ua votes for a. A node v ratifies a iff v is a member of a quorum Ua that ratifies a. THEOREM 4. Two contradictory statements a and „ acannot both be ratified in an FBAS that enjoys quorum intersection and contains no ill-behaved nodes. PROOF. By contradiction. Suppose quorum U1 ratifies a and quorum U2 ratifies „ a. By quorum intersection, ˙v ¸ U1 ª U2. Such a v must have illegally voted for both a and „ a, violating the assumption of no ill-behaved nodes. THEOREM 5. 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 ratifies a then v2 cannot ratify „ a. PROOF. By contradiction. Suppose v1 ratifies a and v2 ratifies „ a. By definition, there must exist a quorum U1 containing v1 that ratified a and quorum U2 containing v2 that ratified „ a. By Theorem 1, since U1 ä B ‘ ç and U2 ä B ‘ ç, both must be quorums in ŒV; QºB, meaning they ratified a and „ arespectively in ŒV; QºB. But ŒV; QºB enjoys quorum intersection and has no ill-behaved nodes, so Theorem 4 tell usa and „ acannot both be ratified. THEOREM 6. Two intact nodes in an FBAS with quorum intersection cannot ratify contradictory statements. PROOF. Let B be the set of befouled nodes. By Theorem 3, B is a DSet. By the defi- nition of DSet, ŒV; Qº enjoys quorum intersection despite B. By Theorem 5, two nodes not in B cannot ratify contradictory statements. 5.2. Blocking sets In centralized consensus, liveness is an all-or-nothing property of the system. Either a unanimously well-behaved quorum exists, or else ill-behaved nodes can prevent the rest of the system from accepting new statements. In FBA, by contrast, liveness may differ across nodes. For instance, in the tiered quorum example of Figure 3, if middle The Stellar Consensus Protocol 13 v1 vote a accept v2 vote a accept v3 vote a accept v4 vote „ a 3/4 Slice is 3 nodes,including self Fig. 9. v4 voted for „ a, which contradicts ratified statement a. tier nodes v6; v7; v8 crash, the leaf tier will be blocked while the top tier and node v5 will continue to enjoy liveness. An FBA protocol can guarantee liveness to a node v only if Q.v/ contains at least one quorum slice comprising only correct nodes. A setB of failed nodes can violate this property if B contains at least one member of each of v’s slices. We term such a set B v-blocking, because it has the power to block progress by v. Definition .v-blocking/. Let v ¸ V be a node in FBASŒV; Qº. A set B Ó V is v-blocking iff it overlaps every one of v’s slices—i.e.,
프로젝트로 돌아가기