ReadWhitepaper

Abstract

International payments are slow and expensive, in part because of multi-hop payment routing through heterogeneous banking systems. Stellar is a new global payment network that can directly transfer digital money anywhere in the world in seconds. The key innovation is a secure transaction mechanism across untrusted intermediaries, using a new Byzantine agreement protocol called SCP. With SCP, each institution specifies other institutions with which to remain in agreement; through the global interconnectedness of the financial system, the whole network then agrees on atomic transactions spanning arbitrary institutions, with no solvency or exchange-rate risk from intermediary asset issuers or market makers. We present SCP’s model, protocol, and formal verification; describe the Stellar payment network; and finally evaluate Stellar empirically through benchmarks and our experience with several years of production use. CCS Concepts • Security and privacy →Distributed systems security; • Computer systems organization → Peer-to-peer architectures; • Information systems → Electronic funds transfer. Keywords blockchain, BFT, quorums, payments ACM Reference Format: Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, Jed McCaleb. 2019. Fast and secure global payments with Stellar. In SOSP ’19: Symposium on Operating Systems Principles, October 27–30, 2019, Huntsville, ON, Canada. ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/3341301.3359636

Résumé

Les paiements internationaux sont lents et coûteux, en partie à cause du routage des paiements à plusieurs niveaux via des réseaux hétérogènes. systèmes bancaires. Stellar est un nouveau réseau de paiement mondial qui peut transférer directement de l'argent numérique n'importe où dans le monde en quelques secondes. L'innovation clé est une transaction sécurisée mécanisme entre intermédiaires non fiables, en utilisant un nouveau Protocole d'accord byzantin appelé SCP. Avec SCP, chacun l'établissement précise les autres établissements avec lesquels rester en accord; grâce à l’interconnectivité mondiale des système financier, l’ensemble du réseau s’accorde alors sur le nucléaire transactions impliquant des institutions arbitraires, sans risque de solvabilité ou de change de la part des émetteurs d’actifs intermédiaires ou des teneurs de marché. Nous présentons le modèle, le protocole et vérification formelle; décrire le réseau de paiement Stellar ; et enfin évaluer Stellar empiriquement à travers des benchmarks et notre expérience avec plusieurs années d'utilisation en production. Concepts du CSC • Sécurité et confidentialité →Distribué sécurité des systèmes ; • Organisation des systèmes informatiques → Architectures peer-to-peer ; • Systèmes d'information → Transfert électronique de fonds. Mots-clés blockchain, BFT, quorums, paiements Format de référence ACM : Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, Jed McCaleb. 2019. Paiements mondiaux rapides et sécurisés avec Stellar. Dans SOSP '19 : Symposium sur les principes des systèmes d'exploitation, du 27 au 30 octobre 2019, Huntsville, Ontario, Canada. ACM, New York, NY, États-Unis, 17 pages. https://doi.org/10.1145/3341301.3359636

Introduction

International payments are notoriously slow and costly [32]. Consider the impracticality of sending $0.50 from the U.S. to *Galois, Inc. †UCLA Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada © 2019 Association for Computing Machinery. ACM ISBN 978-1-4503-6873-5/19/10...$15.00 https://doi.org/10.1145/3341301.3359636 Mexico, two neighboring countries. End users pay nearly $9 for the average such transfer [32], and a bilateral agreement brokered by the countries’ central banks could only reduce the underlying bank cost to $0.67 per item [2]. On top of fees, the latency of international payments is generally counted in days, making it impossible to get money abroad quickly in emergencies. In countries where the banking system doesn’t work or doesn’t serve all citizens, or where fees are intolerable, people resort to sending payments by bus [38], by boat [19], and occasionally now by Bitcoin [55], all of which incur risk, latency, or inconvenience. While there will always be compliance costs, evidence suggests a significant amount is lost to lack of competition [21], which is exacerbated by inefficient technology. Where people can innovate, prices and latencies go down. For instance, remittances from bank accounts in Q2 2019 cost an average of 6.99%, while the figure for mobile money was only 4.88% [13]. An open, global payment network that attracts innovation and competition from non-bank entities could drive down costs and latencies at all layers, including compliance [83]. This paper presents Stellar, a blockchain-based payment network specifically designed to facilitate innovation and competition in international payments. Stellar is the first system to meet all three of the following goals (under a novel but empirically valid “Internet hypothesis”): 1. Open membership – Anyone can issue currency-backed digital tokens that can be exchanged among users. 2. Issuer-enforced finality – A token’s issuer can prevent transactions in the token from being reversed or undone. 3. Cross-issuer atomicity – Users can atomically exchange and trade tokens from multiple issuers. Achieving the first two is easy. Any company can unilaterally offer a product such as Paypal, Venmo, WeChat Pay, or Alipay and ensure the finality of payments in the virtual currencies they have created. Unfortunately, transacting atomically across these currencies is impossible. In fact, despite Paypal having acquired Venmo’s parent company in 2013, it is still impossible for end users to send Venmo dollars to Paypal users [78]. Only recently can merchants even accept both with a single integration. Goals 2 and 3 can be achieved in a closed system. In particular, a number of countries have efficient domestic payment networks, typically overseen by a universally trusted regulatory authority. However, membership is limited to a closed set of chartered banks and the networks are limited to the reach of a country’s regulatory authority.

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. Goals 1 and 3 have been achieved in mined blockchains, most notably in the form of ERC20 tokens on Ethereum [3]. The key idea of these blockchains is to create a new cryptocurrency with which to reward people for making settled transactions hard to revert. Unfortunately, this means token issuers do not control transaction finality. If software errors cause transactions history to be reorganized [26, 73], or when the spoils of defrauding people exceed the cost of reorganizing history [74, 97], issuers may be liable for tokens they have already redeemed for real-world money. The Stellar blockchain has two distinguishing properties. First, it natively supports efficient markets between tokens from different issuers. Specifically, anyone can issue a token, the blockchain provides a built-in orderbook for trade between any pair of tokens, and users can issue path payments that atomically trade across several currency pairs while guaranteeing an end-to-end limit price. Second, Stellar introduces a new Byzantine agreement protocol, SCP (Stellar Consensus Protocol), through which token issuers designate specific validator servers to enforce transaction finality. So long as no one compromises an issuer’s validators (and the underlying digital signatures and cryptographic hashes remain secure), the issuer knows exactly which transactions have occurred and avoids the risk of losses from blockchain history reorganization. SCP’s key idea is that most asset issuers benefit from liquid markets and want to facilitate atomic transactions with other assets. Hence, validator administrators configure their servers to agree with other validators on the exact history of all transactions on all assets. A validator v1 can be configured to agree with v2, or v2 can be configured to agree with v1, or both may be configured to agree with each other; in all cases, neither will commit to a transaction history until it knows the other cannot commit to a different history. By transitivity, if v1 cannot disagree with v2 and v2 cannot disagree with v3 (or vice versa), v1 cannot disagree with v3, whether or not v3 represents assets v1 has even heard of. Under the hypothesis that these agreement relationships transitively connect the whole network, SCP guarantees global agreement, making it a global Byzantine agreement protocol with open membership. We call this new connectedness assumption the Internet hypothesis, and note that it holds of both “the Internet” (which everyone understands to mean the single largest transitively connected IP network) and legacy international payments (which are hop-by-hop non-atomic, but leverage a transitively connected, global network of financial institutions). Stellar has been in production use since September, 2015. To keep the blockchain length manageable, the system runs SCP at 5-second intervals—fast by blockchain standards, but far slower than typical applications of Byzantine agreement. Though the primary use has been payments, Stellar has also proven appealing for non-money fungible tokens that benefit from immediate secondary markets (see Section 7.1). The next section discusses related work. Section 3 presents SCP. Section 4 describes our formal verification of SCP. Section 5 describes Stellar’s payment layer. Section 6 relates some of our deployment experience and lessons learned. Section 7 evaluates the system. Section 8 concludes.

Introduction

Les paiements internationaux sont notoirement lents et coûteux [32]. Considérez l’impossibilité d’envoyer 0,50 $ des États-Unis vers *Galois, Inc. †UCLA Autorisation de faire des copies numériques ou papier de tout ou partie de ce travail pour l'utilisation personnelle ou en classe est autorisée sans frais à condition que les copies ne soient pas réalisés ou distribués dans un but lucratif ou pour un avantage commercial et que les copies portent cet avis et la citation complète sur la première page. Droits d'auteur pour les composants de ce travail appartenant à d’autres qu’ACM doit être honoré. Abstraction avec le crédit est autorisé. Pour copier autrement, ou republier, pour publier sur des serveurs ou pour la redistribution à des listes nécessite une autorisation spécifique préalable et/ou des frais. Demande autorisations de [email protected]. SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada © 2019 Association pour les machines informatiques. ACM ISBN 978-1-4503-6873-5/19/10...15,00 $ https://doi.org/10.1145/3341301.3359636 Le Mexique, deux pays voisins. Les utilisateurs finaux paient près de 9 $ pour la moyenne de ce transfert [32], et un accord bilatéral négociés par les banques centrales des pays ne pouvaient que réduire le coût bancaire sous-jacent à 0,67 $ par article [2]. En plus des frais, la latence des paiements internationaux est généralement comptée en quelques jours, ce qui rend impossible l'obtention rapide d'argent à l'étranger en urgences. Dans les pays où le système bancaire ne fonctionne pas fonctionne ou ne sert pas tous les citoyens, ou lorsque les frais sont intolérables, les gens ont recours à l'envoi de paiements par bus [38], par bateau [19], et occasionnellement maintenant par Bitcoin [55], le tout encourir des risques, des latences ou des désagréments. Même s'il y aura toujours des coûts de mise en conformité, les éléments de preuve suggèrent qu'un montant important est perdu en raison du manque de concurrence [21], ce qui est exacerbé par une technologie inefficace. Où les gens peut innover, les prix et les latences diminuent. Par exemple, les envois de fonds depuis des comptes bancaires au deuxième trimestre 2019 coûtaient en moyenne 6,99%, alors que le chiffre pour l'argent mobile n'était que de 4,88% [13]. Un réseau de paiement ouvert et mondial qui attire l’innovation et la concurrence des entités non bancaires pourrait faire baisser coûts et latences à tous les niveaux, y compris la conformité [83]. Ce document présente Stellar, un paiement basé sur blockchain réseau spécialement conçu pour faciliter l’innovation et concurrence dans les paiements internationaux. Stellar est le premier système pour atteindre les trois objectifs suivants (dans le cadre d’un « hypothèse Internet nouvelle mais empiriquement valable » : 1. Adhésion ouverte – N’importe qui peut émettre des titres adossés à des devises token numériques pouvant être échangés entre utilisateurs. 2. Finalité imposée par l'émetteur – L'émetteur d'un token peut empêcher les transactions dans le token ne soient pas annulées ou annulées. 3. Atomicité entre émetteurs – Les utilisateurs peuvent échanger atomiquement et négociez des token de plusieurs émetteurs. Atteindre les deux premiers est facile. Toute entreprise peut proposer unilatéralement un produit tel que Paypal, Venmo, WeChat Pay, ou Alipay et assurez la finalité des paiements dans les délais monnaies virtuelles qu'ils ont créées. Malheureusement, les transactions atomiques entre ces devises sont impossibles. En fait, bien que Paypal ait acquis la société mère de Venmo en 2013, il est toujours impossible pour les utilisateurs finaux d'envoyer du Venmo dollars aux utilisateurs Paypal [78]. Ce n'est que récemment que les commerçants peuvent acceptez même les deux avec une seule intégration. Les objectifs 2 et 3 peuvent être atteints dans un système fermé. En particulier, un certain nombre de pays disposent de systèmes de paiement nationaux efficaces. réseaux, généralement supervisés par une autorité de régulation universellement fiable. Toutefois, l'adhésion est limitée à un groupe fermé ensemble de banques à charte et les réseaux se limitent au portée de l’autorité de régulation d’un pays.SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. Les objectifs 1 et 3 ont été atteints dans les blockchain extraits, notamment sous la forme d'ERC20 token sur Ethereum [3]. L'idée clé de ces blockchain est de créer une nouvelle crypto-monnaie avec laquelle récompenser les personnes qui s'installent. transactions difficiles à annuler. Malheureusement, cela signifie que les émetteurs token ne contrôlent pas le caractère définitif des transactions. Si le logiciel les erreurs provoquent une réorganisation de l'historique des transactions [26, 73], ou lorsque le butin des fraudeurs dépasse le coût de en réorganisant l'historique [74, 97], les émetteurs peuvent être responsables de tokens ils ont déjà échangé contre de l'argent réel. Le Stellar blockchain possède deux propriétés distinctives. Premièrement, il prend en charge nativement les marchés efficaces entre tokens provenant de différents émetteurs. Plus précisément, n'importe qui peut émettre un token, le blockchain fournit un carnet d'ordres intégré pour les échanges entre n'importe quelle paire de token, et les utilisateurs peuvent émettre des paiements de chemin qui négocient atomiquement sur plusieurs paires de devises tout en garantissant un prix limite de bout en bout. Deuxièmement, Stellar introduit un nouvel accord byzantin protocole, SCP (Stellar Consensus Protocol), à travers lequel Les émetteurs token désignent des serveurs validator spécifiques à appliquer finalité de la transaction. Tant que personne ne compromet les validator d’un émetteur (et les signatures numériques et les hashes cryptographiques restent sécurisés), l'émetteur sait exactement quelles transactions ont eu lieu et évite le risque des pertes résultant de la réorganisation de l'historique blockchain. L’idée clé de SCP est que la plupart des émetteurs d’actifs bénéficient des marchés liquides et veulent faciliter les transactions atomiques avec d'autres actifs. Par conséquent, les administrateurs validator configurent leurs serveurs pour se mettre d'accord avec d'autres validator sur les détails exacts historique de toutes les transactions sur tous les actifs. Un validator v1 peut être configuré pour être d'accord avec la v2, ou la v2 peut être configurée pour être d'accord avec la version v1, ou les deux peuvent être configurés pour s'accorder ; dans tous les cas, ni l'un ni l'autre ne s'engagera sur un historique des transactions jusqu'à ce que il sait que l’autre ne peut pas s’engager dans une histoire différente. Par transitivité, si v1 ne peut pas être en désaccord avec v2 et v2 ne peut pas être en désaccord avec v3 (ou vice versa), v1 ne peut pas être en désaccord avec v3, que v3 représente ou non des actifs dont v1 a même entendu parler de. Sous l’hypothèse que ces relations d’accord connecter transitivement l'ensemble du réseau, garantit SCP accord mondial, ce qui en fait un accord byzantin mondial protocole avec adhésion ouverte. Nous appelons cette nouvelle hypothèse de connectivité l’hypothèse d’Internet et notons qu’elle détient à la fois « Internet » (que tout le monde comprend comme signifie le plus grand réseau IP connecté de manière transitive) et les anciens paiements internationaux (qui sont effectués étape par étape non atomique, mais exploite un système global et connecté de manière transitive. réseau d’institutions financières). Stellar est utilisé en production depuis septembre 2015. Pour que la longueur blockchain reste gérable, le système exécute SCP à intervalles de 5 secondes – rapide selon les normes blockchain, mais beaucoup plus lente que les applications typiques de l’accord byzantin. Bien que l'utilisation principale ait été les paiements, Stellar a également s'est avéré attrayant pour les token non monétaires fongibles qui bénéficient provenant des marchés secondaires immédiats (voir la section 7.1). La section suivante traite des travaux connexes. La section 3 présente SCP. La section 4 décrit notre vérification formelle de SCP. La section 5 décrit la couche de paiement de Stellar. La section 6 concerne une partie de notre expérience de déploiement et des leçons apprises. La section 7 évalue le système. La section 8 conclut.

Related work

The system described in this paper is collectively our third attempt to realize a decentralized payment network. The first attempt, by one of the authors, resulted in the Ripple blockchain. While still in existence, we believe Ripple cannot realize the vision of a truly open payment network for both governance and technical reasons. The governance reasons derive from tension between shareholder interests and network users, but are beyond the scope of this paper. The technical issue is that Ripple’s Byzantine agreement protocol [89] requires nearly closed membership [33], making it functionally similar to conventional Byzantine agreement. The second attempt, a short-lived fork of the Ripple code base called stellard, went live in July, 2014. We had planned to develop SCP and slot it into stellard when ready, but instead decided to build a new system from scratch around SCP, called stellar-core and described in this paper. stellar-core was released along with a description and proof of SCP [68] in April, 2015, and entered production use 5 months later. An Internet draft [20] later described SCP for implementors. SCP’s motivation and structure are similar to asymmetric trust in multiparty computation [40], though that model requires nodes to have a global view of the adversary structure. By introducing a notion of quorum slices, SCP enjoys discoverability and dynamic membership that are important to Stellar’s deployment. Personal Byzantine quorum systems [47] and asymmetric distributed trust [29] generalize SCP’s quorums and simplify comparison to traditional systems. In a more restricted setting, Gotsman et al. [49] also study a generalization of Stellar’s quorums. Several other blockchains have adopted SCP, including MobileCoin [7] and NCNT. Ripple also more recently proposed an open-membership Byzantine agreement protocol called Cobalt [66]. SCP’s safety is optimal, so SCP is safe in any failure scenario where Cobalt is, while the converse is unclear. However, Cobalt claims its safety condition is easier to understand and thus less prone to misconfiguration, which will be interesting to evaluate if Cobalt gets deployed. 2.1 Systems without open membership Like many consensus protocols, SCP is based on voting [50, 94] in a quorum system. Previous work on quorum systems [52, 67, 72], sometimes called “survivor sets” [57], studies quorum systems that are static, i.e., fixed throughout system execution, and uniform, i.e., where all nodes have the same notion of what a quorum is. SCP’s setting is different in that different nodes accept different and evolving quorums.

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Heterogeneous fast consensus [91] allows more nuanced notions of trust to be expressed via labels in a lattice and leverages this to optimize communication, but it assumes closed membership. Other efforts to adapt Byzantine agreement protocols to Blockchain-like settings, including HoneyBadger [70], SBFT [53], and HotStuff [99], have focused on scalability to many participants and performance over wide-area networks, retaining the traditional closed-membership model. Blockchains targeting closed membership have leveraged such protocols, including most recently Libra [11]. 2.2 Systems without issuer-enforced finality Bitcoin [71] was the first fungible digital asset without a trusted authority to track balances. It simultaneously solved two problems: how to distribute a new asset so people believe it has value, and how to provide irreversible transactions that prevent double-spend attacks. Bitcoin creates assets through proof-of-work [43], which its author compares to gold miners investing resources to increase the supply of gold. The proved work depends on transaction history, which thwarts double-spend attacks because rolling back transactions requires work comparable to creating the original history. Attacks on proof-of-work blockchains become feasible once an attacker controls 1/3 of mining power [46, 48]. Proofof-work is particularly risky for new or smaller blockchains [15, 23]; established miners have been known to divert mining power to smaller chains for profit [10, 54, 74, 97, 98] or just to create problems [25, 37] (so-called “Goldfinger attacks” [60]). At times, miners have benevolently mounted such “51% attacks” to roll back the undesired effects of bugs [95]. New blockchains can gain some protection from 51% attacks by leveraging more established blockchains with merged mining [6] or proof of burn [79]. As of this writing, a 51% attack is estimated to cost $823,000/ hour on Bitcoin, $93,000/hour on Ethereum, and under $20,000/ hour for all other tracked blockchains [12]. Ultimately, these costs depend on the value of the cryptocurrency incentivizing the mining, which is independent of the value of issued assets. By contrast, the cost of compromising Stellar validators is somewhat under the control of their administrators; SCP is amenable to high-assurance implementations, such as using hardware security modules to prevent a validator from signing contradictory messages. As an additional benefit, Stellar has no mining costs to recoup through transaction fees or seigniorage. Bitcoin’s massive energy consumption [76] has motivated more energy-efficient variations of proof of work such as proof of space [16, 17, 44, 87], proof of storage [18, 56, 86, 90], and proof of elapsed time [4]. Proof of work can be slow, with blocks of transactions taking minutes to confirm and multiple blocks required for stronger security. However, the work to mine a block can be amortized over an arbitrary-sized batch of transactions, constrained only by political issues and compatibility. BitcoinNG [45] uses proof of work to elect a leader who coordinates a larger batch of transactions. Thunderella [84] can use proofof-work as a fallback “slow path” and optimistically confirm transactions much faster using an asynchronous consensus protocol when an accelerator node and 3/4 of an elected committee are honest. Though SCP is faster than proof-of-work, it requires more messages than Thunderella’s fast path, but could potentially be a useful Thunderella slow path. An alternative to proof of work is proof of stake [59], in which miners obtain influence either directly or indirectly from asset ownership. In some cases, influence increases with the time assets have been held. Some schemes encourage honesty by confiscating miners’ stake if they misbehave [27, 28, 41]. Delegated proof-of-stake [9, 61] has nodes vote their stake to elect representatives for a conventional Byzantine agreement protocol such as PBFT [31]. Algorand [51] uses verifiable random functions to elect representative nodes pseudorandomly, with probability proportional to cryptocurrency holdings. Snow White [39] formalizes the security properties required in proof of stake, accommodating “sleepy” nodes that go on and off line. Though most proof-of-stake schemes cannot be bruteforced with expensive computation, the cost to acquire stake or bribe miners is still related to the value of the underlying cryptocurrency and outside an asset issuer’s control. Even in the absence of malicious miners, bugs can also cause blockchain reorganization [26, 73]. Hence, unlike with SCP, issuers have no way to ensure blockchain finality before redeeming on-chain tokens for a real-world wire transfer or cash withdrawal.

Travaux connexes

Le système décrit dans cet article est collectivement notre troisième tenter de réaliser un réseau de paiement décentralisé. Le la première tentative, par l'un des auteurs, a abouti au Ripple blockchain. Bien qu'il existe encore, nous pensons que Ripple ne peut pas réaliser la vision d'un réseau de paiement véritablement ouvert pour à la fois pour des raisons de gouvernance et techniques. Les raisons de gouvernance découlent des tensions entre les intérêts des actionnaires et utilisateurs du réseau, mais dépassent le cadre de cet article. Le Le problème technique est que le protocole d'accord byzantin de Ripple [89] nécessite une adhésion presque fermée [33], ce qui en fait fonctionnellement similaire à l’accord byzantin conventionnel. La deuxième tentative, un fork éphémère du code Ripple base appelée Stellard, a été mise en service en juillet 2014. Nous avions prévu de développer SCP et l'insérer dans Stellard lorsqu'il est prêt, mais à la place a décidé de construire un nouveau système à partir de zéro autour de SCP, appelé noyau stellaire et décrit dans cet article. noyau stellaire a été libéré avec une description et une preuve de SCP [68] en avril 2015 et est entré en production 5 mois plus tard. Un brouillon Internet [20] a décrit plus tard SCP pour les implémenteurs. La motivation et la structure de SCP sont similaires à la confiance asymétrique dans le calcul multipartite [40], bien que ce modèle nécessite que les nœuds aient une vue globale de la structure de l’adversaire. En introduisant une notion de tranches de quorum, SCP bénéficie la découvrabilité et l’adhésion dynamique qui sont importantes pour le déploiement de Stellar. Quorum byzantin personnel Les systèmes [47] et la confiance distribuée asymétrique [29] généralisent les quorums de SCP et simplifient la comparaison avec les systèmes traditionnels. systèmes. Dans un cadre plus restreint, Gotsman et al. [49] également étudier une généralisation des quorums de Stellar. Plusieurs autres blockchain ont adopté SCP, notamment MobileCoin [7] et NCNT. Ripple a également proposé plus récemment un protocole d'accord byzantin à adhésion ouverte. appelé Cobalt [66]. La sécurité de SCP est optimale, donc SCP est en sécurité dans tout scénario d'échec où se trouve le cobalt, alors que l'inverse est peu clair. Cependant, Cobalt affirme que sa condition de sécurité est plus facile à comprendre et donc moins sujette à une mauvaise configuration, ce qui sera intéressant d’évaluer si Cobalt sera déployé. 2.1 Systèmes sans adhésion ouverte Comme de nombreux protocoles de consensus, SCP est basé sur le vote [50, 94] dans un système de quorum. Des travaux antérieurs sur les systèmes de quorum [52, 67, 72], parfois appelés « ensembles de survivants » [57], étudient les systèmes de quorum qui sont statiques, c'est-à-dire fixes tout au long de l'année. exécution du système et uniforme, c'est-à-dire où tous les nœuds ont le même notion de ce qu'est un quorum. Le paramètre de SCP est différent dans que différents nœuds acceptent des quorums différents et évolutifs.Paiements mondiaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Un consensus rapide et hétérogène [91] permet des analyses plus nuancées notions de confiance à exprimer via des étiquettes dans un treillis et exploite cela pour optimiser la communication, mais cela suppose adhésion fermée. Autres efforts pour adapter les protocoles d'accord byzantins aux paramètres de type Blockchain, y compris HoneyBadger [70], SBFT [53] et HotStuff [99] se sont concentrés sur l'évolutivité à de nombreux participants et des performances sur des réseaux étendus, en conservant le modèle traditionnel à adhésion fermée. Les blockchains ciblant les membres fermés ont tiré parti de tels protocoles, y compris plus récemment Libra [11]. 2.2 Systèmes sans caractère définitif imposé par l'émetteur Bitcoin [71] a été le premier actif numérique fongible sans autorité de confiance pour suivre les soldes. Il a simultanément résolu deux problèmes : comment distribuer un nouvel actif pour que les gens croient il a de la valeur, et comment fournir des transactions irréversibles qui empêcher les attaques à double dépense. Bitcoin crée des actifs grâce à proof-of-work [43], que son auteur compare aux mineurs d'or qui investissent des ressources pour augmenter l'offre d'or. Le le travail prouvé dépend de l’historique des transactions, ce qui contrecarre attaques à double dépense, car l'annulation des transactions nécessite un travail comparable à la création de l'historique d'origine. Les attaques contre les proof-of-work blockchain deviennent possibles une fois qu'un attaquant contrôle 1/3 de la puissance minière [46, 48]. La preuve de travail est particulièrement risquée pour les blockchain nouveaux ou plus petits [15, 23]; on sait que les mineurs établis détournent l'exploitation minière pouvoir aux petites chaînes pour le profit [10, 54, 74, 97, 98] ou simplement pour créer des problèmes [25, 37] (appelés « attaques Goldfinger » [60]). Parfois, les mineurs ont monté avec bienveillance de telles « attaques à 51 % » pour annuler les effets indésirables des bugs [95]. Nouveau Les blockchain peuvent obtenir une certaine protection contre 51 % des attaques en tirer parti de blockchain plus établis avec une exploitation minière fusionnée [6] ou une preuve de brûlage [79]. Au moment d'écrire ces lignes, une attaque à 51 % est estimée à 823 000 $/ heure sur Bitcoin, $93,000/hour on Ethereum, and under $20 000/ heure pour tous les autres blockchain suivis [12]. En fin de compte, ces les coûts dépendent de la valeur de la cryptomonnaie incitant au minage, qui est indépendante de la valeur de l'émission. actifs. En revanche, le coût de la compromission des Stellar validator est dans une certaine mesure sous le contrôle de leurs administrateurs ; SCP se prête à des implémentations à haute assurance, telles que en utilisant des modules de sécurité matériels pour empêcher un validator de signer des messages contradictoires. Comme avantage supplémentaire, Stellar n'a aucun coût minier à récupérer via la transaction droits ou seigneuriage. La consommation énergétique massive de Bitcoin [76] a motivé des variantes de preuve de travail plus économes en énergie telles que preuve d'espace [16, 17, 44, 87], preuve de stockage [18, 56, 86, 90], et une preuve du temps écoulé [4]. La preuve de travail peut être lente, avec des blocs de transactions prendre quelques minutes pour confirmer et plusieurs blocs requis pour une sécurité renforcée. Cependant, le travail pour extraire un bloc peut être amorti sur un lot de transactions de taille arbitraire, limité uniquement par des questions politiques et de compatibilité. BitcoinNG [45] utilise une preuve de travail pour élire un leader qui coordonne un plus grand lot de transactions. Thunderella [84] peut utiliser la preuve de travail comme « chemin lent » de secours et confirmer avec optimisme transactions beaucoup plus rapides grâce à un consensus asynchrone protocole quand un nœud accélérateur et les 3/4 d'un comité élu sont honnêtes. Bien que SCP soit plus rapide que proof-of-work, cela nécessite plus de messages que le chemin rapide de Thunderella, mais pourrait potentiellement être un chemin lent utile pour Thunderella. Une alternative à la preuve de travail est la preuve d'enjeu [59], dans lequel les mineurs obtiennent une influence directe ou indirecte de la propriété des actifs. Dans certains cas, l’influence augmente avec la durée de détention des actifs. Certains schémas encourager l’honnêteté en confisquant les parts des mineurs s’ils se comporter mal [27, 28, 41]. Le délégué proof-of-stake [9, 61] a les nœuds votent selon leur participation pour élire des représentants pour un protocole d'accord byzantin conventionnel tel que PBFT [31]. Algorand [51] utilise des fonctions aléatoires vérifiables pour élire des nœuds représentatifs de manière pseudo-aléatoire, avec une probabilité proportionnelle aux avoirs en crypto-monnaie. Blanche-Neige [39] officialise le propriétés de sécurité requises dans la preuve d'enjeu, accueillant des nœuds « endormis » qui continuent ethors ligne. Bien que la plupart des schémas proof-of-stake ne puissent pas être forcés par des calculs coûteux, le coût d'acquisition de la participation ou la corruption des mineurs est toujours liée à la valeur de la cryptomonnaie sous-jacente et échappe au contrôle de l’émetteur d’actifs. Même en l'absence de mineurs malveillants, les bugs peuvent également provoquer blockchain réorganisation [26, 73]. Ainsi, contrairement à SCP, les émetteurs n'ont aucun moyen de garantir le caractère définitif de blockchain avant échanger des token en chaîne contre un virement bancaire réel ou retrait d'espèces.

Stellar consensus protocol

The Stellar consensus protocol (SCP) is a quorum-based Byzantine agreement protocol with open membership. Quorums emerge from the combined local configuration decisions of individual nodes. However, nodes only recognize quorums to which they belong themselves, and only after learning the local configurations of all other quorum members. One benefit of this approach is that SCP inherently tolerates heterogeneous views of what nodes exist. Hence, nodes can join and leave unilaterally with no need for a “view change” protocol to coordinate membership. 3.1 Federated Byzantine agreement The traditional Byzantine agreement problem consists of a closed system of N nodes, some of which are faulty and may behave arbitrarily. Nodes receive input values and exchange messages to decide on an output value among the inputs. A Byzantine agreement protocol is safe when no two wellbehaved nodes output different decisions and the unique decision was a valid input (for some definition of valid agreed

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. upon beforehand). A protocol is live when it guarantees that every honest node eventually outputs a decision. Typically, protocols assume N = 3f + 1 for some integer f > 0, then guarantee safety and some form of liveness so long as at most f nodes are faulty. At some stage in these protocols, nodes vote on proposed values and a proposal receiving 2f + 1 votes, called a quorum of votes, becomes the decision. With N = 3f + 1 nodes, any two quorums of size 2f + 1 overlap in at least f + 1 nodes; even if f of these overlapping nodes are faulty, the two quorums share at least one non-faulty node, preventing contradictory decisions. However, this approach only works if all nodes agree on what constitutes a quorum, which is impossible in SCP where two nodes may not even know of each other’s existence. With SCP, each node v unilaterally declares sets of nodes, called its quorum slices, such that (a) v believes that if all members of a slice agree about the state of the system, then they are right, and (b) v believes that at least one of its slices will be available to provide timely information about the state of the system. We call the resulting system, consisting of nodes and their slices, a Federated Byzantine Agreement (FBA) system. As we will see next, a quorum system emerges from nodes’ slices. Informally, an FBA node’s slices express with whom the node requires agreement. E.g., a node may require agreement with 4 specific organizations, each running 3 nodes; to accommodate downtime, it may set its slices to be all sets consisting of 2 nodes from each organization. If this “requires agreement with” relation transitively relates any two nodes, we get global agreement. Otherwise, we can get divergence, but only between organizations neither of which requires agreement with the other. Given the topology of today’s financial system, we hypothesize that widespread convergence will keep producing a singe ledger history people call “the Stellar network,” much as we speak of the Internet. Quorums arise from slices as follows. Every node specifies its quorum slices in every message it sends. Let S be the set of nodes from which a set of messages originated. A node considers the set of messages to have reached quorum threshold when every member of S has a slice included in S. By construction, such a set S, if unanimous, satisfies the agreement requirements of each of its members. A faulty peer may advertise slices crafted to change what well-behaved nodes consider quorums. For the sake of protocol analysis, we define a quorum in FBA to be a non-empty set S of nodes encompassing at least one quorum slice of each non-faulty member. This abstraction is sound, as any set of messages purporting to represent a unanimous quorum actually does (even if it contains messages from faulty nodes), and it is precise when S contains only well-behaved nodes. In this section, we also assume that nodes’ slices do not change. Nevertheless, our results transfer to the changing-slice case because a system in which slices change is no less safe than a fixed-slice system in which a node’s slices consist of all the slices it ever uses in the changing-slices case (see Theorem 13 in [68]). As explained in Section 4, liveness depends on well-behaved nodes eventually removing unreliable nodes from their slices. Because different nodes have different agreement requirements, FBA precludes a global definition of safety. We say non-faulty nodes v1 and v2 are intertwined when every quorum of v1 intersects every quorum of v2 in at least one non-faulty node. An FBA protocol can ensure agreement only between intertwined nodes; since SCP does so, its fault tolerance for safety is optimal. The Internet hypothesis, underlying Stellar’s design, states that the nodes people care about will be intertwined. We say a set of nodes I is intact if I is a uniformly nonfaulty quorum such that every two members of I are intertwined even if every node outside of I is faulty. Intuitively, then, I should remain impervious to the actions of non-intact nodes. SCP guarantees both non-blocking liveness [93] and safety to intact sets, though nodes themselves do not need to know (and may not be able to know) which sets are intact. Furthermore, the union of two intact sets that intersect is an intact set. Therefore, intact sets define a partition of the well-behaved nodes, where each partition is safe and live (under some conditions), but different partitions may output divergent decisions. 3.1.1 Safety vs. Liveness considerations in FBA With limited exceptions [64], most closed Byzantine agreement protocols are tuned to the equilibrium point at which safety and liveness have the same fault tolerance. In FBA, that means configurations in which, regardless of failures, all intertwined sets are also intact. Given that FBA determines quorums in a decentralized way, it is unlikely that individual slice choices will lead to this equilibrium. Moreover, at least in Stellar, equilibrium is not desirable: the consequences of a safety failure (namely double-spent digital money) are far worse than those of a liveness failure (namely delays in payments that anyway took days before Stellar). People therefore should and do select large quorum slices such that their nodes are more likely to remain intertwined than intact. Further tipping the scales, it is easier to recover from typical liveness failures in an FBA system than in a traditional closed one. In closed systems, all messages must be interpreted with respect to the same set of quorums. Hence, adding and removing nodes to recover from failure requires reaching consensus on a reconfiguration event, which is difficult once consensus is no longer live. By contrast, with FBA, any node can unilaterally adjust its quorum slices at any time. In response to an outage at a systemically important organization, node administrators can adjust their slices to work around the problem, a bit like coordinating responses to BGP catastrophes [63] (though without the constraints of routing over physical network links).

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada 3.1.2 The cascade theorem SCP follows the template of the basic round model [42]; nodes progress through a series of numbered ballots, each attempting three tasks: (1) identify a “safe” value not contradicted by any decision in a previous ballot (often termed preparing the ballot), (2) agree on the safe value, and (3) detect that agreement was successful. However, FBA’s open membership stymies several common techniques, making it impossible to “port” traditional closed protocols to the FBA model by simply changing the definition of quorum. One technique employed by many protocols is rotating through leader nodes in round-robin fashion following timeouts. In a closed system, round-robin leader selection ensures that eventually a unique honest leader ends up coordinating agreement on a single value. Unfortunately, round-robin cannot work in an FBA system with unknown membership. Another common technique that fails with FBA is assuming a particular quorum can convince all nodes. For instance, if everyone recognizes any 2f + 1 nodes as a quorum, then 2f + 1 signatures suffice to prove protocol state to all nodes. Similarly, if a node receives a quorum of identical messages through reliable broadcast [24], the node can assume all nonfaulty nodes will also see a quorum. In FBA, by contrast, a quorum means nothing to nodes outside the quorum. Finally, non-federated systems often employ “backwards” reasoning about safety: if f + 1 nodes are faulty, all safety guarantees are lost. Hence, if node v hears f + 1 nodes all state some fact F, v can assume at least one is telling the truth (and hence that F is true) with no loss of safety. Such reasoning fails in FBA because safety is a property of pairs of nodes, so a node that has lost safety to some peers can always lose safety to more nodes by assuming bad facts. FBA can, however, reason backwards about liveness. Define a v-blocking set as a set of nodes that intersects every slice of v. If a v-blocking set B is unanimously faulty, B can deny node v a quorum and cost it liveness. Hence, if B unanimously states fact F, then v knows that either F is true or v is not intact. However, v still needs to see a full quorum to know that intertwined nodes won’t contradict F, which leads to a final round of communication in SCP and other FBA protocols [47] that is not required in analogous closed-membership protocols. The result is that we have three possible levels of confidence in potential facts: indeterminate, safe to assume among intact nodes (which we will term accepted facts), and safe to assume among intertwined nodes (which we will term confirmed facts). Node v can efficiently determine whether a set B is vblocking by checking whether B intersects all its slices. Interestingly, if nodes always announce the statements they accept and a full quorum accepts a statement, it sets off a cascading process by which statements propagate throughout intact sets. We call the key fact underlying this propagation the cascade theorem, which sates the following: If I is an intact set, Q is a quorum of any member of I, and S is any superset of Q, then either $S \supseteq I$ or there is a member $v \in I$ such that $v \notin S$ and $I \cap S$ is $v$-blocking. Intuitively, were this not the case, the complement of S would contain a quorum that intersects I but not Q, violating quorum intersection. Note that if we start with S = Q and repeatedly expand S to include all nodes it blocks, we obtain a cascading effect until, eventually, S encompasses all of I. 3.2 Protocol description SCP is a partially synchronous consensus protocol [42] consisting of a series of attempts to reach consensus called ballots. Ballots employ timeouts of increasing duration. A ballot-synchronization protocol ensures that nodes stay on the same ballot for increasing periods of time until the ballots are effectively synchronous. Termination is not guaranteed until ballots are synchronous, but two synchronous ballots in which faulty members of well-behaved nodes’ slices do not interfere are sufficient for SCP to terminate. A balloting protocol specifies the actions taken during each ballot. A ballot begins with a prepare phase, in which nodes try to determine a value to propose that does not contradict any previous decision. Then, in a commit phase, nodes try to make a decision on the prepared value. Balloting employs an agreement sub-protocol called federated voting, in which nodes vote on abstract statements that may eventually be confirmed or get stuck. Some statements might be designated contradictory, and the safety guarantee of federated voting is that no two members of an intertwined set confirm contradictory statements. Confirmation of a statement is not guaranteed except for an intact set whose members all vote the same way. However, if a member of an intact set does confirm a statement, federated voting guarantees that all members of the intact set eventually confirm that statement. Hence, taking irreversible steps in response to confirming statements preserves liveness for intact nodes. Nodes initially propose values obtained from a nomination protocol that increases the chances of all members of an intact set proposing the same value, and that eventually converges (though with no way to determine convergence is complete). Nomination combines federated voting with leader selection. Because round-robin is impossible in FBA, nomination uses a probabilistic leader-selection scheme. The cascade theorem plays a crucial role both in ballot synchronization and in avoiding blocked states from which termination is no longer possible. 3.2.1 Balloting SCP nodes proceed through a series of numbered ballots, employing federated voting to agree on statements about which values are or are not decided in which ballots. If asynchrony or faulty behavior prevents reaching a decision in ballot n, nodes time out and try again in ballot n + 1.

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. Recall federated voting might not terminate. Hence, some statements about ballots can get stuck in a permanently indeterminate state where nodes can never determine if they are still in progress or stuck. Because nodes cannot rule out the possibility of indeterminate statements later proving true, they must never attempt federated voting on new statements contradicting indeterminate ones. In each ballot n, nodes use federated voting on two types of statement: • prepare ⟨n,x⟩– states that no value other than x was or will ever be decided in any ballot $\leq n$. • commit $\langle n, x \rangle$ – states $x$ is decided in ballot $n$. Importantly, note that prepare $\langle n, x \rangle$ contradicts commit $\langle n', x' \rangle$ when $n \geq n'$ and $x \neq x'$. A node starts ballot n by attempting federated voting on a statement prepare ⟨n,x⟩. If any previous prepare statement was successfully confirmed through federated voting, the node chooses x from the confirmed prepare of the highest ballot. Otherwise, the node sets x to the output of the nomination protocol described in the next subsection. If and only if a node successfully confirms prepare ⟨n,x⟩ in ballot n, it attempts federated voting on commit ⟨n,x⟩. If that succeeds, it means SCP has decided, so the node outputs the value from the confirmed commit statement. Consider an intertwined set S. Since at most one value can be confirmed prepared by members of S in a given ballot, no two different values may be confirmed committed by members of S in a given ballot. Moreover, if commit ⟨n,x⟩ is confirmed, then prepare ⟨n,x⟩was confirmed too; since prepare ⟨n,x⟩contradicts any earlier commit for a different value, by the agreement guarantees of federated voting we get that no different value may be decided in an earlier ballot by members of S. By induction on ballot numbers, we therefore get that SCP is safe. For liveness, consider an intact set I and a long enough synchronous ballot n. If faulty nodes appearing in the slices of well-behaved nodes do not interfere in n, then by ballot n + 1 all members of I have confirmed the same set P of prepare statements. If P = ∅and ballot n was long enough, the nomination protocol will have converged on some value x. Otherwise, let x be the value from the prepare with the highest ballot in P. Either way, I will uniformly attempt federated voting on prepare ⟨n + 1,x⟩in the next ballot. Therefore, if n + 1 is also synchronous, a decision for x inevitably follows. 3.2.2 Nomination Nomination entails federated voting on statements: • nominate x – states x is a valid decision candidate. Nodes may vote to nominate multiple values—different nominate statements are not contradictory. However, once a node confirms any nominate statement, it stops voting to nominate new values. Federated voting still allows a node to confirm new nominate statements it didn’t vote for, which vote-or-accept a from quorum accept a from quorum a is valid accept a from blocking set uncommitted voted a accepted a confirmed a voted ¬a Figure 1. Stages of federated voting allows members of an intact set to confirm one another’s nominated values while still withholding new votes. The (evolving) result of nomination is a deterministic combination of all values in confirmed nominate statements. If x represents a set of transactions, nodes can take the union of sets, the largest set, or the one with the highest hash, so long as all nodes do the same. Because nodes withhold new votes after confirming one nominate statement, the set of confirmed statements can contain only finitely many values. The fact that confirmed statements reliably spread through intact sets means intact nodes eventually converge on the same set of nominated values and hence nomination result, though at an unknown point arbitrarily late in the protocol. Nodes employ federated leader selection to reduce the number of different values in nominate statements. Only a leader who has not already voted for a nominate statement may introduce a new x. Other nodes wait to hear from leaders and just copy their leaders’ (valid) nominate votes. To accommodate failure, the set of leaders keeps growing as timeouts occur, though in practice only a few nodes introduce new values of x. 3.2.3 Federated voting Federated voting employs a three-phase protocol shown in Figure 1. Nodes try to agree on abstract statements by first voting, then accepting, and finally confirming statements. A node v may vote for any valid statement a that does not contradict its other outstanding votes and accepted statements. It does so by broadcasting a signed vote message. v then accepts a if a is consistent with other accepted statements and either (case 1)v is a member of a quorum in which each node either votes for a or accepts a, or (case 2) even if v didn’t vote for a, a v-blocking set accepts a. In case 2, v may have previously cast votes contradicting a, which have now been overruled. v is allowed to forget about overruled votes and pretend it never cast them because ifv is intact, it knows overruled votes cannot complete a quorum through case 1. v broadcasts that it accepts a, then confirms a when it is in a quorum that unanimously accepts a. Figure 2 shows the effect of v-blocking sets and the cascade theorem during federated voting. Two intertwined nodes cannot confirm contradictory statements, as the two required quorums would have to share a

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada 3 4 2 1 5 7

Protocole de consensus Stellar

Le protocole de consensus (SCP) Stellar est un protocole basé sur le quorum. Protocole d'accord byzantin avec adhésion ouverte. Les quorums émergent des décisions combinées de configuration locale des nœuds individuels. Cependant, les nœuds ne reconnaissent que collèges auxquels ils appartiennent eux-mêmes, et seulement après apprendre les configurations locales de tous les autres membres du collège. L'un des avantages de cette approche est que SCP est intrinsèquement tolère des vues hétérogènes sur les nœuds existants. Hence, les nœuds peuvent rejoindre et quitter unilatéralement sans avoir besoin d'un protocole « visualiser le changement » pour coordonner l'adhésion. 3.1 Accord byzantin fédéré Le problème traditionnel de l’accord byzantin consiste en un système fermé de N nœuds, dont certains sont défaillants et peuvent behave arbitrarily. Les nœuds reçoivent des valeurs d'entrée et échangent messages pour décider d’une valeur de sortie parmi les entrées. Un protocole d'accord byzantin est sûr lorsqu'il n'y a pas deux nœuds bien élevés qui produisent des décisions différentes et l'unique la décision était une contribution valable (pour une définition d’un accord valideSOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. au préalable). Un protocole est opérationnel lorsqu'il garantit que chaque nœud honnête finit par produire une décision. Généralement, les protocoles supposent N = 3f + 1 pour un nombre entier f > 0, alors garantir la sécurité et une certaine forme de vivacité donc tant qu'au plus les nœuds f sont défectueux. À un moment donné de ces protocoles, les nœuds votent sur les valeurs proposées et une proposition recevoir 2f + 1 voix, appelé quorum de voix, devient la décision. Avec N = 3f + 1 nœuds, deux quorums quelconques de la taille 2f + 1 se chevauche dans au moins f + 1 nœuds ; même si f d'entre eux les nœuds qui se chevauchent sont défectueux, les deux quorums partagent au moins un nœud non défectueux, évitant ainsi les décisions contradictoires. Cependant, cette approche ne fonctionne que si tous les nœuds sont d'accord sur ce qui constitue un quorum, ce qui est impossible dans SCP où deux nœuds peuvent même ne pas connaître l’existence de l’autre. Avec SCP, chaque nœud v déclare unilatéralement des ensembles de nœuds, appelé ses tranches de quorum, telles que (a) v croit que si tous les membres d'une tranche sont d'accord sur l'état du système, alors ils ont raison, et (b) v croit qu'au moins une de ses tranches sera disponible pour fournir des informations en temps opportun sur état du système. Nous appelons le système résultant, constitué de nœuds et de leurs tranches, un accord byzantin fédéré (FBA). Comme nous le verrons ensuite, un système de quorum émerge à partir des tranches des nœuds. De manière informelle, les tranches d'un nœud FBA expriment avec qui le le nœud nécessite un accord. Par exemple, un nœud peut nécessiter un accord avec 4 organisations spécifiques, chacune exécutant 3 nœuds ; à s'adapter aux temps d'arrêt, il peut définir ses tranches pour qu'elles soient toutes définies composé de 2 nœuds de chaque organisation. Si cela « nécessite La relation « accord avec » relie transitivement deux nœuds quelconques, nous obtenons un accord mondial. Sinon, nous pouvons obtenir une divergence, mais seulement entre organisations, ce qui ne nécessite aucune accord avec l'autre. Compte tenu de la topologie actuelle système financier, nous émettons l’hypothèse qu’une convergence généralisée continuera à produire un registre unique que les gens appellent «le réseau Stellar», tout comme nous parlons d'Internet. Les quorums proviennent des tranches comme suit. Chaque nœud spécifie son quorum tranche dans chaque message qu'il envoie. Soit S le ensemble de nœuds à partir duquel un ensemble de messages provient. Un le nœud considère que l'ensemble des messages a atteint le quorum seuil lorsque chaque membre de S a une tranche incluse dans S. Par construction, un tel ensemble S, s’il est unanime, satisfait au exigences contractuelles de chacun de ses membres. Un homologue défectueux peut annoncer des tranches conçues pour changer ce qui les nœuds bien élevés considèrent les quorums. Par souci d'analyse protocolaire, nous définissons un quorum dans FBA comme étant un quorum non vide. ensemble S de nœuds englobant au moins une tranche de quorum de chaque membre non fautif. Cette abstraction est saine, comme tout ensemble de messages prétendant représenter un quorum unanime le fait réellement (même s'il contient des messages provenant de nœuds défectueux), et c'est précis lorsque S ne contient que des nœuds bien élevés. Dans dans cette section, nous supposons également que les tranches des nœuds ne changent pas. Néanmoins, nos résultats sont transférables au cas du changement de tranche car un système dans lequel les tranches changent n'est pas moins sûr qu'un un système à tranches fixes dans lequel les tranches d’un nœud sont constituées de tous les tranches qu'il utilise dans le cas des tranches changeantes (voir le théorème 13 dans [68]). Comme expliqué dans la section 4, la vivacité dépend de les nœuds bien élevés suppriment finalement les nœuds peu fiables de leurs tranches. Étant donné que les différents nœuds ont des exigences d'accord différentes, FBA exclut une définition globale de la sécurité. Nous disons les nœuds non défectueux v1 et v2 sont entrelacés à chaque fois le quorum de v1 croise chaque quorum de v2 dans au moins un nœud non défectueux. Un protocole FBA peut garantir un accord uniquement entre les nœuds entrelacés ; puisque SCP le fait, c'est de la faute la tolérance en matière de sécurité est optimale. L'hypothèse d'Internet, qui sous-tend la conception de Stellar, indique que les nœuds dont les gens se soucient à propos sera entrelacé. Nous disons qu'un ensemble de nœuds I est intact si I est un quorum uniformément non défectueux tel que tous les deux membres de I sont entrelacés même si chaque nœud en dehors de I est défectueux. Intuitivement, alors, je devrais rester imperméable aux actions des personnes non intactes nœuds. SCP garantit à la fois la vivacité non bloquante [93] et sécurité aux ensembles intacts, bien que les nœuds eux-mêmes n'aient pas besoin pour savoir (et peut-être ne pas pouvoir savoir) quels ensembles sont intacts. De plus, l’union de deux ensembles intacts qui se croisent est un ensemble intact. Par conséquent, les ensembles intacts définissent une partition du des nœuds bien élevés, où chaque partition est sûre et active (sous certaines conditions), mais différentes partitions peuvent afficher des décisions divergentes. 3.1.1 Considérations relatives à la sécurité et à la vivacité dans FBA À quelques exceptions près [64], la plupart des protocoles d'accords byzantins fermés sont adaptés au point d'équilibre auquel la sécurité et la vivacité ont la même tolérance aux pannes. Dans Expédié par Amazon, cela signifie des configurations dans lesquelles, quelles que soient les pannes, tous les ensembles entrelacés sont également intacts. Étant donné que Expédié par Amazon détermine quorums de manière décentralisée, il est peu probable que les choix individuels des tranches conduisent à cet équilibre. De plus, à au moins en Stellar, l'équilibre n'est pas souhaitable : les conséquences d'une défaillance de sécurité (à savoir de l'argent numérique dépensé en double) sont bien pires que ceux d'un échec de vivacité (à savoir des retards en paiements qui ont de toute façon pris des jours avant le Stellar). Les gens par conséquent, nous devrions sélectionner et sélectionnons de grandes tranches de quorum telles que leurs nœuds sont plus susceptibles de rester entrelacés qu’intacts. En faisant encore pencher la balance, il est plus facile de se remettre de échecs de vivacité typiques dans un système FBA que dans un système fermé traditionnel. Dans les systèmes fermés, tous les messages doivent être interprété par rapport au même ensemble de quorums. Par conséquent, l'ajout et la suppression de nœuds pour récupérer après une panne nécessitent parvenir à un consensus sur un événement de reconfiguration, ce qui est difficile une fois que le consensus n’est plus d’actualité. En revanche, avec FBA, n'importe quel nœud peut ajuster unilatéralement ses tranches de quorum à tout moment. le temps. En réponse à une panne dans un site d'importance systémique organisation, les administrateurs de nœuds peuvent ajuster leurs tranches en fonction contourner le problème, un peu comme coordonner les réponses aux catastrophes BGP [63] (mais sans les contraintes de routage sur des liens réseau physiques).

Paiements internationaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada 3.1.2 Le théorème des cascades SCP suit le modèle du modèle rond de base [42] ; les nœuds progressent à travers une série de bulletins de vote numérotés, chacun tenter trois tâches : (1) identifier une valeur « sûre » qui n'est contredite par aucune décision lors d'un scrutin précédent (souvent appelée préparer le scrutin), (2) s'entendre sur la valeur sûre et (3) détecter que l'accord a été conclu. Cependant, FBA est ouvert l'adhésion bloque plusieurs techniques courantes, ce qui rend impossible de « porter » les protocoles fermés traditionnels vers le FBA modèle en changeant simplement la définition du quorum. Une technique utilisée par de nombreux protocoles est la rotation via les nœuds leaders de manière circulaire après les délais d'attente. Dans un système fermé, la sélection des leaders à tour de rôle garantit qu'au final, un leader honnête et unique finit par coordonner un accord sur une valeur unique. Malheureusement, le tournoi à la ronde ne peut pas fonctionner dans un système FBA avec une adhésion inconnue. Une autre technique courante qui échoue avec FBA consiste à supposer qu'un quorum particulier peut convaincre tous les nœuds. Par exemple, si tout le monde reconnaît des nœuds 2f + 1 comme quorum, alors Les signatures 2f + 1 suffisent pour prouver l'état du protocole à tous les nœuds. De même, si un nœud reçoit un quorum de messages identiques grâce à une diffusion fiable [24], le nœud peut supposer que tous les nœuds non défectueux verront également un quorum. Dans FBA, en revanche, un le quorum ne signifie rien pour les nœuds en dehors du quorum. Enfin, les systèmes non fédérés emploient souvent des raisonnement sur la sécurité : si les nœuds f + 1 sont défectueux, toute la sécurité les garanties sont perdues. Par conséquent, si le nœud v entend tous les nœuds f + 1 énoncer un fait F, v peut supposer qu'au moins l'un d'eux dit au vérité (et donc que F est vrai) sans perte de sécurité. Tel le raisonnement échoue dans FBA car la sécurité est une propriété des paires de nœuds, donc un nœud qui a perdu sa sécurité au profit de certains pairs peut perdez toujours la sécurité sur plus de nœuds en supposant de mauvais faits. Expédié par Amazon peut cependant raisonner à rebours sur la vivacité. Définir un ensemble de blocage en V comme un ensemble de nœuds qui se croisent tous les tranche de v. Si un ensemble de blocage en v B est unanimement défectueux, B peut refuser au nœud v un quorum et lui coûter de la vivacité. Par conséquent, si B énonce à l’unanimité le fait F, alors v sait que soit F est vrai ou v n’est pas intact. Cependant, v a encore besoin de voir un aperçu complet quorum pour savoir que les nœuds entrelacés ne contrediront pas F, ce qui mène à un dernier cycle de communication dans SCP et d'autres protocoles FBA [47] qui ne sont pas requis dans des protocoles d’adhésion fermée. Le résultat est que nous avons trois niveaux de confiance possibles dans des faits potentiels : indéterminé, sûr à supposer parmi les nœuds intacts (que nous allons terme faits acceptés), et on peut le supposer en toute sécurité parmi les nœuds (que nous appellerons faits confirmés). Le nœud v peut déterminer efficacement si un ensemble B est vbloquant en vérifiant si B coupe toutes ses tranches. Il est intéressant de noter que si les nœuds annoncent toujours les déclarations qu'ils accepter et qu'un quorum complet accepte une déclaration, cela déclenche un processus en cascade par lequel les déclarations se propagent partout ensembles intacts. Nous appelons le fait clé qui sous-tend cette propagation le théorème de la cascade, qui énonce ce qui suit : Si I est un ensemble intact, Q est un quorum de n'importe quel membre de I, et S est n'importe quel surensemble de Q, alors soit S ⊇I soit il y a un membre v ∈I tel que v < S et I ∩S est v-bloquant. Intuitivement, était-ce ce n'est pas le cas, le complément de S contiendrait un quorum qui coupe I mais pas Q, violant l'intersection du quorum. Notez que si nous commençons par S = Q et développons S à plusieurs reprises pour inclure tous les nœuds qu'il bloque, on obtient un effet en cascade jusqu'à ce que, finalement, S englobe tout I. 3.2 Description du protocole SCP est un protocole de consensus partiellement synchrone [42] composé d'une série de tentatives pour parvenir à un consensus appelées bulletins de vote. Les bulletins de vote utilisent des délais d'attente de durée croissante. Un le protocole de synchronisation des bulletins de vote garantit que les nœuds restent activés le même scrutin pour des périodes croissantes jusqu'aux scrutins sont effectivement synchrones. La résiliation n'est pas garantie jusqu'à ce que les scrutins soient synchrones, mais deux scrutins synchrones dans lequel font les membres défectueux des tranches de nœuds bien élevés ne pas interférer sont suffisants pour que SCP se termine. Un protocole de vote précise les actions menées lors de chaque bulletin de vote. Un scrutin commence par une phase de préparation, au cours de laquelle les nœuds essayer de déterminer une valeur à proposer qui ne contredit pas toute décision antérieure. Ensuite, dans une phase de validation, les nœuds essaient pour prendre une décision sur la valeur préparée. Le scrutin utilise un sous-protocole d'accord appelé vote fédéré, jen quels nœuds votent sur des déclarations abstraites cela pourrait éventuellement être confirmé ou rester bloqué. Certaines déclarations peuvent être qualifiées de contradictoires et la sécurité La garantie du vote fédéré est qu'il n'y a pas deux membres d'un un ensemble entrelacé confirme des déclarations contradictoires. La confirmation d'une déclaration n'est pas garantie sauf pour une déclaration intacte ensemble dont les membres votent tous de la même manière. Cependant, si un un membre d'un ensemble intact confirme une déclaration, fédérée le vote garantit que tous les membres de l’ensemble intact finissent par confirmer cette déclaration. Par conséquent, prendre des mesures irréversibles en réponse aux déclarations confirmatives préserve la vivacité pour nœuds intacts. Les nœuds proposent initialement des valeurs obtenues à partir d'une nomination protocole qui augmente les chances de tous les membres d’un groupe intact ensemble proposant la même valeur, et qui finit par converger (bien qu'il n'y ait aucun moyen de déterminer que la convergence est complète). La nomination combine le vote fédéré et la sélection des dirigeants. Parce que le round-robin est impossible dans FBA, la nomination utilise un système probabiliste de sélection des dirigeants. Le théorème de la cascade joue un rôle crucial à la fois dans le scrutin synchronisation et en évitant les états bloqués à partir desquels la résiliation n’est plus possible. 3.2.1 Vote Les nœuds SCP procèdent à une série de scrutins numérotés, en utilisant le vote fédéré pour se mettre d'accord sur des déclarations sur lesquelles les valeurs sont ou ne sont pas décidées dans quels scrutins. Si asynchronie ou un comportement fautif empêche de parvenir à une décision au scrutin n, les nœuds expirent et réessayez au scrutin n + 1.

SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. Le vote fédéré de rappel pourrait ne pas prendre fin. Ainsi, certains les déclarations sur les bulletins de vote peuvent rester bloquées de façon permanente état indéterminé où les nœuds ne peuvent jamais déterminer s'ils sont toujours en cours ou bloqués. Parce que les nœuds ne peuvent pas exclure la possibilité que des déclarations indéterminées s'avèrent plus tard vraies, ils ne doivent jamais tenter de voter de manière fédérée sur de nouvelles déclarations contredisant les indéterminés. A chaque scrutin n, les nœuds utilisent le vote fédéré sur deux types de déclaration: • préparer ⟨n,x⟩– indique qu'aucune valeur autre que x a été ou sera un jour décidé lors d’un scrutin ≤n. • commit ⟨n,x⟩– indique que x est décidé lors du scrutin n. Surtout, notez que préparer ⟨n,x⟩contradit le commit ⟨n′,x ′⟩quand n ≥n′ et x , x ′. Un nœud démarre le scrutin n en tentant un vote fédéré sur un instruction préparer ⟨n,x⟩. Si une instruction de préparation précédente a été confirmé avec succès par un vote fédéré, le Le nœud choisit x dans le plan confirmé du scrutin le plus élevé. Sinon, le nœud définit x sur la sortie du protocole de nomination décrit dans la sous-section suivante. Si et seulement si un nœud confirme avec succès, préparez ⟨n,x⟩ lors du scrutin n, il tente un vote fédéré sur le commit ⟨n,x⟩. Si qui réussit, cela signifie que SCP a décidé, donc le nœud sort la valeur de l'instruction de validation confirmée. Considérons un ensemble entrelacé S. Puisqu'au plus une valeur peuvent être confirmées préparées par les membres de S lors d'un scrutin donné, deux valeurs différentes ne peuvent pas être confirmées par membres de S lors d’un scrutin donné. De plus, si commit ⟨n,x⟩ est confirmé, alors préparer ⟨n,x⟩a également été confirmé ; depuis préparer ⟨n,x⟩contredit tout engagement antérieur pour une valeur différente, par l'accord garantissant le vote fédéré nous obtenons qu'aucune valeur différente ne peut être décidée dans un précédent scrutin par les membres de S. Par induction sur les numéros de scrutin, on assurez-vous donc que SCP est en sécurité. Pour la vivacité, considérons un ensemble I intact et suffisamment long vote synchrone n. Si des nœuds défaillants apparaissent dans les tranches des nœuds bien élevés n'interfèrent pas dans n, alors par scrutin n + 1 tous les membres de I ont confirmé le même ensemble P d'instructions de préparation. Si P = ∅ et que le scrutin n était suffisamment long, le le protocole de nomination aura convergé vers une certaine valeur x. Sinon, soit x la valeur du plan avec le vote le plus élevé dans P. Quoi qu'il en soit, je tenterai uniformément de fédérer voter sur la préparation ⟨n + 1,x⟩au prochain scrutin. Par conséquent, si n + 1 est également synchrone, une décision pour x s'ensuit inévitablement. 3.2.2 Nomination La nomination implique un vote fédéré sur les déclarations : • Nommer x – déclare que x est un candidat à la décision valide. Les nœuds peuvent voter pour désigner plusieurs valeurs, différentes les déclarations de nomination ne sont pas contradictoires. Cependant, une fois un nœud confirme toute déclaration nominative, il arrête de voter pour nommer de nouvelles valeurs. Le vote fédéré permet toujours à un nœud de confirmer les nouvelles déclarations nominatives pour lesquelles il n'a pas voté, ce qui voter ou accepter un du quorum accepter un du quorum a est valide accepter un de ensemble de blocage non engagé a voté un accepté un a confirmé un a voté ¬a Figure 1. Étapes du vote fédéré permet aux membres d’un ensemble intact de se confirmer mutuellement valeurs proposées tout en retenant de nouveaux votes. Le résultat (évolutif) de la nomination est une combinaison déterministe de toutes les valeurs contenues dans les déclarations de nomination confirmées. Si x représente un ensemble de transactions, les nœuds peuvent prendre l'union d'ensembles, l'ensemble le plus grand ou celui avec le hash le plus élevé, donc tant que tous les nœuds font de même. Parce que les nœuds retiennent les nouvelles votes après avoir confirmé une déclaration de nomination, l'ensemble des les déclarations confirmées ne peuvent contenir qu’un nombre fini de valeurs. Le fait que des déclarations confirmées se soient répandues de manière fiable les ensembles intacts signifient que les nœuds intacts finissent par converger vers le même ensemble de valeurs nominées et donc résultat de la nomination, mais à un moment inconnu, arbitrairement tard dans le protocole. Les nœuds utilisent la sélection de leaders fédérés pour réduire le nombre de valeurs différentes dans les instructions nominatives. Seulement un leader qui n'a pas encore voté pour une déclaration de nomination peut introduire un nouveau x. D'autres nœuds attendent des nouvelles dirigeants et copiez simplement les votes de nomination (valides) de leurs dirigeants. Pour faire face à l'échec, l'ensemble des dirigeants ne cesse de croître à mesure que des délais d'attente se produisent, bien qu'en pratique, seuls quelques nœuds introduisent de nouvelles valeurs de x. 3.2.3 Vote fédéré Le vote fédéré utilise un protocole en trois phases illustré dans Figure 1. Les nœuds tentent de se mettre d'accord sur des déclarations abstraites en premier voter, puis accepter et enfin confirmer les déclarations. Un nœud v peut voter pour toute déclaration valide a qui ne correspond pas à contredire son autrevotes en suspens et déclarations acceptées. Pour ce faire, il diffuse un message de vote signé. v accepte alors a si a est cohérent avec d'autres déclarations acceptées et soit (cas 1) v est membre d'un quorum dans lequel chaque nœud vote pour a ou accepte a, ou (cas 2) même si v n'a pas voté pour un, un ensemble de blocage en V accepte un. Dans le cas 2, v peut ont déjà voté contre a, qui ont maintenant été rejetée. v est autorisé à oublier les votes annulés et faire comme s'il ne les avait jamais lancés car si V est intact, il le sait les votes annulés ne peuvent pas atteindre le quorum dans le cas 1. v diffuse qu'il accepte a, puis confirme a lorsqu'il est en un quorum qui accepte à l'unanimité a. La figure 2 montre le effet des ensembles v-bloquants et du théorème de la cascade pendant vote fédéré. Deux nœuds entrelacés ne peuvent pas confirmer des déclarations contradictoires, car les deux quorums requis devraient partager unPaiements internationaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada 3 4 2 1 5 7

Vote X

Vote Y (a) 3 4 2 1 5 7 6 Vote X Vote X Vote X Vote Y Vote X Vote Y Vote Y (b) 3 4 2 1 5 7 6 Accept X Vote X Accept X Vote Y Accept X Vote Y Vote Y (c) 3 4 2 1 5 7 6 Accept X Accept X Accept X Vote Y Accept X Accept X Vote Y (d) 3 4 2 1 5 7 6 Accept X Vote X Accept X Accept X Accept X Accept X Accept X (e) Figure 2. Cascade effect in federated voting. Each node has one quorum slice indicated by arrows to members of the slice. (a) Contradictory statements X and Y are introduced. (b) Nodes vote for valid statements. (c) Node 1 accepts X after its quorum {1, 2, 3, 4} unanimously votes for X. (d) Nodes 1, 2, 3, and 4 all accept X; set {1} is 5-blocking, so node 5 accepts X, overruling its previous vote for Y. (e) Set {5} is 6- and 7-blocking, so 6 and 7 both accept X. non-faulty node that could not accept contradictory statements. Confirmation of a statement is not guaranteed: in case of a split vote, both statements may be permanently stuck waiting for a quorum in the voting phase. However, if a node in an intact set I confirms a statement, the cascade theorem and accept case 2 ensure that all of I will eventually confirm that statement. 3.2.4 Ballot synchronization If nodes are unable to confirm a commit statement for the current ballot, they give up after a timeout. The timeout gets longer with each ballot so as to adjust to arbitrary bounds on network delay. However, timeouts alone are not sufficient to synchronize ballots of nodes that did not start at the same time or got desynchronized for other reasons. To achieve synchronization, nodes start the timer only once they are part of a quorum that is all at the current (or a later) ballot n. This slows down nodes that started early and ensures that no member of an intact set stays too far ahead of the group. Moreover, if a node v ever notices a v-blocking set at a later ballot, it immediately skips to the lowest ballot such that this is no longer the case, regardless of any timers. The cascade theorem then ensures that all stragglers catch up. The result is that ballots are roughly synchronized throughout an intact set once the system becomes synchronous. 3.2.5 Federated leader selection Leader selection allows each node to pick leaders in such a way that nodes generally only choose one or a small number of leaders. To accommodate leader failure, leader selection proceeds through rounds. If leaders of the current round appear not to be fulfilling their responsibilities, then after a certain timeout period nodes proceed to the next round to expand the set of leaders that they follow. Each round employs two unique cryptographic hash functions, H0 and H1, that output integers in the range [0,hmax). For instance, Stellar uses Hi(m) = SHA256(i∥b∥r ∥m), where b is the overall SCP instance (block or ledger number), r is the leader selection round number, and hmax = 2256. Within a round, we define the priority of node v as: priority(v) = H1(v) One strawman would be for each node to choose as leader the nodev with the highest priority(v). This approach works well with nearly identical quorum slices, but doesn’t properly capture the importance of nodes in imbalanced configurations. For instance, if Europe and China each contribute 3 nodes to every quorum, but China runs 1,000 nodes and Europe 4, then China will have the highest-priority node 99.6% of the time. We therefore introduce a notion of slice weight, where $\text{weight}(u,v) \in [0, 1]$ is the fraction of node $u$'s quorum slices containing node $v$. When node $u$ is selecting a new leader, it only considers neighbors, defined as follows:

\[\text{neighbors}(u) = \{ v \mid H_0(v) < h_{\max} \cdot \text{weight}(u,v) \}\]

A node $u$ then starts with an empty set of leaders, and at each round adds to it the node $v$ in $\text{neighbors}(u)$ with the highest $\text{priority}(v)$. If the neighbors set is empty in any round, $u$ instead adds the node $v$ with lowest value of $H_0(v)/\text{weight}(u,v)$.

Votez X

Votez Y (une) 3 4 2 1 5 7 6 Voter X Voter X Voter X Voter Oui Voter X Voter Oui Voter Oui (b) 3 4 2 1 5 7 6 Accepter X Voter X Accepter X Voter Oui Accepter X Voter Oui Voter Oui (c) 3 4 2 1 5 7 6 Accepter X Accepter X Accepter X Voter Oui Accepter X Accepter X Voter Oui (d) 3 4 2 1 5 7 6 Accepter X Voter X Accepter X Accepter X Accepter X Accepter X Accepter X (e) Figure 2. Effet cascade dans le vote fédéré. Chaque nœud possède une tranche de quorum indiquée par des flèches vers les membres de la tranche. (a) Des déclarations contradictoires X et Y sont introduites. (b) Les nœuds votent pour des déclarations valides. (c) Le nœud 1 accepte X après son quorum {1, 2, 3, 4} vote à l'unanimité pour X. (d) Les nœuds 1, 2, 3 et 4 acceptent tous X ; l'ensemble {1} est 5-bloquant, donc le nœud 5 accepte X, annulant son vote précédent pour Y. (e) L'ensemble {5} est bloquant 6 et 7, donc 6 et 7 acceptent tous deux X. nœud non défectueux qui ne pouvait pas accepter de déclarations contradictoires. La confirmation d'une déclaration n'est pas garantie : en En cas de vote partagé, les deux déclarations peuvent être définitivement coincé dans l'attente du quorum lors de la phase de vote. Cependant, si un nœud dans un ensemble intact I confirme une affirmation, la cascade théorème et accepter le cas 2 garantir que tout je finirai par confirmer cette affirmation. 3.2.4 Synchronisation des bulletins de vote Si les nœuds ne sont pas en mesure de confirmer une instruction de validation pour le scrutin en cours, ils abandonnent après un temps mort. Le délai d'attente devient plus longtemps à chaque scrutin afin de s'ajuster à des limites arbitraires sur le retard du réseau. Cependant, les délais d'attente ne suffisent pas à eux seuls à synchroniser les scrutins des nœuds qui n'ont pas démarré en même temps ou qui n'ont pas démarré en même temps. a été désynchronisé pour d'autres raisons. Pour réaliser la synchronisation, les nœuds démarrent le temporisateur uniquement lorsqu'ils font partie d'un quorum atteint lors du scrutin en cours (ou ultérieur) n. Ceci ralentit les nœuds qui ont démarré tôt et garantit qu'aucun un membre d'un ensemble intact reste trop en avance sur le groupe. De plus, si un nœud v remarque un v-blocage défini ultérieurement scrutin, il passe immédiatement au scrutin le plus bas de telle sorte que celui-ci ce n'est plus le cas, quelles que soient les minuteries. La cascade Le théorème garantit alors que tous les retardataires rattrapent leur retard. Le résultat est que les bulletins de vote sont à peu près synchronisés dans un pays intact défini une fois que le système devient synchrone. 3.2.5 Sélection des leaders fédérés La sélection des leaders permet à chaque nœud de choisir des leaders de manière façon dont les nœuds n'en choisissent généralement qu'un ou un petit nombre de dirigeants. Pour s'adapter à l'échec du leader, sélection du leader se déroule par tours. Si les leaders du tour en cours semblent ne pas s'acquitter de leurs responsabilités, puis après un certains nœuds de délai d'attente passent au tour suivant pour élargir l'ensemble des dirigeants qu'ils suivent. Chaque tour utilise deux fonctions cryptographiques uniques hash, H0 et H1, qui génèrent des entiers dans la plage [0,hmax). Par exemple, Stellar utilise Hi(m) = SHA256(i∥b∥r ∥m), où b est l'instance SCP globale (numéro de bloc ou de grand livre), r est le numéro du tour de sélection du leader, et hmax = 2256. Dans un tour, nous définissons la priorité du nœud v comme : priorité(v) = H1(v) Un homme de paille serait choisi pour chaque nœud comme leader le nœudv avec la priorité la plus élevée (v). Cette approche fonctionne bien avec des tranches de quorum presque identiques, mais pas correctement capturer l’importance des nœuds dans les configurations déséquilibrées. Par exemple, si l’Europe et la Chine contribuent chacune à hauteur de 3 nœuds à chaque quorum, mais la Chine gère 1 000 nœuds et l'Europe 4, alors la Chine aura le nœud le plus prioritaire 99,6 % de l'époque. Nous introduisons donc une notion de poids de tranche, où poids(u,v) ∈[0, 1] est la fraction des tranches de quorum du nœud u contenant le nœud v. Lorsque le nœud u sélectionne un nouveau leader, il ne considère que les voisins, définis comme suit : voisins (u) = { v | H0(v) < hmax · poids(u,v) } Un nodeu commence alors avec un ensemble vide de leaders, et à chaque round lui ajoute le nœud v des voisins(u) de plus haut priorité(v). Si l'ensemble des voisins est vide à n'importe quel tour, u ajoute à la place le nœudv avec la valeur la plus basse de H0(v)/weight(u,v).

Formal verification of SCP

To eliminate design errors, we formally verified SCP’s safety and liveness properties (see [65]). Specifically, we verified that intertwined nodes never disagree and that, under conditions discussed below, every member of an intact set eventually decides. Interestingly, verification revealed that the conditions under which SCP guarantees liveness are subtle, and stronger than initially thought [68]: as discussed below, malicious nodes that manipulate timing without otherwise deviating from the protocol may need to be manually evicted from quorum slices.

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. To ensure that the properties proved hold in all possible FBA configurations and executions, we consider an arbitrary number of nodes with arbitrary local configurations. This includes scenarios with disjoint intact sets, as well as potentially infinitely long executions. The drawback is that we face the challenging problem of verifying a parameterized infinite-state system. To keep verification tractable, we modeled SCP in firstorder logic (FOL) using Ivy [69] and the methodology of [82]. The verification process consists of manually providing inductive conjectures that are then automatically checked by Ivy. The FOL model of SCP abstracts over some aspects of FBA systems that are difficult to handle in FOL (e.g., the cascade theorem is taken as an axiom), so we verify the soundness of the abstraction using Isabelle/HOL [75]. After expressing the verification problem in FOL, we verify safety by providing an inductive invariant. The inductive invariant consists of a dozen one-line conjectures for about 150 lines of protocol specification. We then specify SCP’s liveness properties in Ivy’s Linear Temporal Logic and use the liveness to safety reduction of [80, 81] to reduce the liveness verification problem to the problem of finding an inductive invariant. While SCP’s safety is relatively straightforward to prove, SCP’s liveness argument is much more intricate and consists of around 150 single-line invariants. Proving liveness required a precise formalization of the assumptions under which SCP ensures termination. We initially thought an intact set I would always terminate if all members removed faulty nodes from their slices [68]. However, this turned out to be insufficient: a well-behaved (but not intact) node in a quorum of a member of I can, under the influence of faulty nodes, prevent termination by completing a quorum just before the end of a ballot, thereby causing members of I to chose different values of x in the next ballot. We must therefore additionally assume that, informally, each node in a quorum of a member of I eventually either becomes timely or doesn’t send messages at all for a sufficient period. In practice, this means members of I may need to adjust their slices until the condition holds. This issue is not inherent to FBA systems: Losa et al. [47] present a protocol whose liveness depends on the strictly weaker assumptions of just eventual synchrony and eventual leaderelection, without the need to remove faulty nodes from slices.

Vérification formelle du SCP

Pour éliminer les erreurs de conception, nous avons formellement vérifié la sécurité de SCP et propriétés de vivacité (voir [65]). Plus précisément, nous avons vérifié que les nœuds entrelacés ne sont jamais en désaccord et que, dans les conditions discutées ci-dessous, chaque membre d'un ensemble intact finit par décider. Il est intéressant de noter que la vérification a révélé que les conditions dans lesquelles SCP garantit la vivacité sont subtiles, et plus fort qu'on ne le pensait initialement [68] : comme indiqué ci-dessous, nœuds malveillants qui manipulent le timing sans autrement tout écart par rapport au protocole devra peut-être être expulsé manuellement from quorum slices.

SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et al. Pour garantir que les propriétés se sont avérées valables dans toutes les conditions possibles Configurations et exécutions FBA, nous considérons un arbitraire nombre de nœuds avec des configurations locales arbitraires. Ceci inclut des scénarios avec des ensembles intacts disjoints, ainsi que des exécutions potentiellement infinies. L'inconvénient est que nous faire face au problème difficile de la vérification d'un paramètre système à états infinis. Pour que la vérification reste réalisable, nous avons modélisé SCP en logique du premier ordre (FOL) en utilisant Ivy [69] et la méthodologie de [82]. Le processus de vérification consiste à fournir manuellement des conjectures inductives qui sont ensuite automatiquement vérifiées par Ivy. Le modèle FOL de SCP résume certains aspects de Les systèmes Expédié par Amazon difficiles à gérer en FOL (par exemple, le le théorème de cascade est pris comme un axiome), nous vérifions donc le solidité de l'abstraction à l'aide d'Isabelle/HOL [75]. Après avoir exprimé le problème de vérification en FOL, nous vérifions la sécurité en fournissant un invariant inductif. L'inductif invariant se compose d'une douzaine de conjectures sur une seule ligne pour environ 150 lignes de spécification de protocole. Nous spécifions ensuite les propriétés de vivacité de SCP dans la logique temporelle linéaire d'Ivy et utilisons la vivacité à une réduction de sécurité de [80, 81] pour réduire la vivacité problème de vérification au problème de trouver un inductif invariant. Bien que la sécurité de SCP soit relativement simple à prouver, l’argument de la vivacité de SCP est beaucoup plus complexe et se compose d’environ 150 invariants sur une seule ligne. Prouver la vivacité nécessitait une formalisation précise du hypothèses selon lesquelles SCP assure la résiliation. Nous pensions initialement qu'un ensemble intact serait toujours terminé si tous les membres ont supprimé les nœuds défectueux de leurs tranches [68]. Mais cela s'est avéré insuffisant : une personne bien élevée (mais pas intact) nœud dans un quorum d’un membre du Je peux, sous le influence de nœuds défectueux, empêcher la résiliation en complétant un quorum juste avant la fin d'un scrutin, provoquant ainsi les membres de I choisiront différentes valeurs de x lors du prochain scrutin. Nous devons donc en outre supposer que, de manière informelle, chaque nœud d'un quorum d'un membre de I éventuellement soit devient opportun ou n’envoie pas de messages du tout pendant une période suffisante. En pratique, cela signifie que les membres de I may doivent ajuster leurs tranches jusqu'à ce que la condition soit respectée. Ceci le problème n’est pas inhérent aux systèmes Expédié par Amazon : Losa et al. [47] présent un protocole dont la vivacité dépend du strictement plus faible hypothèses d'une éventuelle synchronisation et d'une éventuelle élection du leader, sans qu'il soit nécessaire de supprimer les nœuds défectueux des tranches.

Payment network

This section describes Stellar’s payment network, implemented as a replicated state machine [88] on top of SCP. 5.1 Ledger model Stellar’s ledger is designed around an account abstraction (in contrast to the more coin-centric unspent transaction output or UTXO model of Bitcoin). The ledger contents consists of a set of ledger entries of four distinct types: accounts, trustlines, offers, and account data. Accounts are the principals that own and issue assets. Each account is named by a public key. By default, the corresponding private key can sign transactions for the account. However, accounts can be reconfigured to add other signers and deauthorize the key that names the account, with a “multisig” option to require multiple signers. Each account also contains: a sequence number (included in transactions to prevent replay), some flags, and a balance in a “native” pre-mined cryptocurrency called XLM, intended to mitigate some denial-of-service attacks and facilitate market making as a neutral currency. Trustlines track the ownership of issued assets, which are named by a pair consisting of the issuing account and a short asset code (e.g., “USD” or “EUR”). Each trustline specifies an account, an asset, the account’s balance in that asset, a limit above which the balance cannot rise, and some flags. An account must explicitly consent to holding an asset by creating a trustline, preventing spammers from saddling accounts with unwanted assets. Know-your-customer (KYC) regulations require many financial institutions to know whose deposits they are holding, for instance by checking photo ID. To comply, issuers can set an optional auth_reqired flag on their accounts, restricting ownership of the assets they issue to authorized accounts. To grant such authorization, the issuer sets an authorized flag on customers’ trustlines. Offers correspond to an account’s willingness to trade up to a certain amount of a particular asset for another at a given price on the order book; they are automatically matched and filled when buy/sell prices cross. Finally, account data consists of account, key, value triples, allowing account holders to publish small metadata values. To prevent ledger spam, there is a minimum XLM balance, called the reserve. An account’s reserve increases with each associated ledger entry and decreases when the ledger entry disappears (e.g., when an order is filled or canceled, or when a trustline is deleted). Currently the reserve grows by 0.5 XLM (∼$0.03) per ledger entry. Regardless of the reserve, it is possible to reclaim the entire value of an account by deleting it with an AccountMerge operation. A ledger header, shown in Figure 3, stores global attributes: a ledger number, parameters such as the reserve balance per ledger entry, a hash of the previous ledger header (actually several hashes forming a skiplist), the SCP output including a hash of new transactions applied at this ledger, a hash of the results of those transactions (e.g., success or failure for each), and a snapshot hash of all ledger entries. Because the snapshot hash includes all ledger contents, validators need not retain history to validate transactions. However, to scale to hundreds of millions of anticipated accounts, we cannot rehash all ledger entry tables on every ledger close. Moreover, it is not practical to transfer a ledger

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada ledger # = 4 H(prev hdr) SCP output H∗(results) H∗(snapshot) ... header ledger # = 5 H(prev hdr) SCP output H∗(results) H∗(snapshot) ... header . . . Figure 3. Ledger contents. H is SHA-256, while H ∗represents hierarchical or recursive application of H. SCP output also depends the previous header hash. CreateAccount Create and fund new account ledger entry AccountMerge Delete account ledger entry SetOptions Change account flags and signers Payment Pay specific quantity of asset to dest. acct. PathPayment Like Payment, but pay in different asset (up to limit); specify up to 5 intermediary assets ManageOffer Create/delete/change offer ledger entry, -PassiveOffer with passive variant to allow zero spread ManageData Create/delete/change acct. data ledger entry ChangeTrust Create/delete/change trustline AllowTrust Set or clear authorized flag on trustline BumpSequence Increase seq. number on account Figure 4. Principal ledger operations of that size every time a node has been disconnected from the network for too long. The snapshot hash is therefore designed to optimize both hashing and state reconciliation. Specifically, the snapshot stratifies ledger entries by time of last modification in a set of exponentially-sized containers called buckets. The collection of buckets is called the bucket list, and bears some similarity to log-structured merge-trees (LSM-trees) [77]. The bucket list is not read during transaction processing (see Section 5.4). Hence, certain design aspects of LSM-trees can be relaxed. In particular, random access by key is not required, and buckets are only ever read sequentially as part of merging levels. Hashing the bucket list is done by hashing each bucket as it is merged and calculating a new cumulative hash of the bucket hashes (a small, fixed index of reference hashes) at each ledger close. Reconciling the bucket list after disconnection requires downloading only buckets that differ. 5.2 Transaction model A transaction consists of a source account, validity criteria, a memo, and a list of one or more operations. Figure 4 lists available operations. Each operation has a source account, which defaults to that of the overall transaction. A transaction must be signed by keys corresponding to every source account in an operation. Multisig accounts can require higher signing weight for some operations (such as SetOptions) and lower for others (such as AllowTrust). Transactions are atomic—if any operation fails, none of them execute. This simplifies multi-way deals. Suppose an issuer creates an asset to represent land deeds, and user A wants to exchange a small land parcel plus $10,000 for a bigger land parcel owned by B. The two users can both sign a single transaction containing three operations: two land payments and one dollar payment. A transaction’s main validity criterion is its sequence number, which must be one greater than that of the transaction’s source account ledger entry. Executing a valid transaction (successfully or not) increments the sequence number, preventing replay. Initial sequence numbers contain the ledger number in the high bits to prevent replay even after deleting and re-creating an account. The other validity criterion is an optional limit on when a transaction can execute. Returning to the land and dollar swap above, if A signs the transaction before B, A may not want B to sit on the transaction for a year before submitting it, and so could place a time limit invalidating the transaction after a few days. Multisig accounts can also be configured to give signing weight to the revelation of a hash pre-image, which, combined with time bounds, permits atomic crosschain trading [1]. A transaction’s source account pays a trivial fee in XLM, 10−5 XLM unless there is congestion. Under congestion, the cost of operations is set by Dutch auction. Validators are not compensated by fees because validators are analogous to Bitcoin full nodes, not miners. Rather than destroy XLM, fees are recycled and distributed proportionally by vote of existing XLM holders, which in retrospect might or might not have been worth the complexity. 5.3 Consensus values For each ledger, Stellar uses SCP to agree on a data structure with three fields: a transaction set hash (including a hash of the previous ledger header), a close time, and upgrades. When multiple values are confirmed nominated, Stellar takes the transaction set with the most operations (breaking ties by total fees, then transaction set hash), the union of all upgrades, and the highest close time. A close time is only valid if it is between the last ledger’s close time and the present, so nodes do not nominate invalid times. Upgrades adjust global parameters such as the reserve balance, minimum operation fee, and protocol version. When combined during nomination, higher fees and protocol version numbers supersede lower ones. Upgrades effect governance through a federated-voting tussle space [34], neither egalitarian nor centralized. Each validator is configured as either governing or non-governing (the default), according to whether its operator wants to participate in governance. Governing validators consider three kinds of upgrade: desired, valid, and invalid (anything the validator does not

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. validator core horizon FS DB DB submit client client other validators Figure 5. Stellar validator architecture know how to implement). Desired upgrades are configured to trigger at a specific time, intended to be coordinated among operators. Governing nodes always vote to nominate desired upgrades, accept but do not vote to nominate valid upgrades (i.e., go along with a blocking quorum), and never vote for or accept invalid upgrades. Non-governing validators echo any vote they see for a valid upgrade, essentially delegating the decision on what upgrades are desired to those who opt for a governance role. 5.4 Implementation Figure 5 shows Stellar’s validator architecture. A daemon called stellar-core (∼92k lines of C++, not counting thirdparty libraries) implements the SCP protocol and the replicated state machine. Producing values for SCP requires reducing large numbers of ledger entries to small cryptographic hashes. By contrast, transaction validation and execution requires looking up account state and order matching at the best price. To serve both functions efficiently, stellar-core keeps two representations of the ledger: an external representation containing the bucket list, stored as binary files that can be efficiently updated and incrementally rehashed, and an internal representation in a SQL database (PostgreSQL for production nodes). Stellar-core creates a write-only history archive containing each transaction set that was confirmed and snapshots of buckets. The archive lets new nodes bootstrap themselves when joining the network. It also provides a record of ledger history—there needs to be some place one can look up a transaction from two years ago. Since history is append-only and accessed infrequently, it can be kept in cheap places such as Amazon Glacier or any service allowing one to store and retrieve flat files. Validator hosts typically do not host their own archives so as to avoid any impact on validation performance from serving history. To keep stellar-core simple, it is not intended to be used directly by applications and exposes only a very narrow interface for the submission of new transactions. To support clients, most validators run a daemon called horizon (∼18k lines of Go) that provides an HTTP interface for submitting and learning of transactions. horizon has read-only access to stellar-core’s SQL database, minimizing the risk of horizon destabilizing stellar-core. Features such as payment path finding are implemented entirely in horizon and can be upgraded unilaterally without coordinating with other validators. Several optional higher-layer daemons are clients to horizon, rounding out the ecosystem. A bridge server facilitates integration of Stellar with existing systems, e.g., posting notifications of all payments received by a specific account. A compliance server provides hooks for financial institutions to exchange and approve of sender and beneficiary information on payments, for compliance with sanctions lists. Finally, a federation server implements a human-readable naming system for accounts. 6 Deployment experience Stellar grew for several years into a state with a moderate number of reasonably-reliable full node operators. However, nodes’ configurations were such that liveness (though not safety) depended on us, the Stellar Development Foundation (SDF); had SDF suddenly disappeared, other node operators would have needed to intervene and manually remove us from quorum slices for the network to continue. While we and many others want to reduce SDF’s systemic importance, this goal received increasing priority after researchers [58] quantified and publicized the network’s centralization without differentiating the risks to safety and liveness. A number of operators reacted with active configuration adjustments, primarily increasing the size of their quorum slices in an effort to dilute SDF’s importance; ironically this only increased the risk to liveness. Two problems exacerbated the situation. First, a popular third-party Stellar monitoring tool [5] was systematically overestimating validator uptime by not actually verifying that stellar-core was running; this lead people to include unreliable nodes in their quorum slices. Second, a bug in stellar-core meant once a validator moved to the next ledger, it didn’t adequately help remaining nodes complete the previous ledger in the event of lost messages. As a result, the network experienced 67 minutes of downtime and required manual coordination by validator administrators to restart. Worse, while attempting to restart the network, simultaneous rushed reconfigurations on multiple nodes resulted in a collective misconfiguration that allowed some nodes to diverge, requiring a manual shutdown of those nodes and resubmission of the transactions accepted during the divergence. Luckily, this divergence was caught and corrected quickly and contained no conflicting transactions, but the risk of the network failing to enjoy quorum intersection— splitting while continuing to accept potentially conflicting transactions, simply due to misconfiguration—was made very concrete by this incident. Reviewing these experiences led to two major conclusions and corresponding corrective actions.

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Critical, 100% 51% 51% High, 67% 51% Medium, 67% 51% Low, 67% 51% 51% ... ... ... 51% ... 51% Figure 6. Validator quality hierarchy. Highest quality nodes require the highest threshold of 100%, whereas lower qualities are configured to 67% threshold. Nodes within a single organization require a simple 51% majority. 6.1 Configuration complexity and fragility Stellar expresses quorum slices as nested quorum sets consisting of n entries and a threshold k where any set of k entries constitutes a quorum slice. Each of the n entries then is either a validator public key or, recursively, another quorum set. While flexible and compact, we realized nested quorum sets simultaneously afforded node operators too much flexibility and too little guidance: it was easy to write unsafe (or even nonsensical) configurations. The criteria for grouping nodes into sets, for organizing subsets into a hierarchy, and for choosing thresholds were all insufficiently clear and contributed to operational failures. It wasn’t clear whether to treat a “level” in the nested-set hierarchy as a level of trust, or an organization, or both; many configurations in the field mixed these concepts, in addition to specifying dangerous or meaningless thresholds. We therefore added a simpler configuration mechanism that separates two aspects of nested quorum sets: grouping nodes together by organization, and labeling each organization with a simple trust classification (low, medium, high, or critical). Organizations at and above high are required to publish history archives. The new system synthesizes nestedquorum sets in which each organization is represented as a 51% threshold set, and organizations are grouped into sets with 67% or 100% thresholds (depending on group quality). Each group is a single entry in the next (higher quality) group, as illustrated in Figure 6. This simplified model reduces the likelihood of misconfiguration, both in terms of the structure of the synthesized nested sets and the thresholds chosen for each set. 6.2 Proactive detection of misconfiguration Second, we realized that detecting collective misconfiguration by waiting to observe its negative effects is too late. Especially with respect to misconfigurations that can diverge—a more serious failure mode than halting—the network needs to be able to detect misconfiguration immediately so that operators can revert it before any divergence actually hapens. To address this need, we built a mechanism into the validator software that continuously gathers the collective configuration state of all the peers in the node’s transitive closure and detects the potential for divergence—i.e., disjoint quorums—within that collective configuration. 6.2.1 Checking quorum intersection While gathering quorum slices is easy, finding disjoint quorums among them is co-NP-hard [62]. However, we adopted a set of algorithmic heuristics and case-elimination rules proposed by Lachowski [62] that check typical instances of the problem several orders of magnitude faster than the worst-case cost. Practically speaking, the current network’s quorum slice transitive closures are on the order of 20–30 nodes and, with Lachowski’s optimizations, typically check in a matter of seconds on a single CPU. Should the need arise to enhance performance, we may parallelize the search. 6.2.2 Checking risky configurations Detecting that the network admits disjoint quorums is a step in the right direction, but flags the danger uncomfortably late for such a critical issue. Ideally, we want node operators to receive warnings when the network’s collective configuration is merely approaching a risky state. We therefore extended the quorum-intersection checker to detect a condition we call criticality: when the current collective configuration is one misconfiguration away from a state that admits disjoint quorums. To detect criticality, the checker repeatedly replaces each organization’s configuration with a simulated worst-case misconfiguration, then re-runs the inner quorum intersection checker on the result. If any such critical misconfiguration exists one step away from the current state, the software issues a warning and reports the organization posing a misconfiguration risk. These changes give the community of operators two layers of notice and guidance to insulate against the worst forms of collective misconfiguration.

Réseau de paiement

Cette section décrit le réseau de paiement de Stellar, implémenté en tant que machine à états répliquée [88] au-dessus de SCP. 5.1 Modèle de grand livre Le grand livre de Stellar est conçu autour d'une abstraction de compte (en contrairement à la sortie de transaction non dépensée plus centrée sur les pièces ou modèle UTXO de Bitcoin). Le contenu du grand livre se compose d'un ensemble d'écritures comptables de quatre types distincts : comptes, lignes de confiance, offres et données de compte. Les comptes sont les principaux qui possèdent et émettent des actifs. Chacun le compte est nommé par une clé publique. Par défaut, la clé privée correspondante peut signer les transactions pour le compte. Cependant, les comptes peuvent être reconfigurés pour ajouter d'autres signataires et annuler l'autorisation de la clé qui nomme le compte, avec un Option « multisig » pour exiger plusieurs signataires. Chaque compte contient également : un numéro de séquence (inclus dans les transactions pour éviter les rediffusions), quelques flags, et un solde en mode « natif » crypto-monnaie pré-exploitée appelée XLM, destinée à atténuer certaines attaques par déni de service et faciliter la tenue de marché comme monnaie neutre. Les lignes de confiance suivent la propriété des actifs émis, qui sont nommé par une paire composée du compte émetteur et d'un short code d'actif (par exemple, « USD » ou « EUR »). Chaque ligne de confiance précise un compte, un actif, le solde du compte dans cet actif, un limite au-dessus de laquelle le solde ne peut pas monter, et quelques drapeaux. Un compte doit consentir explicitement à la détention d'un actif par créer une ligne de confiance, empêchant les spammeurs de s'en prendre à vous comptes avec des actifs indésirables. Les réglementations de connaissance du client (KYC) exigent que de nombreuses institutions financières sachent quels dépôts elles détiennent, par exemple en vérifiant une pièce d'identité avec photo. Pour se conformer, les émetteurs peuvent définir un indicateur auth_reqired facultatif sur leurs comptes, limitant la propriété des actifs qu'ils émettent aux comptes autorisés. Pour accorder une telle autorisation, l'émetteur fixe un signaler sur les lignes de confiance des clients. Les offres correspondent à la volonté d’un compte d’échanger à un certain montant d'un actif particulier pour un autre à un moment donné prix sur le carnet de commandes ; ils sont automatiquement mis en correspondance et rempli lorsque les prix d’achat/vente se croisent. Enfin, les données du compte sont constituées de triplets de compte, de clé et de valeur, permettant aux titulaires de compte pour publier de petites valeurs de métadonnées. Pour éviter le spam du grand livre, il existe un solde XLM minimum, appelé la réserve. La réserve d’un compte augmente à chaque fois écriture comptable associée et diminue lorsque l'écriture comptable disparaît (par exemple, lorsqu'une commande est exécutée ou annulée, ou lorsqu'un la ligne de confiance est supprimée). Actuellement, la réserve augmente de 0,5 XLM (∼0,03 $) par écriture au grand livre. Quelle que soit la réserve, c'est possible de récupérer la totalité de la valeur d'un compte en supprimant avec une opération AccountMerge. Un en-tête de grand livre, illustré à la figure 3, stocke les attributs globaux : un numéro de grand livre, des paramètres tels que le solde de réserve par écriture comptable, un hash de l'en-tête comptable précédent (en fait plusieurs hashes formant une liste de saut), la sortie SCP comprenant un hash de nouvelles transactions appliquées à ce grand livre, un hash de les résultats de ces transactions (par exemple, le succès ou l'échec de chacun) et un instantané hash de toutes les écritures du grand livre. Étant donné que l'instantané hash inclut tout le contenu du grand livre, Les validator n'ont pas besoin de conserver l'historique pour valider les transactions. Cependant, pour atteindre les centaines de millions de comptes, nous ne pouvons pas rehash toutes les tables d'écriture du grand livre sur chaque clôture du grand livre. De plus, il n'est pas pratique de transférer un grand livrePaiements internationaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada numéro de grand livre = 4 H (HDR précédent) Sortie SCP H∗(résultats) H∗(instantané) ... en-tête numéro de grand livre = 5 H (HDR précédent) Sortie SCP H∗(résultats) H∗(instantané) ... en-tête . . . Figure 3. Contenu du grand livre. H est SHA-256, tandis que H ∗ représente une application hiérarchique ou récursive de H. Sortie SCP dépend aussi de l'en-tête précédent hash. Créer un compte Créer et financer une nouvelle écriture de compte Fusion de comptes Supprimer l'écriture comptable du compte Définir les options Modifier les indicateurs de compte et les signataires Paiement Payez une quantité spécifique d'actif à destination. compte. CheminPaiement Comme le paiement, mais payez avec un actif différent (jusqu'à limiter); spécifier jusqu'à 5 actifs intermédiaires Gérer l'offre Créer/supprimer/modifier une entrée au grand livre d'offre, -Offre Passive avec variante passive pour permettre un spread nul Gérer les données Créer/supprimer/modifier un compte. saisie de données au grand livre ChangerConfiance Créer/supprimer/modifier une ligne de confiance Autoriser la confiance Définir ou effacer l'indicateur autorisé sur la ligne de confiance Séquence de bosses Augmenter séq. numéro de compte Figure 4. Principales opérations du grand livre de cette taille chaque fois qu'un nœud a été déconnecté de le réseau depuis trop longtemps. L'instantané hash est donc conçu pour optimiser à la fois le hashing et la réconciliation de l’État. Plus précisément, l'instantané stratifie les écritures du grand livre par heure de la dernière modification dans un ensemble de conteneurs de taille exponentielle appelés seaux. La collection de buckets est appelée le bucket liste, et présente une certaine similitude avec les arbres de fusion structurés en journaux (Arbres LSM) [77]. La bucket list n'est pas lue pendant le traitement de la transaction (voir Section 5.4). Par conséquent, certaines conceptions certains aspects des arbres LSM peuvent être assouplis. En particulier, aléatoire l'accès par clé n'est pas requis et les compartiments ne sont que lus séquentiellement dans le cadre de la fusion des niveaux. Hacher le seau La liste est effectuée en hashing chaque compartiment au fur et à mesure de sa fusion et en calculant un nouveau hash cumulatif du bucket hashes (un petit, indice fixe de référence hashes) à chaque clôture du grand livre. La réconciliation de la bucket list après la déconnexion nécessite un téléchargement seulement des seaux qui diffèrent. 5.2 Modèle de transaction Une transaction se compose d'un compte source, de critères de validité, d'un mémo et une liste d’une ou plusieurs opérations. La figure 4 répertorie les opérations disponibles. Chaque opération possède un compte source, qui par défaut, celui de la transaction globale. Une transaction doit être signé par des clés correspondant à chaque compte source dans une opération. Les comptes Multisig peuvent nécessiter une signature plus élevée poids pour certaines opérations (telles que SetOptions) et inférieur pour d'autres (comme AllowTrust). Les transactions sont atomiques : si une opération échoue, aucune des opérations les exécuter. Cela simplifie les transactions multidirectionnelles. Supposons qu'un l'émetteur crée un actif pour représenter les titres de propriété et l'utilisateur A veut échanger une petite parcelle de terrain plus 10 000 $ contre un parcelle de terrain plus grande appartenant à B. Les deux utilisateurs peuvent tous deux signer une seule transaction contenant trois opérations : deux terrains paiements et paiement d’un dollar. Le principal critère de validité d’une transaction est son numéro d’ordre, qui doit être supérieur de un à celui du numéro de séquence de la transaction. écriture comptable du compte source. Exécuter une transaction valide (avec succès ou non) incrémente le numéro de séquence, empêchant la relecture. Les numéros de séquence initiaux contiennent le grand livre numéro dans les bits hauts pour empêcher la relecture même après la suppression et recréer un compte. L'autre critère de validité est une limite facultative quant au moment où une transaction peut s’exécuter. Retour à la terre et au dollar swap ci-dessus, si A signe la transaction avant B, A ne peut pas veut que B reste assis sur la transaction pendant un an avant de la soumettre cela, et pourrait ainsi imposer un délai invalidant la transaction après quelques jours. Les comptes Multisig peuvent également être configurés donner un poids de signature à la révélation d'une pré-image hash, ce qui, combiné à des limites de temps, permet le trading atomique crosschain [1]. Le compte source d'une transaction paie des frais insignifiants en XLM, 10−5 XLM sauf en cas de congestion. En période de congestion, le le coût des opérations est fixé par les enchères néerlandaises. Les validateurs sont non compensé par des frais car les validator sont analogues aux nœuds complets Bitcoin, pas aux mineurs. Plutôt que de détruire XLM, les frais sont recyclés et répartis proportionnellement par vote du les détenteurs XLM existants, qui, rétrospectivement, pourraient ou pourraient cela ne valait pas la complexité. 5.3 Valeurs consensuelles Pour chaque grand livre, Stellar utilise SCP pour convenir d'une structure de données avec trois champs : un ensemble de transactions hash (incluant un hash de l'en-tête du référentiel précédent), une heure de clôture, uned mises à niveau. Lorsque plusieurs valeurs sont confirmées, Stellar prend l'ensemble de transactions avec le plus d'opérations (rupture des liens par frais totaux, puis ensemble de transactions hash), l'union de tous mises à niveau et temps de fermeture le plus élevé. Une heure de fermeture est seulement valable s'il est compris entre l'heure de clôture du dernier référentiel et le présents, afin que les nœuds ne nomment pas d'heures invalides. Les mises à niveau ajustent les paramètres globaux tels que le solde de réserve, les frais de fonctionnement minimum et la version du protocole. Quand combinés lors de la nomination, les frais plus élevés et les numéros de version du protocole remplacent les plus bas. Les mises à niveau affectent la gouvernance à travers un espace de lutte avec vote fédéré [34], ni l'un ni l'autre égalitaire ni centralisé. Chaque validator est configuré comme soit gouvernant, soit non gouvernant (par défaut), selon à savoir si son opérateur souhaite participer à la gouvernance. Les validator gouvernants envisagent trois types de mise à niveau : souhaité, valide et invalide (tout ce que le validator ne fait pas

SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. validator noyau horizon FS Base de données Base de données soumettre client client autres validator Figure 5. Architecture Stellar validator savoir mettre en œuvre). Les mises à niveau souhaitées sont configurées pour déclenchement à un moment précis, destiné à être coordonné entre opérateurs. Les nœuds dirigeants votent toujours pour nommer les candidats souhaités. mises à niveau, acceptez mais ne votez pas pour proposer des mises à niveau valides (c'est-à-dire, acceptez un quorum bloquant) et ne votez jamais pour ou acceptez les mises à niveau non valides. Écho de validators non gouvernementaux tout vote qu'ils voient pour une mise à niveau valide, déléguant essentiellement la décision sur les mises à niveau souhaitées pour ceux qui optent pour un rôle de gouvernance. 5.4 Mise en œuvre La figure 5 montre l'architecture validator de Stellar. Un démon appelé stellar-core (∼92 000 lignes de C++, sans compter les bibliothèques tierces) implémente le protocole SCP et la machine à états répliquée. La production de valeurs pour SCP nécessite de réduire un grand nombre d'écritures comptables à de petites écritures cryptographiques. hashes. En revanche, la validation et l'exécution des transactions nécessite de rechercher l'état du compte et la correspondance des commandes sur le meilleur prix. Pour remplir efficacement ces deux fonctions, Stellar-Core conserve deux représentations du grand livre : une représentation externe contenant la bucket list, stockée sous forme de fichiers binaires qui peut être mis à jour efficacement et réhashed progressivement, et une représentation interne dans une base de données SQL (PostgreSQL pour les nœuds de production). Stellar-core crée une archive d'historique en écriture seule contenant chaque ensemble de transactions confirmé et des instantanés de seaux. L'archive permet aux nouveaux nœuds de s'amorcer eux-mêmes en rejoignant le réseau. Il fournit également un enregistrement du grand livre histoire - il doit y avoir un endroit où l'on peut rechercher une transaction d’il y a deux ans. Puisque l'historique est uniquement ajouté et rarement consulté, il peut être conservé dans des endroits bon marché comme Amazon Glacier ou tout service permettant de stocker et récupérer des fichiers plats. Les hôtes du validateur n'hébergent généralement pas leurs propres archives afin d'éviter tout impact sur la validation performance de l’histoire de service. Pour garder le noyau stellaire simple, il n'est pas destiné à être utilisé directement par les applications et n'expose qu'une interface très étroite pour la soumission de nouvelles transactions. Pour soutenir clients, la plupart des validator exécutent un démon appelé horizon (∼18k lignes de Go) qui fournit une interface HTTP pour la soumission et l'apprentissage des transactions. horizon a un accès en lecture seule à base de données SQL de Stellar-Core, minimisant le risque d'horizon noyau stellaire déstabilisant. Des fonctionnalités telles que la recherche du chemin de paiement sont entièrement mises en œuvre à Horizon et peuvent être mises à niveau unilatéralement sans coordination avec les autres validator. Plusieurs démons facultatifs de couche supérieure sont des clients à horizon, complétant l’écosystème. Un serveur pont facilite intégration de Stellar avec les systèmes existants, par exemple, publication de notifications de tous les paiements reçus par un compte spécifique. Un le serveur de conformité fournit des points d'ancrage aux institutions financières pour échanger et approuver les informations sur l’expéditeur et le bénéficiaire sur les paiements, pour le respect des listes de sanctions. Enfin, un serveur de fédération implémente une dénomination lisible par l'homme système de comptabilité. 6 Expérience de déploiement Stellar s'est développé pendant plusieurs années pour devenir un État à nombre d’opérateurs de nœuds complets raisonnablement fiables. Cependant, les configurations des nœuds étaient telles que la vivacité (mais pas sécurité) dépendait de nous, la Stellar Fondation de Développement (SDF); Si SDF avait soudainement disparu, d'autres opérateurs de nœuds il aurait fallu intervenir et nous supprimer manuellement à partir des tranches de quorum pour que le réseau puisse continuer. Alors que nous et beaucoup d’autres souhaitons réduire l’importance systémique du SDF, cet objectif a reçu une priorité croissante après Les chercheurs [58] ont quantifié et rendu public la centralisation du réseau sans différencier les risques pour la sécurité et la sécurité. vivacité. Un certain nombre d'opérateurs ont réagi en ajustant activement la configuration, principalement en augmentant la taille de leur des tranches de quorum dans le but de diluer l’importance du SDF ; ironiquement, cela n'a fait qu'augmenter le risque pour la vitalité. Deux problèmes ont aggravé la situation. Tout d'abord, un populaire L'outil de surveillance tiers Stellar [5] a été systématiquement surestimer la disponibilité de validator en ne vérifiant pas réellement ce noyau stellaire fonctionnait ; cela amène les gens à inclure nœuds peu fiables dans leurs tranches de quorum. Deuxièmement, un bug dans stellar-core signifiait qu'une fois qu'un validator était passé au registre suivant, cela n'a pas suffisamment aidé les nœuds restants à terminer la précédenteun grand livre en cas de perte de messages. En conséquence, le Le réseau a connu 67 minutes d'indisponibilité et a nécessité coordination manuelle par les administrateurs validator pour redémarrer. Pire encore, lors de la tentative de redémarrage du réseau, des reconfigurations précipitées simultanées sur plusieurs nœuds ont entraîné des reconfigurations précipitées simultanées sur plusieurs nœuds. dans une mauvaise configuration collective qui a permis à certains nœuds de diverger, nécessitant un arrêt manuel de ces nœuds et resoumission des transactions acceptées lors de la divergence. Heureusement, cette divergence a été détectée et corrigée rapidement et ne contenait aucune transaction conflictuelle, mais le risque que le réseau ne parvienne pas à bénéficier de l'intersection du quorum : se diviser tout en continuant à accepter des situations potentiellement conflictuelles transactions, simplement en raison d'une mauvaise configuration, a été effectuée très concret par cet incident. L’examen de ces expériences a conduit à deux conclusions majeures et les actions correctives correspondantes.Paiements mondiaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Critique, 100% 51% 51% Élevé, 67 % 51% Moyen, 67 % 51% Faible, 67 % 51% 51% ... ... ... 51% ... 51% Figure 6. Hiérarchie de qualité du validateur. Nœuds de la plus haute qualité nécessitent le seuil le plus élevé de 100 %, tandis que les qualités inférieures sont configurées au seuil de 67 %. Nœuds au sein d'un même l’organisation requiert une majorité simple de 51 %. 6.1 Complexité et fragilité de la configuration Stellar exprime les tranches de quorum sous forme d'ensembles de quorum imbriqués composés de n entrées et d'un seuil k où tout ensemble de k entrées constitue une tranche de quorum. Chacune des n entrées est alors soit une clé publique validator ou, récursivement, un autre ensemble de quorum. Bien que flexibles et compacts, nous avons réalisé un quorum imbriqué ensembles offraient simultanément aux opérateurs de nœuds trop de flexibilité et trop peu de conseils : il était facile d'écrire de manière non sécurisée (ou voire absurdes). Les critères de regroupement nœuds en ensembles, pour organiser les sous-ensembles dans une hiérarchie, et les choix des seuils n’étaient pas tous suffisamment clairs et ont contribué à des échecs opérationnels. Il n'était pas clair s'il fallait traiter un « niveau » dans la hiérarchie imbriquée comme un niveau de confiance, ou une organisation, ou les deux ; de nombreuses configurations sur le terrain mélangé ces concepts, en plus de préciser les dangers ou des seuils dénués de sens. Nous avons donc ajouté un mécanisme de configuration plus simple qui sépare deux aspects des ensembles de quorum imbriqués : le regroupement nœuds regroupés par organisation et étiquetant chaque organisation avec une classification de confiance simple (faible, moyenne, élevée ou critique). Les organisations de niveau élevé et supérieur sont tenues de publier des archives historiques. Le nouveau système synthétise des ensembles de quorum imbriqués dans lesquels chaque organisation est représentée comme un Un seuil de 51 % est défini et les organisations sont regroupées en ensembles avec des seuils de 67% ou 100% (selon la qualité du groupe). Chaque groupe est une entrée unique dans le groupe suivant (de qualité supérieure), comme illustré à la figure 6. Ce modèle simplifié réduit le probabilité de mauvaise configuration, tant en termes de structure des ensembles imbriqués synthétisés et des seuils choisis pour chaque ensemble. 6.2 Détection proactive des erreurs de configuration Deuxièmement, nous avons réalisé qu’il était trop tard pour détecter une mauvaise configuration collective en attendant d’observer ses effets négatifs. Surtout en ce qui concerne les erreurs de configuration qui peuvent diverger - un mode de défaillance plus grave que l'arrêt : le réseau a besoin être capable de détecter immédiatement une mauvaise configuration afin que les opérateurs puissent y remédier avant qu'une divergence ne se produise réellement. Pour répondre à ce besoin, nous avons intégré un mécanisme dans le logiciel validator qui rassemble en permanence l'état de configuration collective de tous les pairs dans la fermeture transitive du nœud et détecte le potentiel de divergence, c'est-à-dire disjoint. quorums – au sein de cette configuration collective. 6.2.1 Vérification de l'intersection du quorum Bien que rassembler des tranches de quorum soit facile, trouver des quorums disjoints parmi elles est co-NP-difficile [62]. Cependant, nous avons adopté un ensemble d'heuristiques algorithmiques et de règles d'élimination de cas proposé par Lachowski [62] qui vérifie les instances typiques du problème plusieurs ordres de grandeur plus rapidement que le coût dans le pire des cas. En pratique, le réseau actuel les fermetures transitives des tranches de quorum sont de l’ordre de 20 à 30 nœuds et, avec les optimisations de Lachowski, vérifient généralement en quelques secondes sur un seul processeur. Si le besoin s'en fait sentir pour améliorer les performances, nous pouvons paralléliser la recherche. 6.2.2 Vérification des configurations à risque Détecter que le réseau admet des quorums disjoints est une étape dans la bonne direction, mais signale le danger trop tard pour une question aussi cruciale. Idéalement, nous souhaitons que les opérateurs de nœuds reçoivent des avertissements lorsque la configuration collective du réseau s’approche simplement d’un état à risque. Nous avons donc étendu le vérificateur d'intersection de quorum pour détecter une condition que nous appelons criticité : lorsque le courant la configuration collective est à une mauvaise configuration de un État qui admet des quorums disjoints. Pour détecter la criticité, le vérificateur remplace à plusieurs reprises la configuration de chaque organisation par une mauvaise configuration simulée dans le pire des cas, puis réexécute le vérificateur d’intersection de quorum interne sur le résultat. Si une telle mauvaise configuration critique existe à une étape à partir de l'état actuel, le logiciel émet un avertissement et signale que l'organisation présente un risque de mauvaise configuration. Ces changements donnent à la communauté des opérateurs deux niveaux de préavis et de conseils pour se prémunir contre les pires formes de mauvaise configuration collective.

Evaluation

To understand Stellar’s suitablity as a global payment and trading network, we evaluated the state of the public network and ran controlled experiments on a private experimental network. We focused on the following questions: • What does the production network topology look like? How many messages are broadcast on average, and how does SCP experience timeouts? • Do consensus and ledger update latencies remain independent of the number of accounts?

Stellar network quorum slice map showing validator nodes and their bidirectional dependencies

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. • How are latencies affected by increasing (a) transactions per second (and, consequently, transactions per ledger), and (b) the number of validator nodes? • What is the cost of running a node in terms of CPU, memory, and network bandwidth? Payment networks have low transaction rates compared to other types of distributed system. The leading blockchains, Bitcoin and Ethereum, confirm up to 15 transactions/second, less than Stellar. Moreover, these systems take minutes to an hour to confirm a transaction securely, because proof-ofwork requires waiting for several blocks to be mined. The non-blockchain SWIFT network averaged only 420 transactions per second on its peak day [14]. We therefore chose to compare our measurements against the 5-second target ledger interval, a more aggressive target. Our results show that latencies are comfortably below this limit even with several unimplemented optimizations still in the pipeline. 7.1 Anchors The top traded assets by volume include currency (e.g., 3 USD anchors, 2 CNY), a Bitcoin anchor, a real-estate-backed security token [92], and an in-app currency [8]. Different anchors have different policies. For instance, one USD anchor, Stronghold, sets auth_reqired and requires a know-yourcustomer (KYC) process for every account that holds their assets. Another, AnchorUSD, let’s anyone receive and trade their USD (making it literally possible to send $0.50 to Mexico in 5 seconds with a fee of $0.000001). However, AnchorUSD does require KYC and fees to purchase or redeem their USD with conventional wire transfers. In the Philippines, where bank regulations are laxer for incoming payments, coins.ph supports cashing out PHP at any ATM machine [36]. In addition to the aforementioned security token and in-app currency, there’s a range of non-currency tokens ranging from commercial bonds [22] and carbon credits [85, 96] to more esoteric assets such as a token incentivizing collaborative car repossession [35]. 7.2 Public network As of this writing, there are 126 active full nodes, 66 of which participate in consensus by signing vote messages. Figure 7 (generated by [5]) visualizes the network, with a line between two nodes if one appears in the other’s quorum slices and a darker blue line to show bi-directional dependence. At the center is a cluster of 17 de facto “tier-one validators” run by SDF, SatoshiPay, LOBSTR, COINQVEST, and Keybase. Four months ago, before the events of Section 6, there were 15 systemically important nodes: 3 from seemingly tier-one organizations and several random singletons. The graph also looked much less regular. Hence, the new configuration mechanism and/or better operator decisions seem to be contributing to a healthier network topology. Without great financial resources (and corresponding shareholder Figure 7. Quorum slice map obligations), it would have been difficult to recruit 5 tier one organizations from the start, however. This suggests quorum slices play a useful role in network bootstraping: anyone can join with the goal of becoming an important player because there are no gatekeepers to pairwise agreement. There are currently over 3.3M accounts in the ledger. Over a recent 24-hour period, Stellar averaged 4.5 transactions and 15.7 operations per second. Reviewing recent ledgers, most transactions seem to have a single operation, while every few ledgers we see transactions containing many operations that appear to come from market makers managing offers. The mean times to achieve consensus and update the ledger were 1061 ms and 46 ms, respectively. The 99th percentiles were 2252 ms and 142 ms (the former reflecting a 1-second timeout in nomination leader selection). Note SCP’s performance is mostly independent of transactions per second, since SCP agrees on a hash of arbitrarily many transactions. Bottlenecks are more likely to arise from propagating candidate transactions during nomination, executing and validating transactions, and merging buckets. We have not yet needed to parallelize stellar-core’s transaction processing over multiple CPU cores or disk drives. We also evaluated the number of SCP messages broadcast on the production network. In the normal case with a single leader elected to nominate a value, we expect seven logical messages to be broadcast: two messages to vote and accept a nominate statement, two messages to accept and confirm a prepare statement, two message to accept and confirm a commit statement, and finally, an externalize message (sent after committing a new ledger to disk to help stragglers catch up). The implementation combines confirm commit and externalize messages as an optimization, since it is safe to externalize a value after it is committed. We then analyze metrics gathered on a production Stellar validator. Over the course of 68 hours, 1.3 messages/second were emitted, averaging to 6-7 messages per ledger. We note that the total

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Percentile Number of Timeouts Nomination Balloting 75% 0 0 99% 1 0 Max 4 1 Figure 8. Timeouts per ledger over 68 hours count of messages broadcast by validators is larger, since in addition to federated voting messages, nodes also broadcast any transactions they learn about. Figure 8 shows the timeouts experienced by a production validator over a period of 68 hours. Nomination timeouts are a measure of the (in)effectiveness of the leader election function, while ballot timeouts depend heavily on the network and potential message delays. The timeouts are consistent with the number of messages emitted: six messages in the best case scenario, and at least seven messages if an additional nomination round is needed. 7.3 Controlled experiments We ran controlled experiments in containers packed onto Amazon EC2 c5d.9xlarge instances with 72 GiB of RAM, 900 GB of NVMe SSD, and 36 vCPUs. Each instance was in the same EC2 region and had a fixed bandwidth of 10 Gbps. We used SQLite as a store. (Stellar also supports PostgreSQL, but that has asynchronous tasks that inject noise into measurements.) Stellar provides a built-in runtime query, generateload, that allows generating synthetic load at a specific target transaction/second rate. Although Stellar supports various trading features, such as order book and cross-asset path payments, we focused on simple payments. Confirming transactions consists of multiple steps, so we recorded the measurements for each of the following: • Nomination: time from nomination to first prepare • Balloting: time from first prepare to confirming a ballot committed • Ledger update: time to apply consensus value • Transaction count: confirmed transactions per ledger Each of our experiments was defined by three parameters: the number of account entries in the ledger, the amount of load (in the form of XLM payments) submitted per second, and the number of validators. We configured every validator to know about every other validator (a worst-case scenario for SCP), with quorum slices set to any simple majority of nodes (so as to maximize the number of different quorums). Baseline Our baseline experiment measured Stellar with 100,000 accounts, four validators, and the load generation rate of 100 transactions/second. We observed 507 transactions per ledger on average, with standard deviation of 49 (9.7%). Note that no transactions were dropped; the slight 105 106 107 0 500 1,000 1,500 2,000 Accounts Latency [ms] Ledger update Balloting Nomination Figure 9. Latency as number of accounts increases variance is due to scheduling limitations of the load generator. We observed that the number of transactions per ledger was consistent with our load generation rate, given ledger closing every 5 seconds. Nomination, balloting, and ledger update showed mean latencies of 82.53 ms, 95.96 ms, and 174.08 ms, respectively. We observed that nomination latency 99th percentile is consistently under 61ms, with occasional spikes of roughly 1 second, corresponding to the first step in the timeout function of leader selection. Given the baseline performance, we looked at the effects of varying each of the test setup parameters. Accounts The data in Figure 9 suggests that Stellar scales well as the number of accounts increases. Generation of test accounts became a lengthy process, as bucket creation and merging prevented us from simply populating the database with accounts directly via SQL. Therefore, we conducted our experiments for up to 50,000,000 accounts. While there is minimal impact on consensus and ledger update latencies, we note that increasing accounts creates an overhead of merging buckets, which get larger. Transaction rate Transaction rate impacts the amount of traffic multicast among validators, the number of transactions included in each ledger, and the size of the top level buckets. To understand the effects of increasing transaction load, we ran an experiment with 100,000 accounts and 4 validators. Figure 10 shows slow growth in the consensus latency, while the majority of time was spent updating the ledger. Not surprisingly, as the transaction set increases in size, it takes longer to commit it to the database. We also note that ledger update latency is heavily implementation-dependent, and is affected by the choice of the database. Validator nodes To see how increasing the number of tierone validators impacts performance, we ran experiments with 100,000 accounts, 100 transactions/second, and a varying number of validators from 4 to 43. All validators appeared in all validators’ quorum slices; smaller quorum slices would have a lesser impact on performance.

SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada Lokhava et al. 100 150 200 250 300 350 0 500 1,000 1,500 2,000 Load [transactions/second] Latency [ms] Ledger update Balloting Nomination Figure 10. Latency as transaction load increases 10 20 30 40 0 500 1,000 1,500 2,000 Validators Latency [ms] Ledger update Balloting Nomination Figure 11. Latency as number of nodes increases Changing the number of validating nodes on the network impacts the number of SCP messages exchanged as well as the number of potential values during nomination. Figure 11 shows nomination time growing at a relatively small rate. While the data suggests that balloting is the bottleneck, we believe many scaling issues can be addressed by improving Stellar’s overlay network to optimize network traffic. As expected, ledger update latency remained independent of the number of nodes. Close rate Lastly, we wanted to measure Stellar’s end-toend performance by measuring how often ledgers are confirmed and whether Stellar meets its 5-second target without dropping any transactions. We observed average ledger close times of 5.03 s, 5.10 s, and 5.15 s as we increased account entries, transaction rate, and number of nodes, respectively. The results suggest that Stellar can consistently close ledgers under high load. 7.4 Running a validator One of the important features of Stellar is the low cost of running a validator, as anchors should run (or contract with) validators to enforce finality. SDF runs 3 production validators, all on c5.large AWS instances, which have two cores, 4 GiB of RAM and Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz processors. Inspecting resource usage on one of these machines, we observed the Stellar process using around 7% of CPU and 300 MiB of memory. In terms of network traffic, with 28 connections to peers and a quorum size of 34, the incoming and outgoing rates were 2.78 Mbit/s and 2.56 Mbit/s, respectively. Hardware required to run such a process is inexpensive. In our case, the cost is $0.054/hour or about $40/month. 7.5 Future work These experiments suggest Stellar can easily scale 1–2 orders of magnitude beyond today’s network usage. Because the performance demands have been so modest to date, Stellar leaves room for many straight-forward optimizations using well-known techniques. For example, transactions and SCP messages are broadcast by validators using a naïve flooding protocol, but should ideally use more efficient, structured peer-to-peer multicast [30]. Additionally, database-heavy ledger update time can be improved through standard batching and prefetching techniques.

Évaluation

Stellar network quorum slice map showing validator nodes and their bidirectional dependencies

Comprendre l’adéquation de Stellar en tant que paiement global et réseau commercial, nous avons évalué l'état du réseau public et mené des expériences contrôlées sur un laboratoire expérimental privé réseau. Nous nous sommes concentrés sur les questions suivantes : • À quoi ressemble la topologie du réseau de production ? Combien de messages sont diffusés en moyenne, et comment SCP subit-il les délais d'attente ? • Les latences de consensus et de mise à jour du grand livre restent-elles indépendantes du nombre de comptes ?SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. • Comment les latences sont-elles affectées par l'augmentation (a) des transactions par seconde (et, par conséquent, des transactions par seconde) ? grand livre), et (b) le nombre de nœuds validator ? • Quel est le coût de fonctionnement d'un nœud en termes de CPU, mémoire et bande passante réseau ? Les réseaux de paiement ont des taux de transaction faibles par rapport à d’autres types de systèmes distribués. Les principaux blockchain, Bitcoin et Ethereum, confirment jusqu'à 15 transactions/seconde, inférieur à Stellar. De plus, ces systèmes prennent quelques minutes pour une heure pour confirmer une transaction en toute sécurité, car la preuve de travail nécessite d'attendre plusieurs blocs pour être extraits. Le Le réseau SWIFT non blockchain n'a enregistré en moyenne que 420 transactions par seconde lors de sa journée de pointe [14]. Nous avons donc choisi pour comparer nos mesures par rapport à l'objectif de 5 secondes intervalle du grand livre, un objectif plus agressif. Nos résultats montrent que les latences sont confortablement inférieures à cette limite, même avec plusieurs optimisations non implémentées sont toujours en cours. 7.1 Ancres Les actifs les plus négociés en volume incluent la devise (par exemple, 3 USD ancres, 2 CNY), une ancre Bitcoin, un titre adossé à l'immobilier token [92] et une devise intégrée à l'application [8]. Différentes ancres ont des politiques différentes. Par exemple, une ancre en USD, Stronghold, définit auth_reqired et nécessite un processus de connaissance du client (KYC) pour chaque compte qui détient son actifs. Un autre, AnchorUSD, permet à tout le monde de recevoir et d'échanger leur USD (ce qui permet littéralement d'envoyer 0,50 $ au Mexique en 5 secondes avec des frais de 0,000001 $). Cependant, AnchorUSD nécessite un KYC et des frais pour acheter ou échanger leurs USD avec des virements électroniques classiques. Aux Philippines, où les réglementations bancaires sont plus laxistes pour les paiements entrants, coins.ph prend en charge l'encaissement de PHP sur n'importe quel guichet automatique [36]. En plus des token de sécurité susmentionnés et de la devise de l'application, il existe une gamme de token non monétaires allant de obligations commerciales [22] et crédits carbone [85, 96] à plus des actifs ésotériques tels qu'un token collaboratif incitatif reprise de possession de voiture [35]. 7.2 Réseau public Au moment d'écrire ces lignes, il existe 126 nœuds complets actifs, dont 66 participer au consensus en signant les messages de vote. Figure 7 (généré par [5]) visualise le réseau, avec une ligne entre deux nœuds si l’un apparaît dans les tranches de quorum de l’autre et un ligne bleue plus foncée pour montrer la dépendance bidirectionnelle. Au Le centre est un groupe de 17 « validators » de facto gérés par SDF, SatoshiPay, LOBSTR, COINQVEST et Keybase. Il y a quatre mois, avant les événements de la Section 6, il y avait il y avait 15 nœuds d'importance systémique : 3 provenant apparemment organisations de premier niveau et plusieurs singletons aléatoires. Le le graphique semblait également beaucoup moins régulier. Par conséquent, le nouveau mécanisme de configuration et/ou de meilleures décisions des opérateurs semblent contribuer à une topologie de réseau plus saine. Sans d'excellentes ressources financières (et un actionnaire correspondant Figure 7. Carte des tranches de quorum obligations), il aurait été difficile de recruter 5 tier one organisations dès le départ. Cela suggère un quorum les tranches jouent un rôle utile dans l'amorçage du réseau : n'importe qui peut rejoindre avec l'objectif de devenir un acteur important car il n’y a pas de gardiens à l’accord par paires. Il y a actuellement plus de 3,3 millions de comptes dans le grand livre. Fini sur une période récente de 24 heures, Stellar a réalisé en moyenne 4,5 transactions et 15,7 opérations par seconde. En examinant les registres récents, la plupart les transactions semblent avoir une seule opération, alors que toutes les quelques grands livres, nous voyons des transactions contenant de nombreuses opérations qui semblent provenir des teneurs de marché gérant les offres. Le les délais moyens pour parvenir à un consensus et mettre à jour le grand livre étaient 1061 ms et 46 ms, respectivement. Les 99e percentiles étaient 2252 ms et 142 ms (le premier reflétant un délai d'attente d'une seconde dans la sélection des chefs de file des nominations). Notez que les performances de SCP sont principalement indépendant des transactions par seconde, puisque SCP s'entend sur un hash de transactions arbitrairement nombreuses. Les goulots d'étranglement sont plus susceptibles de provenir de la propagation des candidats transactions lors de la nomination, de l’exécution et de la validation transactions et fusion de compartiments. Nous n'avons pas encore eu besoin pour paralléliser le traitement des transactions de Stellar-Core sur plusieurs cœurs de processeur ou lecteurs de disque. Nous avons également évalué le nombre de messages SCP diffusés sur le réseau de production. Dans le cas normal avec un seul leader élu pour désigner une valeur, nous nous attendons à sept logiques messages à diffuser : deux messages pour voter et accepter un nomidéclaration nate, deux messages pour accepter et confirmer une instruction de préparation, deux messages pour accepter et confirmer une instruction de validation et enfin un message d'externalisation (envoyé après avoir validé un nouveau registre sur le disque pour aider les retardataires rattraper). L'implémentation combine confirmer le commit et externaliser les messages comme une optimisation, car c'est il est sûr d’externaliser une valeur après son engagement. Nous analysons ensuite les métriques recueillies sur une production Stellar validator. Fini en 68 heures, 1,3 messages/seconde ont été émis, en moyenne 6 à 7 messages par registre. Nous notons que le total

Paiements internationaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Centile Nombre de délais d'attente Nomination Vote 75% 0 0 99% 1 0 Max. 4 1 Figure 8. Délais d'attente par grand livre sur 68 heures le nombre de messages diffusés par validators est plus grand, car dans En plus des messages de vote fédérés, les nœuds diffusent également toutes les transactions dont ils ont connaissance. La figure 8 montre les délais d'attente rencontrés par une production validator sur une période de 68 heures. Les délais de nomination sont une mesure de l’(in)efficacité de la fonction d’élection des dirigeants, alors que les délais d’attente des votes dépendent fortement du réseau et les retards potentiels des messages. Les délais d'attente sont cohérents avec le nombre de messages émis : six messages dans le dans le meilleur des cas, et au moins sept messages si un tour de nomination supplémentaire est nécessaire. 7.3 Expériences contrôlées Nous avons mené des expériences contrôlées dans des conteneurs emballés sur Instances Amazon EC2 c5d.9xlarge avec 72 Gio de RAM, 900 Go de SSD NVMe et 36 vCPU. Chaque instance était dans la même région EC2 et avait une bande passante fixe de 10 Gbit/s. Nous avons utilisé SQLite comme magasin. (Stellar prend également en charge PostgreSQL, mais cela comporte des tâches asynchrones qui injectent du bruit dans les mesures.) Stellar fournit une requête d'exécution intégrée, generateload, qui permet de générer une charge synthétique sur une cible spécifique transaction/second taux. Bien que Stellar prenne en charge divers fonctionnalités de trading, telles que le carnet d'ordres et le parcours multi-actifs paiements, nous nous sommes concentrés sur les paiements simples. La confirmation des transactions comprend plusieurs étapes, nous enregistré les mesures pour chacun des éléments suivants : • Nomination : délai entre la nomination et la première préparation. • Vote : temps écoulé entre la première préparation et la confirmation d'un scrutin engagé • Mise à jour du grand livre : il est temps d'appliquer la valeur consensuelle • Nombre de transactions : transactions confirmées par grand livre Chacune de nos expériences a été définie par trois paramètres : le nombre d'écritures de compte dans le grand livre, le montant de charge (sous forme de paiements XLM) soumise par seconde, et le nombre de validator. Nous avons configuré chaque validator connaître tous les autres validator (le pire des cas pour SCP), avec des tranches de quorum fixées à une majorité simple de nœuds (afin de maximiser le nombre de quorums différents). Référence Notre expérience de base mesurait Stellar avec 100 000 comptes, quatre validator et la génération de charge taux de 100 transactions/seconde. Nous avons observé 507 transactions par grand livre en moyenne, avec un écart type de 49. (9,7%). Notez qu'aucune transaction n'a été abandonnée ; le léger 105 106 107 0 500 1 000 1 500 2 000 Comptes Latence [ms] Mise à jour du grand livre Vote Nomination Figure 9. Latence à mesure que le nombre de comptes augmente la variance est due aux limitations de planification du générateur de charge. Nous avons observé que le nombre de transactions par grand livre était cohérent avec notre taux de génération de charge, compte tenu du grand livre fermeture toutes les 5 secondes. Nomination, vote et grand livre la mise à jour a montré des latences moyennes de 82,53 ms, 95,96 ms et 174,08 ms, respectivement. Nous avons observé que la latence de nomination Le 99e centile est constamment inférieur à 61 ms, avec des des pics d'environ 1 seconde, correspondant à la première étape dans la fonction de timeout de sélection du leader. Compte tenu des performances de base, nous avons examiné les effets de faire varier chacun des paramètres de configuration du test. Comptes Les données de la figure 9 suggèrent que Stellar évolue ainsi que le nombre de comptes augmente. Génération de test les comptes sont devenus un processus long, à mesure que la création du compartiment et la fusion nous a empêché de simplement remplir la base de données avec des comptes directement via SQL. C'est pourquoi nous avons mené notre expériences pour un maximum de 50 000 000 de comptes. Alors qu'il y a impact minimal sur les latences de consensus et de mise à jour du grand livre, nous constatons que l'augmentation des comptes crée une surcharge de fusionner des buckets, qui deviennent plus grands. Taux de transactions Le taux de transaction a un impact sur le montant de multidiffusion du trafic entre validators, le nombre de transactions incluses dans chaque grand livre et la taille du niveau supérieur seaux. Comprendre les effets de l’augmentation des transactions charge, nous avons mené une expérience avec 100 000 comptes et 4 validator. La figure 10 montre une croissance lente de la latence du consensus, tandis que la majorité du temps était consacrée à la mise à jour du grand livre. Il n’est pas surprenant qu’à mesure que la taille de l’ensemble des transactions augmente, prend plus de temps pour le valider dans la base de données. Nous notons également que la latence de mise à jour du grand livre dépend fortement de la mise en œuvre, et est affecté par le choix de la base de données. Nœuds de validation Pour voir comment augmenter le nombre de validator tieronea un impact sur les performances, nous avons mené des expériences avec 100 000 comptes, 100 transactions/seconde et un nombre variable de validator de 4 à 43. Tous les validator sont apparus dans toutes les tranches de quorum de validator ; des tranches de quorum plus petites ont un moindre impact sur les performances.SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada Lokhava et coll. 100 150 200 250 300 350 0 500 1 000 1 500 2 000 Charger [transactions/seconde] Latence [ms] Mise à jour du grand livre Vote Nomination Figure 10. Latence à mesure que la charge de transaction augmente 10 20 30 40 0 500 1 000 1 500 2 000 Validateurs Latence [ms] Mise à jour du grand livre Vote Nomination Figure 11. Latence à mesure que le nombre de nœuds augmente Modification du nombre de nœuds de validation sur le réseau impacte le nombre de messages SCP échangés ainsi que le nombre de valeurs potentielles lors de la nomination. Figure 11 montre que le temps de nomination augmente à un rythme relativement faible. Même si les données suggèrent que le scrutin constitue le goulot d'étranglement, nous Je pense que de nombreux problèmes de mise à l'échelle peuvent être résolus en améliorant Réseau superposé de Stellar pour optimiser le trafic réseau. Comme attendu, la latence de mise à jour du grand livre est restée indépendante de le nombre de nœuds. Taux de clôture Enfin, nous voulions mesurer les performances de bout en bout de Stellar en mesurant la fréquence à laquelle les grands livres sont confirmés et si Stellar atteint son objectif de 5 secondes sans abandonnant toute transaction. Nous avons observé une clôture moyenne du grand livre des temps de 5,03 s, 5,10 s et 5,15 s à mesure que nous augmentions le compte entrées, taux de transaction et nombre de nœuds, respectivement. Les résultats suggèrent que Stellar peut clôturer systématiquement les grands livres sous forte charge. 7.4 Exécution d'un validator L'une des caractéristiques importantes de Stellar est le faible coût de exécuter un validator, car les ancres devraient exécuter (ou contracter avec) validators pour faire respecter le caractère définitif. SDF exécute 3 validator de production, tous sur des instances AWS c5.large, qui ont deux cœurs, 4 Go de RAM et processeur Intel(R) Xeon(R) Platinum 8124M @ Processeurs 3,00 GHz. Inspecter l'utilisation des ressources sur un de ces machines, nous avons observé le processus Stellar utilisant environ 7% du CPU et 300 Mo de mémoire. En termes de trafic réseau, avec 28 connexions aux pairs et une taille de quorum sur 34, les débits entrants et sortants étaient de 2,78 Mbit/s et 2,56 Mbit/s, respectivement. Matériel requis pour exécuter un tel le processus est peu coûteux. Dans notre cas, le coût est de 0,054$/heure soit environ 40$/mois. 7.5 Travaux futurs Ces expériences suggèrent que Stellar peut facilement faire évoluer 1 à 2 commandes d’ampleur au-delà de l’utilisation actuelle du réseau. Parce que le les exigences de performance ont été si modestes jusqu'à présent, Stellar laisse place à de nombreuses optimisations simples en utilisant techniques bien connues. Par exemple, les transactions et SCP les messages sont diffusés par validators à l'aide d'une inondation naïve protocole, mais devrait idéalement utiliser un protocole plus efficace et plus structuré. Multidiffusion peer-to-peer [30]. De plus, lourd en base de données Le temps de mise à jour du grand livre peut être amélioré grâce à des techniques standard de traitement par lots et de prélecture.

Conclusion

International payments are expensive and take days. Fund custody passes through multiple financial institutions including correspondent banks and money transfer services. Because each hop must be fully trusted, it is difficult for new entrants to gain market share and compete. Stellar shows how to send money around the world cheaply in seconds. The key innovation is a new open-membership Byzantine agreement protocol, SCP, that leverages the peer-to-peer structure of the financial network to achieve global consensus under a novel Internet hypothesis. SCP lets Stellar atomically commit irreversible transactions across arbitrary participants who don’t know about or trust each other. That in turn guarantees new entrants access to the same markets as established players, makes it secure to get the best available exchange rates even from untrusted market makers, and dramatically reduces payment latency. Acknowledgments Stellar would not be where it is today without the early leadership of Joyce Kim or the tremendous contributions of Scott Fleckenstein and Bartek Nowotarski in building and maintaining horizon, the Stellar SDK, and other key pieces of the Stellar ecosystem. We also thank Kolten Bergeron, Henry Corrigan-Gibbs, Candace Kelly, Kapil K. Jain, Boris Reznikov, Jeremy Rubin, Christian Rudder, Eric Saunders, Torsten Stüber, Tomer Weller, the anonymous reviewers, and our shepherd Justine Sherry for their helpful comments on earlier drafts. Disclaimer Professor Mazières’s contribution to this publication was as a paid consultant, and was not part of his Stanford University duties or responsibilities.

Fast and secure global payments with Stellar SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada

Conclusion

Les paiements internationaux sont chers et prennent des jours. Fonds la garde passe par plusieurs institutions financières, notamment des banques correspondantes et des services de transfert d'argent. Parce que chaque saut doit être pleinement fiable, il est difficile pour les nouveaux entrants pour gagner des parts de marché et être compétitifs. Stellar affiche comment envoyer de l'argent partout dans le monde à moindre coût en quelques secondes. Le L'innovation clé est un nouveau protocole d'accord byzantin à adhésion ouverte, SCP, qui exploite la structure peer-to-peer du réseau financier pour parvenir à un consensus mondial dans le cadre nouvelle hypothèse sur Internet. SCP permet à Stellar de s'engager atomiquement transactions irréversibles entre participants arbitraires qui ne se connaissent pas et ne se font pas confiance. Cela garantit à son tour l’accès des nouveaux entrants aux mêmes marchés que ceux établis. joueurs, permet d'obtenir en toute sécurité le meilleur échange disponible taux même de la part de teneurs de marché peu fiables, et de façon spectaculaire réduit la latence de paiement. Remerciements Stellar ne serait pas là où il est aujourd'hui sans le début le leadership de Joyce Kim ou les formidables contributions de Scott Fleckenstein et Bartek Nowotarski dans la construction et maintenir Horizon, le SDK Stellar et d'autres éléments clés de l’écosystème Stellar. Nous remercions également Kolten Bergeron, Henry Corrigan-Gibbs, Candace Kelly, Kapil K. Jain, Boris Reznikov, Jeremy Rubin, Christian Rudder, Eric Saunders, Torsten Stüber, Tomer Weller, les évaluateurs anonymes et notre berger Justine Sherry pour ses commentaires utiles sur versions antérieures. Avis de non-responsabilité La contribution du professeur Mazières à cette publication était à titre de consultant rémunéré et ne faisait pas partie de son mandat. Devoirs ou responsabilités de l'Université de Stanford.

Paiements mondiaux rapides et sécurisés avec Stellar SOSP '19, du 27 au 30 octobre 2019, Huntsville, ON, Canada