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