bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 1쪽
The Stellar Consensus Protocol:
A Federated Model for Internet-level Consensus
DAVID MAZI`ERES, Stellar Development Foundation
This paper introduces a new model for consensus called federated Byzantine agreement (FBA). FBA achieves
robustness through quorum slices—individual trust decisions made by each node that together determine
system-level quorums. Slices bind the system together much the way individual networks’ peering and tran-
sit decisions now unify the Internet.
We also present the Stellar Consensus Protocol (SCP), a construction for FBA. Like all Byzantine agree-
ment protocols, SCP makes no assumptions about the rational behavior of attackers. Unlike prior Byzantine
agreement models, which presuppose a unanimously accepted membership list, SCP enjoys open member-
ship that promotes organic network growth. Compared to decentralized proof of-work and proof-of-stake
schemes, SCP has modest computing and financial requirements, lowering the barrier to entry and poten-
tially opening up financial systems to new participants.
CCS Concepts: Security and privacy Distributed systems security; Security protocols;
Additional Key Words and Phrases: Byzantine fault tolerance, asynchronous systems
1. INTRODUCTION
Financial infrastructure is currently a mess of closed systems. Gaps between these
systems mean that transaction costs are high [Provost 2013] and money moves slowly
across political and geographic boundaries [Banning-Lover 2015; CGAP 2008]. This
friction has curtailed the growth of financial services, leaving billions of people under-
served financially [Demirguc-Kunt et al. 2015].
To solve these problems, we need financial infrastructure that supports the kind of
organic growth and innovation we’ve seen from the Internet, yet still ensures the in-
tegrity of financial transactions. Historically, we have relied on high barriers to entry to
ensure integrity. We trust established financial institutions and do our best to regulate
them. But this exclusivity conflicts with the goal of organic growth. Growth demands
new, innovative participants, who may possess only modest financial and computing
resources.
We need a worldwide financial network open to anyone, so that new organizations
can join and extend financial access to unserved communities. The challenge for such
a network is ensuring participants record transactions correctly. With a low barrier
to entry, users won’t trust providers to police themselves. With worldwide reach,
providers won’t all trust a single entity to operate the network. A compelling alter-
native is a decentralized system in which participants together ensure integrity by
agreeing on the validity of one another’s transactions. Such agreement hinges on a
mechanism for worldwide consensus.
This paper presents federated Byzantine agreement (FBA), a model suitable for
worldwide consensus. In FBA, each participant knows of others it considers impor-
tant. It waits for the vast majority of those others to agree on any transaction before
considering the transaction settled. In turn, those important participants do not agree
to the transaction until the participants they consider important agree as well, and so
on. Eventually, enough of the network accepts a transaction that it becomes infeasible
for an attacker to roll it back. Only then do any participants consider the transaction
settled. FBA’s consensus can ensure the integrity of a financial network. Its decentral-
ized control can spur organic growth.
This paper further presents the Stellar consensus protocol (SCP), a construction for
FBA. We prove that SCP’s safety is optimal for an asynchronous protocol, in that it
guarantees agreement under any node-failure scenario that admits such a guarantee.
Draft of February 25, 2016
2 D. Mazi`eres
We also show that SCP is free from blocked states—in which consensus is no longer
possible—unless participant failures make it impossible to satisfy trust dependencies.
SCP is the first provably safe consensus mechanism to enjoy four key properties simul-
taneously:
— Decentralized control. Anyone is able to participate and no central authority
dictates whose approval is required for consensus.
— Low latency. In practice, nodes can reach consensus at timescales humans expect
for web or payment transactions—i.e., a few seconds at most.
— Flexible trust. Users have the freedom to trust any combination of parties they
see fit. For example, a small non-profit may play a key role in keeping much larger
institutions honest.
— Asymptotic security. Safety rests on digital signatures and hash families whose
parameters can realistically be tuned to protect against adversaries with unimag-
inably vast computing power.
SCP has applications beyond financial markets for ensuring organizations perform
important functions honestly. An example is certificate authorities (CAs), who literally
hold the keys to the web. Experience shows that CAs sign incorrect certificates that get
used in the wild [Microsoft 2013; Langley 2015]. Several proposals address this prob-
lem through certificate transparency [Kim et al. 2013; Laurie et al. 2013; Basin et al.
2014; Melara et al. 2014]. Certificate transparency allows users to examine the history
of certificates issued for any given entity and detect attempts by CAs to change an en-
tity’s public key without the endorsement of the previous key. SCP holds the potential
to strengthen the indelible certificate history at the core of certificate transparency.
Demanding global consensus on certificate history among a decentralized group of au-
ditors would make it harder to backpedal and override previously issued certificates.
The next section discusses previous approaches to consensus. Section 3 defines fed-
erated Byzantine agreement (FBA) and lays out notions of safety and liveness ap-
plicable in the FBA model. Section 4 discusses optimal failure resilience in an FBA
system, thereby establishing the security goals for SCP. Section 5 develops federated
voting, a key building block of the SCP protocol. Section 6 presents SCP itself, proving
safety and freedom from blocked states. Section 7 discusses limitations of SCP. Finally,
Section 8 summarizes results. For readers less familiar with mathematical notation,
Appendix A defines some symbols used throughout the paper.
2. RELATED WORK
Figure 1 summarizes how SCP differs from previous consensus mechanisms. The most
famous decentralized consensus mechanism is the proof-of-work scheme advanced by
Bitcoin [Nakamoto 2008]. Bitcoin takes a two-pronged approach to consensus. First, it
provides incentives for rational actors to behave well. Second, it settles transactions
through a proof-of-work [Dwork and Naor 1992] algorithm designed to protect against
ill-behaved actors who do not possess the majority of the system’s computing power.
Bitcoin has overwhelmingly demonstrated the appeal of decentralized consensus [Bon-
neau et al. 2015].
Proof of work has limitations, however. First, it wastes resources: by one estimate
from 2014, Bitcoin might consume as much electric power as the entire country of Ire-
land [O’Dwyer and Malone 2014]. Second, secure transaction settlement suffers from
expected latencies in the minutes or tens of minutes [Karame et al. 2012]. Finally,
in contrast to traditional cryptographic protocols, proof of work offers no asymptotic
security. Given non-rational attackers—or ones with extrinsic incentives to sabotage
The Stellar Consensus Protocol 3
mechanism
decentralized
control
low
latency
flexible
trust
asymptotic
security
proof of work !
proof of stake ! maybe maybe
Byzantine agreement ! ! !
Tendermint ! ! !
SCP (this work) ! ! ! !
Fig. 1. Properties of different consensus mechanisms
consensus—small computational advantages can invalidate the security assumption,
allowing history to be re-written in so-called “51% attacks.” Worse, attackers initially
controlling less than 50% of computation can game the system to provide dispropor-
tionate rewards for those who join them [Eyal and Sirer 2013], thereby potentially
gaining majority control. As the leading digital currency backed by the most computa-
tional power, Bitcoin enjoys a measure of protection against 51% attacks. Smaller sys-
tems have fallen victim [crazyearner 2013; Bradbury 2013], however, posing a problem
for any proof-of-work system not built on the Bitcoin block chain.
An alternative to proof of work is proof of stake [King and Nadal 2012], in which
consensus depends on parties that have posted collateral. Like proof of work, rewards
encourage rational participants to obey the protocol; some designs additionally penal-
ize bad behavior [Buterin 2014; Davarpanah et al. 2015]. Proof of stake opens the pos-
sibility of so-called “nothing at stake” attacks, in which parties that previously posted
collateral but later cashed it in and spent the money can go back and rewrite history
from a point where they still had stake. To mitigate such attacks, systems effectively
combine proof of stake with proof of work—scaling down the required work in pro-
portion to stake—or delay refunding collateral long enough for some other (sometimes
informal) consensus mechanism to establish an irreversible checkpoint.
Still another approach to consensus is Byzantine agreement [Pease et al. 1980; Lam-
port et al. 1982], the best known variant of which is PBFT [Castro and Liskov 1999].
Byzantine agreement ensures consensus despite arbitrary (including non-rational) be-
havior on the part of some fraction of participants. This approach has two appealing
properties. First, consensus can be fast and efficient. Second, trust is entirely decou-
pled from resource ownership, which makes it possible for a small non-profit to help
keep more powerful organizations, such as banks or CAs, honest. Complicating mat-
ters, however, all parties must agree on the the exact list of participants. Moreover,
attackers must be prevented from joining multiple times and exceeding the system’s
failure tolerance, a so-called Sybil attack [Douceur 2002]. BFT-CUP [Alchieri et al.
2008] accommodates unknown participants, but still presupposes a Sybil-proof cen-
tralized admission-control mechanism.
Generally, membership in Byzantine agreement systems is set by a central authority
or closed negotiation. Prior attempts to decentralize admission have given up some of
the benefits. One approach, taken by Ripple, is to publish a “starter” membership list
that participants can edit for themselves, hoping people’s edits are either inconsequen-
tial or reproduced by an overwhelming fraction of participants. Unfortunately, because
divergent lists invalidate safety guarantees [Schwartz et al. 2014], users are reluctant
to edit the list in practice and a great deal of power ends up concentrated in the main-
tainer of the starter list. Another approach, taken by Tendermint [Kwon 2014], is to
base membership on proof of stake. However, doing so once again ties trust to resource
4 D. Mazi`eres
ownership. SCP is the first Byzantine agreement protocol to give each participant max-
imum freedom in chosing which combinations of other participants to trust.
3. FEDERATED BYZANTINE AGREEMENT SYSTEMS
This section introduces the federated Byzantine agreement (FBA) model. Like non-
federated Byzantine agreement, FBA addresses the problem of updating replicated
state, such as a transaction ledger or certificate tree. By agreeing on what updates to
apply, nodes avoid contradictory, irreconcilable states. We identify each update by a
unique slot from which inter-update dependencies can be inferred. For instance, slots
may be consecutively numbered positions in a sequentially applied log.
An FBA system runs a consensus protocol that ensures nodes agree on slot contents.
A node v can safely apply update x in slot i when it has safely applied updates in all
slots upon which i depends and, additionally, it believes all correctly functioning nodes
will eventually agree on x for slot i. At this point, we say v has externalized x for slot i.
The outside world may react to externalized values in irreversible ways, so a node
cannot later change its mind about them.
A challenge for FBA is that malicious parties can join many times and outnumber
honest nodes. Hence, traditional majority-based quorums do not work. Instead, FBA
determines quorums in a decentralized way, by each node selecting what we call quo-
rum slices. The next subsection defines quorums based on slices. The following subsec-
tion provides some examples and discussion. Finally, we define the key properties of
safety and liveness that a consensus protocol should hope to achieve.
3.1. Quorum slices
In a consensus protocol, nodes exchange messages asserting statements about slots.
We assume such assertions cannot be forged, which can be guaranteed if nodes are
named by public key and they digitally sign messages. When a node hears a sufficient
set of nodes assert a statement, it assumes no functioning node will ever contradict
that statement. We call such a sufficient set a quorum slice, or, more concisely, just a
slice. To permit progress in the face of node failures, a node may have multiple slices,
any one of which is sufficient to convince it of a statement. At a high level, then, an
FBA system consists of a loose confederation of nodes each of which has chosen one or
more slices. More formally:
Definition .FBAS/. A federated Byzantine agreement system, or FBAS, is a pair
ŒV; Qº comprising a set of nodes V and a quorum function Q : V 22V ä ^ç‘ speci-
fying one or more quorum slices for each node, where a node belongs to all of its own
quorum slices—i.e., ¯v ¸ V; ¯q ¸ Q.v/; v ¸ q. (Note 2X denotes the powerset of X.)
Definition .quorum/. A set of nodes U Ó V in FBAS ŒV; Qº is a quorum iff U ç and
U contains a slice for each member—i.e., ¯v ¸ U ;˙q ¸ Q.v/ such that q Ó U .
A quorum is a set of nodes sufficient to reach agreement. A quorum slice is the
subset of a quorum convincing one particular node of agreement. A quorum slice may
be smaller than a quorum. Consider the four-node system in Figure 2, where each node
has a single slice and arrows point to the other members of that slice. Node v1’s slice
^v1; v2; v3‘ is sufficient to convince v1 of a statement. But v2’s and v3’s slices include v4,
meaning neither v2 nor v3 can assert a statement without v4’s agreement. Hence, no
agreement is possible without v4’s participation, and the only quorum including v1 is
the set of all nodes ^v1; v2; v3; v4‘.
Traditional, non-federated Byzantine agreement requires all nodes to accept the
same slices, meaning ¯v1; v2; Q.v1/ = Q.v2/. Because every member accepts every slice,
traditional systems do not distinguish between slices and quorums. The downside is
The Stellar Consensus Protocol 5
v1
v2 v3
v4
Q.v1/ = ^^ v1; v2; v3‘‘
Q.v2/ = Q.v3/ = Q.v4/ =
^^v2; v3; v4‘‘
Fig. 2. v1’s quorum slice is not a quorum without v4.
v1 v2 v3 v4 Top tier: slice is 3 out of^v1; v2; v3; v4‘, including self
v5 v6 v7 v8 Middle tier: slice is self + any2 top tier nodes
v9 v10 Leaf tier: slice is self + any2 middle tier nodes
2/4
2/4
3/4
Fig. 3. Tiered quorum structure example
that membership and quorums must somehow be pre-ordained, precluding open mem-
bership and decentralized control. A traditional system, such as PBFT [Castro and
Liskov 1999], typically has 3f + 1 nodes, any 2f + 1 of which constitute a quorum. Here
f is the maximum number of Byzantine failures—meaning nodes acting arbitrarily—
the system can survive.
FBA, introduced by this paper, generalizes Byzantine agreement to accommodate a
greater range of settings. FBA’s key innovation is enabling each nodev to chose its own
quorum slice set Q.v/. System-wide quorums thus arise from individual decisions made
by each node. Nodes may select slices based on arbitrary criteria such as reputation
or financial arrangements. In some settings, no individual node may have complete
knowledge of all nodes in the system, yet consensus should still be possible.
3.2. Examples and discussion
Figure 3 shows an example of a tiered system in which different nodes have different
slice sets, something possible only with FBA. A top tier, comprising v1; § ; v4, is struc-
tured like a PBFT system with f = 1, meaning it can tolerate one Byzantine failure so
long as the other three nodes are reachable and well-behaved. Nodes v5; § ; v8 consti-
tute a middle tier and depend not on each other, but rather on the top tier. Only two
top tier nodes are required to form a slice for a middle tier node. (The top tier assumes
at most one Byzantine failure, so two top tier nodes cannot both fail unless the whole
system has failed.) Nodes v9 and v10 are in a leaf tier for which a slice consists of any
6 D. Mazi`eres
v1
v2
v3
v4
v5
v6
Q.vi/ = ^vi; v.i mod 6/+1 ‘
Fig. 4. Cyclic quorum structure example
two middle tier nodes. Note that v9 and v10 may pick disjoint slices such as ^v5; v6‘ and
^v7; v8‘; nonetheless, both will indirectly depend on the top tier.
In practice, the top tier could consist of anywhere from four to dozens of widely
known and trusted financial institutions. As the size of the top tier grows, there may
not be exact agreement on its membership, but there will be significant overlap be-
tween most parties’ notions of top tier. Additionally, one can imagine multiple middle
tiers, for instance one for each country or geographic region.
This tiered structure resembles inter-domain network routing. The Internet today
is held together by individual peering and transit relationships between pairs of net-
works. No central authority dictates or arbitrates these arrangements. Yet these pair-
wise relationships have sufficed to create a notion of de facto tier one ISPs [Norton
2010]. Though Internet reachability does suffer from firewalls, transitive reachability
is nearly complete—e.g., a firewall might block The New York Times, but if it allows
Google, and Google can reach The New York Times, then The New York Times is tran-
sitively reachable. Transitive reachability may be of limited utility for web sites, but it
is crucial for consensus; the equivalent example would be Google accepting statements
only if The New York Times does.
If we think of quorum slices as analogous to network reachability and quorums as
analogous to transitive reachability, then the Internet’s near complete transitive reach-
ability suggests we can likewise ensure worldwide consensus with FBA. In many ways,
consensus is an easier problem than inter-domain routing. While transit consumes re-
sources and costs money, slice inclusion merely requires checking digital signatures.
Hence, FBA nodes can err on the side of inclusiveness, constructing conservative slices
with greater interdependence and redundancy than typically seen in peering and tran-
sit arrangements.
Another example not possible with centralized consensus is cyclic dependency struc-
tures, such as the one depicted in Figure 4. Such a cycle is unlikely to arise intention-
ally, but when individual nodes choose their own slices, it is possible for the overall
system to end up embedding dependency cycles. The bigger point is that, compared to
traditional Byzantine agreement, an FBA protocol must cope with a far wider variety
of quorum structures.
3.3. Safety and liveness
We categorize nodes as eitherwell-behaved or ill-behaved. A well-behaved node chooses
sensible quorum slices (discussed further in Section 4.1) and obeys the protocol, includ-
ing eventually responding to all requests. An ill-behaved node does not. Ill-behaved
nodes suffer Byzantine failure, meaning they behave arbitrarily. For instance, an ill-
The Stellar Consensus Protocol 7
Byzantine,
including
crashed
ill-behaved well-behaved
blocked divergent correct
failed
correct
Fig. 5. Venn diagram of node failures
behaved node may be compromised, its owner may have maliciously modified the soft-
ware, or it may have crashed.
The goal of Byzantine agreement is to ensure that well-behaved nodes externalize
the same value프로젝트로 돌아가기