WWW.BOOK.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Books, dissertations, abstract
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |

«This paper introduces a new model for consensus called federated Byzantine agreement (FBA). FBA achieves robustness through quorum ...»

-- [ Page 1 ] --

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 financial requirements, lowering the barrier to entry and potentially 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 underserved 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 integrity 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 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 financial 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 first 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 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 unimaginably 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 problem 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 entity’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 auditors would make it harder to backpedal and override previously issued certificates.

The next section discusses previous approaches to consensus. Section 3 defines 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 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 [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 efficient. Second, trust is entirely decoupled 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 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 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 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 first Byzantine agreement protocol to give each participant maximum 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 nonfederated 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 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 defines quorums based on slices. The following subsection 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.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |


Similar works:

«Articulating Wind Turbine A Major Qualifying Project to be submitted to the Faculty of Worcester Polytechnic Institute in partial fulfillment of the requirements for the degree of Bachelor of Science Submitted by: Morgan Boyd Matthew Jackson Anne Cecilie Jacobsen Jason Lackie Patrick Rosica Submitted to: Project Advisors: Brian Savilonis, Worcester Polytechnic Institute April 30, 2015 This report represents work of WPI undergraduate students submitted to the faculty as evidence of a degree...»

«Magellan Wine Imports, Inc.RATINGS FROM THE WINE PRESS Clüsserath-Weiler (Germany, Mosel-Saar-Ruwer) 94 points 2007 Trittenheimer Apotheke Riesling Auslese* Wine Spectator 93 points – 2007 Trittenheimer Apotheke Riesling Spatlese – Wine Spectator 92 points – 2007 Trittenheimer Apotheke Riesling Spatlese – Wine Enthusiast 92 points 2007 Fahrfels Riesling – Wine Advocate 92 points 2007 Trittenheimer Apotheke Riesling Auslese 2 Star – Wine Advocate 90 points 2007 Mehringer Zellerberg...»

«INTERNATIONAL LABOUR OFFICE Governing Body GB.316/INS/9/1 316th Session, Geneva, 1–16 November 2012 INS Institutional Section NINTH ITEM ON THE AGENDA Reports of the Committee on Freedom of Association 365th Report of the Committee on Freedom of Association Contents Paragraphs Introduction Case No. 2861 (Argentina): Report in which the Committee requests to be kept informed of developments Complaint against the Government of Argentina presented by the Confederation of Education Workers of...»

«STAND-ALONE PROJECT FINAL REPORT Project number P23690-B13 Project title1 Transkriptionsfaktoren bei Entzündung und Krebs (Transcription factors in inflammation and cancer) Project leader Johannes A. Schmid Project website2 http://www.meduniwien.ac.at/user/johannes.schmid/FWF-Project1/index.html 1 Short title in English and German language 2 Projects that started after January 1, 2009 are encouraged to have a website. Part I: 1. Zusammenfassung für die Öffentlichkeitsarbeit Das Projekt...»

«From Proceedingsof the IFIP Conference on Data Semantics, October 1997 Incorporating generalized quantifiers into description logic for representing data source contents Steven Yi-cheng Tu and Stuart E. Madnick Sloan WP #3998 CISL WP #98-01 January 1998 The Sloan School of Management Massachusetts Institute of Technology Cambridge, MA 02142 Incorporating generalized quantifiers into description logic for representing data source contents S. Y Tu andS. Madnick Context InterchangeSystems...»

«Concept Maps & E-Learning Autor: Sigmar-Olaf Tergan Portalbereich: Didaktisches Design Stand: 11.08.2005 Inhaltsverzeichnis 1 Einleitung 2 Was sind Concept Maps? 3 Ein Wissensmanagement-Szenario 4 Concept Mapping Tools 5 Erfahrungen und Perspektiven 6 Glossar 7 Literatur 1 Einleitung.. Im Rahmen virtueller Lehrszenarien werden digitale Medien genutzt, um Informationen verfügbar zu machen, die Kooperation zwischen Lernenden zu erleichtern und durch Kommunikation zwischen Lehrenden und...»

«Institut für Ethnologie und Afrikastudien Department of Anthropology and African Studies Arbeitspapiere / Working Papers Nr. 33 Katja Werthmann A Field Full of Researchers. Fieldwork as a Collective Experience The Working Papers are edited by Institut für Ethnologie und Afrikastudien, Johannes Gutenberg-Universität, Forum 6, D-55099 Mainz, Germany. Tel. +49-6131-392.3720, Email: ifeas@mail.uni-mainz.de; http://www.uni-mainz.de/~ifeas Geschäftsführender Herausgeber/ Managing Editor: Thomas...»

«3 PIC18 Development Tools 3.1 Objectives After completing this chapter, you should be able to Explain the function of software tools I Explain the basic function of hardware tools I Use MPLAB® IDE to enter programs and build I the executable code Use MPLAB ICD2 to perform software I debugging for the PIC18 microcontroller Use MPLAB simulator in perform software I debugging for the PIC18 microcontroller 90 I Chapter 3 PIC18 Development Tools 3.2 Development Tools Development tools for...»

«Appellate Case: 12-1175 Document: 01019574558 Date Filed: 02/22/2016 Page: 1 FILED United States Court of Appeals Tenth Circuit PUBLISH February 22, 2016 UNITED STATES COURT OF APPEALS Elisabeth A. Shumaker FOR THE TENTH CIRCUIT Clerk of Court _ DIRECT MARKETING ASSOCIATION, The Plaintiff Appellee, v. No. 12-1175 BARBARA BROHL, in her capacity as Executive Director, Colorado Department of Revenue, Defendant Appellant, and MULTISTATE TAX COMMISSION; INTERESTED LAW PROFESSORS; THE RETAIL INDUSTRY...»

«2016 X. Kong, J. Pakusch, D. Jansen, S. Emmerling, J. Neubauer, F. Goetz-Neunhoeffer: Effect of polymer latexes with cleaned serum on the phase development of hydrating cement pastes. Cem. Con. Res. 8, 30-40 (2016). http://dx.doi.org/10.1016/j.cemconres.2016.02.013 T. Hertel, J. Neubauer, F. Goetz-Neunhoeffer: Study of hydration potential and kinetics of the ferrite phase in iron-rich CAC. Cem. Con. Res. 83, 79-85 (2016).http://dx.doi.org/10.1016/j.cemconres.2016.01.004 A. Sobolkina, V....»





 
<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.