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