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프로젝트로 돌아가기