«This paper introduces a new model for consensus called federated Byzantine agreement (FBA). FBA achieves robustness through quorum ...»
The Stellar Consensus Protocol:
A Federated Model for Internet-level Consensus
DAVID MAZIERES, 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 transit decisions now unify the Internet.
We also present the Stellar Consensus Protocol (SCP), a construction for FBA. Like all Byzantine agreement 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 membership that promotes organic network growth. Compared to decentralized proof of-work and proof-of-stake schemes, SCP has modest computing and ﬁnancial requirements, lowering the barrier to entry and potentially opening up ﬁnancial 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 ﬁnancial services, leaving billions of people underserved ﬁnancially [Demirguc-Kunt et al. 2015].
To solve these problems, we need ﬁnancial infrastructure that supports the kind of organic growth and innovation we’ve seen from the Internet, yet still ensures the integrity of ﬁnancial transactions. Historically, we have relied on high barriers to entry to ensure integrity. We trust established ﬁnancial institutions and do our best to regulate them. But this exclusivity conﬂicts with the goal of organic growth. Growth demands new, innovative participants, who may possess only modest ﬁnancial and computing resources.
We need a worldwide ﬁnancial network open to anyone, so that new organizations can join and extend ﬁnancial 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 alternative 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 ofothers it considers important. 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 ﬁnancial network. Its decentralized 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. Mazieres 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 ﬁrst provably safe consensus mechanism to enjoy four key properties simultaneously:
— 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 ﬁt. For example, a small non-proﬁt 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 unimaginably vast computing power.
SCP has applications beyond ﬁnancial markets for ensuring organizations perform important functions honestly. An example is certiﬁcate authorities (CAs), who literally hold the keys to the web. Experience shows that CAs sign incorrect certiﬁcates that get used in the wild [Microsoft 2013; Langley 2015]. Several proposals address this problem through certiﬁcate transparency [Kim et al. 2013; Laurie et al. 2013; Basin et al.
2014; Melara et al. 2014]. Certiﬁcate transparency allows users to examine the history of certiﬁcates issued for any given entity and detect attempts by CAs to change an entity’s public key without the endorsement of the previous key. SCP holds the potential to strengthen the indelible certiﬁcate history at the core of certiﬁcate transparency.
Demanding global consensus on certiﬁcate history among a decentralized group of auditors would make it harder to backpedal and override previously issued certiﬁcates.
The next section discusses previous approaches to consensus. Section 3 deﬁnes federated Byzantine agreement (FBA) and lays out notions of safety and liveness applicable 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 deﬁnes 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 [Bonneau 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 Ireland [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
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 disproportionate rewards for those who join them [Eyal and Sirer 2013], thereby potentially gaining majority control. As the leading digital currency backed by the most computational power, Bitcoin enjoys a measure of protection against 51% attacks. Smaller systems 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 penalize bad behavior [Buterin 2014; Davarpanah et al. 2015]. Proof of stake opens the possibility 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 proportion 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; Lamport et al. 1982], the best known variant of which is PBFT [Castro and Liskov 1999].
Byzantine agreement ensures consensus despite arbitrary (including non-rational) behavior on the part of some fraction of participants. This approach has two appealing properties. First, consensus can be fast and efﬁcient. Second, trust is entirely decoupled from resource ownership, which makes it possible for a small non-proﬁt to help keep more powerful organizations, such as banks or CAs, honest. Complicating matters, 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 centralized 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 beneﬁts. One approach, taken by Ripple, is to publish a “starter” membership list that participants can edit for themselves, hoping people’s edits are either inconsequential 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 maintainer 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. Mazieres ownership. SCP is the ﬁrst Byzantine agreement protocol to give each participant maximum freedom in chosing which combinations of other participants to trust.
3. FEDERATED BYZANTINE AGREEMENT SYSTEMSThis section introduces the federated Byzantine agreement (FBA) model. Like nonfederated Byzantine agreement, FBA addresses the problem of updating replicated state, such as a transaction ledger or certiﬁcate 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 can safely apply update in slot when it has safely applied updates in all slots upon which depends and, additionally, it believes all correctly functioning nodes will eventually agree on for slot. At this point, we say has externalized for slot.
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 quorum slices. The next subsection deﬁnes quorums based on slices. The following subsection provides some examples and discussion. Finally, we deﬁne 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.