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

Resumo

Os pagamentos internacionais são lentos e caros, em parte devido ao roteamento de pagamentos multi-hop através de plataformas heterogêneas. sistemas bancários. Stellar é uma nova rede global de pagamentos que pode transferir dinheiro digital diretamente para qualquer lugar do mundo em segundos. A principal inovação é uma transação segura mecanismo através de intermediários não confiáveis, usando um novo Protocolo de acordo bizantino denominado SCP. Com o SCP, cada instituição especifica outras instituições com as quais permanecer de acordo; através da interconectividade global do sistema financeiro, toda a rede concorda então com a energia atômica transações abrangendo instituições arbitrárias, sem risco de solvência ou de taxa de câmbio de emissores intermediários de ativos ou formadores de mercado. Apresentamos o modelo, protocolo e verificação formal; descrever a rede de pagamento Stellar; e finalmente avaliar Stellar empiricamente através de benchmarks e nossa experiência com vários anos de uso em produção. Conceitos de CCS • Segurança e privacidade →Distribuído segurança de sistemas; • Organização de sistemas informáticos → Arquiteturas ponto a ponto; • Sistemas de informação → Transferência eletrônica de fundos. Palavras-chave blockchain, BFT, quóruns, pagamentos Formato de referência ACM: Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, Jed McCaleb. 2019. Pagamentos globais rápidos e seguros com Stellar. No SOSP '19: Simpósio sobre Princípios de Sistemas Operacionais, 27 a 30 de outubro, 2019, Huntsville, ON, Canadá. ACM, Nova York, NY, EUA, 17 páginas. 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.

Introdução

Os pagamentos internacionais são notoriamente lentos e caros [32]. Considere a impraticabilidade de enviar US$ 0,50 dos EUA para * Galois, Inc. †UCLA Permissão para fazer cópias digitais ou impressas de todo ou parte deste trabalho para o uso pessoal ou em sala de aula é concedido gratuitamente, desde que as cópias não sejam feitos ou distribuídos com fins lucrativos ou vantagens comerciais e que as cópias contenham este aviso e a citação completa na primeira página. Direitos autorais para componentes deste trabalho de propriedade de terceiros que não a ACM devem ser honrados. Abstraindo com crédito é permitido. Para copiar de outra forma, ou republicar, para postar em servidores ou para redistribuir para listas, requer permissão prévia específica e/ou taxa. Solicitação permissões de [email protected]. SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá © 2019 Associação de Máquinas de Computação. ACM ISBN 978-1-4503-6873-5/19/10...$15,00 https://doi.org/10.1145/3341301.3359636 México, dois países vizinhos. Os usuários finais pagam quase US$ 9 para a média dessa transferência [32], e um acordo bilateral intermediada pelos bancos centrais dos países só poderia reduzir o banco subjacente custa US$ 0,67 por item [2]. Além das taxas, a latência dos pagamentos internacionais é geralmente contada em dias, impossibilitando a obtenção rápida de dinheiro no exterior em emergências. Em países onde o sistema bancário não funciona ou não serve todos os cidadãos, ou onde as taxas são intoleráveis, as pessoas recorrem ao envio de pagamentos por autocarro [38], por barco [19], e ocasionalmente agora por Bitcoin [55], todos os quais incorrer em risco, latência ou inconveniência. Embora sempre haja custos de conformidade, as evidências sugerem que uma quantia significativa é perdida devido à falta de concorrência [21], que é exacerbado pela tecnologia ineficiente. Onde as pessoas pode inovar, os preços e as latências caem. Por exemplo, as remessas de contas bancárias no segundo trimestre de 2019 custaram em média 6,99%, enquanto o valor do dinheiro móvel foi de apenas 4,88% [13]. Uma rede de pagamentos aberta e global que atrai inovação e a concorrência de entidades não bancárias poderá reduzir custos e latências em todas as camadas, incluindo conformidade [83]. Este artigo apresenta Stellar, um sistema de pagamento baseado em blockchain rede especificamente projetada para facilitar a inovação e concorrência nos pagamentos internacionais. Stellar é o primeiro sistema para atender a todos os três objetivos a seguir (sob um “hipótese da Internet” nova, mas empiricamente válida: 1. Associação aberta – Qualquer pessoa pode emitir títulos garantidos por moeda tokens digitais que podem ser trocados entre os usuários. 2. Finalidade imposta pelo emissor – O emissor de um token pode evitar transações em token sejam revertidas ou desfeitas. 3. Atomicidade entre emissores – Os usuários podem trocar atomicamente e negociar tokens de vários emissores. Alcançar os dois primeiros é fácil. Qualquer empresa pode oferecer unilateralmente um produto como Paypal, Venmo, WeChat Pay, ou Alipay e garantir a finalização dos pagamentos no moedas virtuais que eles criaram. Infelizmente, fazer transações atomicamente entre essas moedas é impossível. Na verdade, apesar do Paypal ter adquirido a controladora da Venmo em 2013, ainda é impossível para os usuários finais enviarem Venmo dólares para usuários do Paypal [78]. Só recentemente os comerciantes podem até mesmo aceitar ambos com uma única integração. Os objectivos 2 e 3 podem ser alcançados num sistema fechado. Em particular, vários países dispõem de sistemas de pagamento internos eficientes redes, normalmente supervisionadas por uma autoridade reguladora de confiança universal. No entanto, a adesão é limitada a um período fechado conjunto de bancos licenciados e as redes são limitadas ao alcance da autoridade reguladora de um país.SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. As metas 1 e 3 foram alcançadas em blockchains minadas, mais notavelmente na forma de ERC20 tokens em Ethereum [3]. A ideia principal desses blockchains é criar uma nova criptomoeda com a qual recompensar as pessoas por fazerem acordos transações difíceis de reverter. Infelizmente, isso significa que os emissores token não controlam a finalidade da transação. Se software erros fazem com que o histórico de transações seja reorganizado [26, 73], ou quando os despojos de fraudar as pessoas excedem o custo de reorganizando o histórico [74, 97], os emissores podem ser responsáveis por tokens eles já foram resgatados por dinheiro do mundo real. O Stellar blockchain possui duas propriedades distintas. Primeiro, ele oferece suporte nativo a mercados eficientes entre tokens de diferentes emissores. Especificamente, qualquer pessoa pode emitir um token, o blockchain fornece uma carteira de pedidos integrada para negociação entre qualquer par de tokens, e os usuários podem emitir pagamentos de caminho que negociam atomicamente em vários pares de moedas enquanto garantindo um preço limite de ponta a ponta. Em segundo lugar, Stellar introduz um novo acordo bizantino protocolo, SCP (Stellar Protocolo de Consenso), através do qual token emissores designam servidores validator específicos para aplicar finalidade da transação. Contanto que ninguém comprometa os validators de um emissor (e as assinaturas digitais subjacentes e hashes criptográficos permanecem seguros), o emissor sabe exatamente quais transações ocorreram e evita o risco de perdas decorrentes da reorganização histórica de blockchain. A ideia principal do SCP é que a maioria dos emitentes de activos beneficiam mercados líquidos e querem facilitar as transações atômicas com outros ativos. Portanto, os administradores validator configuram seus servidores para concordar com outros validators sobre o exato histórico de todas as transações em todos os ativos. Um validator v1 pode ser configurado para concordar com v2, ou v2 pode ser configurado para concordar com v1, ou ambos podem ser configurados para concordar entre si; em todos os casos, nenhum dos dois se comprometerá com um histórico de transações até sabe que o outro não pode comprometer-se com uma história diferente. Por transitividade, se v1 não pode discordar de v2 e v2 não pode discordar de v3 (ou vice-versa), v1 não pode discordar de v3. v3, se v3 representa ou não ativos, v1 já ouviu falar de. Sob a hipótese de que essas relações de acordo conectar transitivamente toda a rede, o SCP garante acordo global, tornando-o um acordo bizantino global protocolo com adesão aberta. Chamamos esta nova suposição de conectividade de hipótese da Internet, e notamos que ela detém tanto da “Internet” (que todos entendem significa a maior rede IP conectada transitivamente) e pagamentos internacionais legados (que são executados passo a passo não atômico, mas alavancar um mundo transitivamente conectado e global rede de instituições financeiras). Stellar está em uso em produção desde setembro de 2015. Para manter o comprimento blockchain gerenciável, o sistema executa SCP em intervalos de 5 segundos – rápido para os padrões blockchain, mas muito mais lento do que as aplicações típicas do acordo bizantino. Embora o uso principal tenha sido pagamentos, Stellar também comprovadamente atraente para tokens fungíveis não monetários que se beneficiam provenientes de mercados secundários imediatos (ver Secção 7.1). A próxima seção discute trabalhos relacionados. A seção 3 apresenta SCP. A Seção 4 descreve nossa verificação formal do SCP. A seção 5 descreve a camada de pagamento de Stellar. A seção 6 relaciona um pouco de nossa experiência de implantação e lições aprendidas. A seção 7 avalia o sistema. A seção 8 conclui.

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.

Trabalho relacionado

O sistema descrito neste artigo é coletivamente nosso terceiro tentativa de realizar uma rede de pagamentos descentralizada. O primeira tentativa, de um dos autores, resultou no Ripple blockchain. Embora ainda exista, acreditamos que a Ripple não pode concretizar a visão de uma rede de pagamento verdadeiramente aberta para tanto por razões de governação como técnicas. As razões de governança decorrem da tensão entre os interesses dos acionistas e usuários da rede, mas estão além do escopo deste documento. O O problema técnico é que o protocolo do acordo bizantino da Ripple [89] requer adesão quase fechada [33], tornando-o funcionalmente semelhante ao acordo bizantino convencional. A segunda tentativa, uma bifurcação de curta duração do código Ripple base chamada Stellard, entrou em operação em julho de 2014. Tínhamos planejado desenvolver SCP e encaixá-lo no Stellar quando estiver pronto, mas em vez disso decidiu construir um novo sistema do zero em torno do SCP, chamado de núcleo estelar e descrito neste artigo. núcleo estelar foi divulgado junto com uma descrição e prova de SCP [68] em abril de 2015 e entrou em uso em produção 5 meses depois. Um rascunho da Internet [20] descreveu posteriormente o SCP para implementadores. A motivação e a estrutura do SCP são semelhantes à confiança assimétrica na computação multipartidária [40], embora esse modelo exige que os nós tenham uma visão global da estrutura adversária. Ao introduzir uma noção de fatias de quórum, o SCP desfruta capacidade de descoberta e associação dinâmica que são importantes para a implantação de Stellar. Quórum pessoal bizantino sistemas [47] e confiança distribuída assimétrica [29] generalizam os quóruns do SCP e simplificam a comparação com os tradicionais sistemas. Num cenário mais restrito, Gotsman et al. [49] também estude uma generalização dos quóruns de Stellar. Vários outros blockchains adotaram SCP, incluindo MobileCoin [7] e NCNT. Ripple também propôs mais recentemente um protocolo de acordo bizantino de adesão aberta chamado Cobalto [66]. A segurança do SCP é ótima, então o SCP está seguro em qualquer cenário de falha onde o Cobalt esteja, enquanto o inverso é não está claro. No entanto, a Cobalt afirma que sua condição de segurança é mais fácil de entender e, portanto, menos propensa a erros de configuração. o que será interessante avaliar se o Cobalt for implantado. 2.1 Sistemas sem adesão aberta Como muitos protocolos de consenso, o SCP é baseado em votação [50, 94] em um sistema de quórum. Trabalhos anteriores sobre sistemas de quórum [52, 67, 72], às vezes chamados de “conjuntos sobreviventes” [57], estudam sistemas de quórum que são estáticos, ou seja, fixos por toda parte execução do sistema e uniforme, ou seja, onde todos os nós possuem o mesma noção do que é um quórum. A configuração do SCP é diferente em que nós diferentes aceitam quóruns diferentes e em evolução.Pagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Consenso rápido e heterogêneo [91] permite mais nuances noções de confiança a serem expressas através de rótulos em uma rede e aproveita isso para otimizar a comunicação, mas assume adesão fechada. Outros esforços para adaptar os protocolos do acordo bizantino para configurações semelhantes a Blockchain, incluindo HoneyBadger [70], SBFT [53] e HotStuff [99] se concentraram na escalabilidade para muitos participantes e desempenho em redes de longa distância, mantendo o modelo tradicional de associação fechada. Blockchains direcionados a membros fechados alavancaram tais protocolos, incluindo mais recentemente Libra [11]. 2.2 Sistemas sem finalidade imposta pelo emissor Bitcoin [71] foi o primeiro ativo digital fungível sem autoridade confiável para rastrear saldos. Resolveu simultaneamente dois problemas: como distribuir um novo ativo para que as pessoas acreditem tem valor e como fornecer transações irreversíveis que evitar ataques de gasto duplo. Bitcoin cria ativos por meio de proof-of-work [43], que seu autor compara aos garimpeiros que investem recursos para aumentar a oferta de ouro. O o trabalho comprovado depende do histórico de transações, o que impede ataques de gasto duplo porque reverter transações requer um trabalho comparável à criação do histórico original. Ataques a proof-of-work blockchains tornam-se viáveis uma vez que um invasor controla 1/3 do poder de mineração [46, 48]. A prova de trabalho é particularmente arriscada para blockchains novos ou menores [15, 23]; mineiros estabelecidos são conhecidos por desviar a mineração poder para cadeias menores com fins lucrativos [10, 54, 74, 97, 98] ou apenas para criar problemas [25, 37] (os chamados “ataques Goldfinger” [60]). Às vezes, os mineiros montaram benevolentemente esses “ataques de 51%” para reverter os efeitos indesejados dos bugs [95]. Novo blockchains podem obter alguma proteção contra ataques de 51% por aproveitando blockchains mais estabelecidos com mineração mesclada [6] ou prova de queima [79]. No momento em que este livro foi escrito, estimava-se que um ataque de 51% custasse US$ 823.000/ hora em Bitcoin, $93,000/hour on Ethereum, and under $20.000/ hora para todos os outros blockchains [12] rastreados. Em última análise, estes os custos dependem do valor da criptomoeda que incentiva a mineração, que independe do valor da moeda emitida ativos. Por outro lado, o custo de comprometer Stellar validators está de certa forma sob o controle de seus administradores; O SCP é passível de implementações de alta garantia, como usando módulos de segurança de hardware para evitar que um validator assinando mensagens contraditórias. Como benefício adicional, Stellar não tem custos de mineração para recuperar por meio de transação honorários ou senhoriagem. O enorme consumo de energia de Bitcoin [76] motivou variações de prova de trabalho com maior eficiência energética, como comprovante de espaço [16, 17, 44, 87], comprovante de armazenamento [18, 56, 86, 90], e comprovante de tempo decorrido [4]. A prova de trabalho pode ser lenta, com blocos de transações levando minutos para confirmar e vários blocos necessários para segurança mais forte. Entretanto, o trabalho para minerar um bloco pode ser amortizado em um lote de transações de tamanho arbitrário, limitado apenas por questões políticas e compatibilidade. BitcoinNG [45] usa prova de trabalho para eleger um líder que coordena um lote maior de transações. Thunderella [84] pode usar prova de trabalho como um “caminho lento” alternativo e confirmar com otimismo transações muito mais rápidas usando um consenso assíncrono protocolo quando um nó acelerador e 3/4 de um comitê eleito são honestos. Embora SCP seja mais rápido que proof-of-work, requer mais mensagens do que o caminho rápido de Thunderella, mas poderia ser potencialmente um caminho lento útil para Thunderella. Uma alternativa à prova de trabalho é a prova de aposta [59], em que os mineiros obtêm influência direta ou indiretamente da propriedade de ativos. Em alguns casos, a influência aumenta com o tempo em que os ativos são mantidos. Alguns esquemas encorajar a honestidade confiscando as participações dos mineiros se eles comportar-se mal [27, 28, 41]. Delegado proof-of-stake [9, 61] tem os nós votam sua aposta para eleger representantes para um protocolo de acordo bizantino convencional, como PBFT [31]. Algorand [51] usa funções aleatórias verificáveis para eleger nós representativos pseudoaleatoriamente, com probabilidade proporcional para participações em criptomoedas. Branca de Neve [39] formaliza o propriedades de segurança exigidas na prova de aposta, acomodando nós “sonolentos” que continuam eoff-line. Embora a maioria dos esquemas proof-of-stake não possam ser submetidos à força bruta com computação cara, o custo para adquirir participação ou subornar mineradores ainda está relacionado ao valor da criptomoeda subjacente e está fora do controle do emissor de ativos. Mesmo na ausência de mineradores maliciosos, os bugs também podem causar blockchain reorganização [26, 73]. Portanto, diferentemente do SCP, os emissores não têm como garantir a finalidade de blockchain antes resgatar tokens on-chain para uma transferência bancária no mundo real ou retirada de dinheiro.

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

Stellar protocolo de consenso

O protocolo de consenso Stellar (SCP) é um protocolo baseado em quórum Protocolo de acordo bizantino com adesão aberta. Os quóruns emergem das decisões combinadas de configuração local de nós individuais. No entanto, os nós só reconhecem quóruns aos quais eles próprios pertencem, e somente depois aprender as configurações locais de todos os outros membros do quórum. Um benefício desta abordagem é que o SCP inerentemente tolera visões heterogêneas de quais nós existem. Portanto, nós podem ingressar e sair unilateralmente sem necessidade de um Protocolo de “visualização de mudança” para coordenar a adesão. 3.1 Acordo Federado Bizantino O problema tradicional do acordo bizantino consiste em um sistema fechado de N nós, alguns dos quais são defeituosos e podem comportar-se arbitrariamente. Os nós recebem valores de entrada e trocam mensagens para decidir sobre um valor de saída entre as entradas. Um protocolo de acordo bizantino é seguro quando dois nós bem comportados não produzem decisões diferentes e o único decisão foi uma entrada válida (para alguma definição de acordo válidoSOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. previamente). Um protocolo está ativo quando garante que cada nó honesto eventualmente produz uma decisão. Normalmente, os protocolos assumem N = 3f + 1 para algum número inteiro f > 0, então garanta segurança e alguma forma de vivacidade para que desde que no máximo f nós estejam com defeito. Em algum momento destes protocolos, os nós votam nos valores propostos e uma proposta receber 2f + 1 votos, chamado de quórum de votos, torna-se a decisão. Com N = 3f + 1 nós, quaisquer dois quóruns de tamanho 2f + 1 sobreposição em pelo menos f + 1 nós; mesmo que f destes nós sobrepostos estão com defeito, os dois quóruns compartilham pelo menos um nó não defeituoso, evitando decisões contraditórias. No entanto, esta abordagem só funciona se todos os nós concordarem o que constitui um quórum, o que é impossível no SCP onde dois nós podem nem saber da existência um do outro. Com SCP, cada nó v declara unilateralmente conjuntos de nós, chamado de fatias de quorum, de modo que (a) v acredita que se todos membros de uma fatia concordam sobre o estado do sistema, então eles estão certos, e (b) v acredita que pelo menos uma de suas fatias estará disponível para fornecer informações oportunas sobre o estado do sistema. Chamamos o sistema resultante, consistindo de nós e suas fatias, um Acordo Bizantino Federado (FBA) sistema. Como veremos a seguir, surge um sistema de quórum das fatias dos nós. Informalmente, as fatias de um nó FBA expressam com quem o nó requer acordo. Por exemplo, um nó pode exigir acordo com 4 organizações específicas, cada uma executando 3 nós; para acomodar o tempo de inatividade, ele pode definir suas fatias como todas definidas consistindo em 2 nós de cada organização. Se isso “requer acordo com” relação relaciona transitivamente quaisquer dois nós, obtemos um acordo global. Caso contrário, podemos obter divergência, mas apenas entre organizações, nenhuma das quais exige acordo com o outro. Dada a topologia de hoje sistema financeiro, levantamos a hipótese de que a convergência generalizada continuará a produzir um único livro-razão histórico que as pessoas chamam “a rede Stellar”, assim como falamos da Internet. Os quóruns surgem das fatias da seguinte maneira. Cada nó especifica seu quórum é dividido em cada mensagem que envia. Seja S o conjunto de nós dos quais um conjunto de mensagens se originou. Um nó considera que o conjunto de mensagens atingiu o quorum limite quando cada membro de S tem uma fatia incluída em S. Por construção, tal conjunto S, se unânime, satisfaz o requisitos de acordo de cada um dos seus membros. Um colega defeituoso pode anunciar fatias criadas para mudar o que nós bem comportados consideram quóruns. Para fins de análise de protocolo, definimos um quórum no FBA como um valor não vazio conjunto S de nós abrangendo pelo menos uma fatia de quorum de cada membro não defeituoso. Esta abstração é sólida, como qualquer conjunto de mensagens que pretendem representar um quórum unânime realmente faz (mesmo que contenha mensagens de nós defeituosos), e é preciso quando S contém apenas nós bem comportados. Em nesta seção, também assumimos que as fatias dos nós não mudam. No entanto, nossos resultados são transferidos para o caso da fatia variável porque um sistema no qual as fatias mudam não é menos seguro do que um sistema de fatia fixa em que as fatias de um nó consistem em todos os fatias que ele usa no caso de fatias variáveis (ver Teorema 13 em [68]). Conforme explicado na Seção 4, a vivacidade depende de nós bem comportados eventualmente removendo nós não confiáveis de suas fatias. Como nós diferentes têm requisitos de acordo diferentes, a FBA impede uma definição global de segurança. Nós dizemos nós não defeituosos v1 e v2 estão interligados quando cada O quorum de v1 cruza todo quorum de v2 em pelo menos um nó não defeituoso. Um protocolo FBA pode garantir acordo apenas entre nós interligados; já que SCP faz isso, é culpa a tolerância à segurança é ótima. A hipótese da Internet, subjacente ao design de Stellar, afirma que as pessoas dos nós se importam sobre estarão interligados. Dizemos que um conjunto de nós I está intacto se I for um quorum uniformemente não defeituoso, tal que todos os dois membros de I estejam interligados, mesmo que todos os nós fora de I estejam defeituosos. Intuitivamente, então, eu deveria permanecer imune às ações de pessoas não intactas nós. SCP garante atividade sem bloqueio [93] e segurança para conjuntos intactos, embora os próprios nós não precisem saber (e pode não ser capaz de saber) quais conjuntos estão intactos. Além disso, a união de dois conjuntos intactos que se cruzam é um conjunto intacto. Portanto, conjuntos intactos definem uma partição do nós bem comportados, onde cada partição é segura e ativa (sob algumas condições), mas partições diferentes podem gerar decisões divergentes. 3.1.1 Considerações de segurança versus vivacidade no FBA Com exceções limitadas [64], a maioria dos protocolos de acordos bizantinos fechados estão sintonizados no ponto de equilíbrio em que segurança e vivacidade têm a mesma tolerância a falhas. Na FBA, isso significa configurações nas quais, independentemente de falhas, todos conjuntos entrelaçados também estão intactos. Dado que a FBA determina quóruns de forma descentralizada, é improvável que as escolhas individuais das fatias conduzam a este equilíbrio. Além disso, em pelo menos em Stellar, o equilíbrio não é desejável: as consequências de uma falha de segurança (ou seja, dinheiro digital gasto duas vezes) são muito piores do que aqueles de uma falha de vivacidade (ou seja, atrasos em pagamentos que, de qualquer forma, demoraram dias antes de Stellar). Pessoas portanto, deve e seleciona grandes fatias de quorum, de modo que é mais provável que seus nós permaneçam entrelaçados do que intactos. Inclinando ainda mais a balança, é mais fácil recuperar-se de falhas típicas de vivacidade em um sistema FBA do que em um sistema fechado tradicional. Em sistemas fechados, todas as mensagens devem ser interpretada em relação ao mesmo conjunto de quóruns. Portanto, adicionar e remover nós para se recuperar de falhas requer chegar a um consenso sobre um evento de reconfiguração, o que é difícil quando o consenso já não existe. Em contrapartida, com a FBA, qualquer nó pode ajustar unilateralmente suas fatias de quorum a qualquer momento. tempo. Em resposta a uma interrupção em um local sistemicamente importante organização, os administradores de nós podem ajustar suas fatias para contornar o problema, um pouco como coordenar respostas às catástrofes do BGP [63] (embora sem as restrições de roteamento em links de rede física).

Pagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá 3.1.2 O teorema da cascata SCP segue o modelo do modelo redondo básico [42]; nós progridem através de uma série de cédulas numeradas, cada tentando três tarefas: (1) identificar um valor “seguro” não contrariado por qualquer decisão em uma votação anterior (muitas vezes denominado preparar a votação), (2) concordar com o valor seguro e (3) detectar que o acordo foi bem sucedido. No entanto, a FBA está aberta a adesão atrapalha diversas técnicas comuns, tornando impossível “portar” protocolos fechados tradicionais para a FBA modelo simplesmente alterando a definição de quórum. Uma técnica empregada por muitos protocolos é a rotação através de nós líderes em modo round-robin após tempos limites. Em um sistema fechado, a seleção do líder round-robin garante que eventualmente um líder único e honesto acaba coordenando um acordo sobre um único valor. Infelizmente, round-robin não pode funcionar em um sistema FBA com associação desconhecida. Outra técnica comum que falha com o FBA é assumir que um quorum específico pode convencer todos os nós. Por exemplo, se todos reconhecerem quaisquer nós 2f + 1 como um quorum, então Assinaturas 2f + 1 são suficientes para provar o estado do protocolo para todos os nós. Da mesma forma, se um nó receber um quorum de mensagens idênticas por meio de transmissão confiável [24], o nó pode assumir que todos os nós não defeituosos também verão um quorum. Na FBA, por outro lado, um quorum não significa nada para nós fora do quorum. Finalmente, os sistemas não federados muitas vezes empregam raciocínio sobre segurança: se f + 1 nós estiverem com defeito, todos os nós de segurança garantias são perdidas. Portanto, se o nó v ouvir f + 1 nós, todos declarar algum fato F, v pode assumir que pelo menos um está contando ao verdade (e, portanto, que F é verdadeiro) sem perda de segurança. Tal o raciocínio falha na FBA porque a segurança é uma propriedade dos pares de nós, então um nó que perdeu segurança para alguns pares pode sempre perdem a segurança para mais nós ao presumir fatos ruins. A FBA pode, no entanto, raciocinar ao contrário sobre a vivacidade. Defina um conjunto de bloqueio v como um conjunto de nós que intercepta todos fatia de v. Se um conjunto de bloqueio v B for unanimemente defeituoso, B pode negar ao nó v um quorum e custar-lhe vida. Portanto, se B declara unanimemente o fato F, então v sabe que ou F é verdadeiro ou v não está intacto. No entanto, v ainda precisa ver uma visão completa quorum para saber que nós entrelaçados não contradirão F, o que leva a uma rodada final de comunicação em SCP e outros protocolos FBA [47] que não são necessários em análogos protocolos de adesão fechada. O resultado é que temos três níveis possíveis de confiança em fatos potenciais: indeterminado, seguro para assumir entre nós intactos (que iremos termos aceitos), e seguro para assumir entre interligados nós (que chamaremos de fatos confirmados). O nó v pode determinar com eficiência se um conjunto B está bloqueando, verificando se B intercepta todas as suas fatias. Curiosamente, se os nós sempre anunciam as declarações que eles aceita e um quórum completo aceita uma declaração, ele desencadeia um processo em cascata pelo qual as declarações se propagam por toda parte conjuntos intactos. Chamamos o fato chave subjacente a esta propagação o teorema da cascata, que afirma o seguinte: Se I é um conjunto intacto, Q é um quorum de qualquer membro de I, e S é qualquer superconjunto de Q, então S ⊇I ou existe um membro v ∈I tal que v < S e I ∩S é v-bloqueio. Intuitivamente, se isso não for o caso, o complemento de S conteria um quorum que cruza I, mas não Q, violando a interseção de quorum. Observe que se começarmos com S = Q e expandirmos repetidamente S para incluir todos os nós que ele bloqueia, obtemos um efeito cascata até que, eventualmente, S abrange tudo de I. 3.2 Descrição do protocolo SCP é um protocolo de consenso parcialmente síncrono [42] que consiste em uma série de tentativas para chegar a um consenso chamadas cédulas. As cédulas empregam tempos limite de duração crescente. Um protocolo de sincronização de votos garante que os nós permaneçam ligados mesma cédula por períodos crescentes de tempo até que as cédulas são efetivamente síncronos. A rescisão não é garantida até que as votações sejam síncronas, mas duas votações síncronas em que membros defeituosos de fatias de nós bem comportados não interferir são suficientes para que o SCP seja encerrado. Um protocolo de votação especifica as ações tomadas durante cada votação. Uma votação começa com uma fase de preparação, na qual os nós tentar determinar um valor a propor que não contradiga qualquer decisão anterior. Então, em uma fase de commit, os nós tentam para tomar uma decisão sobre o valor preparado. A votação emprega um subprotocolo de acordo denominado votação federada, i.n quais nós votam em declarações abstratas que pode eventualmente ser confirmado ou travar. Algumas declarações podem ser consideradas contraditórias e a segurança A garantia do voto federado é que não haja dois membros de um conjunto entrelaçado confirma afirmações contraditórias. A confirmação de uma declaração não é garantida, exceto por uma declaração intacta conjunto cujos membros votam todos da mesma maneira. No entanto, se um membro de um conjunto intacto confirma uma declaração, federado a votação garante que todos os membros do conjunto intacto eventualmente confirmem essa afirmação. Portanto, tomar medidas irreversíveis em resposta a declarações de confirmação preserva a vivacidade para nós intactos. Os nós propõem inicialmente valores obtidos a partir de uma nomeação protocolo que aumenta as chances de todos os membros de um grupo intacto conjunto que propõe o mesmo valor, e que eventualmente converge (embora sem nenhuma maneira de determinar que a convergência está completa). A nomeação combina votação federada com seleção de líderes. Como o round-robin é impossível na FBA, a nomeação usa um esquema probabilístico de seleção de líderes. O teorema da cascata desempenha um papel crucial tanto na votação sincronização e em evitar estados bloqueados dos quais a rescisão não é mais possível. 3.2.1 Votação Os nós SCP procedem através de uma série de cédulas numeradas, empregando votação federada para chegar a acordo sobre as declarações sobre as quais os valores são ou não decididos em quais votações. Se assincronia ou comportamento defeituoso impede a tomada de uma decisão na votação n, os nós expiram e tentam novamente na votação n + 1.

SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. A votação federada de recall pode não terminar. Portanto, alguns declarações sobre cédulas podem ficar presas permanentemente estado indeterminado onde os nós nunca podem determinar se eles ainda estão em andamento ou travados. Porque os nós não podem descartar a possibilidade de declarações indeterminadas mais tarde se provarem verdadeiras, eles nunca devem tentar a votação federada em novas declarações contradizendo os indeterminados. Em cada votação n, os nós usam votação federada em dois tipos de declaração: • prepare ⟨n,x⟩– afirma que nenhum valor diferente de x foi ou será decidido em qualquer votação ≤n. • commit ⟨n,x⟩– afirma que x foi decidido na votação n. É importante ressaltar que prepare ⟨n,x⟩contradicts commit ⟨n′,x ′⟩quando n ≥n′ e x , x ′. Um nó inicia a votação n tentando uma votação federada em um instrução prepare ⟨n,x⟩. Se alguma declaração de preparação anterior foi confirmado com sucesso através da votação federada, o o nó escolhe x do resultado confirmado da votação mais alta. Caso contrário, o nó define x como a saída do protocolo de nomeação descrito na próxima subseção. Se e somente se um nó confirmar com sucesso a preparação ⟨n,x⟩ na votação n, ele tenta a votação federada no commit ⟨n,x⟩. Se tiver sucesso, significa que o SCP decidiu, então o nó gera o valor da instrução de commit confirmada. Considere um conjunto entrelaçado S. Como no máximo um valor podem ser confirmados preparados pelos membros de S em uma determinada votação, dois valores diferentes não podem ser confirmados cometidos por membros de S em uma determinada votação. Além disso, se cometer ⟨n,x⟩ for confirmado, então prepare ⟨n,x⟩foi confirmado também; desde prepare ⟨n,x⟩ contradiz qualquer commit anterior por um valor diferente, pelas garantias do acordo de votação federada entendemos que nenhum valor diferente pode ser decidido em um momento anterior votação pelos membros de S. Por indução nos números das cédulas, nós portanto, certifique-se de que o SCP é seguro. Para vivacidade, considere um conjunto intacto I e um tempo suficiente votação síncrona f Se nós defeituosos aparecerem nas fatias de nós bem comportados não interferem em n, então por votação n + 1 todos os membros de I confirmaram o mesmo conjunto P de instruções de preparação. Se P = ∅ e a votação n fosse longa o suficiente, o protocolo de nomeação terá convergido para algum valor x. Caso contrário, seja x o valor do plano com a votação mais alta em P. De qualquer forma, tentarei uniformemente votando em preparar ⟨n + 1,x⟩na próxima votação. Portanto, se n + 1 também é síncrono, segue-se inevitavelmente uma decisão para x. 3.2.2 Nomeação A nomeação implica votação federada nas declarações: • nomear x – afirma que x é um candidato válido à decisão. Os nós podem votar para nomear vários valores – diferentes as declarações de nomeação não são contraditórias. Contudo, uma vez um nó confirma qualquer declaração de nomeação, ele para de votar para indicar novos valores. A votação federada ainda permite que um nó confirmar novas declarações de nomeação nas quais não votou, o que votar ou aceitar um do quórum aceitar um do quórum a é válido aceitar um de conjunto de bloqueio descomprometido votei em um aceitou um confirmou um votei ¬a Figura 1. Etapas da votação federada permite que membros de um conjunto intacto confirmem as opiniões uns dos outros valores indicados enquanto ainda retém novos votos. O resultado (evolutivo) da nomeação é uma combinação determinística de todos os valores em declarações de nomeação confirmadas. Se x representa um conjunto de transações, os nós podem assumir a união de conjuntos, o maior conjunto ou aquele com o maior hash, então desde que todos os nós façam o mesmo. Como os nós retêm novos votos depois de confirmar uma declaração de nomeação, o conjunto de declarações confirmadas podem conter apenas um número finito de valores. O facto de declarações confirmadas se espalharem de forma fiável através de conjuntos intactos significa que nós intactos eventualmente convergem para o mesmo conjunto de valores indicados e, portanto, resultado da nomeação, embora em um ponto desconhecido arbitrariamente no final do protocolo. Os nós empregam seleção de líderes federados para reduzir o número de valores diferentes em instruções nomeadas. Somente um líder que ainda não tenha votado a favor de uma declaração de nomeação pode introduzir um novo x. Outros nós esperam para ouvir líderes e apenas copiar os votos indicados (válidos) de seus líderes. Para acomodar o fracasso, o conjunto de líderes continua a crescer à medida que ocorrem tempos limite, embora na prática apenas alguns nós introduzam novos valores de x. 3.2.3 Votação federada A votação federada emprega um protocolo de três fases mostrado em Figura 1. Os nós tentam concordar com declarações abstratas primeiro votando, depois aceitando e, finalmente, confirmando as declarações. Um nó v pode votar em qualquer afirmação válida a que não contradiga seu outrovotos pendentes e declarações aceitas. Fá-lo através da transmissão de uma mensagem de voto assinada. v então aceita a se a for consistente com outras declarações aceitas e (caso 1)v for membro de um quórum no qual cada nó vota em a ou aceita a, ou (caso 2) mesmo se v não votou em a, um conjunto de bloqueio v aceita a. No caso 2, v pode já emitiram votos contradizendo a, que agora foi anulado. v pode esquecer os votos anulados e fingir que nunca os lançou porque se estiver intacto, ele sabe votos anulados não podem completar o quórum no caso 1. v transmite que aceita a e depois confirma a quando estiver em um quórum que aceita por unanimidade a. A Figura 2 mostra o efeito dos conjuntos de bloqueio v e o teorema da cascata durante votação federada. Dois nós entrelaçados não podem confirmar declarações contraditórias, pois os dois quóruns necessários teriam que compartilhar umPagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá 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)$.

Votar X

Vote Y (a) 3 4 2 1 5 7 6 Votar X Votar X Votar X Votar S Votar X Votar S Votar S (b) 3 4 2 1 5 7 6 Aceitar X Votar X Aceitar X Votar S Aceitar X Votar S Votar S (c) 3 4 2 1 5 7 6 Aceitar X Aceitar X Aceitar X Votar S Aceitar X Aceitar X Votar S (d) 3 4 2 1 5 7 6 Aceitar X Votar X Aceitar X Aceitar X Aceitar X Aceitar X Aceitar X (e) Figura 2. Efeito cascata na votação federada. Cada nó possui uma fatia de quorum indicada por setas para os membros da fatia. (a) As declarações contraditórias X e Y são introduzidas. (b) Os nós votam em declarações válidas. (c) O nó 1 aceita X após seu quorum {1, 2, 3, 4} vota por unanimidade em X. (d) Todos os nós 1, 2, 3 e 4 aceitam X; o conjunto {1} tem bloqueio 5, então o nó 5 aceita X, anulando seu voto anterior em Y. (e) O conjunto {5} é bloqueador de 6 e 7, então 6 e 7 aceitam X. nó não defeituoso que não poderia aceitar declarações contraditórias. A confirmação de uma declaração não é garantida: em caso de votação por partes, ambas as declarações poderão ser permanentemente preso à espera de quórum na fase de votação. No entanto, se um nó em um conjunto intacto I confirma uma afirmação, a cascata teorema e aceitar o caso 2 garantem que tudo I acabará confirme essa afirmação. 3.2.4 Sincronização de votação Se os nós não conseguirem confirmar uma instrução de commit para o votação atual, eles desistem após um tempo limite. O tempo limite fica mais tempo a cada votação para se ajustar a limites arbitrários no atraso da rede. No entanto, os tempos limite por si só não são suficientes para sincronizar cédulas de nós que não iniciaram ao mesmo tempo ou ficou dessincronizado por outros motivos. Para conseguir a sincronização, os nós iniciam o temporizador apenas quando fazem parte de um quorum que está todo na votação atual (ou posterior) n. Isto retarda os nós que começaram cedo e garante que não membro de um conjunto intacto fica muito à frente do grupo. Além disso, se um nó v perceber um bloqueio v definido posteriormente votação, ele pula imediatamente para a votação mais baixa, de modo que este não é mais o caso, independentemente de quaisquer temporizadores. A cascata o teorema garante então que todos os retardatários o alcancem. O resultado é que as cédulas são aproximadamente sincronizadas ao longo de um período intacto definido assim que o sistema se tornar síncrono. 3.2.5 Seleção de líder federado A seleção de líderes permite que cada nó escolha líderes de tal maneira que os nós geralmente escolhem apenas um ou um pequeno número de líderes. Para acomodar o fracasso do líder, a seleção do líder prossegue através das rodadas. Se os líderes da rodada atual parecem não estar cumprindo com suas responsabilidades, então, após um certos nós de período de tempo limite avançam para a próxima rodada para expandir o conjunto de líderes que eles seguem. Cada rodada emprega duas funções criptográficas exclusivas hash, H0 e H1, que geram números inteiros no intervalo [0,hmax). Por exemplo, Stellar usa Hi(m) = SHA256(i∥b∥r ∥m), onde b é a instância geral do SCP (número do bloco ou razão), r é o número da rodada de seleção do líder e hmax = 2256. Dentro uma rodada, definimos a prioridade do nó v como: prioridade(v) = H1(v) Um espantalho seria para cada nó escolher como líder o nodev com a prioridade mais alta (v). Essa abordagem funciona funciona bem com fatias de quorum quase idênticas, mas não funciona corretamente capturar a importância dos nós em configurações desequilibradas. Por exemplo, se a Europa e a China contribuírem cada uma com 3 nós para cada quórum, mas a China executa 1.000 nós e a Europa 4, então a China terá o nó de maior prioridade 99,6% da época. Introduzimos, portanto, uma noção de peso da fatia, onde peso(u,v) ∈[0, 1] é a fração das fatias de quorum do nó u contendo o nó v. Quando o nó u está selecionando um novo líder, ele considera apenas vizinhos, definidos da seguinte forma: vizinhos(você) = { v | H0(v) < hmax · peso(u,v) } Um nodeu então começa com um conjunto vazio de líderes, e em cada round adiciona a ele o nó v em vizinhos (u) com o maior prioridade (v). Se o conjunto de vizinhos estiver vazio em qualquer rodada, u adiciona o nóv com menor valor de H0(v)/peso(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.

Verificação formal do SCP

Para eliminar erros de projeto, verificamos formalmente a segurança do SCP e propriedades de vivacidade (ver [65]). Especificamente, verificamos que os nós entrelaçados nunca discordam e que, nas condições discutidas abaixo, cada membro de um conjunto intacto eventualmente decide. Curiosamente, a verificação revelou que o as condições sob as quais o SCP garante a vivacidade são sutis, e mais forte do que se pensava inicialmente [68]: conforme discutido abaixo, nós maliciosos que manipulam o tempo sem de outra forma desviar-se do protocolo pode precisar ser despejado manualmente de fatias de quórum.

SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. Para garantir que as propriedades provaram ser válidas em todos os Configurações e execuções FBA, consideramos um arbitrário número de nós com configurações locais arbitrárias. Isto inclui cenários com conjuntos intactos disjuntos, bem como execuções potencialmente infinitamente longas. A desvantagem é que nós enfrentar o desafiador problema de verificar um parametrizado sistema de estados infinitos. Para manter a verificação tratável, modelamos SCP em lógica de primeira ordem (FOL) usando Ivy [69] e a metodologia de [82]. O processo de verificação consiste em fornecer manualmente conjecturas indutivas que são então automaticamente verificadas por Hera. O modelo FOL do SCP abstrai alguns aspectos do Sistemas FBA que são difíceis de manusear em FOL (por exemplo, o teorema da cascata é tomado como um axioma), então verificamos o solidez da abstração usando Isabelle/HOL [75]. Após expressar o problema de verificação em FOL, verificamos a segurança fornecendo um invariante indutivo. O indutivo invariante consiste em uma dúzia de conjecturas de uma linha para cerca de 150 linhas de especificação de protocolo. Em seguida, especificamos as propriedades de vivacidade de SCP na Lógica Temporal Linear de Ivy e usamos o vivacidade para redução de segurança de [80, 81] para reduzir a vivacidade problema de verificação ao problema de encontrar um indutivo invariante. Embora a segurança do SCP seja relativamente simples de provar, o argumento da vivacidade do SCP é muito mais complexo e consiste em cerca de 150 invariantes de linha única. Provar a vivacidade exigiu uma formalização precisa do premissas sob as quais a SCP garante a rescisão. Inicialmente pensamos que um conjunto intacto eu sempre encerraria se todos os membros removeram nós defeituosos de suas fatias [68]. No entanto, isto revelou-se insuficiente: um homem bem comportado (mas não intacto) nó em um quorum de um membro de posso, sob o influência de nós defeituosos, evite a terminação completando um quórum pouco antes do final da votação, causando assim membros de I escolham valores diferentes de x na próxima votação. Devemos, portanto, assumir adicionalmente que, informalmente, cada nó em um quorum de um membro de I eventualmente torna-se oportuno ou não envia mensagens por um período suficiente. Na prática, isso significa que os membros do I podem precisam ajustar suas fatias até que a condição seja mantida. Isto a questão não é inerente aos sistemas FBA: Losa et al. [47] presente um protocolo cuja vivacidade depende do estritamente mais fraco suposições de apenas eventual sincronia e eventual eleição de líder, sem a necessidade de remover nós defeituosos das fatias.

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.

Rede de pagamento

Esta seção descreve a rede de pagamento de Stellar, implementada como uma máquina de estado replicada [88] sobre SCP. 5.1 Modelo de razão O razão de Stellar é projetado em torno de uma abstração de conta (em contraste com a saída de transações não gastas mais centrada em moedas ou modelo UTXO de Bitcoin). O conteúdo do razão consiste em um conjunto de entradas contábeis de quatro tipos distintos: contas, linhas confiáveis, ofertas e dados da conta. As contas são os principais que possuem e emitem ativos. Cada conta é nomeada por uma chave pública. Por padrão, a chave privada correspondente pode assinar transações para a conta. No entanto, as contas podem ser reconfiguradas para adicionar outros assinantes e desautorizar a chave que dá nome à conta, com um Opção “multisig” para exigir vários assinantes. Cada conta também contém: um número de sequência (incluído em transações para evitar replay), algumas bandeiras e um equilíbrio em um modo “nativo” criptomoeda pré-minerada chamada XLM, destinada a mitigar alguns ataques de negação de serviço e facilitar a criação de mercado como uma moeda neutra. Trustlines rastreiam a propriedade dos ativos emitidos, que são nomeado por um par que consiste na conta emissora e uma conta curta código do ativo (por exemplo, “USD” ou “EUR”). Cada linha confiável especifica uma conta, um ativo, o saldo da conta nesse ativo, um limite acima do qual a balança não pode subir e algumas bandeiras. Uma conta deve consentir explicitamente em manter um ativo por criando uma linha confiável, evitando que spammers sobrecarreguem contas com ativos indesejados. As regulamentações Conheça seu Cliente (KYC) exigem que muitas instituições financeiras saibam de quem são os depósitos que possuem, por exemplo, verificando um documento de identidade com foto. Para cumprir, os emitentes podem definir um sinalizador auth_reqired opcional em suas contas, restringindo a propriedade dos ativos que emitem a contas autorizadas. Para conceder tal autorização, o emissor estabelece um sinalizar nas linhas de confiança dos clientes. As ofertas correspondem à disposição de uma conta em negociar a uma certa quantia de um determinado ativo por outro em um determinado preço na carteira de pedidos; eles são automaticamente combinados e preenchido quando os preços de compra/venda se cruzam. Por fim, os dados da conta consistem em triplos de conta, chave e valor, permitindo aos titulares de contas para publicar pequenos valores de metadados. Para evitar spam contábil, há um saldo mínimo de XLM, chamada de reserva. A reserva de uma conta aumenta com cada entrada do razão associada e diminui quando a entrada do razão desaparece (por exemplo, quando um pedido é atendido ou cancelado, ou quando um a linha confiável é excluída). Atualmente a reserva cresce 0,5 XLM (∼$0,03) por entrada no razão. Independentemente da reserva, é possível recuperar o valor total de uma conta excluindo isso com uma operação AccountMerge. Um cabeçalho de razão, mostrado na Figura 3, armazena atributos globais: um número de razão, parâmetros como o saldo de reserva por entrada do razão, um hash do cabeçalho do razão anterior (na verdade vários hashes formando uma skiplist), a saída SCP incluindo um hash de novas transações aplicadas neste razão, um hash de os resultados dessas transações (por exemplo, sucesso ou fracasso para cada) e um instantâneo hash de todas as entradas do razão. Como o instantâneo hash inclui todo o conteúdo do razão, validators não precisam reter histórico para validar transações. No entanto, para escalar para centenas de milhões de contas, não podemos rehash todas as tabelas de lançamento contábil em cada fechamento do livro razão. Além disso, não é prático transferir um livro razãoPagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá razão # = 4 H (hdr anterior) Saída SCP H∗(resultados) H∗(instantâneo) ... cabeçalho razão # = 5 H (hdr anterior) Saída SCP H∗(resultados) H∗(instantâneo) ... cabeçalho . . . Figura 3. Conteúdo do razão. H é SHA-256, enquanto H ∗representa aplicação hierárquica ou recursiva de H. Saída SCP também depende do cabeçalho anterior hash. Criar conta Criar e financiar nova entrada no razão da conta Mesclagem de contas Excluir entrada do razão da conta Definir opções Alterar sinalizadores e assinantes da conta Pagamento Pague uma quantidade específica de ativo ao destino. conta. CaminhoPagamento Semelhante ao Pagamento, mas pague em ativos diferentes (até limitar); especifique até 5 ativos intermediários Gerenciar oferta Criar/excluir/alterar entrada do razão de ofertas, -Oferta passiva com variante passiva para permitir spread zero Gerenciar dados Criar/excluir/alterar conta. entrada de dados Mudança de confiança Criar/excluir/alterar linha confiável Permitir confiança Definir ou limpar sinalizador autorizado na linha confiável Sequência de Bump Aumente a sequência. número na conta Figura 4. Principais operações contábeis desse tamanho toda vez que um nó foi desconectado a rede por muito tempo. O instantâneo hash é, portanto, projetado para otimizar hashing e reconciliação de estado. Especificamente, o instantâneo estratifica as entradas do razão por tempo da última modificação em um conjunto de contêineres de tamanho exponencial chamados baldes. A coleção de baldes é chamada de balde lista e tem alguma semelhança com árvores de mesclagem estruturadas em log (Árvores LSM) [77]. A lista de baldes não é lida durante o processamento da transação (ver Seção 5.4). Portanto, certo design aspectos das árvores LSM podem ser relaxados. Em particular, aleatório o acesso por chave não é necessário e os buckets só são lidos sequencialmente como parte da fusão de níveis. Hashing do balde list é feita hash cada intervalo à medida que ele é mesclado e calculando um novo hash cumulativo do intervalo hashes (um pequeno, índice fixo de referência hashes) em cada fechamento do razão. Reconciliar a lista de baldes após a desconexão requer download apenas baldes que diferem. 5.2 Modelo de transação Uma transação consiste em uma conta de origem, critérios de validade, um memorando e uma lista de uma ou mais operações. A Figura 4 lista as operações disponíveis. Cada operação possui uma conta de origem, que o padrão é o da transação geral. Uma transação deve ser assinado por chaves correspondentes a cada conta de origem em uma operação. Contas Multisig podem exigir assinatura superior peso para algumas operações (como SetOptions) e menor para outros (como AllowTrust). As transações são atômicas – se alguma operação falhar, nenhuma delas eles executam. Isso simplifica negócios multidirecionais. Suponha que um o emissor cria um ativo para representar escrituras de terra, e o usuário A quer trocar um pequeno terreno mais US$ 10.000 por um maior parcela de terreno de propriedade de B. Os dois usuários podem assinar uma única transação contendo três operações: dois terrenos pagamentos e pagamento de um dólar. O principal critério de validade de uma transação é o seu número de sequência, que deve ser um valor maior que o número da transação. entrada no razão da conta de origem. Executando uma transação válida (com sucesso ou não) incrementa o número de sequência, evitando a repetição. Os números de sequência iniciais contêm o razão número nos bits altos para evitar a repetição mesmo após a exclusão e recriar uma conta. O outro critério de validade é um limite opcional sobre quando uma transação pode ser executada. Voltando à terra e ao dólar swap acima, se A assinar a transação antes de B, A não poderá quer que B permaneça na transação por um ano antes de enviar isso, e assim poderia colocar um limite de tempo invalidando a transação depois de alguns dias. Contas Multisig também podem ser configuradas para dar peso de assinatura à revelação de uma pré-imagem hash, que, combinado com limites de tempo, permite a negociação atômica de crosschain [1]. A conta de origem de uma transação paga uma taxa trivial em XLM, 10−5 XLM, a menos que haja congestionamento. Sob congestionamento, o o custo das operações é definido por leilão holandês. Validadores são não compensado por taxas porque validators são análogos para Bitcoin nós completos, não mineradores. Em vez de destruir o XLM, as taxas são recicladas e distribuídas proporcionalmente pelo voto dos detentores de XLM existentes, que em retrospecto podem ou podem não valeu a pena a complexidade. 5.3 Valores de consenso Para cada razão, Stellar usa SCP para chegar a um acordo sobre uma estrutura de dados com três campos: um conjunto de transações hash (incluindo um hash do cabeçalho do razão anterior), um horário de fechamento, umd atualizações. Quando vários valores são confirmados como nomeados, Stellar leva o conjunto de transações com mais operações (quebrando empates por taxas totais, então conjunto de transações hash), a união de todos atualizações e o maior tempo de fechamento. Um tempo próximo é apenas válido se for entre o horário de fechamento do último razão e o presente, então os nós não nomeiam tempos inválidos. As atualizações ajustam parâmetros globais como saldo de reserva, taxa mínima de operação e versão do protocolo. Quando combinados durante a nomeação, taxas mais altas e números de versão de protocolo substituem os mais baixos. As atualizações afetam a governança por meio de um espaço de disputa de votação federada [34], nem igualitário nem centralizado. Cada validator é configurado como governamental ou não governamental (o padrão), de acordo com se o seu operador deseja participar na governação. Os validators governantes consideram três tipos de atualização: desejado, válido e inválido (qualquer coisa que validator não

SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. validator núcleo horizonte FS BD BD enviar cliente cliente outros validators Figura 5. Arquitetura Stellar validator saiba como implementar). As atualizações desejadas são configuradas para acionado em um momento específico, destinado a ser coordenado entre operadores. Os nós governantes sempre votam para nomear os atualizações, aceite, mas não vote para nomear atualizações válidas (ou seja, concordar com um quórum de bloqueio) e nunca votar ou aceitar atualizações inválidas. Eco de validators não governamentais qualquer voto que eles vejam para uma atualização válida, essencialmente delegando a decisão sobre quais upgrades são desejados para aqueles que optam para um papel de governança. 5.4 Implementação A Figura 5 mostra a arquitetura validator de Stellar. Um demônio chamado stellar-core (∼92k linhas de C++, sem contar bibliotecas de terceiros) implementa o protocolo SCP e a máquina de estado replicada. A produção de valores para SCP requer a redução de um grande número de entradas contábeis para pequenos valores criptográficos. hashes. Por outro lado, a validação e execução de transações requer a consulta do estado da conta e da correspondência de pedidos em o melhor preço. Para servir ambas as funções de forma eficiente, stellar-core mantém duas representações do razão: uma representação externa contendo a lista de baldes, armazenada como arquivos binários que pode ser atualizado de forma eficiente e rehashed incrementalmente, e uma representação interna em um banco de dados SQL (PostgreSQL para nós de produção). Stellar-core cria um arquivo de histórico somente gravação contendo cada conjunto de transações que foi confirmado e instantâneos de baldes. O arquivo permite que novos nós sejam inicializados ao ingressar na rede. Ele também fornece um registro do razão história - é preciso haver algum lugar onde se possa procurar um transação de dois anos atrás. Como o histórico é apenas anexado e acessado com pouca frequência, pode ser mantido em lugares baratos como Amazon Glacier ou qualquer serviço que permita armazenar e recuperar arquivos simples. Os hosts validadores normalmente não hospedam seus próprios arquivos, de modo a evitar qualquer impacto na validação desempenho do histórico de veiculação. Para manter o núcleo estelar simples, ele não se destina a ser usado diretamente pelas aplicações e expõe apenas uma interface muito estreita para o envio de novas transações. Para apoiar clientes, a maioria dos validators executam um daemon chamado horizonte (∼18k linhas de Go) que fornece uma interface HTTP para enviar e aprendizagem de transações. Horizon tem acesso somente leitura a banco de dados SQL do stellar-core, minimizando o risco de horizonte núcleo estelar desestabilizador. Recursos como localização de caminhos de pagamento são implementados inteiramente no horizonte e podem ser atualizados unilateralmente sem coordenação com outros validators. Vários daemons opcionais de camada superior são clientes do horizonte, completando o ecossistema. Um servidor bridge facilita integração de Stellar com sistemas existentes, por exemplo, publicação de notificações de todos os pagamentos recebidos por uma conta específica. Um servidor de conformidade fornece ganchos para instituições financeiras trocar e aprovar informações do remetente e do beneficiário sobre pagamentos, para cumprimento das listas de sanções. Finalmente, um servidor de federação implementa uma nomenclatura legível por humanos sistema de contas. 6 Experiência de implantação Stellar cresceu durante vários anos até se tornar um estado com um moderado número de operadores de nó completo razoavelmente confiáveis. No entanto, as configurações dos nós eram tais que a vivacidade (embora não segurança) dependia de nós, a Stellar Fundação de Desenvolvimento (FDS); se o SDF desaparecesse repentinamente, outros operadores de nó precisaria intervir e nos remover manualmente das fatias de quórum para a rede continuar. Embora nós e muitos outros desejemos reduzir a importância sistémica do FDS, este objectivo recebeu prioridade crescente após pesquisadores [58] quantificaram e divulgaram a centralização da rede sem diferenciar os riscos à segurança e vivacidade. Vários operadores reagiram com ajustes activos de configuração, aumentando principalmente o tamanho dos seus fatias de quórum num esforço para diluir a importância do SDF; ironicamente, isso apenas aumentou o risco de vida. Dois problemas agravaram a situação. Primeiro, um popular ferramenta de monitoramento Stellar de terceiros [5] foi sistematicamente superestimando o tempo de atividade de validator por não verificar realmente aquele núcleo estelar estava funcionando; isso leva as pessoas a incluir nós não confiáveis em suas fatias de quorum. Em segundo lugar, um bug no núcleo estelar significa uma vez que um validator mudou para o próximo livro-razão, não ajudou adequadamente os nós restantes a completar o anteriorlivro contábil em caso de perda de mensagens. Como resultado, o rede experimentou 67 minutos de inatividade e exigiu coordenação manual por administradores validator para reiniciar. Pior ainda, ao tentar reiniciar a rede, resultaram reconfigurações apressadas simultâneas em vários nós. em uma configuração incorreta coletiva que permitiu que alguns nós divergem, exigindo um desligamento manual desses nós e reapresentação das operações aceitas durante a divergência. Felizmente, esta divergência foi detectada e corrigida rapidamente e não continha transações conflitantes, mas o risco de a rede não aproveitar a interseção de quorum - divisão enquanto continua a aceitar conflitos potencialmente conflitantes transações, simplesmente devido a configuração incorreta - foi feita muito concreto por este incidente. A revisão dessas experiências levou a duas conclusões principais e ações corretivas correspondentes.Pagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Crítico, 100% 51% 51% Alto, 67% 51% Médio, 67% 51% Baixo, 67% 51% 51% ... ... ... 51% ... 51% Figura 6. Hierarquia de qualidade do validador. Nós da mais alta qualidade exigem o limite mais alto de 100%, enquanto as qualidades mais baixas são configuradas para o limite de 67%. Nós dentro de um único organização exige uma maioria simples de 51%. 6.1 Complexidade e fragilidade da configuração Stellar expressa fatias de quorum como conjuntos de quorum aninhados que consistem em n entradas e um limite k onde qualquer conjunto de k entradas constitui uma fatia do quórum. Cada uma das n entradas é então uma chave pública validator ou, recursivamente, outro conjunto de quorum. Embora flexíveis e compactos, percebemos o quórum aninhado conjuntos simultaneamente proporcionavam aos operadores de nós muita flexibilidade e pouca orientação: era fácil escrever de forma insegura (ou configurações até mesmo absurdas). Os critérios para agrupamento nós em conjuntos, para organizar subconjuntos em uma hierarquia, e Os critérios para a escolha dos limiares eram insuficientemente claros e contribuíram para falhas operacionais. Não estava claro se deveria tratar um “nível” na hierarquia de conjunto aninhado como um nível de confiança; ou uma organização, ou ambos; muitas configurações no campo misturou esses conceitos, além de especificar perigosos ou limites sem sentido. Portanto, adicionamos um mecanismo de configuração mais simples que separa dois aspectos dos conjuntos de quorum aninhados: agrupamento nós juntos por organização e rotulando cada organização com uma classificação de confiança simples (baixa, média, alta ou crítico). As organizações de nível superior ou superior são obrigadas a publicar arquivos históricos. O novo sistema sintetiza conjuntos de quorum aninhados nos quais cada organização é representada como um Limite de 51% definido e as organizações são agrupadas em conjuntos com limites de 67% ou 100% (dependendo da qualidade do grupo). Cada grupo é uma única entrada no próximo grupo (de qualidade superior), conforme ilustrado na Figura 6. Este modelo simplificado reduz o probabilidade de configuração incorreta, tanto em termos de estrutura dos conjuntos aninhados sintetizados e os limites escolhidos para cada conjunto. 6.2 Detecção proativa de configuração incorreta Em segundo lugar, percebemos que detectar a má configuração colectiva, esperando para observar os seus efeitos negativos, é demasiado tarde. Especialmente no que diz respeito a configurações incorretas que podem divergir – uma modo de falha mais sério do que a parada – a rede precisa ser capaz de detectar erros de configuração imediatamente para que os operadores possam revertê-los antes que qualquer divergência realmente aconteça. Para atender a essa necessidade, construímos um mecanismo no software validator que reúne continuamente o estado de configuração coletiva de todos os pares no fechamento transitivo do nó e detecta o potencial de divergência - ou seja, disjunção. quóruns – dentro dessa configuração coletiva. 6.2.1 Verificando a interseção do quórum Embora coletar fatias de quórum seja fácil, encontrar quóruns disjuntos entre eles é co-NP-difícil [62]. Contudo, adotamos um conjunto de heurísticas algorítmicas e regras de eliminação de casos proposto por Lachowski [62] que verifica instâncias típicas do problema várias ordens de magnitude mais rápido do que custo do pior caso. Na prática, a actual rede os fechamentos transitivos da fatia de quorum são da ordem de 20 a 30 nós e, com as otimizações de Lachowski, normalmente verifica em questão de segundos em uma única CPU. Caso surja a necessidade para melhorar o desempenho, podemos paralelizar a pesquisa. 6.2.2 Verificando configurações arriscadas Detectar que a rede admite quóruns disjuntos é um passo na direção certa, mas sinaliza o perigo desconfortavelmente tarde para uma questão tão crítica. Idealmente, queremos que os operadores dos nós recebam avisos quando a configuração coletiva da rede está apenas se aproximando de um estado de risco. Portanto, estendemos o verificador de interseção de quorum para detectar uma condição que chamamos de criticidade: quando a corrente configuração coletiva está a uma configuração incorreta de um estado que admite quóruns disjuntos. Para detectar criticidade, o verificador substitui repetidamente a configuração de cada organização por uma configuração incorreta simulada do pior caso e, em seguida, executa novamente o verificador de interseção de quorum interno no resultado. Se alguma configuração incorreta crítica existir a um passo de distância do estado atual, o software emite um aviso e relata que a organização representa um risco de configuração incorreta. Estas mudanças dão à comunidade de operadores duas camadas aviso e orientação para isolar contra as piores formas de má configuração coletiva.

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.

Avaliação

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

Para entender a adequação de Stellar como pagamento global e rede comercial, avaliamos o estado da rede pública e realizou experimentos controlados em um laboratório experimental privado rede. Nós nos concentramos nas seguintes questões: • Qual é a aparência da topologia da rede de produção? Quantas mensagens são transmitidas em média e como o SCP experimenta tempos limite? • O consenso e as latências de atualização do razão permanecem independentes do número de contas?SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. • Como as latências são afetadas pelo aumento de (a) transações por segundo (e, consequentemente, transações por razão) e (b) o número de nós validator? • Qual é o custo de execução de um nó em termos de CPU, memória e largura de banda da rede? As redes de pagamento têm taxas de transação baixas em comparação para outros tipos de sistema distribuído. Os principais blockchains, Bitcoin e Ethereum, confirme até 15 transações/segundo, menos de Stellar. Além disso, esses sistemas levam minutos para uma hora para confirmar uma transação com segurança, porque a prova de trabalho exige a espera pela mineração de vários blocos. O A rede SWIFT não blockchain teve uma média de apenas 420 transações por segundo em seu dia de pico [14]. Escolhemos, portanto, para comparar nossas medições com a meta de 5 segundos intervalo de contabilidade, um alvo mais agressivo. Nossos resultados mostram que as latências estão confortavelmente abaixo deste limite, mesmo com várias otimizações não implementadas ainda em andamento. 7.1 Âncoras Os ativos mais negociados por volume incluem moeda (por exemplo, 3 USD âncoras, 2 CNY), uma âncora Bitcoin, um título garantido por imóveis token [92] e uma moeda no aplicativo [8]. Âncoras diferentes têm políticas diferentes. Por exemplo, uma âncora em USD, Stronghold, define auth_reqired e exige um processo conheça seu cliente (KYC) para cada conta que possui seu ativos. Outro, AnchorUSD, vamos receber e negociar seus dólares americanos (tornando literalmente possível enviar US$ 0,50 para o México em 5 segundos com uma taxa de US$ 0,000001). No entanto, AnchorUSD exige KYC e taxas para comprar ou resgatar seus dólares americanos com transferências bancárias convencionais. Nas Filipinas, onde regulamentações bancárias são mais flexíveis para pagamentos recebidos, coins.ph suporta saques de PHP em qualquer caixa eletrônico [36]. Além da segurança token mencionada acima e da moeda no aplicativo, há uma variedade de tokens não monetários que variam de títulos comerciais [22] e créditos de carbono [85, 96] para mais ativos esotéricos, como um token que incentiva a colaboração reintegração de posse do carro [35]. 7.2 Rede pública No momento em que este livro foi escrito, havia 126 nós completos ativos, 66 dos quais participar do consenso assinando mensagens de voto. Figura 7 (gerado por [5]) visualiza a rede, com uma linha entre dois nós se um aparecer nas fatias de quorum do outro e um linha azul mais escura para mostrar dependência bidirecional. No center é um cluster de 17 “validators” de fato de primeiro nível administrado por SDF, SatoshiPay, LOBSTR, COINQVEST e Keybase. Há quatro meses, antes dos acontecimentos da Secção 6, houve havia 15 nós sistemicamente importantes: 3 de aparentemente organizações de nível um e vários singletons aleatórios. O o gráfico também parecia muito menos regular. Portanto, o novo mecanismo de configuração e/ou melhores decisões do operador parecem contribuir para uma topologia de rede mais saudável. Sem grandes recursos financeiros (e correspondentes Figura 7. Mapa de fatia de quórum obrigações), teria sido difícil recrutar 5 níveis um organizações desde o início, no entanto. Isso sugere quórum fatias desempenham um papel útil na inicialização da rede: qualquer um pode junte-se com o objetivo de se tornar um player importante porque não há guardiões para o acordo entre pares. Existem atualmente mais de 3,3 milhões de contas no livro razão. Acabou um período recente de 24 horas, Stellar teve uma média de 4,5 transações e 15,7 operações por segundo. Revendo livros contábeis recentes, a maioria as transações parecem ter uma única operação, enquanto a cada poucas livros, vemos transações contendo muitas operações que parecem vir de formadores de mercado que gerenciam ofertas. O os tempos médios para alcançar consenso e atualizar o livro foram 1061ms e 46ms, respectivamente. Os percentis 99 foram 2252 ms e 142 ms (o primeiro refletindo um tempo limite de 1 segundo na seleção do líder de nomeação). Observe que o desempenho do SCP é principalmente independente de transações por segundo, uma vez que SCP concorda com um hash de muitas transações arbitrárias. É mais provável que gargalos surjam da propagação de candidatos transações durante a nomeação, execução e validação transações e mesclagem de buckets. Ainda não precisamos para paralelizar o processamento de transações do Stellar-Core em vários núcleos de CPU ou unidades de disco. Também avaliamos o número de mensagens SCP transmitidas na rede de produção. No caso normal com um único líder eleito para indicar um valor, esperamos sete mensagens a serem transmitidas: duas mensagens para votar e aceitar um nomedeclaração nate, duas mensagens para aceitar e confirmar uma declaração de preparação, duas mensagens para aceitar e confirmar uma declaração de commit e, finalmente, uma mensagem externalizada (enviado depois de enviar um novo livro-razão para o disco para ajudar os retardatários alcançar). A implementação combina confirmar commit e externalizar mensagens como uma otimização, uma vez que é seguro externalizar um valor após ele ser confirmado. Em seguida, analisamos as métricas coletadas em uma produção Stellar validator. Acabou ao longo de 68 horas, foram emitidas 1,3 mensagens/segundo, em média de 6 a 7 mensagens por livro-razão. Notamos que o total

Pagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Percentil Número de tempos limite Nomeação Votação 75% 0 0 99% 1 0 Máx. 4 1 Figura 8. Tempos limite por razão superior a 68 horas contagem de mensagens transmitidas por validators é maior, pois em além das mensagens de votação federada, os nós também transmitem quaisquer transações sobre as quais tomem conhecimento. A Figura 8 mostra os tempos limite experimentados por uma produção validator durante um período de 68 horas. Os tempos limite de nomeação são uma medida da (in)eficácia da função eleitoral do líder, enquanto o tempo limite da votação depende muito da rede e possíveis atrasos nas mensagens. Os tempos limite são consistentes com o número de mensagens emitidas: seis mensagens no melhor cenário, e pelo menos sete mensagens se uma rodada de nomeação adicional for necessária. 7.3 Experimentos controlados Realizamos experimentos controlados em recipientes embalados em Instâncias c5d.9xlarge do Amazon EC2 com 72 GiB de RAM, 900 GB de SSD NVMe e 36 vCPUs. Cada instância estava em na mesma região EC2 e tinha largura de banda fixa de 10 Gbps. Usamos SQLite como loja. (Stellar também suporta PostgreSQL, mas isso tem tarefas assíncronas que injetam ruído nas medições.) Stellar fornece uma consulta de tempo de execução integrada, generateload, que permite gerar carga sintética em um alvo específico transação/segunda taxa. Embora Stellar suporte vários recursos de negociação, como carteira de pedidos e caminho entre ativos pagamentos, nos concentramos em pagamentos simples. A confirmação de transações consiste em várias etapas, por isso registrou as medições para cada um dos seguintes: • Nomeação: tempo desde a nomeação até a primeira preparação • Votação: tempo desde a primeira preparação até a confirmação de um votação confirmada • Atualização do razão: hora de aplicar o valor de consenso • Contagem de transações: transações confirmadas por razão Cada um de nossos experimentos foi definido por três parâmetros: o número de lançamentos de conta no razão, a quantidade de carga (na forma de pagamentos XLM) enviada por segundo, e o número de validators. Configuramos cada validator saber sobre todos os outros validator (o pior cenário para SCP), com fatias de quórum definidas para qualquer maioria simples de nós (de modo a maximizar o número de quóruns diferentes). Linha de base Nosso experimento de linha de base mediu Stellar com 100.000 contas, quatro validators e a geração de carga taxa de 100 transações/segundo. Observamos em média 507 transações por razão, com desvio padrão de 49 (9,7%). Observe que nenhuma transação foi descartada; o leve 105 106 107 0 500 1.000 1.500 2.000 Contas Latência [ms] Atualização do razão Votação Nomeação Figura 9. Latência à medida que o número de contas aumenta a variação é devida a limitações de programação do gerador de carga. Observamos que o número de transações por razão foi consistente com nossa taxa de geração de carga, dado o razão fechando a cada 5 segundos. Nomeação, votação e registro atualização mostrou latências médias de 82,53 ms, 95,96 ms e 174,08ms, respectivamente. Observamos que a latência de nomeação O percentil 99 está consistentemente abaixo de 61 ms, com ocasionais picos de aproximadamente 1 segundo, correspondendo à primeira etapa na função de tempo limite de seleção do líder. Dado o desempenho da linha de base, analisamos os efeitos de variar cada um dos parâmetros de configuração do teste. Contas Os dados da Figura 9 sugerem que Stellar escala bem como o número de contas aumenta. Geração de teste contas tornou-se um processo demorado, pois a criação de buckets e a fusão nos impediu de simplesmente preencher o banco de dados com contas diretamente via SQL. Por isso, conduzimos nosso experimentos para até 50 milhões de contas. Enquanto houver impacto mínimo no consenso e nas latências de atualização do razão, notamos que o aumento de contas cria uma sobrecarga de mesclando baldes, que ficam maiores. Taxa de transação A taxa de transação afeta a quantidade de multicast de tráfego entre validators, o número de transações incluídas em cada razão e o tamanho do nível superior baldes. Para entender os efeitos do aumento das transações load, realizamos um experimento com 100.000 contas e 4 validators. A Figura 10 mostra o crescimento lento na latência de consenso, enquanto a maior parte do tempo foi gasta atualizando o razão. Não é de surpreender que, à medida que o conjunto de transações aumenta de tamanho, leva mais tempo para confirmá-lo no banco de dados. Notamos também que a latência de atualização do razão depende fortemente da implementação, e é afetado pela escolha do banco de dados. Nós validadores Para ver como aumentar o número de níveis validatorsafeta o desempenho, realizamos experimentos com 100.000 contas, 100 transações/segundo e um número variável de validators de 4 a 43. Todos os validators apareceram em todas as fatias de quorum de validators; fatias de quórum menores seriam têm um impacto menor no desempenho.SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá Lokhava et al. 100 150 200 250 300 350 0 500 1.000 1.500 2.000 Carregar [transações/segundo] Latência [ms] Atualização do razão Votação Nomeação Figura 10. Latência à medida que a carga da transação aumenta 10 20 30 40 0 500 1.000 1.500 2.000 Validadores Latência [ms] Atualização do razão Votação Nomeação Figura 11. Latência conforme o número de nós aumenta Alterando o número de nós de validação na rede afeta o número de mensagens SCP trocadas, bem como o número de valores potenciais durante a nomeação. Figura 11 mostra o tempo de nomeação crescendo a uma taxa relativamente pequena. Embora os dados sugiram que a votação é o gargalo, acredito que muitos problemas de escala podem ser resolvidos melhorando Rede de sobreposição de Stellar para otimizar o tráfego de rede. Como esperado, a latência de atualização do razão permaneceu independente de o número de nós. Taxa de fechamento Por último, queríamos medir o desempenho ponta a ponta de Stellar medindo a frequência com que os livros contábeis são confirmados e se Stellar atinge sua meta de 5 segundos sem descartando qualquer transação. Observamos o razão médio próximo tempos de 5,03 s, 5,10 s e 5,15 s à medida que aumentamos a conta entradas, taxa de transação e número de nós, respectivamente. Os resultados sugerem que Stellar pode fechar livros contábeis de forma consistente sob alta carga. 7.4 Executando um validator Uma das características importantes de Stellar é o baixo custo de executando um validator, como as âncoras devem ser executadas (ou contratadas) validators para impor finalidade. O SDF executa três validators de produção, todos em instâncias c5.large da AWS, que possuem dois núcleos, 4 GiB de RAM e CPU Intel(R) Xeon(R) Platinum 8124M @ Processadores de 3,00 GHz. Inspecionando o uso de recursos em um dessas máquinas, observamos o processo Stellar usando cerca de 7% da CPU e 300 MiB de memória. Em termos de tráfego de rede, com 28 conexões a pares e tamanho de quorum de 34, as taxas de entrada e saída eram de 2,78 Mbit/s e 2,56 Mbit/s, respectivamente. Hardware necessário para executar tal processo é barato. No nosso caso, o custo é de US$ 0,054/hora ou cerca de US$ 40/mês. 7,5 Trabalho futuro Esses experimentos sugerem que Stellar pode facilmente escalar de 1 a 2 pedidos de magnitude além do uso atual da rede. Porque o as demandas de desempenho têm sido tão modestas até o momento, Stellar deixa espaço para muitas otimizações diretas usando técnicas bem conhecidas. Por exemplo, transações e SCP mensagens são transmitidas por validators usando uma inundação ingênua protocolo, mas idealmente deveria usar protocolo mais eficiente e estruturado multicast ponto a ponto [30]. Além disso, bancos de dados pesados o tempo de atualização do razão pode ser melhorado por meio de técnicas padrão de lote e pré-busca.

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

Conclusão

Os pagamentos internacionais são caros e demoram dias. Fundo a custódia passa por múltiplas instituições financeiras, incluindo bancos correspondentes e serviços de transferência de dinheiro. Como cada salto deve ser totalmente confiável, é difícil para novos novos participantes ganhem participação de mercado e concorram. Stellar mostra como enviar dinheiro para todo o mundo de forma barata em segundos. O A principal inovação é um novo protocolo de acordo bizantino de adesão aberta, SCP, que aproveita a estrutura peer-to-peer da rede financeira para alcançar um consenso global sob um nova hipótese da Internet. SCP permite que Stellar confirme atomicamente transações irreversíveis entre participantes arbitrários que não conhecem ou confiam um no outro. Isso, por sua vez, garante aos novos participantes o acesso aos mesmos mercados estabelecidos jogadores, torna seguro obter a melhor troca disponível taxas mesmo de formadores de mercado não confiáveis, e dramaticamente reduz a latência de pagamento. Agradecimentos Stellar não estaria onde está hoje sem o início liderança de Joyce Kim ou as tremendas contribuições de Scott Fleckenstein e Bartek Nowotarski na construção e mantendo o horizonte, o Stellar SDK e outras peças importantes do ecossistema Stellar. Agradecemos também a Kolten Bergeron, Henry Corrigan-Gibbs, Candace Kelly, Kapil K. Jain, Boris Reznikov, Jeremy Rubin, Christian Leme, Eric Saunders, Torsten Stüber, Tomer Weller, os revisores anônimos e nossa pastora Justine Sherry por seus comentários úteis sobre rascunhos anteriores. Isenção de responsabilidade A contribuição do Professor Mazières para esta publicação foi como consultor remunerado e não fez parte de seu trabalho. Deveres ou responsabilidades da Universidade de Stanford.

Pagamentos globais rápidos e seguros com Stellar SOSP '19, 27 a 30 de outubro de 2019, Huntsville, ON, Canadá