Stellar 백서

Stellar

원문

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