The Stellar Consensus Protocol

TheStellar Consensus Protocol: AFederatedModelforInternet-level Consensus ` DAVIDMAZIERES,StellarDevelopmentFoundation ThispaperintroducesanewmodelforconsensuscalledfederatedByzantineagreement(FBA).FBAachieves 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. Wealsopresent the Stellar Consensus Protocol (SCP), a construction for FBA. Like all Byzantine agree- mentprotocols,SCPmakesnoassumptionsabouttherationalbehaviorofattackers.UnlikepriorByzantine 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. CCSConcepts:•Securityandprivacy→Distributedsystemssecurity;Securityprotocols; 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- tegrityoffinancialtransactions.Historically,wehavereliedonhighbarrierstoentryto ensureintegrity. Wetrustestablishedfinancialinstitutionsanddoourbesttoregulate 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. Weneed 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 mechanismforworldwideconsensus. 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. 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. SCPisthefirstprovablysafeconsensusmechanismtoenjoyfourkeypropertiessimul- taneously: —Decentralized control. Anyone is able to participate and no central authority dictates whose approval is required for consensus. —Lowlatency.Inpractice,nodescanreachconsensusattimescaleshumansexpect 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. —Asymptoticsecurity. Safety rests on digital signatures and hash families whose parameters can realistically be tuned to protect against adversaries with unimag- inably vast computing power. SCPhasapplications beyond financial markets for ensuring organizations perform importantfunctionshonestly. Anexampleiscertificateauthorities(CAs),wholiterally holdthekeystotheweb.ExperienceshowsthatCAssignincorrectcertificatesthatget 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;Melaraetal.2014].Certificatetransparencyallowsuserstoexaminethehistory 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. Demandingglobalconsensusoncertificatehistory amongadecentralized 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 andfreedomfromblockedstates.Section7discusseslimitationsofSCP.Finally, Section 8 summarizes results. For readers less familiar with mathematical notation, Appendix A defines some symbols used throughout the paper. 2. RELATEDWORK Figure1summarizeshowSCPdiffersfrompreviousconsensusmechanisms.Themost 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 overwhelminglydemonstratedtheappealofdecentralizedconsensus[Bon- neauetal. 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

TheStellar Consensus Protocol 3 decentralized low flexible asymptotic mechanism control latency trust 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- temshavefallenvictim[crazyearner2013;Bradbury2013],however,posingaproblem 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[Peaseetal.1980;Lam- port et al. 1982], the best known variant of which is PBFT [Castro and Liskov 1999]. Byzantineagreementensuresconsensusdespitearbitrary(includingnon-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,membershipinByzantineagreementsystemsissetbyacentralauthority 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 thatparticipantscaneditforthemselves,hopingpeople’seditsareeitherinconsequen- 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 basemembershiponproofofstake.However,doingsoonceagaintiestrusttoresource

` 4 D. Mazieres ownership.SCPisthefirstByzantineagreementprotocoltogiveeachparticipantmax- imumfreedominchosingwhichcombinationsofotherparticipants to trust. 3. FEDERATEDBYZANTINEAGREEMENTSYSTEMS 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 maybeconsecutively numbered positions in a sequentially applied log. AnFBAsystemrunsaconsensusprotocolthatensuresnodesagreeonslotcontents. Anode 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. Achallenge 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- rumslices. 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 namedbypublickeyandtheydigitallysignmessages.Whenanodehearsasufficient 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 FBAsystemconsistsofalooseconfederation of nodes each of which has chosen one or moreslices. More formally: Definition (FBAS). A federated Byzantine agreement system, or FBAS, is a pair 2V ⟨V,Q⟩ comprising a set of nodes V and a quorum function Q ∶ V → 2 ⧵ {ç} speci- fying one or more quorum slices for each node, where a node belongs to all of its own X quorumslices—i.e., ∀v ∈ V,∀q ∈ Q(v),v ∈ q. (Note 2 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 besmallerthanaquorum.Considerthefour-nodesysteminFigure2,whereeachnode has a single slice and arrows point to the other members of that slice. Node v1’s slice {v ,v ,v } is sufficient to convince v of a statement. But v ’s and v ’s slices include v , 1 2 3 1 2 3 4 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 {v ,v ,v ,v }. 1 2 3 4 Traditional, non-federated Byzantine agreement requires all nodes to accept the sameslices, meaning ∀v ,v ,Q(v ) = Q(v ). Because every member accepts every slice, 1 2 1 2 traditional systems do not distinguish between slices and quorums. The downside is

TheStellar Consensus Protocol 5 v4 Q(v ) = {{v ,v ,v }} 1 1 2 3 v2 v3 Q(v ) = Q(v ) = Q(v ) = 2 3 4 {{v ,v ,v }} 2 3 4 v1 Fig. 2. v ’s quorum slice is not a quorum without v . 1 4 3/4 v v v v Top tier: slice is 3 out of 1 2 3 4 {v ,v ,v ,v }, including self 1 2 3 4 2/4 v v v v Middle tier: slice is self + any 5 6 7 8 2 top tier nodes 2/4 v v Leaf tier: slice is self + any 9 10 2 middle tier nodes Fig. 3. Tiered quorum structure example that membershipandquorumsmustsomehowbepre-ordained,precludingopenmem- bership and decentralized control. A traditional system, such as PBFT [Castro and Liskov1999],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 greaterrangeofsettings.FBA’skeyinnovationisenablingeachnodevtochoseitsown quorumslicesetQ(v).System-widequorumsthusarisefromindividualdecisionsmade 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 v ,…,v , is struc- 1 4 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 v ,…,v consti- 5 8 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 v and v are in a leaf tier for which a slice consists of any 9 10

` 6 D. Mazieres v1 v6 v2 Q(v) = {v,v } i i (i mod 6)+1 v5 v3 v4 Fig. 4. Cyclic quorum structure example twomiddletiernodes.Notethatv andv maypickdisjointslicessuchas{v ,v }and 9 10 5 6 {v ,v }; nonetheless, both will indirectly depend on the top tier. 7 8 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 analogoustotransitivereachability,thentheInternet’snearcompletetransitivereach- ability suggests we can likewise ensure worldwideconsensuswithFBA.Inmanyways, 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,FBAnodescanerronthesideofinclusiveness,constructingconservativeslices withgreaterinterdependenceandredundancythantypicallyseeninpeeringandtran- sit arrangements. Anotherexamplenotpossiblewithcentralizedconsensusiscyclicdependencystruc- 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 Wecategorizenodesaseitherwell-behavedorill-behaved.Awell-behavednodechooses sensiblequorumslices(discussedfurtherinSection4.1)andobeystheprotocol,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-

TheStellar Consensus Protocol 7 ill-behaved well-behaved failed Byzantine, correct including blocked divergent correct crashed Fig. 5. Venndiagramofnodefailures 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 values despite the presence of such ill-behaved nodes. There are two parts to this goal. First, we would like to prevent nodes from diverging and externalizing different values for the same slot. Second, we would like to ensure nodes can actually externalize values, as opposed to getting blocked in some dead-end state from which consensus is no longer possible. We introduce the following two terms for these prop- erties: Definition (safety). A set of nodes in an FBAS enjoy safety if no two of them ever externalize different values for the same slot. Definition (liveness). A node in an FBAS enjoys liveness if it can externalize new values without the participation of any failed (including ill-behaved) nodes. Wecall well-behaved nodes that enjoy both safety and liveness correct. Nodes that are not correct have failed. All ill-behaved nodes have failed, but a well-behaved node can fail, too, by waiting indefinitely for messages from ill-behaved nodes, or, worse, by having its state poisoned by incorrect messages from ill-behaved nodes. Figure 5 illustrates the possible kinds of node failure. To the left are Byzantine failures, meaning the ill-behaved nodes. To the right are two kinds of well-behaved but failed nodes. Nodes that lack liveness are termed blocked, while those that lack safety are termed divergent. An attack violating safety is strictly more powerful than one violating only liveness, so we classify divergent nodes as a subset of blocked ones. Ourdefinition of liveness is weak in that it says a node can externalize new values, not that it will. Hence, it admits a state of perpetual preemption in which consensus remains forever possible, yet the network continually thwarts it by delaying or re- ordering critical messages in just the wrong way. Perpetual preemption is inevitable in a purely asynchronous, deterministic system that survives node failure [Fischer et al. 1985]. Fortunately, preemption is transient. It does not indicate node failure, be- cause the system can recover at any time. Protocols can mitigate the problem through randomness [Ben-Or 1983; Bracha and Toueg 1985] or through realistic assumptions about message latency [Dwork et al. 1988]. Latency assumptions are more practical when one would like to limit execution time or avoid the trusted dealers often re- quired by more efficient Randomized algorithms [?]. Of course, only termination and not safety should depend upon message timing. 4. OPTIMALRESILIENCE Whether or not nodes enjoy safety and liveness depends on several factors: what quo- rum slices they have chosen, which nodes are ill-behaved, and of course the concrete consensus protocol and network behavior. As is common for asynchronous systems, we assume the network eventually delivers messages between well-behaved nodes, but can otherwise arbitrarily delay or reorder messages.

` 8 D. Mazieres v v 1 4 Q(v ) = Q(v4) = 1 Q(v ) = Q(v5) = 2 Q(v ) = Q(v6) = 3 {{v ,v ,v }} v v v v {{v ,v ,v }} 1 2 3 2 3 5 6 4 5 6 Fig. 6. FBASlackingquorumintersection Q(v ) = {{v }} 7 7 v v7 v 1 4 Q(v1) = Q(v4) = Q(v2) = Q(v5) = Q(v3) = Q(v6) = {{v ,v ,v ,v }} v v v v {{v ,v ,v ,v }} 1 2 3 7 2 3 5 6 4 5 6 7 Fig. 7. Ill-behaved node v can undermine quorum intersection. 7 This section answers the following question: given a specific ⟨V,Q⟩ and particular subset of V that is ill-behaved, what are the best safety and liveness that any feder- ated Byzantine agreement protocol can guarantee regardless of the network? We first discuss quorum intersection, a property without which safety is impossible to guar- antee. We then introduce a notion of dispensable sets—sets of failed nodes in spite of which it is possible to guarantee both safety and liveness. 4.1. Quorum intersection Aprotocol can guarantee agreement only if the quorum slices represented by function Qsatisfy a validity property we call quorum intersection. Definition (quorum intersection). An FBAS enjoys quorum intersection iff any two of its quorums share a node—i.e., for all quorums U and U , U ∩U ≠ ç. 1 2 1 2 Figure 6 illustrates a system lacking quorum intersection, where Q permits two quo- rums, {v ,v ,v } and {v ,v ,v }, that do not intersect. Disjoint quorums can indepen- 1 2 3 4 5 6 dentlyagreeoncontradictorystatements,underminingsystem-wideagreement.When manyquorumsexist, quorum intersection fails if any two do not intersect. For exam- ple, the set of all nodes {v ,…,v } in Figure 6 is a quorum that intersects the other two, 1 6 but the system still lacks quorum intersection because the other two do not intersect each other. Noprotocol can guarantee safety in the absence of quorum intersection, since such a configuration can operate as two different FBAS systems that do not exchange any messages. However, even with quorum intersection, safety may be impossible to guar- antee in the presence of ill-behaved nodes. Compare Figure 6, in which there are two disjoint quorums, to Figure 7, in which two quorums intersect at a single node v , and 7 v is ill-behaved. If v makes inconsistent statements to the left and right quorums, 7 7 the effect is equivalent to disjoint quorums. In fact, since ill-behaved nodes contribute nothing to safety, no protocol can guaran- tee safety without the well-behaved nodes enjoying quorum intersection on their own. After all, in a worst-case scenario for safety, ill-behaved nodes can just always make any possible (contradictory) statement that completes a quorum. Two quorums over- lapping only at ill-behaved nodes will again be able to operate like two different FBAS

TheStellar Consensus Protocol 9 systems thanks to the duplicity of the ill-behaved nodes. In short, FBAS ⟨V,Q⟩ can survive Byzantine failure by a set of nodes B ⊆ V iff ⟨V,Q⟩ enjoys quorum intersection after deleting the nodes in B from V and from all slices in Q. More formally: Definition (delete). If ⟨V,Q⟩ is an FBAS and B ⊆ V is a set of nodes, then to delete B B B from ⟨V,Q⟩, written ⟨V,Q⟩ , means to compute the modified FBAS ⟨V⧵B,Q ⟩ where B Q (v) = {q ⧵B ∣ q ∈ Q(v)}. It is the responsibility of each node v to ensure Q(v) does not violate quorum inter- section. One way to do so is to pick conservative slices that lead to large quorums. Of course, a malicious v may intentionally pick Q(v) to violate quorum intersection. But a malicious v can also lie about the value of Q(v) or ignore Q(v) to make arbitrary as- sertions. In short, Q(v)’s value is not meaningful when v is ill-behaved. This is why the necessary property for safety—quorum intersection of well-behaved nodes after deleting ill-behaved nodes—is unaffected by the slices of ill-behaved nodes. SupposeFigure6evolvedfromathree-nodeFBASv ,v ,v withquorumintersection 1 2 3 to a six-node FBAS without. When v ,v ,v join, they maliciously choose slices that 4 5 6 violate quorum intersection and no protocol can guarantee safety for V. Fortunately, {v ,v ,v } deleting the bad nodes to yield ⟨V,Q⟩ 4 5 6 restores quorum intersection, meaning at least {v ,v ,v } can enjoy safety. Note that deletion is conceptual, for the sake of 1 2 3 describing optimal safety. A protocol should guarantee safety for v ,v ,v without their 1 2 3 needing to know that v ,v ,v are ill-behaved. 4 5 6 4.2. Dispensable sets (DSets) We capture the fault tolerance of nodes’ slice selections through the notion of a dis- pensible set or DSet. Informally, the safety and liveness of nodes outside a DSet can be guaranteedregardlessofthebehaviorofnodesinsidetheDSet.Putanotherway,inan optimally resilient FBAS, if a single DSet encompasses every ill-behaved node, it also contains every failed node, and conversely all nodes outside the DSet are correct. As an example, in a centralized PBFT system with 3f +1 nodes and quorum size 2f +1, anyf orfewernodesconstituteaDSet.SincePBFTinfactsurvivesuptof Byzantine failures, its robustness is optimal. In the less regular example of Figure 3, {v1} is a DSet, since one top tier node can fail without affecting the rest of the system. {v } is also a DSet because no other node 9 dependsonv forcorrectness.{v ,…,v }isaDSet,becauseneitherv northetoptier 9 6 10 5 depend on any of those five nodes. {v ,v } is not a DSet, as it is a slice for v and v 5 6 9 10 and hence, if entirely malicious, can lie to v9 and v10 and convince them of assertions inconsistent with each other or the rest of the system. To prevent a misbehaving DSet from affecting the correctness of other nodes, two properties must hold. For safety, deleting the DSet cannot undermine quorum inter- section. For liveness, the DSet cannot deny other nodes a functioning quorum. This leads to the following definition: Definition (DSet). Let ⟨V,Q⟩ be an FBAS and B ⊆ V be a set of nodes. We say B is a dispensible set, or DSet, iff: B (1) (quorum intersection despite B) ⟨V,Q⟩ enjoys quorum intersection, and (2) (quorum availability despite B) Either V⧵B is a quorum in ⟨V,Q⟩ or B = V. Quorum availability despite B protects against nodes in B refusing to answer re- quests and blocking other nodes’ progress. Quorum intersection despite B protects against the opposite—nodes in B making contradictory assertions that enable other nodes to externalize inconsistent values for the same slot. Nodes must balance the two threats in slice selection. All else equal, bigger slices lead to bigger quorums with

` 10 D. Mazieres well-behaved / Local property of nodes, independent of other nodes (except for ill-behaved the validity of slice selection). intact / Property of nodes given their quorum slices and a particular set befouled of ill-behaved nodes. Befouled nodes are ill-behaved or depend, possibly indirectly, on too many ill-behaved nodes. correct / Property of nodes given their quorum slices, a concrete protocol, failed and actual network behavior. The goal of a consensus protocol is to guarantee correctness for all intact nodes. Fig. 8. Keyproperties of FBAS nodes greater overlap, meaning fewer failed node sets B will undermine quorum intersection whendeleted. On the other hand, bigger slices are more likely to contain failed nodes, endangering quorum availability. The smallest DSet containing all ill-behaved nodes may encompass well-behaved nodes as well, reflecting the fact that a sufficiently large set of ill-behaved nodes can cause well-behaved nodes to fail. For instance, in Figure 3, the smallest DSet contain- ing v and v is {v ,v ,v ,v }. The set of all nodes, V, is always a DSet, as an FBAS 5 6 5 6 9 10 ⟨V,Q⟩vacuouslyenjoysquorumintersectiondespiteVand,byspecialcase,alsoenjoys quorum availability despite V. The motivation for the special case is that given suffi- ciently many ill-behaved nodes, V may be the smallest DSet to contain all ill-behaved ones, indicating a scenario under which no protocol can guarantee anything better than complete system failure. The DSets in an FBAS are determined a priori by the quorum function Q. Which nodesarewell-andill-behaveddependsonruntimebehavior,suchasmachinesgetting compromised.TheDSetswecareaboutarethosethatencompassallill-behavednodes, as they help us distinguish nodes that should be guaranteed correct from ones for which such a guarantee is impossible. To this end, we introduce the following terms: Definition (intact). A node v in an FBAS is intact iff there exists a DSet B containing all ill-behaved nodes and such that v ∉ B. Definition (befouled). A node v in an FBAS is befouled iff it is not intact. Abefouled node v is surrounded by enough failed nodes to block its progress or poi- sonitsstate, even if v itself is well-behaved. No FBAS can guarantee the correctness of abefoulednode.However,anoptimalFBASguaranteesthateveryintactnoderemains correct. Figure 8 summarizes the key properties of nodes. The following theorems fa- cilitate analysis by showing that the set of befouled nodes is always a DSet in an FBAS with quorum intersection. THEOREM1. LetU beaquoruminFBAS⟨V,Q⟩,letB ⊆Vbeasetofnodes,andlet ¨ ¨ ¨ B U =U⧵B.IfU ≠çthenU isaquorumin⟨V,Q⟩ . PROOF. Because U is a quorum, every node v ∈ U has a q ∈ Q(v) such that q ⊆ U. SinceU¨ ⊆ U,itfollowsthateveryv ∈ U¨ hasaq ∈ Q(v)suchthatq⧵B ⊆ U¨.Rewriting with deletion notation yields ∀v ∈ U¨,∃q ∈ QB(v) such that q ⊆ U¨, which, because U¨ ⊆ V⧵B,meansthatU¨ isaquorumin⟨V,Q⟩B. THEOREM2. If B and B are DSets in an FBAS ⟨V,Q⟩ enjoying quorum intersec- 1 2 tion, then B = B ∩B is a DSet, too. 1 2 PROOF. LetU =V⧵B andU =V⧵B .IfU =ç,thenB =VandB=B (aDSet), 1 1 2 2 1 1 2 so we are done. Similarly, if U = ç, then B = B , and we are done. Otherwise, note 2 1

TheStellar Consensus Protocol 11 that by quorum availability despite DSets B and B , U and U are quorums in ⟨V,Q⟩. 1 2 1 2 It follows from the definition that the union of two quorums is also a quorum. Hence V⧵B=U ∪U isaquorumandwehavequorumavailabilitydespiteB. 1 2 We must now show quorum intersection despite B. Let U and U be any two a b B quorums in ⟨V,Q⟩ . Let U = U ∩ U = U ⧵ B . By quorum intersection of ⟨V,Q⟩, 1 2 2 1 B U = U ∩U ≠ ç. But then by Theorem 1, U = U ⧵B must be a quorum in ⟨V,Q⟩ 1. 1 2 2 1 NowconsiderthatU ⧵B andU ⧵B cannotbothbeempty,orelseU ⧵B =U would a 1 a 2
a a B B1 B1 be. Hence, by Theorem1,eitherU ⧵B isaquorumin ⟨V,Q⟩ =⟨V,Q⟩ ,orU ⧵B
a 1 a 2 B B2 B is a quorum in ⟨V,Q⟩ =⟨V,Q⟩ 2,orboth.Intheformercase,notethatifU ⧵B is a 1 B B a quorum in ⟨V,Q⟩ 1, then by quorum intersection of ⟨V,Q⟩ 1, (U ⧵B )∩U ≠ ç; since a 1 (U ⧵B )∩U = (U ⧵B )⧵B , it follows that U ⧵B ≠ ç, making U ⧵B a quorum in a 1 a 1 2 a 2 a 2 B2 B2 ⟨V,Q⟩ . By a similar argument, U ⧵B must be a quorum in ⟨V,Q⟩ . But then quo- b 2 rumintersection despite B tells us that (U ⧵B )∩(U ⧵B ) ≠ ç, which is only possible 2 a 2 b 2 if U ∩U ≠ç. a b THEOREM3. In an FBAS with quorum intersection, the set of befouled nodes is a DSet. PROOF. Let B be the intersection of every DSet that contains all ill-behaved min nodes. It follows from the definition of intact that a node v is intact iff v ∉ B . Thus, min B is precisely the set of befouled nodes. By Theorem 2, DSets are closed under in- min tersection, so B is also a DSet. min 5. FEDERATEDVOTING This section develops a federated voting technique that FBAS nodes can use to agree on a statement. At a high level, the process for agreeing on some statement a involves nodes exchanging two sets of messages. First, nodes vote for a. Then, if the vote was successful, nodes confirm a, effectively holding a second vote on the fact that the first vote succeeded. From each node’s perspective, the two rounds of messages divide agreement on a statement a into three phases: unknown, accepted, and confirmed. (This pattern dates backtothree-phasecommit[SkeenandStonebraker1983].)Initially,a’sstatusiscom- pletely unknowntoanodev—acouldenduptrue,false,orevenstuckinapermanently indeterminate state. If the first vote succeeds, v may come to accept a. No two intact nodeseveracceptcontradictorystatements,soifvisintactandacceptsa,thenacannot be false. For two reasons, however, v accepting a does not suffice for v to act on a. First, the fact that v accepted a does not mean all intact nodes can; a could be stuck for other nodes. Second, if v is befouled, then accepting a means nothing—a may be false at intact nodes. Yet even if v is befouled—which v does not know—the system may still enjoy quorum intersection of well-behaved nodes, in which case, for optimal safety, v needs greater assurance of a. Holding a second vote addresses both problems. If the second vote succeeds, v moves to the confirmed phase in which it can finally deem a true and act on it. The next few subsections detail the federated voting process. Because voting does not rule out the possibility of stuck statements, Section 5.6 discusses how to cope with them. Section 6 will turn federated voting into a consensus protocol that avoids the possibility of stuck slots for intact nodes.

` 12 D. Mazieres 5.1. Voting with open membership Acorrect node in a Byzantine agreement system acts on a statement a only when it knows that other correct nodes will never agree to statements contradicting a. Most protocols employ voting for this purpose. Well-behaved nodes vote for a statement a only if it is valid. Well-behaved nodes also never change their votes. Hence, in central- ized Byzantine agreement, it is safe to accept a if a quorum comprising a majority of well-behaved nodes has voted for it. We say a statement is ratified once it has received the necessary votes. Inafederatedsetting,wemustadaptvotingtoaccommodateopenmembership.One difference is that a quorum no longer corresponds to a majority of well-behaved nodes. However, the majority requirement primarily serves to ensure quorum intersection of well-behaved nodes, which Section 4.1 already adapted to FBA. Another implication of open membership is that nodes must discover what constitutes a quorum as part of the voting process. To implement quorum discovery, a protocol should specify Q(v) in all messages from v. Definition (vote). A node v votes for an (abstract) statement a iff (1) v asserts a is valid and consistent with all statements v has accepted, and (2) v asserts it has never voted against a—i.e., voted for a statement that contra- dicts a—and v promises never to vote against a in the future. Definition (ratify). A quorum U ratifies a statement a iff every member of U votes a a for a. A node v ratifies a iff v is a member of a quorum U that ratifies a. a THEOREM4. Two contradictory statements a and ā cannot both be ratified in an FBASthatenjoysquorumintersection and contains no ill-behaved nodes. PROOF. By contradiction. Suppose quorum U ratifies a and quorum U ratifies ā. 1 2 By quorum intersection, ∃v ∈ U ∩ U . Such a v must have illegally voted for both a 1 2 andā, violating the assumption of no ill-behaved nodes. THEOREM5. Let ⟨V,Q⟩ be an FBAS enjoying quorum intersection despite B, and suppose B contains all ill-behaved nodes. Let v and v be two nodes not in B. Let a and 1 2 ā be contradictory statements. If v ratifies a then v cannot ratify ā. 1 2 PROOF. Bycontradiction. Suppose v ratifies a and v ratifies ā. By definition, there 1 2 mustexistaquorumU containingv thatratifiedaandquorumU containingv that 1 1 2 2 ratified ā. By Theorem 1, since U ⧵ B ≠ ç and U ⧵ B ≠ ç, both must be quorums 1 2 B B B in ⟨V,Q⟩ , meaning they ratified a and ā respectively in ⟨V,Q⟩ . But ⟨V,Q⟩ enjoys quorumintersection and has no ill-behaved nodes, so Theorem 4 tell us a and ā cannot both be ratified. THEOREM6. Twointact nodes in an FBAS with quorum intersection cannot ratify contradictory statements. PROOF. Let B be the set of befouled nodes. By Theorem 3, B is a DSet. By the defi- nition of DSet, ⟨V,Q⟩ enjoys quorum intersection despite B. By Theorem 5, two nodes not in B cannot ratify contradictory statements. 5.2. Blocking sets In centralized consensus, liveness is an all-or-nothing property of the system. Either a unanimously well-behaved quorum exists, or else ill-behaved nodes can prevent the rest of the system from accepting new statements. In FBA, by contrast, liveness may differ across nodes. For instance, in the tiered quorum example of Figure 3, if middle

TheStellar Consensus Protocol 13 3/4 Slice is 3 nodes, including self v v v v 1 2 3 4 vote a vote a vote a vote ā accept accept accept Fig. 9. v voted for ā, which contradicts ratified statement a. 4 tier nodes v ,v ,v crash, the leaf tier will be blocked while the top tier and node v 6 7 8 5 will continue to enjoy liveness. An FBA protocol can guarantee liveness to a node v only if Q(v) contains at least onequorumslicecomprisingonlycorrectnodes.AsetB offailednodescanviolatethis property if B contains at least one member of each of v’s slices. We term such a set B v-blocking, because it has the power to block progress by v. Definition (v-blocking). Let v ∈ V be a node in FBAS ⟨V,Q⟩. A set B ⊆ V is v-blocking iff it overlaps every one of v’s slices—i.e., ∀q ∈ Q(v),q ∩ B ≠ ç. THEOREM7. Let B ⊆ V be a set of nodes in FBAS ⟨V,Q⟩. ⟨V,Q⟩ enjoys quorum availability despite B iff B is not v-blocking for any v ∈ V ⧵ B. PROOF. “∀v ∈ V⧵B,B is not v-blocking” is equivalent to “∀v ∈ V⧵B,∃q ∈ Q(v) such that q ⊆ V ⧵ B.” By the definition of quorum, the latter holds iff V ⧵ B is a quorum or B=V,theexactdefinitionofquorumavailability despite B. Asacorollary, the DSet of befouled nodes is not v-blocking for any intact v. 5.3. Accepting statements Whenanintact node v learns that it has ratified a statement, Theorem 6 tells v that other intact nodes will not ratify contradictory statements. This condition is sufficient for v to accept a, but we cannot make it necessary. Ratifying a statement requires vot- ingforit,andsomenodesmayhavevotedforcontradictorystatements.InFigure9,for example, v votes for ā before learning that the other three nodes ratified the contra- 4 dictory statement a. Though v4 cannot now vote for a, we would still like it to accept a to be consistent with the other nodes. Akeyinsightisthatifanodevisintact,thennov-blockingsetB canconsistentirely of befouled nodes. Now suppose B is a v-blocking set and every member of B claims to accept statement a. If v is intact, at least one member of B must be, too. The intact member will not lie about accepting a; hence, a is true and v can accept it. Of course, if v is befouled, then a might not be true. But a befouled node can accept anything and vacuously not affect the correctness of intact nodes. Definition (accept). An FBAS node v accepts a statement a iff it has never accepted astatement contradicting a and it determines that either (1) There exists a quorum U such that v ∈ U and each member of U either voted for a or claims to accept a, or (2) Each member of a v-blocking set claims to accept a. Though a well-behaved node cannot vote for contradictory statements, condition 2 above allows a node to vote for one statement and later accept a contradictory one.

` 14 D. Mazieres 3/4 Slice is 3 nodes, including self v v v v 1 2 3 4 vote a vote a vote a vote ā accept a) 3/4 v v v v 1 2 3 4 ̄ vote a vote a vote a vote ā ̄ accept vote a b) Fig. 10. Scenarios indistinguishable to v when v does not see bold messages 2 2 THEOREM8. Twointactnodes in an FBAS that enjoys quorum intersection cannot accept contradictory statements. PROOF. Let⟨V,Q⟩beanFBASwithquorumintersectionandletBbeitsDSetofbe- fouled nodes (which exists by Theorem 3). Suppose an intact node accepts statement a. Let v be the first intact node to accept a. At the point v accepts a, only befouled nodes in B can claim to accept it. Since by the corollary to Theorem 7, B cannot be v-blocking, it must be that v accepted a through condition 1. Thus, v identified a quorum U such that every node claimed to vote for or accept a, and since v is the first intact node to ac- cepta,itmustmeanallnodesinU⧵Bvotedfora.Inotherwords,vratifiedain⟨V,Q⟩B. Generalizing, any statement accepted by an intact node in ⟨V,Q⟩ must be ratified in B B ⟨V,Q⟩ . Because B is a DSet, ⟨V,Q⟩ enjoys quorum intersection. Because addition- ally B contains all ill-behaved nodes, Theorem 4 rules out ratification of contradictory statements. 5.4. Accepting is not enough Unfortunately, for nodes to assume the truth of accepted statements would yield sub- optimal safety and liveness guarantees in a federated consensus protocol. We discuss the issues with safety and liveness in turn. To provide some context, we then explain whytheseissues are thornier in FBA than in centralized Byzantine agreement. 5.4.1. Safety. Consider an FBAS ⟨V,Q⟩ in which the only quorum is unanimous consent—i.e., ∀v,Q(v) = {V}. This ought to be a conservative choice for safety—don’t doanythingunlesseveryoneagrees.Yetsinceeverynodeisv-blockingforeveryv,any node can single-handedly convince any other node to accept arbitrary statements. The problem is that accepted statements are only safe among intact nodes. But as discussed in Section 4.1, the only condition necessary to guarantee safety is quorum intersection of well-behaved nodes, which might hold even in the case that some well- behavednodesarebefouled.Inparticular,whenQ(v) = {V},theonlyDSetsareçandV, meaning any node failure befouls the whole system. By contrast, quorum intersection holds despite every B ⊆ V. 5.4.2. Liveness. Another limitation of accepted statements is that other intact nodes maybeunabletoacceptthem.Thispossibilitymakesrelianceonacceptedstatements

TheStellar Consensus Protocol 15 problematic for liveness. If a node proceeds to act on a statement because it accepted the statement, other nodes could be unable to proceed in a similar fashion. Consider Figure 10a, in which node v crashes after helping v ratify and accept 3 1 statementa.Thoughv1 acceptsa,v2 andv4 cannot.Inparticular,fromv2’sperspective, thesituation depicted is indistinguishable from Figure 10b, in which v3 voted for ā and is well-behaved but slow to respond, while v is ill-behaved and sent v a vote for ā 1 3 (thereby causing v to accept ā) while illegally also sending v a vote for a. 3 2 Tosupportaprotocol-levelnotionoflivenessincaseslikeFigure10a,v needsaway 1 to ensure every other intact node can eventually accept a before v acts on a. Once this 1 is the case, it makes sense to say the system agrees on a. Definition (agree). An FBAS ⟨V,Q⟩ agrees on a statement a iff, regardless of what subsequently transpires, once sufficient messages are delivered and processed, every intact node will accept a. 5.4.3. Comparison to centralized voting. To understand why the above issues arise in fed- erated voting, consider a centralized Byzantine agreement system of N nodes with quorum size T. Such a system enjoys quorum availability with f = N −T or fewer L nodefailures. Since any two quorumsshareatleast2T −N nodes,quorumintersection of well-behaved nodes holds up to fS = 2T −N −1 Byzantine failures. Centralized Byzantine agreement systems typically set N = 3f + 1 and T = 2f + 1 to yield f =f =f,theequilibriumpointatwhichsafetyandlivenesshavethesame L S fault tolerance. If safety is more important than liveness, some protocols increase T ` so that f > f [Li and Mazieres 2007]. In FBA, because quorums arise organically, S L systems are unlikely to find themselves at equilibrium, making it far more important to protect safety in the absence of liveness. Nowconsider a centralized system in which, because of node failure and contradic- tory votes, some node v cannot ratify statement a that was ratified by other nodes. If v hears f + 1 nodes claim a was ratified, v knows that either one of them is well- S behavedorallsafetyguaranteeshavecollapsed.Eitherway,vcanactonawithnoloss of safety. The FBA equivalent would be to hear from a set B where B, if deleted, un- dermines quorum intersection of well-behaved nodes. Identifying such a B is hard for three reasons: one, quorums are discovered dynamically; two, ill-behaved nodes may lie about slices; and three, v does not know which nodes are well-behaved. Instead, we defined federated voting to accept a when a v-blocking set does. The v-blocking prop- erty has the advantage of being easily checkable, but is equivalent to hearing from f +1nodesinacentralizedsystemwhenwereallywantf +1. L S To guarantee agreement among all well-behaved nodes in a centralized system, one merely needs f +f +1 nodes to acknowledge that a statement was ratified. If more L S than f of them fail, we do not expect liveness anyway. If f or fewer fail, then we L L knowf +1nodesremainwillingtoattest to ratification, which will in turn convince S all other well-behaved nodes. The reliance on fS has no easy analogue in the FBA model. Interestingly, however, f + f + 1 = T, the quorum size, suggesting a similar L S approach might work with a more complex justification. Put another way, at some point nodes need to believe a statement strongly enough to depend on its truth for safety. A centralized system offers two ways to reach this point for a statement a: ratify a first-hand, or reason backwards from f + 1 nodes S claiming a was ratified, figuring safety is hopeless if they have all lied. FBA lacks the latter approach; the only tool it has for safety among well-behaved nodes is first-hand ratification. Since nodes still need a way to overcome votes against ratified statements, we introduced a notion of accepting, but it provides a weaker consistency guarantee limited to intact nodes.

` 16 D. Mazieres 5.5. Statement confirmation Both limitations of accepted statements stem from complications when a set of intact nodes S votes against a statement a that is nonetheless ratified. Particularly in light of FBA’s non-uniform quorums, S may prevent some intact node from ever ratifying v. Toprovidevameansofacceptingadespitevotesagainstit,thedefinitionofaccepthas a second criterion based on v-blocking sets. But the second criterion is weaker than ratification, offering no guarantees to befouled nodes that enjoy quorum intersection. Nowsupposeastatement a has the property that no intact node ever votes against it. Then we have no need to accept a and can instead insist that nodes directly ratify a before acting on it. We call such statements irrefutable. Definition (irrefutable). A statementaisirrefutableinanFBASifnointactnodecan ever vote against it. Theorem 8 tells us that two intact nodes cannot accept contradictory statements. Thus, while some intact nodes may vote against a statement a that was accepted by anintact node, the statement “an intact node accepted a” is irrefutable. This suggests holding a second vote to ratify the fact that an intact node accepted a. Definition (confirm). A quorum U in an FBAS confirms a statement a iff ∀v ∈ U , a a v claims to accept a. A node confirms a iff it is in such a quorum. Nodes express that they have accepted statement a by stating “accept(a),” an ab- breviation of the statement, “An intact node accepted a.” To confirm a means to ratify accept(a). A well-behaved node v can vote for accept(a) only after accepting a, as v cannot assume any particular other nodes are intact. If v itself is befouled, accept(a) might be false, in which case voting for it may cost v liveness, but a befouled node has no guarantee of liveness anyway. Thenexttheoremshowsthatnodescanrelyonconfirmedstatementswithoutlosing optimal safety. Theorem 11 then shows that confirmed statements meet the defini- tion of agreement from Section 5.4.2, meaning nodes can rely on confirmed statements without endangering the liveness of intact nodes. THEOREM9. Let ⟨V,Q⟩ be an FBAS enjoying quorum intersection despite B, and suppose B contains all ill-behaved nodes. Let v and v be two nodes not in B. Let a and 1 2 ā be contradictory statements. If v confirms a, then v cannot confirm ā. 1 2 PROOF. First note that accept(a) contradicts accept(ā)—no well-behaved node can vote for both. Note further that v1 must ratify accept(a) to confirm a. By Theorem 5, v2 cannot ratify accept(ā) and hence cannot confirm ā. THEOREM10. Let B be the set of befouled nodes in an FBAS ⟨V,Q⟩ with quorum intersection. Let U be a quorum containing an intact node (U ⊈ B), and let S be any set suchthatU ⊆S ⊆V.LetS+ =S⧵BbethesetofintactnodesinS,andletS− =(V⧵S)⧵B be the set of intact nodes not in S. Either S− = ç, or ∃v ∈ S− such that S+ is v-blocking. PROOF. If S+ is v-blocking for some v ∈ S−, then we are done. Otherwise, we must showS− =ç.IfS+ is not v-blocking for any v ∈ S−, then, by Theorem 7, either S− = ç − B or S is a quorum in ⟨V,Q⟩ . In the former case we are done, while in the latter we B get a contradiction: By Theorem 1, U ⧵B is a quorum in ⟨V,Q⟩ . Since B is a DSet (by B − Theorem3),⟨V,Q⟩ mustenjoyquorumintersection,meaningS ∩(U⧵B)≠ç.Thisis impossible, since (U ⧵B) ⊆ S and S− ∩S = ç. THEOREM11. If an intact node in an FBAS ⟨V,Q⟩ with quorum intersection con- firms a statement a, then, whatever subsequently transpires, once sufficient messages are delivered and processed, every intact node will accept and confirm a.

TheStellar Consensus Protocol 17 quorumsatisfying v quorumsatisfying v each votes or accepts a confirmsa a is valid voted a accepted a confirmed a uncommitted v-blocking set accepts a voted ā Fig. 11. Possible states of an accepted statement a at a single node v a-valent a agreed bivalent stuck ā-valent ā agreed Fig. 12. Possible system-wide status of a statement a PROOF. Let B be the DSet of befouled nodes and let U ⊈ B be the quorum through whichanintactnodeconfirmeda.LetnodesinU⧵Bbroadcastaccept(a).Bydefinition, any node v, regardless of how it has voted, accepts a after receiving accept(a) from a v-blocking set. Hence, these messages may convince additional nodes to accept a. Let these additional nodes in turn broadcast accept(a) until a point is reached at which, regardless of future communication, no further intact nodes can ever accept a. At this point let S be the set of nodes that claim to accept a (where U ⊆ S), let S+ be the set of intact nodes in S, and let S− be the set of intact nodes not in S. S+ cannot be v-blocking for any node in S−, or else more nodes could come to accept a. By Theorem 10, then, S− =ç, meaning every intact node has accepted a. Figure 11 summarizes the paths an intact node v can take to confirm a. Given no knowledge, v might vote for either a or the contradictory ā. If v votes for ā, it cannot later vote for a, but can nonetheless accept a if a v-blocking set accepts it. A subsequent quorum of confirmation messages allows v to confirm a, which by Theorem 11 means the system agrees on a. 5.6. Liveness and neutralization The main challenge of distributed consensus, whether centralized or not, is that a statement can get stuck in a permanently indeterminate state before the system reaches agreement on it. Hence, a protocol must not attempt to ratify externalized values directly. Should the statement “The value of slot i is x” get stuck, the system will be forever unable to agree on slot i, losing liveness. The solution is to craft the statements in votes carefully. It must be possible to break a stuck statement’s hold on the question we really care about, namely slot contents. We call the process of obsolet- ing a stuck statement neutralization.

` 18 D. Mazieres Local state System-widestatusofa uncommitted unknown(any) voted a unknown(any) voted ā unknown(any) accepted a stuck, a-valent, or a agreed confirmeda a agreed Fig. 13. Whatanintactnodeknowsaboutthestatusofstatementa More concretely, Figure 12 depicts the potential status a statement a can have system-wide. Initially, the system is bivalent, by which we mean there is one sequence of possible events through which all intact nodes will accept a, and another sequence through which all intact nodes will reject a (i.e., accept a statement ā contradicting a). At some point, one of these two outcomes may cease to be possible. If no intact node can ever reject a, we say the system is a-valent; conversely, if no intact node can ever accept a, we say the system is ā-valent. At the time an FBAS transitions from bivalent to a-valent, there is a possible out- come in which all intact nodes accept a. However, this might not remain the case. ConsideraPBFT-likefour-nodesystem{v ,…,v }inwhichanythreenodesconstitute 1 4 a quorum. If v and v vote for a, the system becomes a-valent; no three nodes can 1 2 ratify a contradictory statement. However, if v3 and v4 subsequently vote for ā contra- dicting a, it also becomes impossible to ratify a. In this case, a’s state is permanently indeterminate, or stuck. As seen in Figure 10a, even once an intact node accepts a, the system may still fail to reach system-wide agreement on a. However, by Theorem 11, once an intact node confirms a, all intact nodes can eventually come to accept it; hence the system has agreed upon a. Figure 13 summarizes what intact nodes know about the global state of a statement from their own local state. Topreservethepossibilityofconsensus,aprotocolmustensurethateverystatement is either irrefutable, and hence cannot get stuck, or neutralizable, and hence cannot block progress if stuck. There are two popular approaches to crafting neutralizable statements: the view-based approach, pioneered by viewstamped replication [Oki and Liskov 1988] and favored by PBFT [Castro and Liskov 1999]; and the ballot-based ap- proach, invented by Paxos [Lamport 1998]. The ballot-based approach may be harder to understand [Ongaro and Ousterhout 2014]. Compounding confusion, people often call viewstamped replication “Paxos” or assert that the two algorithms are the same whentheyarenot[vanRenesseetal.2014]. View-basedprotocols associate the slots in votes with monotonically increasing view numbers.Shouldconsensusgetstuckontheithslotinviewn,nodesrecoverbyagree- ingthatviewnhadfewerthanimeaningfulslotsandmovingtoahigherviewnumber. Ballot-based protocols associate the values in votes with monotonically increasing bal- lot numbers. Should a ballot get stuck, nodes retry the same slot with a higher ballot, taking care never to select values that would contradict prior stuck ballots. Thisworktakesaballot-basedapproach,asdoingsomakesiteasiertodoawaywith the notion of a distinguished primary node or leader. For example, leader behavior can be emulated [Lamport 2011b]. 6. SCP: A FEDERATEDBYZANTINEAGREEMENTPROTOCOL This section presents the Stellar Consensus Protocol, SCP. At a high level, SCP con- sists of two sub-protocols: a nomination protocol and a ballot protocol. The nomination

TheStellar Consensus Protocol 19 protocol produces candidate values for a slot. If run long enough, it eventually pro- duces the same set of candidate values at every intact node, which means nodes can combine the candidate values in a deterministic way to produce a single composite value for the slot. There are two huge caveats, however. First, nodes have no way of knowing when the nomination protocol has reached the point of convergence. Second, even after convergence, ill-behaved nodes may be able to reset the nomination process afinite number of times. When nodes guess that the nomination protocol has converged, they execute the ballot protocol, which employs federated voting to commit and abort ballots associated with composite values. When intact nodes agree to commit a ballot, the value associ- ated with the ballot will be externalized for the slot in question. When they agree to abort a ballot, the ballot’s value becomes irrelevant. If a ballot gets stuck in a state where one or more intact nodes cannot commit or abort it, then nodes try again with a higher ballot; they associate the new ballot with the same value as the stuck one in case any node believes the stuck ballot was committed. Intuitively, safety results from ensuring that all stuck and committed ballots are associated with the same value. Liveness follows from the fact that a stuck ballot can be neutralized by moving to a higher ballot. The remainder of this section presents the nomination and ballot protocols. Each is described first in terms of conceptual statements, then as a concrete protocol with messages representing sets of conceptual statements. Finally, Section 6.3 shows the correctness of the protocol. SCP treats each slot completely independently and can be viewed as many separate instances of a single-slot consensus protocol (akin to the “single-decree synod” in Paxos [Lamport 1998]). Concepts such as candidate values andballots must always be interpreted in the context of a particular slot even if much of the discussion leaves the slot implicit. 6.1. Nomination protocol Because slots need only be partially 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]. Thenominationprotocol 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 confirmedthestatementnominatex—i.e., v has ratified accept(nominate x).

` 20 D. Mazieres 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.Assoonasvhasacandidatevalue,however,itmustceasevotingtonominatex 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. Nowconsider 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- suredbecauseonceeachintactnodeconfirmsatleastonecandidatevalue—whichwill happeninafiniteamountoftime—nointactnodeswillvotetonominateanynewval- 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,…,ℎ −1}. (H might be SHA-256 [National Institute of Standards and Technol- max ogy 2012], in which case ℎ = 2256.) Let G (m) = H(i,x , m) be a slot-specific hash max i i−1 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). Givenaslotiandaroundnumbern,eachnodevcomputesasetofneighbors andapriority for each neighbor as follows: ó ¨ ó {q ∣ q ∈ Q(v) ∧ v ∈ q} ó ó ¨ ó ó weight(v,v ) = ó ó Q(v) ó ó ¨ ó ¨ ó ¨ neighbors(v,n) = v ∣ G (N,n,v ) < ℎ ⋅ weight(v,v ) i max ¨ ¨ priority(n,v ) = G (P,n,v ) i 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 theprobability 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 v ∈ neighbors(v,0) that maximizes 0 priority(0,v ) among nodes it can communicate with, then vote to nominate the same 0 values as v . Only if v = v should v introduce a new value to nominate. v should use 0 0 timeouts to decide on new nominate statements to vote for. After n timeouts, v should

TheStellar Consensus Protocol 21 Variable Meaning X Thesetofvaluesnodevhasvotedtonominate Y Thesetofvalues node v has accepted as nominated Z Thesetofvaluesthatnodevconsiderscandidatevalues N Thesetofthelatest NOMINATE messagereceivedfromeachnode Fig. 14. Nomination state maintained by node v for each slot NOMINATEviXY 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: — {nominatex∣x∈X} (votes to nominate each value in X) — {accept(nominate x) ∣ x ∈ Y } (votes to confirm nominations in Y) Fig. 15. Messageinnominationprotocol findanodev ∈neighbors(v,n)maximizingpriority(n,v ) and vote to nominate every- n n thing v has voted to nominate. n THEOREM12. Eventually,allintact 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. Suchvalueswillneedtohavegarneredvotesfromwell-behavednodes, however,whichlimitsthemtoafiniteset.Eventually,ill-behavednodeswilleitherstop perturbingthesystemorrunoutofnewcandidatevaluestoinject,inwhichcaseintact 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 as D does not change mid-nomination (or D 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 mustcopewithdifferentcompositevaluesatdifferentnodes.Asanoptimization,then,

` 22 D. Mazieres 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 NOMINATEmessage. 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 ≥ 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. Wespeak of committing and aborting a ballot b as a shorthand for using federated votingtoagreeonthestatementscommitbandabortb,respectively.Foragivenballot, 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 mustcontainthesamevalue.Roughlyspeaking,thismeanscommitstatements are invalid if they conflict with lower-numbered unaborted ballots. Definition (compatible). Two ballots b and b are compatible, written b ∼ b , iff 1 2 1 2 b .x = b .x and incompatible, written b ≁ b , iff b .x ≠ b .x. We also write b ≲ b or 1 2 1 2 1 2 1 2 b ≳ b iff b ≤ b (or equivalently b ≥ b ) and b ∼ b . Similarly, b ⋦ b or b ⋧ b 2 1 1 2 2 1 1 2 1 2 2 1 meansb ≤b (orequivalently b ≥ b ) and b ≁ b . 1 2 2 1 1 2 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 these aborts. Tocommitaballotbandexternalizeitsvalueb.x,SCPnodesfirstacceptandconfirm 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 commitbefore acting on it in case v is befouled. 6.2.1. Concrete ballot protocol. Figure 16 illustrates the per-slot state maintained by eachnode.Anodevstores:itscurrentphase';itscurrentballotb;thetwomostrecent ¨ incompatible ballots it has prepared (p,p ); the lowest (c) and highest (ℎ) 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 ℎ are non-decreasing within a phase. In addition, if c ≠ 0—meaning v may

TheStellar Consensus Protocol 23 Variable Meaning ' Currentphase:oneof PREPARE, CONFIRM,or EXTERNALIZE b Current ballot that node v is attempting to prepare and commit (b ≠ 0) ¨ ¨ p ,p Thetwohighestballots accepted as prepared such that p ⋦ p, where ¨ ¨ p =0orp=p =0iftherearenosuchballots c,ℎ In PREPARE: ℎ is the highest ballot confirmed as prepared, or 0 if none; if c ≠ 0, then c is lowest and ℎ 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 ≲ ℎ ≲ b. z Value to use in next ballot. If ℎ = 0, then z is the composite value (see Section 6.1); otherwise, z = ℎ.x. M Setofthelatestballotmessageseenfromeachnode Fig. 16. Ballot state maintained by each node v for each slot ¨ PREPARE vibpp c.nℎ.nD 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 ℎ.x are elided as c.x = ℎ.x = b.x when c.n ≠ 0. This concrete message encodes a host of conceptual statements, as follows: ¨ ¨ ¨ — {abortb ∨ 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) ¨ ¨ — {commitb ∣c.n≠0 ∧ c ≲b ≲ℎ} (a vote to commit c,…,ℎ if c ≠ 0) CONFIRMvibp.nc.nℎ.nD Sent by v to try to externalize b.x for slot i after accepting a commit. Implies ¨ ¨ p.x = c.x = ℎ.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: — Everythingimplied by PREPARE v i ⟨∞,b.x⟩ p 0 c.n ∞ D ¨ ¨ — {accept(commitb ) ∣ c ≲ b ≲ ℎ} (a vote to confirm commit c,…,ℎ) EXTERNALIZE vixc.nℎ.nD 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 ℎ = ⟨ℎ.n,x⟩. For ¨ convenience, we also say b = p = ℎ = ⟨∞,x⟩, and p = 0. Encodes: — Everythingimplied by CONFIRM v i ⟨∞,x⟩ ∞ c.n ∞ D — Everythingimplied by CONFIRM v i ⟨∞,x⟩ ∞ c.n ℎ.n {{v}} Fig. 17. Messages in SCP’s ballot protocol have participated in ratifying commit c—code must ensure c ≲ ℎ ≲ 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 ℎ = 0, a node may update z in response to a NOMINATE message. Note

` 24 D. Mazieres 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 b ,p ,p ,… to v v v denote the values of b,p,p¨,… in node v’s state as described in Figure 16. Similarly, we ¨ let v denote message m’s sender, and b ,p ,p ,… denote the corresponding values of m m m m b,p,p¨,… in v ’s state as implied by m. 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,ℎ) 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 messageswithpeers,sendingwhicheverballotmessageisindicatedby'.Uponadding anewlyreceived message m to M , a node v updates its state as follows: v ¨ (1) If ' = PREPARE and m lets v accept new ballots as prepared, update p and p . Afterwards, if either p ⋧ ℎ or p¨ ⋧ ℎ, then set c ← 0. (2) If ' = PREPARE and m lets v confirm new higher ballots prepared, then raise ℎ to the highest such ballot and set z ← ℎ.x. ¨ (3) If ' = PREPARE, c = 0, b ≤ ℎ, and neither p ⋧ ℎ nor p ⋧ ℎ, then set c to the lowest ballot satisfying b ≤ c ≲ ℎ. (4) If ' = PREPARE and v accepts commit for one or more ballots, set c to the lowest such ballot, then set ℎ to the highest ballot such that v accepts all {commit b¨ ∣ ¨ c ≲ b ≲ ℎ}, and set ' ← CONFIRM. Also set z ← ℎ.x after updating ℎ, and unless ℎ≲b,setb←ℎ. (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 ℎ¨ be the highest ballot such that v accepts all {commit b¨ ∣ b ≲ b¨ ≲ ℎ¨} (if any). If there exists such an ℎ¨ and ℎ¨ > ℎ, then set ℎ ← ℎ¨, and, if necessary, raise c to ¨ ¨ the lowest ballot such that v accepts all {commit b ∣ c ≲ b ≲ ℎ}. (7) If ' = CONFIRM and v confirms commit c¨ for any c¨, set c and ℎ to the lowest and highest such ballots, set ' ← EXTERNALIZE, externalize c.x, and terminate. (8) If ' ∈ {PREPARE,CONFIRM} and b < ℎ, then set b ← ℎ. (9) If ' ∈ {PREPARE,CONFIRM} and ∃S ⊆ M such that the set of senders {v ¨ ∣ ¨ ¨ v m m ∈ S} is v-blocking and ∀m ∈ S, b ¨.n > b .n, then set b ← ⟨n,z⟩, where n is m v the lowest counter for which no such S exists. Repeat the previous steps after updating b. Whilec = 0,theaboveprotocolimplementsfederatedvotingtoconfirmbisprepared. Oncec ≠0,theprotocol implements federated voting on commit c¨ for every c ≲ c¨ ≲ ℎ. 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,thevalueofitsballotissafetoexternalizeassumingquorumintersection. ¨ All messages sent by a particular node are totally ordered by ⟨',b,p,p ,ℎ⟩, with ' the most significant and ℎ 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

TheStellar Consensus Protocol 25 from each node without relying on timing to order the messages, since the network mayre-order messages. Afewdetailsoftheprotocolmeritexplanation.Thestatementsimpliedby PREPARE 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 ≥ b in step 3. Because nodes never vote abort c for any c ≥ 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 ℎ—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 ℎ such that ℎ ≁ c ≠ 0, as step 1 will set c ← 0 if the new ℎ 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 ≲ ℎ}. 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 EXTERNALIZE. Eliminating D allows a single static EXTERNALIZE message to help other nodes catch up arbitrarily far in the future, even if quorum slices have changed significantly in the meantime. Only one RPC is needed to exchange ballot messages. The argument is the sender’s latest message and the return value is the receiver’s latest message. As with NOMI- NATE, if D or the values x in ballots are cryptographic hashes, then a separate RPC is needed to retrieve uncached hash preimages. 6.2.2. Timeouts and ballot updates. If all intact nodes start with the same ballot b, then steps 1 to 9 on the previous page are sufficient to confirm commit b and externalize value b.x. Unfortunately, if the ballot protocol starts before the nomination protocol hasconverged, nodes may start off with different values for z. If a ballot fails, or takes long enough that it may fail because of unresponsive nodes, then nodes must time out andtryagainwithahigherballot. For this reason, nodes employ a timer as follows: (a) A node v with ' ≠ EXTERNALIZE arms a timer whenever ∃S ⊆ M such that v v the set of senders U = {v ∣ m ∈ S } is a quorum, v ∈ U, and ∀m ∈ S, b .n ≥ b .n. m m v (b) If the timer fires, v updates its ballot by setting b ← ⟨b .n + 1,z ⟩. v v v Different nodes may start ballots at different times. However, condition (a) delays setting a timer at a node v that has gotten ahead of a quorum. Conversely, step 9 on the preceding page allows nodes that have fallen too far behind to catch up without waiting for timers. Taken together, these rules ensure that given long enough timers, intact nodes will spend time together on the same ballot; moreover, this time will grow proportionally to the timer duration. To ensure timeouts are long enough without pre- dicting latencies, an implementation can increase the timeout as a function of b.n. 6.3. Correctness AnSCPnodecannotvotetoconfirmcommitbuntilithasvotedtoconfirmabortforall lower-numberedincompatibleballots.Becauseawell-behavednodecannotaccept(and

` 26 D. Mazieres hence vote to confirm) contradictory statements, this means that for a given ⟨V,Q⟩, Theorem 5 ensures a set S of well-behaved nodes cannot externalize contradictory values so long as S enjoys quorum intersection despite V⧵S. This safety holds if V and Qchangeonlybetweenslots,butwhatiftheychangemid-slot(forinstance,inreaction to node crashes)? To reason about safety under reconfiguration, we join all old and new quorum slice sets, reflecting the fact that nodes may make decisions based on a combination of mes- sages from different configuration eras. To be very conservative, we might require quorum intersection of the aggregation of the present configuration with every past configuration. However, we can relax this slightly by separating nodes that have sent illegal messages from those that have merely crashed. THEOREM13. Let ⟨V ,Q ⟩,…,⟨V ,Q ⟩ be the set of configurations an FBAS has 1 1 k k experienced during agreement on a single slot. Let V = V ∪ ⋯ ∪ V and Q(v) = {q ∣ 1 k ∃j such that v ∈ V ∧ q ∈ Q (v)}. Let B ⊆ V be a set such that B contains all ill- j j behaved nodes that have sent illegal messages, though V⧵B may still contain crashed (unresponsive) nodes. Suppose nodes v and v are well-behaved, v externalizes x for 1 2 1 1 the slot, and v externalizes x . If ⟨V,Q⟩B enjoys quorum intersection, then x = x . 2 2 1 2 PROOF. For v to externalize x , it must have ratified accept(commit ⟨n ,x ⟩) in col- 1 1 1 1 laboration with a pseudo-quorum U ⊆ V. We say pseudo-quorum because U might 1 1 not be a quorum in ⟨V ,Q ⟩ for any particular j, as ratification may have involved j j messages spanning multiple configurations. Nonetheless, for ratification to succeed ∀v ∈ U ,∃j,∃q ∈ Q (v) such that q ⊆ U . It follows from the construction of Q that 1 j 1 q ∈ Q(v). Hence U is a quorum in ⟨V,Q⟩. By a similar argument a pseudo-quorum 1 U musthave ratified accept(commit ⟨n ,x ⟩), and U must be a quorum in ⟨V,Q⟩. By 2 2 2 2 B quorumintersection of ⟨V,Q⟩ , there must exist some v ∈ V⧵B such that v ∈ U ∩U . 1 2 By assumption, such a v ∉ B could not claim to accept incompatible ballots. Since v confirmedacceptingcommitforballotswithbothx andx ,itmustbethatx =x . 1 2 1 2 For liveness of a node v, we care about several things when an FBAS has undergone a series of reconfigurations ⟨V ,Q ⟩,…,⟨V ,Q ⟩ within a single slot. First, the safety 1 1 k k prerequisites of Theorem 13 must hold for v and the set of nodes v cares about, since violating safety undermines liveness and Theorem 11 requires quorum intersection. Second,thesetofill-behavednodesinthelateststate,⟨V ,Q ⟩,mustnotbev-blocking, k k as this could deny v a quorum and prevent it from ratifying statements. Finally, v’s state must never have been poisoned by a v-blocking set falsely claiming to accept a statement. To summarize, then, if B is the set of nodes that have sent illegal messages, we consider a node v to be cumulatively intact when the following conditions hold: (1) v is intact in the latest configuration ⟨V ,Q ⟩, k k (2) The aggregation of the present and all past configurations has quorum intersec- tion despite B (i.e., the prerequisite for Theorem 13 holds), and (3) B is not v-blocking in ⟨V ,Q ⟩ for any 1 ≤ j ≤ k. j j The next few theorems show that ill-behaved nodes cannot drive intact nodes into dead-end stuck states: THEOREM14. In an FBAS with quorum intersection, if no intact node is in the EXTERNALIZE phase and an intact node with ballot ⟨n,x⟩ arms its timer as described in Section 6.2.2, then, given sufficient communication, every intact node v can set bv ≥ n before any timer fires.

TheStellar Consensus Protocol 27 PROOF. LetS ={v∣bv ≥n}bethesetofnodeswithcountersatleastn.Byassump- tion, S contains an intact node. Furthermore, because that intact node armed its timer, S must also encompass a quorum. Let S+ be the intact subset of S, and S− be the set of intact nodes not in S. By Theorem 10, either S− = ç (in which case the theorem is trivial), or S+ is v-blocking for some v ∈ S. By step 9 on page 24, v will adjust its ballot so b .n ≥ n. At this point, repeat the argument with S ← S ∪ {v} until such point as − v S =ç. THEOREM15. Given long enough timeouts, if an intact node has reached the CON- FIRM phase with b.x = x, then eventually all intact nodes will terminate. PROOF. If an intact node has reached the EXTERNALIZE phase, it has confirmed commit c for some ballot c. By Theorem 11, all intact nodes will confirm commit c, after which they will terminate in step 7 on page 24. Otherwise, an intact node in the CONFIRM phase has accepted commit c where c = ⟨n,x⟩. Beforehand, an intact node confirmed c was prepared. By Theorem 11, all intact nodes will eventually have ℎ ≥ c. Moreover, by Theorem 8, no intact node v can accept abort c, so no intact node can accept as prepared any ballot p such that p ⋧ c. Hence, after sufficient communication, every intact node will permanently have ℎ ≳ c. The intact node or nodes with the lowest b will, by Theorem 14, raise their ballots until such point as all intact nodes with armed timers have the same ballot counter. Since they also have identical z = ℎ.x = x, they will all have the same ballot. If they cannot complete the protocol because one or more intact nodes have higher ballots, the nodes with higher numbered ballots will not have timers set. Hence, the nodes with lower- numberedballots will after a timeout set set b ← ⟨b.n+1,x⟩ until eventually all intact nodes are on the same ballot and can complete the protocol THEOREM16. Regardlessofpastill-behavior, given long enough timeouts and peri- ods in which ill-behaved nodes do not send new messages, intact nodes running SCP will terminate. PROOF. By Theorem 12, all intact nodes will eventually have identical sets Z of candidate values. Assume this point has passed and every intact node v has the same composite value z = combine(Z). If no intact node ever confirms any ballot b prepared without b.x = z, then after at most one timeout, all new ballots of intact nodes will have value z and, given a sufficient timeout, complete the protocol. By Theorem 15, nodeswill also complete if any intact node has progressed beyond the PREPARE phase. The remaining case is that an intact node has ℎ ≠ 0 and all intact nodes have ' = PREPARE.ByTheorem14,whentheintactnodeornodeswiththehighestb.narmtheir timers, if timers are long enough, other nodes will catch up. Moreover, by Theorem 11, if timers are long enough, nodes will converge on the value of ℎ (the highest confirmed prepared ballot) before the next timeout, at which point all intact nodes will raise b to the same value and complete the protocol. Theorem 16 assures us there are no dead-end states in SCP. However, a set of ill- behaved nodes with very good timing could perpetually preempt an SCP system by delaying messages so that some fraction of intact nodes update ℎ right before timers fire and the remaining update it after, preventing intact nodes from converging on the nextballot. Nodescanrecoverfromsuchanattackbyremovingill-behavednodesfrom their slices. An alternative would be to add randomness to the protocol, for instance changing step 2 on page 24 to update z with probability 1∕2 (or even with probability propor- tional to the fraction of the timer remaining). Such an approach would terminate with

` 28 D. Mazieres probability 1, but in worse expected running time for the common case that most or all nodes are well-behaved or fail-stop. 7. LIMITATIONS SCPcanonlyguaranteesafetywhennodeschooseadequatequorumslices.Section3.2 discusses why we can reasonably expect them to do so. Nonetheless, when security depends upon a user-configurable parameter, there is always the possibility people will set it wrong. Even when people set quorum slices correctly and SCP guarantees safety, safety alone does not rule out other security issues that may arise in a federated system. For example, in a financial market, widely trusted nodes could leverage their position in the network to gain information with which to engage in front running or other unethical activities. Byzantine nodes may attempt to filter transactions on the input side of SCP while otherwise producing the correct output. If well-behaved nodes accept all transactions, the combine function takes the union of transactions, and there are intact nodes, then such filtering will eventually fail to block victim transactions with probability 1, but maynonetheless impose delays. ThoughSCP’ssafetyisoptimal,itsperformanceandcommunicationlatencyarenot. In the commoncasethatnodeshavenotpreviouslyvotedtocommitballotsincompati- ble with the current one, it is possible to reduce the number of communication rounds by one. An earlier version of SCP did so, but the protocol description was more com- plex. First, it required nodes to cache and retransmit signed messages previously sent by failed nodes. Second, it was no longer possible to gloss over the distinction between votes and confirmations of abort statements in PREPARE messages, so nodes had to send around potentially unbounded lists of exceptions to their abort votes. SCPcansufferperpetualpreemptionasdiscussedinSection6.3.Anopenquestionis whether,withoutrandomness,adifferentprotocolcouldguaranteeterminationassum- ing bounded communication latency but tolerating Byzantine nodes that continuously to inject bad messages at exactly the point where timeouts fire. Such a protocol is not ruled out by the FLP impossibility result [Fischer et al. 1985]. However, the two main techniques to guarantee termination assuming synchrony do not directly apply in the FBAmodel: PBFT [Castro and Liskov 1999] chooses a leader in round-robin fashion, which is not directly applicable when nodes do not agree on membership. (Possibly something along the lines of priority in Section 6.1 could be adapted.) The Byzan- tine Generals protocol [Lamport et al. 1982] relays messages so as to compensate for ill-behaved nodes saying different things to different honest nodes, an approach that cannot help when nodes depend on distinct ill-behaved nodes in their slices. Still an- other possibility might be to leverage both randomness and synchrony to terminate with probability 1, but in shorter expected time than Ben Or-style randomized proto- cols [Ben-Or 1983] that make no synchrony assumptions. Public coin techniques [?] that speed up randomized centralized Byzantine agreement protocols appear to be dif- ficult to adapt to the federated model, barring some cryptographic breakthrough in federated threshold signatures. Unfortunately, changing slices mid-slot to accommodate failed nodes is problematic for liveness if a well-behaved node v has ever experienced a wholly malicious and col- luding v-blocking set. The good news is that Theorem 13 guarantees safety to any set S of well-behaved nodes enjoying quorum intersection despite V⧵S, even when S has befouled members. The bad news is that updating Q may be insufficient to unblock nodesifwell-behavednodesweretrickedintovotingtoconfirmabadcommitmessage. In such a situation, nodes must disavow past votes, which they can do only by rejoin- ing the system under a new node names. There may exist a way to automate such

TheStellar Consensus Protocol 29 recovery, such as having other nodes recognize reincarnated nodes and automatically update their slices. The FBA model requires continuity of participants over time. Should all nodes si- multaneously and permanently leave, restarting consensus would require central co- ordination or human-level agreement. By contrast, a proof-of-work system such as Bitcoin could undergo sudden complete turnover yet continue to operate with little hu- man intervention. On the other hand, if nodes do return, an FBAS can recover from an arbitrarily long outage, while a proof-of-work scheme would face the possibility of anattacker working on a fork during the outage. Anintriguing possibility is to leverage SCP to mediate tussles [Clark et al. 2005] by voting on changes to configuration parameters or upgrades to an application protocol. Onewaytodothisistonominatespecialmessagesthatupdateparameters.Candidate values could then consist of both a set of values and a set of parameter updates. A big limitation of this approach is that a set of malicious nodes large enough to deny the system a quorum but not large enough to undermine safety could nonetheless trigger configurationchangesbylyingandputtingconfigurationchangesinY thatwerenever ratified. It remains an open question how to vote on parameter changes in a way that requires the consent of a full quorum but also never jeopardizes liveness. 8. SUMMARY Byzantine agreement has long enabled distributed systems to achieve consensus with efficiency, standard cryptographic security, and flexibility in designating trusted par- ticipants. More recently, Bitcoin introduced the revolutionary notion of decentralized consensus, leading to many new systems and research challenges. This paper intro- duces federated Byzantine agreement (FBA), a model for achieving decentralized con- sensus while preserving the traditional benefits of Byzantine agreement. The key dis- tinction between FBA and prior Byzantine agreement systems is that FBA forms quo- rums from participants’ individual trust decisions, allowing an organic growth model similar to that of the Internet. The Stellar Consensus Protocol (SCP) is a construction for FBA that achieves optimal safety against ill-behaved participants. Acknowledgments Jed McCaleb inspired this work and provided feedback, terminology suggestions, and help thinking through numerous conjectures. Jessica Collier collaborated on writing the paper. Stan Polu created the first implementation of SCP and provided invaluable corrections, suggestions, simplifications, and feedback in the process. Jelle van den Hooff provided the key idea to restructure the paper around quorum intersection and federated voting, as well as other crucial suggestions for terminology, organization, and presentation. Nicolas Barry found several bugs in the paper as he implemented the protocol, as well as identifying necessary clarifications. Ken Birman, Bekki Bolt- house, Joseph Bonneau, Mike Hamburg, Graydon Hoare, Joyce Kim, Tim Makarios, Mark Moir, Robert Morris, Lucas Ryan, and Katherine Tom slogged through drafts of the paper, identifying errors and sources of confusion as well as providing helpful suggestions. Eva Gantz provided helpful motivation and references. Winnie Lim pro- vided guidance on figures. The reddit community and Tahoe-LAFS group pointed out a censorship weakness in an earlier version of SCP, leading to the improved nomina- tion protocol. Finally, the author would like to thank the whole Stellar team for their support, feedback, and encouragement. Disclaimer ` ProfessorMazieres’scontributiontothispublicationwasasapaidconsultant,andwas not part of his Stanford University duties or responsibilities.

` 30 D. Mazieres REFERENCES ´ EduardoA.Alchieri, Alysson Neves Bessani, Joni Silva Fraga, and Fabıola Greve. 2008. Byzantine Consensus with Unknown Participants. In Proceedings of the 12th International Conference on Principles of Distributed Systems. 22–40. JamesAspnes.2010.AModularApproachtoShared-memoryConsensus,withApplicationstothe Probabilistic-write Model. In Proceedings of the 29th Symposium on Principles of Distributed Computing. 460–467. Rachel Banning-Lover. 2015. Boatfuls of cash: how do you get money into fragile states? (February 2015). http://www.theguardian.com/global-development-professionals-network/2015/feb/19/boatfuls- of-cash-how-do-you-get-money-into-fragile-states. David Basin, Cas Cremers, Tiffany Hyun-Jin Kim, Adrian Perrig, Ralf Sasse, and Pawel Szalachowski. 2014. ARPKI: Attack Resilient Public-Key Infrastructure. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 382–393. Michael Ben-Or. 1983. Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous AgreementProtocols. In Proceedings of the 2nd Symposium on Principles of Distributed Computing. 27–30. Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, and Edward W. Felten. 2015. Research Perspectives and Challenges for Bitcoin and Cryptocurrencies. In Proceedings of the 36th IEEE Symposium on Security and Privacy. Gabriel Bracha and Sam Toueg. 1985. Asynchronous Consensus and Broadcast Protocols. Journal of the ACM32,4(Oct.1985),824–840. DannyBradbury.2013.Feathercoin hit by massive attack. (June 2013). http://www.coindesk.com/feathercoin-hit-by-massive-attack/. Vitalik Buterin. 2014. Slasher: A Punitive Proof-of-Stake Algorithm. (January 2014). https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/. Miguel Castro and Barbara Liskov. 1999. Practical byzantine fault tolerance. In Proceedings of the 3rd SymposiumonOperatingSystemsDesignandImplementation.173–186. CGAP.2008.MakingMoneyTransfersWorkforMicrofinanceInstitutions.(March2008). http://www.cgap.org/sites/default/files/CGAP-Technical-Guide-Making-Money-Transfers-Work- for-Microfinance-Institutions-A-Technical-Guide-to-Developing-and-Delivering-Money- Transfers-Mar-2008.pdf. David D. Clark, John Wroclawski, Karen R. Sollins, and Robert Braden. 2005. Tussle in Cyberspace: DefiningTomorrow’sInternet. IEEE/ACMTransactions on Networking 13, 3 (June 2005), 462–475. crazyearner. 2013. TERRACOIN ATTACKOVER1.2THATTACKCONFIRMD[sic].(July2013). https://bitcointalk.org/index.php?topic=261986.0. KouroshDavarpanah,DanKaufman,andOpheliePubellier.2015.NeuCoin:theFirstSecure, Cost-efficient and Decentralized Cryptocurrency. (March 2015). http://www.neucoin.org/en/whitepaper/download. Asli Demirguc-Kunt, Leora Klapper, Dorothe Singer, and Peter Van Oudheusden. 2015. The Global Findex Database 2014 Measuring Financial Inclusion Around the World. Policy Research Working Paper 7255. World Bank. http://www-wds.worldbank.org/external/default/WDSContentServer/WDSP/IB/2015/ 04/15/090224b082dca3aa/1_0/Rendered/PDF/The0Global0Fin0ion0around0the0world.pdf. JohnR.Douceur.2002.TheSybilAttack.InRevisedPapersfromtheFirstInternational Workshop on Peer-to-Peer Systems. 251–260. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. Journal of the ACM 35, 2 (April 1988), 288–323. Cynthia Dwork and Moni Naor. 1992. Pricing via Processing or Combatting Junk Mail. In Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. 139–147. ¨ Ittay Eyal and Emin Gun Sirer. 2013. Majority is not Enough: Bitcoin Mining is Vulnerable. (November 2013). http://arxiv.org/abs/1311.0243. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32, 2 (April 1985), 374–382. GhassanO.Karame,ElliAndroulaki,andSrdjanCapkun.2012.Double-spendingfastpaymentsinbitcoin. In Proceedings of the 2012 ACM conference on Computer and communications security. 906–917. Tiffany Hyun-Jin Kim, Lin-Shung Huang, Adrian Perring, Collin Jackson, and Virgil Gligor. 2013. Accountable Key Infrastructure (AKI): A Proposal for a Public-key Validation Infrastructure. In Proceedings of the 22nd International Conference on World Wide Web. 679–690.

TheStellar Consensus Protocol 31 SunnyKingandScottNadal.2012.PPCoin:Peer-to-PeerCrypto-Currency with Proof-of-Stake. (August 2012). http://peercoin.net/assets/paper/peercoin-paper.pdf. Jae Kwon. 2014. Tendermint: Consensus without Mining. (2014). http://tendermint.com/docs/tendermint.pdf. Leslie Lamport. 1998. The Part-Time Parliament. 16, 2 (May 1998), 133–169. Leslie Lamport. 2011a. Brief Announcement: Leaderless Byzantine Paxos. In Proceedings of the 25th International Conference on Distributed Computing. 141–142. Leslie Lamport. 2011b. Byzantizing Paxos by Refinement. In Proceedings of the 25th International Conference on Distributed Computing. 211–224. Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programing Languages and Systems 4, 3 (July 1982), 382–401. AdamLangley.2015.Maintainingdigital certificate security. (March 2015). http: //googleonlinesecurity.blogspot.com/2015/03/maintaining-digital-certificate-security.html. BenLaurie, AdamLangley, and Emilia Kasper. 2013. Certificate Transparency. RFC 6962. Internet Engineering Task Force (IETF). http://tools.ietf.org/html/rfc6962. ` Jinyuan Li and David Mazieres. 2007. Beyond One-third Faulty Replicas in Byzantine Fault Tolerant Systems. In Proceedings of the 4th Symposium on Networked Systems Design and Implementation. 131–144. Marcela S. Melara, Aaron Blankstein, Joseph Bonneau, Michael J. Freedman, and Edward W. Felten. 2014. CONIKS:APrivacy-PreservingConsistent Key Service for Secure End-to-End Communication. Cryptology ePrint Archive, Report 2014/1004. (December 2014). http://eprint.iacr.org/2014/1004. Microsoft. 2013. Fraudulent Digital Certificates Could Allow Spoofing. Microsoft Security Advisory 2798897. (January 2013). https://technet.microsoft.com/en-us/library/security/2798897.aspx. Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008). http://bitcoin.org/bitcoin.pdf. National Institute of Standards and Technology. 2012. Secure Hash Standard (SHS). Federal Information Processing Standards Publication 180-4. http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf. William B. Norton. 2010. The Art of Peering: The Peering Playbook. (August 2010). http://drpeering.net/white-papers/Art-Of-Peering-The-Peering-Playbook.html. Karl J. O’Dwyer and David Malone. 2014. Bitcoin Mining and its Energy Footprint. In Irish Signals and Systems Conference. Limerick, Ireland, 280–285. Brian M. Oki and Barbara H. Liskov. 1988. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In Proceedings of the 7th Symposium on Principles of Distributed Computing. 8–17. Diego Ongaro and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In 2014 USENIXAnnualTechnicalConference.305–319. Marshall Pease, Robert Shostak, and Leslie Lamport. 1980. Reaching Agreement in the Presence of Faults. Journal of the ACM 27, 2 (April 1980), 228–234. Claire Provost. 2013. Why do Africans pay the most to send money home? (January 2013). http://www.theguardian.com/global-development/2013/jan/30/africans-pay-most-send-money. David Schwartz, Noah Youngs, and Arthur Britto. 2014. The Ripple Protocol Consensus Algorithm. (2014). https://ripple.com/files/ripple_consensus_whitepaper.pdf. Dale Skeen and Michael Stonebraker. 1983. A Formal Model of Crash Recovery in a Distributed System. IEEETransactions on Software Engineering 9, 3 (May 1983), 219–228. ´ Robbert van Renesse, Nicolas Schiper, and Fred B. Schneider. 2014. Vive la Difference: Paxos vs. ViewstampedReplication vs. Zab. IEEE Transactions on Dependable and Secure Computing (September 2014).

` 32 D. Mazieres A. GLOSSARYOFNOTATION Notation Name Definition iff Anabbreviation of “if and only if” f ∶ A → B function Function f maps each element of set A to a result in set B. f(x) application Theresult of calculating function f on argument x ā complement Anoverbarconnotes the opposite, i.e., ā is the opposite of a. ⟨a ,…,a ⟩ tuple Astructure (compound value) with field values a ,…,a 1 n 1 n A ∧ B logical and Both A and B are true. A ∨ B logical or At least one, possibly both, of A and B are true. ∃e,C(e) there exists There is at least one value e for which condition C(e) is true. ∀e,C(e) for all C(e) is true of every value e. {a,b,…} set Asetcontaining the listed elements (a,b,…) {e ∣ C(e)} set-builder Thesetofall elements e for which C(e) is true ç emptyset Thesetcontaining no elements ðSð cardinality ThenumberofelementsinsetS e ∈ S element of ElementeisamemberofsetS. A⊆B subset Every memberofsetAisalsoamemberofsetB. A⫋B strict subset A⊆BandA≠B. A 2 powerset Thesetofsets containing every possible combination of members of A, i.e., 2A = {B ∣ B ⊆ A} A∪B union Thesetcontaining all elements that are members of A or members of B, i.e., A ∪ B = {e ∣ e ∈ A ∨ e ∈ B} A∩B intersection Thesetcontaining all elements that are members of both A and B, i.e., A∩B={e∣e∈A ∧ e∈B} A⧵B set difference Thesetcontaining every element of A that is not a member of B, i.e., A⧵B={e∣e∈A ∧ e∉B} ̸ not Negates a symbol’s meaning. E.g., e ∉ A means e ∈ A is false, while ∄e,C(e) means no e exists such that C(e) is true.