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

Resumen

Los pagos internacionales son lentos y costosos, en parte debido al enrutamiento de pagos de múltiples saltos a través de canales heterogéneos. sistemas bancarios. Stellar es una nueva red de pagos global que puede transferir dinero digital directamente a cualquier parte del mundo mundo en segundos. La innovación clave es una transacción segura mecanismo a través de intermediarios no confiables, utilizando un nuevo Protocolo de acuerdo bizantino llamado SCP. Con SCP, cada institución especifica otras instituciones con las cuales permanecer de acuerdo; a través de la interconexión global de la sistema financiero, toda la red se pone de acuerdo en términos atómicos. transacciones que abarcan instituciones arbitrarias, sin solvencia ni riesgo de tipo de cambio por parte de emisores de activos intermediarios o creadores de mercado. Presentamos el modelo, protocolo y verificación formal; describir la red de pago Stellar; y finalmente evaluar Stellar empíricamente a través de puntos de referencia y nuestra experiencia con varios años de uso en producción. Conceptos de CCS • Seguridad y privacidad →Distribuida seguridad de sistemas; • Organización de sistemas informáticos → Arquitecturas de igual a igual; • Sistemas de información → Transferencia electrónica de fondos. Palabras clave blockchain, BFT, quórumes, pagos Formato de referencia ACM: Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, Jed McCaleb. 2019. Pagos globales rápidos y seguros con Stellar. En SOSP '19: Simposio sobre principios de sistemas operativos, 27 al 30 de octubre, 2019, Huntsville, ON, Canadá. ACM, Nueva York, NY, EE.UU., 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.

Introducción

Los pagos internacionales son notoriamente lentos y costosos [32]. Considere la impracticabilidad de enviar 0,50 dólares desde EE.UU. a *Galois, Inc. †UCLA Permiso para realizar copias digitales o impresas de todo o parte de este trabajo para El uso personal o en el aula se concede sin cargo, siempre que no se realicen copias. realizados o distribuidos con fines de lucro o ventaja comercial y que las copias lleven este aviso y la cita completa en la primera página. Derechos de autor de los componentes de este trabajo propiedad de terceros distintos de ACM deben ser respetados. Abstraer con Se permite el crédito. Para copiar de otra manera, o republicar, para publicar en servidores o para redistribuir a listas, requiere permiso previo específico y/o una tarifa. Solicitar permisos de [email protected]. SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá © 2019 Asociación de Maquinaria de Computación. ACM ISBN 978-1-4503-6873-5/19/10...$15,00 https://doi.org/10.1145/3341301.3359636 México, dos países vecinos. Los usuarios finales pagan casi 9 dólares para el promedio de dicha transferencia [32], y un acuerdo bilateral mediada por los bancos centrales de los países sólo podría reducir el costo bancario subyacente a $0,67 por artículo [2]. Además de las tarifas, la latencia de los pagos internacionales generalmente se cuenta en días, lo que hace imposible sacar dinero del extranjero rápidamente en emergencias. En países donde el sistema bancario no funciona o no sirve a todos los ciudadanos, o cuando las tarifas son intolerables, la gente recurre a enviar pagos en autobús [38], por barco [19], y ocasionalmente ahora por Bitcoin [55], todos los cuales incurrir en riesgos, latencia o inconvenientes. Si bien siempre habrá costos de cumplimiento, la evidencia sugiere que se pierde una cantidad significativa por falta de competencia [21], lo cual se ve exacerbado por la tecnología ineficiente. donde la gente puede innovar, los precios y las latencias bajan. Por ejemplo, las remesas desde cuentas bancarias en el segundo trimestre de 2019 costaron un promedio de 6,99%, mientras que la cifra del dinero móvil fue sólo del 4,88% [13]. Una red de pagos abierta y global que atrae la innovación y la competencia de entidades no bancarias podría reducir costos y latencias en todas las capas, incluido el cumplimiento [83]. Este documento presenta Stellar, un pago basado en blockchain red diseñada específicamente para facilitar la innovación y Competencia en pagos internacionales. Stellar es el primero sistema para cumplir los tres objetivos siguientes (bajo un “hipótesis de Internet novedosa pero empíricamente válida”): 1. Membresía abierta: cualquiera puede emitir bonos respaldados por moneda. tokens digitales que se pueden intercambiar entre usuarios. 2. Finalidad impuesta por el emisor: el emisor de un token puede evitar transacciones en el token se reviertan o deshagan. 3. Atomicidad entre emisores: los usuarios pueden intercambiar atómicamente y negociar tokens de múltiples emisores. Lograr los dos primeros es fácil. Cualquier empresa puede ofrecer unilateralmente un producto como Paypal, Venmo, WeChat. Pay, o Alipay y garantizar la firmeza de los pagos en el monedas virtuales que han creado. Desafortunadamente, realizar transacciones atómicas entre estas monedas es imposible. De hecho, a pesar de que Paypal adquirió la empresa matriz de Venmo En 2013, todavía es imposible que los usuarios finales envíen Venmo. dólares a los usuarios de Paypal [78]. Sólo recientemente los comerciantes pueden incluso aceptar ambos con una sola integración. Los objetivos 2 y 3 se pueden lograr en un sistema cerrado. En particular, varios países cuentan con sistemas de pago internos eficientes. redes, normalmente supervisadas por una autoridad reguladora de confianza universal. Sin embargo, la membresía está limitada a un recinto cerrado. conjunto de bancos autorizados y las redes se limitan a la alcance de la autoridad reguladora de un país.SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. Los objetivos 1 y 3 se han logrado en blockchain minados, más notablemente en forma de ERC20 tokens en Ethereum [3]. La idea clave de estos blockchains es crear una nueva criptomoneda con la que recompensar a las personas por establecerse transacciones difíciles de revertir. Desafortunadamente, esto significa que los emisores token no controlan la finalidad de la transacción. Si el software los errores hacen que el historial de transacciones se reorganice [26, 73], o cuando el botín de defraudar a la gente excede el costo de historial de reorganización [74, 97], los emisores pueden ser responsables de tokens ya han canjeado por dinero del mundo real. El Stellar blockchain tiene dos propiedades distintivas. En primer lugar, admite de forma nativa mercados eficientes entre tokens de diferentes emisores. Específicamente, cualquiera puede emitir un token, el blockchain proporciona un libro de pedidos integrado para el comercio entre cualquier par de token y los usuarios pueden emitir pagos de ruta que comercian atómicamente en varios pares de divisas mientras garantizando un precio límite de extremo a extremo. En segundo lugar, Stellar introduce un nuevo acuerdo bizantino. protocolo, SCP (Stellar Protocolo de Consenso), a través del cual Los emisores token designan servidores validator específicos para hacer cumplir finalidad de la transacción. Siempre y cuando nadie comprometa los validators de un emisor (y las firmas digitales subyacentes y Los hashes criptográficos permanecen seguros), el emisor sabe exactamente qué transacciones se han producido y evita el riesgo. de pérdidas por blockchain reorganización histórica. La idea clave de SCP es que la mayoría de los emisores de activos se benefician de mercados líquidos y quieren facilitar las transacciones atómicas con otros activos. Por lo tanto, los administradores validator configuran sus servidores para acordar con otros validators exactamente historial de todas las transacciones sobre todos los activos. Un validator v1 puede ser configurado para estar de acuerdo con v2, o v2 puede configurarse para estar de acuerdo con v1, o ambos pueden configurarse para que coincidan entre sí; En todos los casos, ninguno se comprometerá con un historial de transacciones hasta sabe que el otro no puede comprometerse con una historia diferente. Por transitividad, si v1 no puede estar en desacuerdo con v2 y v2 no puede estar en desacuerdo con v3 (o viceversa), v1 no puede estar en desacuerdo con v3, ya sea que v3 represente o no activos, v1 incluso ha escuchado de. Bajo la hipótesis de que estas relaciones de acuerdo conectar transitivamente toda la red, SCP garantiza acuerdo global, lo que lo convierte en un acuerdo bizantino global protocolo con membresía abierta. A este nuevo supuesto de conectividad lo llamamos hipótesis de Internet y observamos que posee tanto de “Internet” (que todo el mundo entiende como significa la red IP más grande conectada transitivamente) y pagos internacionales heredados (que son salto a salto no atómico, pero aprovecha un sistema global transitivamente conectado. red de instituciones financieras). Stellar ha estado en uso de producción desde septiembre de 2015. Para mantener manejable la longitud blockchain, el sistema ejecuta SCP a intervalos de 5 segundos: rápido según los estándares blockchain, pero mucho más lento que las aplicaciones típicas del acuerdo bizantino. Aunque el uso principal ha sido pagos, Stellar también ha probado atractivo para tokens fungibles no monetarios que se benefician de los mercados secundarios inmediatos (ver Sección 7.1). La siguiente sección analiza el trabajo relacionado. La sección 3 presenta SCP. La Sección 4 describe nuestra verificación formal de SCP. La sección 5 describe la capa de pago de Stellar. La sección 6 se relaciona parte de nuestra experiencia de implementación y lecciones aprendidas. La sección 7 evalúa el sistema. La sección 8 concluye.

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.

Trabajo relacionado

El sistema descrito en este artículo es colectivamente nuestro tercer Intentar realizar una red de pagos descentralizada. el El primer intento, por parte de uno de los autores, resultó en el Ripple. blockchain. Mientras aún exista, creemos que Ripple no puede hacer realidad la visión de una red de pagos verdaderamente abierta para razones tanto técnicas como de gobernanza. Las razones de gobernanza derivan de la tensión entre los intereses de los accionistas y usuarios de la red, pero están fuera del alcance de este documento. el El problema técnico es que el protocolo de acuerdo bizantino de Ripple [89] requiere una membresía casi cerrada [33], lo que lo hace funcionalmente similar al acuerdo bizantino convencional. El segundo intento, una bifurcación de corta duración del código Ripple. base llamada Stellard, entró en funcionamiento en julio de 2014. Habíamos planeado desarrollar SCP y colocarlo en estelar cuando esté listo, pero en su lugar decidió construir un nuevo sistema desde cero en torno a SCP, llamado núcleo estelar y descrito en este artículo. núcleo estelar fue publicado junto con una descripción y prueba de SCP [68] en abril de 2015 y entró en uso en producción 5 meses después. Un borrador de Internet [20] describió posteriormente el SCP para los implementadores. La motivación y la estructura de SCP son similares a la confianza asimétrica en el cálculo multipartito [40], aunque ese modelo Requiere que los nodos tengan una visión global de la estructura del adversario. Al introducir una noción de porciones de quórum, SCP disfruta capacidad de descubrimiento y membresía dinámica que son importantes para la implementación de Stellar. Quórum bizantino personal Los sistemas [47] y la confianza distribuida asimétrica [29] generalizan los quórums de SCP y simplifican la comparación con los tradicionales. sistemas. En un entorno más restringido, Gotsman et al. [49] también estudiar una generalización de los quórums de Stellar. Varios otros blockchains han adoptado SCP, incluido MobileCoin [7] y NCNT. Ripple también propuso más recientemente un protocolo de acuerdo bizantino de membresía abierta. llamado Cobalto [66]. La seguridad de SCP es óptima, por lo que SCP es seguro en cualquier escenario de falla donde esté Cobalt, mientras que lo contrario es poco claro. Sin embargo, Cobalt afirma que su condición de seguridad es más fácil de entender y, por lo tanto, menos propensa a una mala configuración. Lo cual será interesante evaluar si se implementa Cobalt. 2.1 Sistemas sin membresía abierta Como muchos protocolos de consenso, el SCP se basa en la votación [50, 94] en un sistema de quórum. Trabajos anteriores sobre sistemas de quórum [52, 67, 72], a veces llamados “conjuntos de supervivientes” [57], estudian sistemas de quórum que son estáticos, es decir, fijos en todo momento. ejecución del sistema, y uniforme, es decir, donde todos los nodos tienen la misma noción de lo que es un quórum. La configuración de SCP es diferente en que diferentes nodos acepten quórums diferentes y en evolución.Pagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá El consenso rápido y heterogéneo [91] permite obtener más matices nociones de confianza que se expresarán a través de etiquetas en un entramado y aprovecha esto para optimizar la comunicación, pero supone membresía cerrada. Otros esfuerzos para adaptar los protocolos de los acuerdos bizantinos a configuraciones similares a Blockchain, incluido HoneyBadger [70], SBFT [53] y HotStuff [99] se han centrado en la escalabilidad a muchos participantes y desempeño a través de redes de área amplia, conservando el modelo tradicional de membresía cerrada. Las cadenas de bloques dirigidas a membresías cerradas han aprovechado dichos protocolos, incluido el más reciente Libra [11]. 2.2 Sistemas sin finalidad impuesta por el emisor Bitcoin [71] fue el primer activo digital fungible sin autoridad confiable para realizar un seguimiento de los saldos. Se resolvió simultáneamente dos problemas: cómo distribuir un nuevo activo para que la gente crea tiene valor y cómo proporcionar transacciones irreversibles que prevenir ataques de doble gasto. Bitcoin crea activos a través de proof-of-work [43], que su autor compara con los mineros de oro que invierten recursos para aumentar la oferta de oro. el El trabajo demostrado depende del historial de transacciones, lo que frustra ataques de doble gasto porque revertir transacciones requiere un trabajo comparable al de crear el historial original. Los ataques a proof-of-work blockchain se vuelven factibles una vez que un atacante controla 1/3 del poder minero [46, 48]. La prueba de trabajo es particularmente riesgosa para blockchains nuevos o más pequeños [15, 23]; Se sabe que los mineros establecidos desvían la minería poder a cadenas más pequeñas con fines de lucro [10, 54, 74, 97, 98] o simplemente para crear problemas [25, 37] (los llamados “ataques Goldfinger” [60]). En ocasiones, los mineros han montado con benevolencia tales “ataques del 51%” para revertir los efectos no deseados de los errores [95]. Nuevo blockchains pueden obtener cierta protección contra ataques del 51% al aprovechando blockchains más establecidos con minería fusionada [6] o prueba de quema [79]. Al momento de escribir este artículo, se estima que un ataque del 51% cuesta $823,000/ hora el Bitcoin, $93,000/hour on Ethereum, and under $20,000/ hora para todos los demás blockchains [12] rastreados. En definitiva, estos Los costos dependen del valor de la criptomoneda que incentiva la minería, que es independiente del valor de la criptomoneda emitida. activos. Por el contrario, el coste de comprometer a Stellar validators está en cierta medida bajo el control de sus administradores; SCP es susceptible de implementaciones de alta seguridad, tales como utilizando módulos de seguridad de hardware para evitar que un validator firmar mensajes contradictorios. Como beneficio adicional, Stellar no tiene costos de minería que recuperar mediante la transacción tasas o señoreaje. El consumo masivo de energía de Bitcoin [76] ha motivado Variaciones de prueba de trabajo más eficientes energéticamente, como prueba de espacio [16, 17, 44, 87], prueba de almacenamiento [18, 56, 86, 90], y prueba del tiempo transcurrido [4]. La prueba de trabajo puede ser lenta y con bloques de transacciones tomando minutos para confirmar y múltiples bloques requeridos para mayor seguridad. Sin embargo, el trabajo para extraer un bloque puede ser se amortiza en un lote de transacciones de tamaño arbitrario, limitado únicamente por cuestiones políticas y de compatibilidad. BitcoinNG [45] utiliza prueba de trabajo para elegir un líder que coordine un lote más grande de transacciones. Thunderella [84] puede utilizar la prueba de trabajo como un “camino lento” alternativo y confirmar con optimismo transacciones mucho más rápidas usando un consenso asincrónico protocolo cuando un nodo acelerador y 3/4 de un comité electo son honestos. Aunque SCP es más rápido que proof-of-work, Requiere más mensajes que el camino rápido de Thunderella, pero potencialmente podría ser un camino lento útil para Thunderella. Una alternativa a la prueba de trabajo es la prueba de participación [59], en el que los mineros obtienen influencia directa o indirectamente de la propiedad de activos. En algunos casos, la influencia aumenta con el tiempo que se mantienen los activos. Algunos esquemas Fomentar la honestidad confiscando la participación de los mineros si portarse mal [27, 28, 41]. El delegado proof-of-stake [9, 61] tiene los nodos votan su participación para elegir representantes para un protocolo de acuerdo bizantino convencional como PBFT [31]. Algorand [51] utiliza funciones aleatorias verificables para elegir nodos representativos de forma pseudoaleatoria, con probabilidad proporcional a las tenencias de criptomonedas. Blancanieves [39] formaliza la propiedades de seguridad requeridas en la prueba de participación, acomodando nodos "somnolientos" que van y vienenfuera de línea. Aunque la mayoría de los esquemas proof-of-stake no pueden imponerse mediante cálculos costosos, el costo de adquirir una participación o sobornar a los mineros todavía está relacionado con el valor de la criptomoneda subyacente y está fuera del control del emisor de activos. Incluso en ausencia de mineros maliciosos, los errores también pueden causar blockchain reorganización [26, 73]. Por lo tanto, a diferencia de SCP, los emisores no tienen forma de garantizar la firmeza de blockchain antes canjear tokens en cadena por una transferencia bancaria del mundo real o retiro de efectivo.

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

El protocolo de consenso (SCP) Stellar es un protocolo basado en quórum Protocolo de acuerdo bizantino con membresía abierta. Los quórums surgen de las decisiones de configuración local combinadas de nodos individuales. Sin embargo, los nodos sólo reconocen quórums a los que pertenecen ellos mismos, y sólo después aprender las configuraciones locales de todos los demás miembros del quórum. Un beneficio de este enfoque es que SCP es inherentemente Tolera visiones heterogéneas de los nodos que existen. Por lo tanto, Los nodos pueden unirse y salir unilateralmente sin necesidad de un Protocolo de “ver cambio” para coordinar la membresía. 3.1 Acuerdo bizantino federado El problema tradicional del acuerdo bizantino consiste en una sistema cerrado de N nodos, algunos de los cuales están defectuosos y pueden comportarse arbitrariamente. Los nodos reciben valores de entrada e intercambian mensajes para decidir sobre un valor de salida entre las entradas. Un protocolo de acuerdo bizantino es seguro cuando no hay dos nodos con buen comportamiento que produzcan decisiones diferentes y el único decisión fue un insumo válido (para alguna definición de acuerdo válidoSOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. previamente). Un protocolo está activo cuando garantiza que cada nodo honesto eventualmente genera una decisión. Normalmente, los protocolos suponen N = 3f + 1 para algún número entero f > 0, entonces garantizamos seguridad y alguna forma de vida para que siempre y cuando como máximo f nodos estén defectuosos. En algún momento de estos protocolos, los nodos votan sobre los valores propuestos y una propuesta recibir 2f + 1 votos, llamado quórum de votos, se convierte en la decisión. Con N = 3f + 1 nodos, dos quórumes cualesquiera de el tamaño 2f + 1 se superpone en al menos f + 1 nodos; incluso si f de estos Los nodos superpuestos son defectuosos, los dos quórums comparten al menos un nodo no defectuoso, evitando decisiones contradictorias. Sin embargo, este enfoque sólo funciona si todos los nodos están de acuerdo lo que constituye un quórum, lo cual es imposible en SCP donde Es posible que dos nodos ni siquiera sepan de la existencia del otro. Con SCP, cada nodo v declara unilateralmente conjuntos de nodos, llamado sus sectores de quórum, de modo que (a) v cree que si todos los miembros de un segmento están de acuerdo sobre el estado del sistema, entonces tienen razón, y (b) v cree que al menos una de sus porciones estará disponible para brindar información oportuna sobre la estado del sistema. Llamamos al sistema resultante, que consiste de nodos y sus cortes, un Acuerdo Bizantino Federado (Logística de Amazon). Como veremos a continuación, surge un sistema de quórum de los cortes de los nodos. De manera informal, las porciones de un nodo Logística de Amazon expresan con quién El nodo requiere acuerdo. Por ejemplo, un nodo puede requerir un acuerdo con 4 organizaciones específicas, cada una de las cuales ejecuta 3 nodos; a acomodar el tiempo de inactividad, puede configurar sus sectores para que sean todos los conjuntos compuesto por 2 nodos de cada organización. Si esto “requiere La relación “acuerdo con” relaciona transitivamente dos nodos cualesquiera, conseguimos un acuerdo global. De lo contrario, podemos obtener divergencia, pero sólo entre organizaciones ninguna de las cuales requiere acuerdo con el otro. Dada la topología actual sistema financiero, planteamos la hipótesis de que la convergencia generalizada seguirá produciendo una historia de contabilidad única que la gente llama “la red Stellar”, del mismo modo que hablamos de Internet. Los quórums surgen de las porciones de la siguiente manera. Cada nodo especifica su quórum se divide en cada mensaje que envía. Sea S el conjunto de nodos desde los cuales se originó un conjunto de mensajes. un El nodo considera que el conjunto de mensajes ha alcanzado el quórum. umbral cuando cada miembro de S tiene un segmento incluido en S. Por construcción, tal conjunto S, si es unánime, satisface la requisitos de acuerdo de cada uno de sus miembros. Un par defectuoso puede anunciar porciones diseñadas para cambiar lo que Los nodos con buen comportamiento consideran quórumes. Por el bien del análisis del protocolo, definimos un quórum en Logística de Amazon como no vacío. conjunto S de nodos que abarcan al menos una porción de quórum de cada miembro no defectuoso. Esta abstracción es sólida, como cualquier conjunto. de mensajes que pretenden representar un quórum unánime realmente lo hace (incluso si contiene mensajes de nodos defectuosos), y es preciso cuando S contiene sólo nodos que se comportan bien. en En esta sección, también asumimos que los sectores de los nodos no cambian. Sin embargo, nuestros resultados se transfieren al caso del segmento cambiante. porque un sistema en el que cambian las porciones no es menos seguro que un sistema de corte fijo en el que los cortes de un nodo constan de todos los sectores que alguna vez utiliza en el caso de sectores cambiantes (ver Teorema 13 en [68]). Como se explica en la Sección 4, la vivacidad depende de Los nodos con buen comportamiento eventualmente eliminan los nodos no confiables. de sus rebanadas. Debido a que diferentes nodos tienen diferentes requisitos de acuerdo, Logística de Amazon excluye una definición global de seguridad. decimos Los nodos no defectuosos v1 y v2 se entrelazan cuando cada El quórum de v1 interseca cada quórum de v2 en al menos un nodo no defectuoso. Un protocolo de Logística de Amazon puede garantizar un acuerdo sólo entre nodos entrelazados; ya que SCP lo hace, es culpa suya La tolerancia a la seguridad es óptima. La hipótesis de Internet, subyacente al diseño de Stellar, afirma que los nodos que a la gente le importan sobre estarán entrelazados. Decimos que un conjunto de nodos I está intacto si I es un quórum uniformemente no defectuoso tal que cada dos miembros de I están entrelazados incluso si todos los nodos fuera de I son defectuosos. Intuitivamente, Entonces, debería permanecer inmune a las acciones de los no intactos. nodos. SCP garantiza tanto la vida sin bloqueo [93] como seguridad para conjuntos intactos, aunque los nodos en sí no necesitan saber (y tal vez no poder saber) qué conjuntos están intactos. Además, la unión de dos conjuntos intactos que se cruzan es un conjunto intacto. Por lo tanto, los conjuntos intactos definen una partición del Nodos de buen comportamiento, donde cada partición es segura y activa. (bajo algunas condiciones), pero pueden generarse diferentes particiones decisiones divergentes. 3.1.1 Consideraciones de seguridad versus vida en Logística de Amazon Con excepciones limitadas [64], la mayoría de los protocolos de acuerdos bizantinos cerrados están ajustados al punto de equilibrio en el que la seguridad y la vivacidad tienen la misma tolerancia a fallos. En Logística de Amazon, eso significa configuraciones en las que, independientemente de las fallas, todos Los conjuntos entrelazados también están intactos. Dado que Logística de Amazon determina quórums de forma descentralizada, es poco probable que las elecciones de sectores individuales conduzcan a este equilibrio. Además, en al menos en Stellar, el equilibrio no es deseable: las consecuencias de una falla de seguridad (es decir, dinero digital doblemente gastado) son mucho peores que los de una falla en la vida (es decir, retrasos en pagos que de todos modos tomaban días antes del Stellar). gente por lo tanto, debe seleccionar y selecciona porciones de quórum grandes tales que es más probable que sus nodos permanezcan entrelazados que intactos. Inclinando aún más la balanza, es más fácil recuperarse de fallas de vida típicas en un sistema Logística de Amazon que en uno cerrado tradicional. En sistemas cerrados, todos los mensajes deben ser interpretado con respecto al mismo conjunto de quórumes. Por lo tanto, Agregar y eliminar nodos para recuperarse de una falla requiere llegar a un consenso sobre un evento de reconfiguración, lo cual es difícil una vez que el consenso ya no existe. Por el contrario, con Logística de Amazon, cualquier nodo puede ajustar unilateralmente sus porciones de quórum en cualquier tiempo. En respuesta a una interrupción en un sistema de importancia sistémica organización, los administradores de nodos pueden ajustar sus sectores para solucionar el problema, un poco como coordinar respuestas a catástrofes de BGP [63] (aunque sin las limitaciones de enrutamiento a través de enlaces de red física).

Pagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá 3.1.2 El teorema de la cascada SCP sigue la plantilla del modelo redondo básico [42]; Los nodos avanzan a través de una serie de papeletas numeradas, cada una intentar tres tareas: (1) identificar un valor “seguro” que no esté en contradicción con ninguna decisión en una votación anterior (a menudo denominada preparar la papeleta), (2) acordar el valor seguro, y (3) detectar que el acuerdo fue exitoso. Sin embargo, Logística de Amazon está abierta La membresía obstaculiza varias técnicas comunes, lo que hace que sea imposible "portar" los protocolos cerrados tradicionales a la Logística de Amazon modelo simplemente cambiando la definición de quórum. Una técnica empleada por muchos protocolos es la rotación a través de los nodos líderes en forma de turnos después de los tiempos de espera. En un sistema cerrado, la selección del líder por turnos garantiza que eventualmente un líder único y honesto termine coordinando un acuerdo sobre un único valor. Desafortunadamente, todos contra todos no puede funcionar en un sistema Logística de Amazon con membresía desconocida. Otra técnica común que falla con Logística de Amazon es asumir que un quórum particular puede convencer a todos los nodos. Por ejemplo, Si todos reconocen cualquier nodo 2f + 1 como quórum, entonces 2f + 1 firmas son suficientes para demostrar el estado del protocolo en todos los nodos. De manera similar, si un nodo recibe un quórum de mensajes idénticos A través de la transmisión confiable [24], el nodo puede asumir que todos los nodos que no son defectuosos también verán un quórum. En cambio, en Logística de Amazon, una El quórum no significa nada para los nodos fuera del quórum. Por último, los sistemas no federados suelen emplear sistemas "al revés". razonamiento sobre seguridad: si los nodos f + 1 están defectuosos, toda la seguridad Se pierden las garantías. Por lo tanto, si el nodo v escucha f + 1 nodos, todos declarar algún hecho F, v puede suponer que al menos uno le está diciendo al verdad (y por tanto que F es verdadera) sin pérdida de seguridad. tal El razonamiento falla en Logística de Amazon porque la seguridad es una propiedad de pares. de nodos, por lo que un nodo que ha perdido seguridad para algunos pares puede Siempre se pierde seguridad frente a más nodos al asumir hechos incorrectos. Sin embargo, Logística de Amazon puede razonar al revés sobre la vitalidad. Defina un conjunto de bloqueo v como un conjunto de nodos que intersecta cada porción de v. Si un conjunto de bloqueo de v B es unánimemente defectuoso, B puede negarle al nodo v un quórum y costarle vida. Por lo tanto, si B declara unánimemente el hecho F, entonces v sabe que F es true o v no está intacto. Sin embargo, todavía necesita ver una versión completa. quórum para saber que los nodos entrelazados no contradicen a F, lo que conduce a una ronda final de comunicación en SCP y otros protocolos de Logística de Amazon [47] que no se requieren en casos análogos protocolos de membresía cerrada. El resultado es que tenemos tres posibles niveles de confianza en hechos potenciales: indeterminado, seguro de asumir entre nodos intactos (que veremos término hechos aceptados), y es seguro asumir entre entrelazados nodos (que llamaremos hechos confirmados). El nodo v puede determinar de manera eficiente si un conjunto B está bloqueando v verificando si B cruza todos sus sectores. Curiosamente, si los nodos siempre anuncian las declaraciones que aceptar y un quórum completo acepta una declaración, se desencadena un proceso en cascada mediante el cual las declaraciones se propagan a lo largo conjuntos intactos. Al hecho clave que subyace a esta propagación lo llamamos el teorema de la cascada, que establece lo siguiente: Si I es un conjunto intacto, Q es un quórum de cualquier miembro de I, y S es cualquier superconjunto de Q, entonces S ⊇I o hay un miembro v ∈I tal que v < S y I ∩S es v-bloqueo. Intuitivamente, ¿fue esto no es el caso, el complemento de S contendría un quórum que cruza I pero no Q, violando la intersección de quórum. Tenga en cuenta que si comenzamos con S = Q y expandimos repetidamente S hasta incluir todos los nodos que bloquea, obtenemos un efecto en cascada hasta que, eventualmente, S abarca todo I. 3.2 Descripción del protocolo SCP es un protocolo de consenso parcialmente sincrónico [42] que consta de una serie de intentos para llegar a un consenso llamado papeletas. Las papeletas emplean tiempos de espera de duración cada vez mayor. un El protocolo de sincronización de boletas garantiza que los nodos permanezcan encendidos. la misma papeleta por períodos de tiempo crecientes hasta que las papeletas son efectivamente sincrónicos. La rescisión no está garantizada hasta que las votaciones sean sincrónicas, pero dos votaciones sincrónicas en el que los miembros defectuosos de los sectores de nodos con buen comportamiento no no interferir son suficientes para que SCP termine. Un protocolo de votación especifica las acciones tomadas durante cada boleta. Una votación comienza con una fase de preparación, en la que los nodos tratar de determinar un valor a proponer que no contradiga cualquier decisión previa. Luego, en una fase de confirmación, los nodos intentan para tomar una decisión sobre el valor preparado. La votación emplea un subprotocolo de acuerdo llamado votación federada, in qué nodos votan sobre declaraciones abstractas eso eventualmente puede confirmarse o quedarse estancado. Algunas declaraciones pueden considerarse contradictorias y la seguridad La garantía del voto federado es que no pueden haber dos miembros de un conjunto entrelazado confirma afirmaciones contradictorias. La confirmación de una declaración no está garantizada excepto si está intacta. conjunto cuyos miembros votan todos de la misma manera. Sin embargo, si un miembro de un conjunto intacto confirma una declaración, federada la votación garantiza que todos los miembros del conjunto intacto eventualmente confirmen esa afirmación. Por lo tanto, tomar medidas irreversibles en respuesta a declaraciones confirmatorias preserva la vivacidad de nodos intactos. Los nodos inicialmente proponen valores obtenidos de una nominación. protocolo que aumenta las posibilidades de todos los miembros de una comunidad intacta. conjunto que propone el mismo valor, y que eventualmente converge (aunque no hay forma de determinar que la convergencia sea completa). La nominación combina la votación federada con la selección de líderes. Debido a que el sistema de todos contra todos es imposible en Logística de Amazon, la nominación utiliza un esquema probabilístico de selección de líderes. El teorema de la cascada juega un papel crucial tanto en la votación sincronización y en evitar estados bloqueados desde los cuales la terminación ya no es posible. 3.2.1 votación Los nodos SCP proceden a través de una serie de votaciones numeradas, empleando votación federada para acordar declaraciones sobre qué Los valores se deciden o no en qué papeletas. Si hay asincronía o un comportamiento incorrecto impide llegar a una decisión en la votación n, Los nodos se agotan y vuelven a intentarlo en la boleta n + 1.

SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. Recordemos que el voto federado podría no terminar. Por lo tanto, algunos Las declaraciones sobre las papeletas pueden quedar atascadas permanentemente. Estado indeterminado donde los nodos nunca pueden determinar si todavía están en progreso o atascados. Porque los nodos no pueden descartar la posibilidad de que declaraciones indeterminadas luego resulten verdaderas, nunca deben intentar una votación federada sobre nuevas declaraciones contradictorios con los indeterminados. En cada votación n, los nodos utilizan votación federada en dos tipos de declaración: • preparar ⟨n,x⟩– indica que ningún valor distinto de x se decidió o se decidirá alguna vez en cualquier votación ≤n. • comprometer ⟨n,x⟩– indica que x se decide en la votación n. Es importante destacar que preparar ⟨n,x⟩contradice el compromiso ⟨n′,x ′⟩cuando n ≥n′ y x , x ′. Un nodo inicia la votación n intentando la votación federada en un declaración preparar ⟨n,x⟩. Si alguna declaración previa preparar fue confirmado con éxito mediante votación federada, el El nodo elige x del grupo confirmado de la boleta superior. De lo contrario, el nodo establece x como la salida del protocolo de nominación descrito en la siguiente subsección. Si y sólo si un nodo confirma con éxito preparar ⟨n,x⟩ en la votación n, intenta la votación federada sobre el compromiso ⟨n,x⟩. si que tiene éxito, significa que SCP ha decidido, por lo que el nodo genera el valor de la declaración de confirmación confirmada. Considere un conjunto S entrelazado. Dado que como máximo un valor pueden ser confirmados preparados por miembros de S en una votación determinada, no se pueden confirmar dos valores diferentes comprometidos por miembros de S en una votación determinada. Además, si se compromete ⟨n,x⟩ se confirma, luego prepare ⟨n,x⟩se confirmó también; desde preparar ⟨n,x⟩ contradice cualquier compromiso anterior por un valor diferente, por el acuerdo que garantiza el voto federado conseguimos que no se puede decidir ningún valor diferente en una fecha anterior votación de los miembros de S. Por inducción sobre los números de la boleta, Por lo tanto, consiga que SCP sea seguro. Para darle vida, considere un conjunto I intacto y un tiempo suficientemente largo. votación sincrónica Si aparecen nodos defectuosos en los cortes de nodos con buen comportamiento no interfieren en n, luego por votación n + 1 todos los miembros de I han confirmado el mismo conjunto P de declaraciones de preparación. Si P = ∅ y la votación n fue lo suficientemente larga, la El protocolo de nominación habrá convergido en algún valor x. De lo contrario, sea x el valor del equipo con la votación más alta en P. De cualquier manera, intentaré uniformemente votar sobre preparar ⟨n + 1,x⟩ en la próxima votación. Por lo tanto, si n + 1 también es sincrónico, por lo que inevitablemente se sigue una decisión para x. 3.2.2 Nominación La nominación implica votación federada de las declaraciones: • nominar x – indica que x es un candidato de decisión válido. Los nodos pueden votar para nominar múltiples valores, diferentes Las declaraciones nominadas no son contradictorias. Sin embargo, una vez un nodo confirma cualquier declaración nominada, deja de votar para proponer nuevos valores. La votación federada todavía permite que un nodo confirmar nuevas declaraciones nominadas por las que no votó, que votar o aceptar un del quórum aceptar un del quórum una es válida aceptar un de conjunto de bloqueo no comprometido votó un aceptó un confirmó un votó ¬a Figura 1. Etapas del voto federado permite a los miembros de un conjunto intacto confirmar entre sí los valores nominados y al mismo tiempo retener nuevos votos. El resultado (evolutivo) de la nominación es una combinación determinista de todos los valores en las declaraciones de nominación confirmadas. si x representa un conjunto de transacciones, los nodos pueden tomar la unión de conjuntos, el conjunto más grande o el que tiene el hash más alto, por lo que siempre y cuando todos los nodos hagan lo mismo. Porque los nodos retienen nuevos votos después de confirmar una declaración nominada, el conjunto de Las declaraciones confirmadas sólo pueden contener un número finito de valores. El hecho de que las declaraciones confirmadas se difundieran de forma fiable conjuntos intactos significa que los nodos intactos eventualmente convergen en el mismo conjunto de valores nominados y, por tanto, resultado de la nominación, aunque en un punto desconocido arbitrariamente tarde en el protocolo. Los nodos emplean la selección de líderes federados para reducir la número de valores diferentes en declaraciones nominadas. Sólo un líder que aún no haya votado a favor de una declaración propuesta puede introducir una nueva x. Otros nodos esperan recibir noticias líderes y simplemente copiar los votos de nominación (válidos) de sus líderes. Para adaptarse al fracaso, el conjunto de líderes sigue creciendo a medida que avanza. Se producen tiempos de espera, aunque en la práctica sólo unos pocos nodos introducen nuevos valores de x. 3.2.3 Voto federado La votación federada emplea un protocolo de tres fases que se muestra en Figura 1. Los nodos intentan ponerse de acuerdo sobre declaraciones abstractas primero votar, luego aceptar y finalmente confirmar las declaraciones. Un nodo v puede votar por cualquier declaración válida a que no contradice su otrovotos pendientes y declaraciones aceptadas. Lo hace mediante la difusión de un mensaje de voto firmado. v luego acepta a si a es consistente con otras declaraciones aceptadas y (caso 1)v es miembro de un quórum en el que cada nodo vota por a o acepta a, o (caso 2) incluso si v no votó por a, un conjunto de bloqueo v acepta a. En el caso 2, v mayo han emitido previamente votos que contradicen a, que ahora han sido anulado. A v se le permite olvidarse de los votos anulados. y pretender que nunca los lanzó porque siv está intacto, lo sabe los votos anulados no pueden completar el quórum mediante el caso 1. v transmite que acepta a y luego confirma a cuando está en un quórum que acepte por unanimidad a. La figura 2 muestra la efecto de los conjuntos de bloqueo v y el teorema de la cascada durante votación federada. Dos nodos entrelazados no pueden confirmar declaraciones contradictorias, ya que los dos quórums requeridos tendrían que compartir unPagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre 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)$.

Vota X

Vota Y (un) 3 4 2 1 5 7 6 votar x votar x votar x votar Y votar x votar Y votar Y (b) 3 4 2 1 5 7 6 Aceptar x votar x Aceptar x votar Y Aceptar x votar Y votar Y (c) 3 4 2 1 5 7 6 Aceptar x Aceptar x Aceptar x votar Y Aceptar x Aceptar x votar Y (d) 3 4 2 1 5 7 6 Aceptar x votar x Aceptar x Aceptar x Aceptar x Aceptar x Aceptar x (e) Figura 2. Efecto cascada en el voto federado. Cada nodo tiene un segmento de quórum indicado por flechas para los miembros del segmento. (a) Se introducen declaraciones contradictorias X e Y. (b) Los nodos votan por declaraciones válidas. (c) El nodo 1 acepta X después de su quórum {1, 2, 3, 4} vota unánimemente por X. (d) Los nodos 1, 2, 3 y 4 aceptan X; el conjunto {1} es de bloqueo 5, por lo que el nodo 5 acepta X, anulando su voto anterior por Y. (e) El conjunto {5} bloquea 6 y 7, por lo que 6 y 7 aceptan X. nodo no defectuoso que no podía aceptar declaraciones contradictorias. No se garantiza la confirmación de una declaración: en En caso de votación dividida, ambas declaraciones podrán ser permanentemente estancado esperando por un quórum en la fase de votación. Sin embargo, si un nodo en un conjunto intacto I confirma una declaración, la cascada teorema y acepte el caso 2, asegúrese de que todos los I eventualmente confirmar esa afirmación. 3.2.4 Sincronización de boletas Si los nodos no pueden confirmar una declaración de confirmación para el votación actual, se dan por vencidos después de un tiempo muerto. El tiempo de espera llega más tiempo con cada votación para ajustarse a límites arbitrarios en el retraso de la red. Sin embargo, los tiempos de espera por sí solos no son suficientes para sincronizar las votaciones de los nodos que no comenzaron al mismo tiempo o se desincronizó por otras razones. Para lograr la sincronización, los nodos inician el temporizador sólo una vez que son parte de un quórum que se obtiene en la votación actual (o en una posterior) n. esto ralentiza los nodos que se iniciaron temprano y garantiza que no miembro de un conjunto intacto se mantiene demasiado por delante del grupo. Además, si un nodo v alguna vez nota un bloqueo v establecido en un momento posterior votación, salta inmediatamente a la votación más baja, de modo que esta ya no es el caso, independientemente de los temporizadores. la cascada El teorema entonces asegura que todos los rezagados se pongan al día. El resultado es que las papeletas están aproximadamente sincronizadas en todo un país intacto. se establece una vez que el sistema se vuelve sincrónico. 3.2.5 Selección de líder federado La selección de líderes permite a cada nodo elegir líderes de tal manera forma en que los nodos generalmente solo eligen uno o un pequeño número de líderes. Para adaptarse al fracaso del líder, selección del líder procede a través de rondas. Si los líderes de la ronda actual parecen no estar cumpliendo con sus responsabilidades, luego de un ciertos nodos del período de tiempo de espera pasan a la siguiente ronda para ampliar el conjunto de líderes que siguen. Cada ronda emplea dos funciones criptográficas hash únicas, H0 y H1, que generan números enteros en el rango [0,hmax). Por ejemplo, Stellar usa Hi(m) = SHA256(i∥b∥r ∥m), donde b es la instancia SCP general (bloque o número de libro mayor), r es el número de ronda de selección de líder, y hmax = 2256. Dentro una ronda, definimos la prioridad del nodo v como: prioridad(v) = H1(v) Un muñeco de paja sería para que cada nodo eligiera como líder. el nodev con la mayor prioridad (v). Este enfoque funciona bien con porciones de quórum casi idénticas, pero no funciona correctamente Captar la importancia de los nodos en configuraciones desequilibradas. Por ejemplo, si Europa y China aportan cada una 3 nodos para cada quórum, pero China tiene 1000 nodos y Europa 4, entonces China tendrá el nodo de mayor prioridad (99,6%). de la época. Por lo tanto, introducimos una noción de peso de corte, donde peso(u,v) ∈[0, 1] es la fracción de los sectores de quórum del nodo u que contiene el nodo v. Cuando el nodo u selecciona un nuevo líder, sólo considera vecinos, definidos de la siguiente manera: vecinos(u) = { v | H0(v) < hmáx · peso(u,v) } Luego, un nodo comienza con un conjunto vacío de líderes, y en cada round le agrega el nodo v en vecinos(u) con el mayor prioridad (v). Si el conjunto de vecinos está vacío en cualquier ronda, u agrega el nodov con el valor más bajo 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.

Verificación formal de SCP

Para eliminar errores de diseño, verificamos formalmente la seguridad de SCP. y propiedades de vida (ver [65]). En concreto, verificamos que los nodos entrelazados nunca están en desacuerdo y que, bajo las condiciones que se analizan más adelante, cada miembro de un conjunto intacto finalmente decide. Curiosamente, la verificación reveló que el Las condiciones bajo las cuales el SCP garantiza la vida son sutiles, y más fuerte de lo que se pensaba inicialmente [68]: como se analiza a continuación, nodos maliciosos que manipulan el tiempo sin otra cosa Es posible que sea necesario desalojar manualmente a aquellos que se desvían del protocolo. de porciones de quórum.

SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. Para garantizar que las propiedades demostradas se mantengan en todos los aspectos posibles. Configuraciones y ejecuciones de Logística de Amazon, consideramos una opción arbitraria. número de nodos con configuraciones locales arbitrarias. esto incluye escenarios con conjuntos intactos desunidos, así como ejecuciones potencialmente infinitamente largas. El inconveniente es que nosotros enfrentar el desafiante problema de verificar un parámetro parametrizado sistema de estados infinitos. Para mantener la verificación manejable, modelamos SCP en lógica de primer orden (FOL) usando Ivy [69] y la metodología de [82]. El proceso de verificación consiste en proporcionar manualmente conjeturas inductivas que luego son verificadas automáticamente por Hiedra. El modelo FOL de SCP resume algunos aspectos de Sistemas FBA que son difíciles de manejar en FOL (por ejemplo, el teorema de la cascada se toma como axioma), por lo que verificamos la solidez de la abstracción usando Isabelle/HOL [75]. Después de expresar el problema de verificación en FOL, verificamos la seguridad proporcionando un invariante inductivo. el inductivo invariante consta de una docena de conjeturas de una sola línea durante aproximadamente 150 líneas de especificación de protocolo. Luego especificamos las propiedades de vida de SCP en la Lógica Temporal Lineal de Ivy y usamos el vida a la reducción de seguridad de [80, 81] para reducir la vida problema de verificación al problema de encontrar un inductivo invariante. Si bien la seguridad de SCP es relativamente sencilla de demostrar, el argumento de la vida de SCP es mucho más complejo y consta de alrededor de 150 invariantes de una sola línea. Demostrar vivacidad requería una formalización precisa de la supuestos bajo los cuales SCP garantiza la terminación. Inicialmente pensamos que un conjunto intacto siempre lo terminaría si todos Los miembros eliminaron nodos defectuosos de sus sectores [68]. Sin embargo, esto resultó ser insuficiente: un hombre bien educado (pero no intacto) nodo en un quórum de un miembro de Puedo, bajo el influencia de nodos defectuosos, evite la terminación completando un quórum justo antes del final de la votación, provocando así Los miembros de I elegirán diferentes valores de x en la próxima votación. Por lo tanto, debemos suponer además que, informalmente, cada nodo en un quórum de un miembro de I eventualmente se vuelve oportuno o no envía ningún mensaje durante un período de tiempo suficiente. En la práctica, esto significa que los miembros de I may necesitan ajustar sus rebanadas hasta que la condición se mantenga. esto El problema no es inherente a los sistemas Logística de Amazon: Losa et al. [47] presente un protocolo cuya vida depende de los estrictamente más débiles suposiciones de una eventual sincronía y una eventual elección de líder, sin la necesidad de eliminar los nodos defectuosos de los cortes.

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.

Red de pago

Esta sección describe la red de pago de Stellar, implementada como una máquina de estado replicada [88] encima de SCP. 5.1 modelo de libro mayor El libro mayor de Stellar está diseñado en torno a una abstracción de cuenta (en contraste con la producción de transacciones no gastadas más centradas en monedas o UTXO modelo de Bitcoin). El contenido del libro mayor consta de un conjunto de asientos contables de cuatro tipos distintos: cuentas, líneas de confianza, ofertas y datos de la cuenta. Las cuentas son los principales que poseen y emiten activos. cada uno La cuenta recibe el nombre de una clave pública. De forma predeterminada, la clave privada correspondiente puede firmar transacciones para la cuenta. Sin embargo, las cuentas se pueden reconfigurar para agregar otros firmantes y desautorizar la clave que nombra la cuenta, con un Opción “multisig” para requerir múltiples firmantes. cada cuenta también contiene: un número de secuencia (incluido en las transacciones para evitar la repetición), algunas banderas y un equilibrio en un “nativo” criptomoneda preminada llamada XLM, destinada a mitigar algunos ataques de denegación de servicio y facilitar la creación de mercado como moneda neutral. Las líneas fiduciarias rastrean la propiedad de los activos emitidos, que son nombrado por un par que consta de la cuenta emisora y una cuenta corta código de activo (por ejemplo, “USD” o “EUR”). Cada línea de confianza especifica una cuenta, un activo, el saldo de la cuenta en ese activo, un límite por encima del cual el saldo no puede aumentar, y algunas banderas. Una cuenta debe dar su consentimiento explícito a mantener un activo mediante creando una línea de confianza, evitando que los spammers ensillaran cuentas con activos no deseados. Las regulaciones de Know-your-customer (KYC) requieren que muchas instituciones financieras sepan de quién son los depósitos que tienen, por ejemplo, comprobando una identificación con fotografía. Para cumplir, los emisores pueden establecer una marca auth_reqired opcional en sus cuentas, restringiendo la propiedad de los activos que emiten a cuentas autorizadas. Para otorgar dicha autorización, el emisor fija un límite autorizado marcar las líneas de confianza de los clientes. Las ofertas corresponden a la voluntad de una cuenta de negociar a una cierta cantidad de un activo particular por otro en un momento dado precio en el libro de pedidos; se emparejan automáticamente y se llena cuando los precios de compra/venta se cruzan. Finalmente, los datos de la cuenta constan de triples de cuenta, clave y valor, lo que permite a los titulares de cuentas para publicar pequeños valores de metadatos. Para evitar el spam en el libro mayor, existe un saldo XLM mínimo, llamada reserva. La reserva de una cuenta aumenta con cada asiento contable asociado y disminuye cuando el asiento contable desaparece (por ejemplo, cuando se completa o cancela una orden, o cuando una se elimina la línea de confianza). Actualmente la reserva crece 0,5 XLM (~$0,03) por asiento del libro mayor. Independientemente de la reserva, es Es posible recuperar el valor total de una cuenta eliminando con una operación AccountMerge. Un encabezado de libro mayor, que se muestra en la Figura 3, almacena atributos globales: un número de libro mayor, parámetros como el saldo de reserva por asiento contable, un hash del encabezado del libro mayor anterior (en realidad varios hashes que forman una lista de omisión), la salida de SCP incluye un hash de nuevas transacciones aplicadas en este libro mayor, un hash de los resultados de esas transacciones (por ejemplo, éxito o fracaso para cada uno) y una instantánea hash de todos los asientos del libro mayor. Debido a que la instantánea hash incluye todo el contenido del libro mayor, validators no necesitan conservar el historial para validar las transacciones. Sin embargo, para escalar a cientos de millones de anticipados cuentas, no podemos rehash todas las tablas de asientos contables en cada cierre del libro mayor. Además, no es práctico transferir un libro mayorPagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá libro mayor # = 4 H(hdr anterior) salida SCP H∗(resultados) H∗(instantánea) ... encabezado libro mayor # = 5 H(hdr anterior) salida SCP H∗(resultados) H∗(instantánea) ... encabezado . . . Figura 3. Contenido del libro mayor. H es SHA-256, mientras que H ∗ representa la aplicación jerárquica o recursiva de H. Salida SCP También depende del encabezado anterior hash. Crear cuenta Crear y financiar un nuevo asiento de cuenta en el libro mayor Fusión de cuentas Eliminar asiento del libro mayor de cuenta Establecer opciones Cambiar indicadores y firmantes de cuentas Pago Pagar una cantidad específica de activo al destino. cuenta RutaPago Como Pago, pero paga en un activo diferente (hasta limitar); especificar hasta 5 activos intermediarios AdministrarOferta Crear/eliminar/cambiar asiento de libro mayor de ofertas, -Oferta Pasiva con variante pasiva para permitir un spread cero Administrar datos Crear/eliminar/cambiar cuenta. entrada de datos en el libro mayor CambiarConfianza Crear/eliminar/cambiar línea de confianza Permitir confianza Establecer o borrar la bandera autorizada en la línea de confianza Secuencia de golpes Aumentar sec. numero en cuenta Figura 4. Operaciones del libro mayor principal de ese tamaño cada vez que un nodo se ha desconectado de la red durante demasiado tiempo. Por lo tanto, la instantánea hash es diseñado para optimizar tanto la hashing como la conciliación estatal. Específicamente, la instantánea estratifica los asientos del libro mayor por tiempo. de la última modificación en un conjunto de contenedores de tamaño exponencial llamados cubos. La colección de cubos se llama cubo. lista, y tiene cierta similitud con los árboles de fusión estructurados logarítmicamente (árboles LSM) [77]. La lista de deseos no se lee durante el procesamiento de transacciones (consulte la Sección 5.4). Por lo tanto, cierto diseño Se pueden relajar algunos aspectos de los árboles LSM. En particular, al azar No se requiere acceso mediante clave y los depósitos solo se leen. secuencialmente como parte de la fusión de niveles. Haciendo el cubo La lista se realiza hashing cada depósito a medida que se fusiona y calculando un nuevo hash acumulativo del depósito hashes (un pequeño, índice fijo de referencia hashes) en cada cierre del libro mayor. Conciliar la lista de deseos después de la desconexión requiere descarga sólo cubos que difieren. 5.2 Modelo de transacción Una transacción consta de una cuenta fuente, criterios de validez, una memorándum y una lista de una o más operaciones. La Figura 4 enumera las operaciones disponibles. Cada operación tiene una cuenta fuente, que por defecto es el de la transacción global. Una transacción debe estar firmado por claves correspondientes a cada cuenta de origen en una operación. Las cuentas multifirma pueden requerir una firma más alta peso para algunas operaciones (como SetOptions) y menor para otros (como AllowTrust). Las transacciones son atómicas: si alguna operación falla, ninguna de ellas ellos ejecutan. Esto simplifica los acuerdos multidireccionales. Supongamos que un El emisor crea un activo para representar títulos de propiedad y el usuario A. quiere cambiar una pequeña parcela de tierra más $10,000 por una parcela de tierra más grande propiedad de B. Los dos usuarios pueden firmar una única transacción que contiene tres operaciones: dos terrenos Pagos y pago de un dólar. El principal criterio de validez de una transacción es su número de secuencia, que debe ser uno mayor que el de la transacción. asiento contable de la cuenta fuente. Ejecutar una transacción válida (con éxito o no) incrementa el número de secuencia, evitando la repetición. Los números de secuencia iniciales contienen el libro mayor. número en los bits altos para evitar la reproducción incluso después de eliminar y volver a crear una cuenta. El otro criterio de validez es un límite opcional sobre cuándo se puede ejecutar una transacción. Volviendo a la tierra y al dólar intercambio anterior, si A firma la transacción antes que B, A no puede quiere que B se quede sentado en la transacción durante un año antes de presentarla ello, y por lo tanto podría imponer un límite de tiempo que invalida la transacción después de unos días. También se pueden configurar cuentas multifirma para dar peso de firma a la revelación de una preimagen hash, que, combinado con límites de tiempo, permite el comercio atómico entre cadenas [1]. La cuenta fuente de una transacción paga una tarifa trivial en XLM, 10-5 XLM a menos que haya congestión. En condiciones de congestión, el El coste de las operaciones se fija en una subasta holandesa. Los validadores son no compensado por tarifas porque los validators son análogos a Bitcoin nodos completos, no mineros. En lugar de destruir XLM, las tarifas se reciclan y distribuyen proporcionalmente mediante el voto de titulares de XLM existentes, que en retrospectiva podrían o podrían No habría valido la pena la complejidad. 5.3 Valores de consenso Para cada libro mayor, Stellar utiliza SCP para acordar una estructura de datos con tres campos: un conjunto de transacciones hash (incluido un hash del encabezado del libro mayor anterior), una hora de cierre, unaactualizaciones. Cuando se confirma la nominación de varios valores, Stellar toma el conjunto de transacciones con más operaciones (rompiendo lazos por tarifas totales, luego conjunto de transacciones hash), la unión de todos actualizaciones y el tiempo de cierre más alto. Un tiempo cercano es sólo válido si es entre la hora de cierre del último libro mayor y la presente, por lo que los nodos no nominan tiempos no válidos. Las actualizaciones ajustan parámetros globales como el saldo de reserva, la tarifa mínima de operación y la versión del protocolo. cuando combinados durante la nominación, las tarifas más altas y los números de versión del protocolo reemplazan a los más bajos. Las actualizaciones afectan la gobernanza a través de un espacio de disputa de votación federada [34], ninguno de los dos igualitario ni centralizado. Cada validator está configurado como ya sea gobernante o no gubernamental (el valor predeterminado), según a si su operador quiere participar en la gobernanza. Los validator que gobiernan consideran tres tipos de actualización: deseado, válido e inválido (cualquier cosa que el validator no

SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. validator núcleo horizonte FS DB DB enviar cliente cliente otros validators Figura 5. Arquitectura Stellar validator saber implementar). Las actualizaciones deseadas se configuran para desencadenar en un momento específico, destinado a ser coordinado entre operadores. Los nodos gobernantes siempre votan para nominar a los candidatos deseados. actualizaciones, acepte pero no vote para nominar actualizaciones válidas (es decir, aceptar un quórum de bloqueo) y nunca votar por o aceptar actualizaciones no válidas. Eco no gubernamental de validators cualquier voto que vean para una actualización válida, esencialmente delegando la decisión sobre qué actualizaciones se desean para aquellos que optan para un rol de gobernanza. 5.4 Implementación La Figura 5 muestra la arquitectura validator de Stellar. un demonio llamado stellar-core (~92k líneas de C++, sin contar bibliotecas de terceros) implementa el protocolo SCP y la máquina de estado replicada. Producir valores para SCP requiere reducir un gran número de entradas del libro mayor a pequeños valores criptográficos. hashes. Por el contrario, la validación y ejecución de transacciones requiere buscar el estado de la cuenta y la correspondencia de pedidos en el mejor precio. Para cumplir ambas funciones de manera eficiente, stellar-core mantiene dos representaciones del libro mayor: una representación externa que contiene la lista de deseos, almacenada como archivos binarios que se puede actualizar de manera eficiente y modificar incrementalmentehash, y una representación interna en una base de datos SQL (PostgreSQL para nodos de producción). Stellar-core crea un archivo histórico de solo escritura que contiene cada conjunto de transacciones que se confirmó y instantáneas de cubos. El archivo permite que los nuevos nodos se inicien solos al unirse a la red. También proporciona un registro del libro mayor. historia: es necesario que haya algún lugar donde se pueda buscar una transacción de hace dos años. Dado que el historial es solo para agregar y se accede con poca frecuencia, se puede guardar en lugares baratos como Amazon Glacier o cualquier servicio que permita almacenar y recuperar archivos planos. Los hosts validadores normalmente no alojan sus propios archivos para evitar cualquier impacto en la validación desempeño de la historia del servicio. Para mantener simple el núcleo estelar, no está diseñado para ser utilizado directamente por las aplicaciones y expone sólo una interfaz muy estrecha para el envío de nuevas transacciones. para apoyar clientes, la mayoría de los validator ejecutan un demonio llamado horizonte (∼18k líneas de Go) que proporciona una interfaz HTTP para enviar y aprendizaje de transacciones. horizonte tiene acceso de sólo lectura a base de datos SQL de stellar-core, minimizando el riesgo de horizonte núcleo estelar desestabilizador. Funciones como la búsqueda de rutas de pago se implementan completamente en el horizonte y se pueden actualizar unilateralmente sin coordinarse con otros validators. Varios demonios opcionales de capa superior son clientes del horizonte, completando el ecosistema. Un servidor puente facilita integración de Stellar con sistemas existentes, por ejemplo, publicación de notificaciones de todos los pagos recibidos por una cuenta específica. un El servidor de cumplimiento proporciona ganchos para que las instituciones financieras intercambiar y aprobar información del remitente y del beneficiario sobre pagos, para el cumplimiento de listas de sanciones. Finalmente, un servidor de federación implementa un nombre legible por humanos sistema de cuentas. 6 Experiencia de implementación Stellar creció durante varios años hasta convertirse en un estado con una moderada número de operadores de nodo completo razonablemente confiables. Sin embargo, Las configuraciones de los nodos eran tales que la vida (aunque no seguridad) dependía de nosotros, la Fundación para el Desarrollo Stellar (FDS); Si SDF hubiera desaparecido repentinamente, otros operadores de nodos Habría sido necesario intervenir y eliminarnos manualmente. de porciones de quórum para que la red continúe. Si bien nosotros y muchos otros queremos reducir la importancia sistémica del SDF, este objetivo recibió una prioridad cada vez mayor después de Los investigadores [58] cuantificaron y dieron a conocer la centralización de la red sin diferenciar los riesgos para la seguridad y vivacidad. Varios operadores reaccionaron con ajustes activos de configuración, principalmente aumentando el tamaño de su divisiones de quórum en un esfuerzo por diluir la importancia del SDF; Irónicamente, esto sólo aumentó el riesgo para la vida. Dos problemas agravaron la situación. Primero, un popular herramienta de monitoreo de terceros Stellar [5] fue sistemáticamente sobreestimar el tiempo de actividad de validator al no verificarlo ese núcleo estelar estaba funcionando; esto lleva a la gente a incluir nodos poco confiables en sus sectores de quórum. En segundo lugar, un error en núcleo estelar significaba que una vez que un validator se movía al siguiente libro mayor, no ayudó adecuadamente a los nodos restantes a completar el proceso anteriorlibro mayor en caso de pérdida de mensajes. Como resultado, el La red experimentó 67 minutos de inactividad y requirió coordinación manual por parte de validator administradores para reiniciar. Peor aún, al intentar reiniciar la red, se produjeron reconfiguraciones apresuradas simultáneas en varios nodos. en una mala configuración colectiva que permitió que algunos nodos divergen, lo que requiere un apagado manual de esos nodos y nueva presentación de las transacciones aceptadas durante la divergencia. Afortunadamente, esta divergencia fue detectada y corregida. rápidamente y no contenía transacciones conflictivas, pero el riesgo de que la red no pueda disfrutar de la intersección del quórum: dividiéndose mientras se continúa aceptando situaciones potencialmente conflictivas. transacciones, simplemente debido a una mala configuración, se realizó muy concreto por este incidente. La revisión de estas experiencias llevó a dos conclusiones principales. y las acciones correctivas correspondientes.Pagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Crítico, 100% 51% 51% Alto, 67% 51% Medio, 67% 51% Bajo, 67% 51% 51% ... ... ... 51% ... 51% Figura 6. Jerarquía de calidad del validador. Nodos de la más alta calidad requieren el umbral más alto del 100%, mientras que las calidades más bajas están configuradas con un umbral del 67%. Nodos dentro de un solo organización requiere una mayoría simple del 51%. 6.1 Complejidad y fragilidad de la configuración. Stellar expresa sectores de quórum como conjuntos de quórum anidados que constan de n entradas y un umbral k donde cualquier conjunto de k entradas constituye una porción de quórum. Cada una de las n entradas entonces es una clave pública validator o, de forma recursiva, otro conjunto de quórum. Aunque flexibles y compactos, implementamos el quórum anidado conjuntos simultáneamente brindaban a los operadores de nodos demasiada flexibilidad y muy poca orientación: era fácil escribir datos inseguros (o incluso configuraciones sin sentido). Los criterios para agrupar nodos en conjuntos, para organizar subconjuntos en una jerarquía, y para elegir los umbrales no fueron suficientemente claros y contribuyeron a fallos operativos. No estaba claro si tratar un "nivel" en la jerarquía de conjuntos anidados como un nivel de confianza, o una organización, o ambos; muchas configuraciones en el campo mezcló estos conceptos, además de especificar peligros o umbrales sin sentido. Por lo tanto, agregamos un mecanismo de configuración más simple. que separa dos aspectos de los conjuntos de quórum anidados: agrupación nodos juntos por organización y etiquetando cada organización con una clasificación de confianza simple (baja, media, alta o crítico). Las organizaciones en niveles superiores y superiores deben publicar archivos de historia. El nuevo sistema sintetiza conjuntos de quórum anidados en los que cada organización está representada como un Se establece un umbral del 51 % y las organizaciones se agrupan en conjuntos con umbrales del 67% o 100% (dependiendo de la calidad del grupo). Cada grupo es una entrada única en el siguiente grupo (de mayor calidad), como se ilustra en la Figura 6. Este modelo simplificado reduce la probabilidad de una mala configuración, tanto en términos de la estructura de los conjuntos anidados sintetizados y los umbrales elegidos para cada conjunto. 6.2 Detección proactiva de errores de configuración En segundo lugar, nos dimos cuenta de que detectar la mala configuración colectiva esperando a observar sus efectos negativos es demasiado tarde. Especialmente con respecto a configuraciones erróneas que pueden divergir: un modo de falla más grave que detenerse: la red necesita para poder detectar errores de configuración inmediatamente para que los operadores puedan revertirlos antes de que ocurra cualquier divergencia. Para abordar esta necesidad, construimos un mecanismo en el software validator que recopila continuamente el estado de configuración colectiva de todos los pares en el cierre transitivo del nodo y detecta el potencial de divergencia, es decir, disjuntos. quórums, dentro de esa configuración colectiva. 6.2.1 Comprobando la intersección del quórum Si bien reunir porciones de quórum es fácil, encontrar quórums disjuntos entre ellas es co-NP-difícil [62]. Sin embargo, adoptamos un conjunto de heurísticas algorítmicas y reglas de eliminación de casos propuesto por Lachowski [62] que verifica casos típicos del problema varios órdenes de magnitud más rápido que el costo en el peor de los casos. En la práctica, la red actual Los cierres transitivos de sectores de quórum son del orden de 20 a 30. nodos y, con las optimizaciones de Lachowski, normalmente verifica en cuestión de segundos en una sola CPU. Si surge la necesidad Para mejorar el rendimiento, podemos paralelizar la búsqueda. 6.2.2 Comprobando configuraciones riesgosas Detectar que la red admite quórums disjuntos es un paso en la dirección correcta, pero advierte el peligro incómodamente tarde para un tema tan crítico. Idealmente, queremos que los operadores de nodos reciban advertencias cuando la configuración colectiva de la red simplemente se está acercando a un estado de riesgo. Por lo tanto, ampliamos el verificador de intersección de quórum para detectar una condición que llamamos criticidad: cuando la corriente La configuración colectiva está a una mala configuración de un estado que admite quórumes disjuntos. Para detectar la criticidad, el verificador reemplaza repetidamente la configuración de cada organización con una configuración incorrecta simulada en el peor de los casos, luego Vuelve a ejecutar el verificador de intersección del quórum interno en el resultado. Si existe algún error de configuración crítico, a un paso de distancia desde el estado actual, el software emite una advertencia y informa que la organización presenta un riesgo de configuración incorrecta. Estos cambios dan a la comunidad de operadores dos capas de aviso y orientación para aislarse contra las peores formas de una mala configuración colectiva.

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.

Evaluación

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

Comprender la idoneidad de Stellar como pago global y red comercial, evaluamos el estado de la red pública y realizó experimentos controlados en un laboratorio experimental privado. red. Nos centramos en las siguientes preguntas: • ¿Cómo es la topología de la red de producción? ¿Cuántos mensajes se transmiten en promedio y ¿Cómo experimenta SCP los tiempos de espera? • ¿Las latencias de actualización del consenso y del libro mayor siguen siendo independientes del número de cuentas?SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. • ¿Cómo se ven afectadas las latencias por el aumento de (a) las transacciones por segundo (y, en consecuencia, las transacciones por segundo)? libro mayor), y (b) el número de validator nodos? • ¿Cuál es el costo de ejecutar un nodo en términos de CPU? memoria y ancho de banda de la red? Las redes de pago tienen tasas de transacción bajas en comparación a otros tipos de sistemas distribuidos. Los principales blockchains, Bitcoin y Ethereum, confirman hasta 15 transacciones/segundo, menos de Stellar. Además, estos sistemas tardan unos minutos en Una hora para confirmar una transacción de forma segura, porque la prueba de trabajo requiere esperar a que se extraigan varios bloques. el La red SWIFT no blockchain promedió solo 420 transacciones por segundo en su día pico [14]. Por lo tanto elegimos para comparar nuestras mediciones con el objetivo de 5 segundos intervalo del libro mayor, un objetivo más agresivo. Nuestros resultados muestran que las latencias están cómodamente por debajo de este límite incluso con Varias optimizaciones no implementadas aún están en proceso. 7.1 Anclas Los principales activos negociados por volumen incluyen divisas (por ejemplo, 3 USD anclas, 2 CNY), un ancla Bitcoin, un valor respaldado por bienes raíces token [92] y una moneda en la aplicación [8]. Diferentes anclas tienen diferentes políticas. Por ejemplo, un ancla en USD, Stronghold, establece auth_reqired y requiere un proceso de conocimiento de su cliente (KYC) para cada cuenta que tenga su activos. Otro, AnchorUSD, cualquiera puede recibir e intercambiar sus USD (haciendo literalmente posible enviar $0.50 a México en 5 segundos con una tarifa de $0.000001). Sin embargo, AnchorUSD requiere KYC y tarifas para comprar o canjear sus USD con transferencias bancarias convencionales. En Filipinas, donde Las regulaciones bancarias son más laxas para los pagos entrantes, monedas.ph admite el retiro de PHP en cualquier cajero automático [36]. Además de la seguridad token mencionada anteriormente y la moneda de la aplicación, existe una variedad de tokens no monetarios que van desde bonos comerciales [22] y créditos de carbono [85, 96] a más activos esotéricos como un token que incentiva la colaboración recuperación del automóvil [35]. 7.2 Red pública Al momento de escribir este artículo, hay 126 nodos completos activos, 66 de los cuales participar en el consenso firmando mensajes de voto. Figura 7 (generado por [5]) visualiza la red, con una línea entre dos nodos si uno aparece en los sectores de quórum del otro y un Línea azul más oscura para mostrar dependencia bidireccional. en el El centro es un grupo de 17 “validators de nivel uno” de facto dirigidos por SDF, SatoshiPay, LOBSTR, COINQVEST y Keybase. Hace cuatro meses, antes de los acontecimientos de la Sección 6, había Había 15 nodos sistémicamente importantes: 3 de aparentemente organizaciones de primer nivel y varios singletons aleatorios. el El gráfico también parecía mucho menos regular. Por lo tanto, el nuevo mecanismo de configuración y/o mejores decisiones del operador parecen contribuir a una topología de red más saludable. sin Grandes recursos financieros (y el correspondiente accionista). Figura 7. Mapa de porción de quórum obligaciones), hubiera sido difícil reclutar 5 niveles uno organizaciones desde el principio. Esto sugiere quórum Los sectores desempeñan un papel útil en el arranque de la red: cualquiera puede unirse con el objetivo de convertirme en un jugador importante porque no existen barreras para el acuerdo por parejas. Actualmente hay más de 3,3 millones de cuentas en el libro mayor. Más En un período reciente de 24 horas, Stellar promedió 4,5 transacciones y 15,7 operaciones por segundo. Revisando los libros de contabilidad recientes, la mayoría Las transacciones parecen tener una sola operación, mientras que cada pocos En los libros mayores vemos transacciones que contienen muchas operaciones que parecen provenir de creadores de mercado que gestionan ofertas. el Los tiempos medios para lograr el consenso y actualizar el libro mayor fueron 1061 ms y 46 ms, respectivamente. Los percentiles 99 fueron 2252 ms y 142 ms (el primero refleja un tiempo de espera de 1 segundo en la selección del líder de nominación). Tenga en cuenta que el rendimiento de SCP es en su mayoría independiente de las transacciones por segundo, ya que SCP acuerda un hash de muchas transacciones arbitrarias. Es más probable que surjan cuellos de botella al propagar el candidato. transacciones durante la nominación, ejecución y validación transacciones y fusión de depósitos. todavía no hemos necesitado para paralelizar el procesamiento de transacciones de stellar-core en múltiples núcleos de CPU o unidades de disco. También evaluamos la cantidad de mensajes SCP transmitidos. en la red de producción. En el caso normal con un solo líder elegido para nominar un valor, esperamos siete lógicas mensajes a difundir: dos mensajes para votar y aceptar una nomiDeclaración de nacimiento, dos mensajes para aceptar y confirmar. una declaración de preparación, dos mensajes para aceptar y confirmar una declaración de confirmación y, finalmente, un mensaje de externalización (enviado después de enviar un nuevo libro mayor al disco para ayudar a los rezagados ponerse al día). La implementación combina confirmar el compromiso. y externalizar mensajes como una optimización, ya que es Es seguro externalizar un valor una vez comprometido. Luego analizamos las métricas recopiladas en una producción Stellar validator. Más En el transcurso de 68 horas se emitieron 1,3 mensajes/segundo, con un promedio de 6 a 7 mensajes por libro mayor. Observamos que el total

Pagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá percentil Número de tiempos de espera Nominación votación 75% 0 0 99% 1 0 máx. 4 1 Figura 8. Tiempos de espera por libro mayor de 68 horas El recuento de mensajes transmitidos por validators es mayor, ya que en Además de los mensajes de votación federados, los nodos también transmiten cualquier transacción que conozcan. La Figura 8 muestra los tiempos de espera experimentados por una producción. validator durante un período de 68 horas. Los tiempos de espera para las nominaciones son una medida de la (in)eficacia de la función de elección del líder, mientras que los tiempos de espera de las votaciones dependen en gran medida de la red y posibles retrasos en los mensajes. Los tiempos de espera son consistentes. con el número de mensajes emitidos: seis mensajes en el en el mejor de los casos, y al menos siete mensajes si se necesita una ronda de nominaciones adicional. 7.3 Experimentos controlados Realizamos experimentos controlados en contenedores empaquetados en Instancias Amazon EC2 c5d.9xlarge con 72 GiB de RAM, 900 GB de SSD NVMe y 36 vCPU. Cada instancia estaba en la misma región EC2 y tenía un ancho de banda fijo de 10 Gbps. Usamos SQLite como tienda. (Stellar también es compatible con PostgreSQL, pero eso tiene tareas asincrónicas que inyectan ruido en las mediciones). Stellar proporciona una consulta de tiempo de ejecución integrada, generateload, que permite generar carga sintética en un objetivo específico transacción/segunda tasa. Aunque Stellar admite varios Funciones comerciales, como libro de órdenes y ruta entre activos. pagos, nos centramos en pagos simples. La confirmación de transacciones consta de varios pasos, por lo que registró las medidas para cada uno de los siguientes: • Nominación: tiempo desde la nominación hasta la primera preparación. • Votación: tiempo desde la primera preparación hasta la confirmación de una boleta comprometida • Actualización del libro mayor: es hora de aplicar el valor de consenso • Recuento de transacciones: transacciones confirmadas por libro mayor Cada uno de nuestros experimentos estuvo definido por tres parámetros: el número de asientos de cuenta en el libro mayor, la cantidad de carga (en forma de pagos XLM) enviada por segundo, y el número de validators. Configuramos cada validator saber sobre todos los demás validator (el peor de los casos para SCP), con porciones de quórum establecidas en cualquier mayoría simple de nodos (para maximizar el número de quórums diferentes). Línea de base Nuestro experimento de referencia midió Stellar con 100.000 cuentas, cuatro validator y la generación de carga tasa de 100 transacciones/segundo. Observamos 507 transacciones por libro mayor en promedio, con una desviación estándar de 49 (9,7%). Tenga en cuenta que no se descartaron transacciones; el ligero 105 106 107 0 500 1.000 1.500 2.000 Cuentas Latencia [ms] Actualización del libro mayor votación Nominación Figura 9. Latencia a medida que aumenta el número de cuentas La variación se debe a limitaciones de programación del generador de carga. Observamos que el número de transacciones por libro mayor fue consistente con nuestra tasa de generación de carga, dado el libro mayor cerrando cada 5 segundos. Nominación, votación y libro mayor La actualización mostró latencias medias de 82,53 ms, 95,96 ms y 174,08 ms, respectivamente. Observamos que la latencia de nominación El percentil 99 está constantemente por debajo de 61 ms, con ocasionales picos de aproximadamente 1 segundo, correspondientes al primer paso en la función de tiempo de espera de la selección de líder. Dado el desempeño de referencia, analizamos los efectos de variar cada uno de los parámetros de configuración de la prueba. Cuentas Los datos de la Figura 9 sugieren que Stellar escala así como el número de cuentas aumenta. Generación de prueba Las cuentas se convirtieron en un proceso largo, ya que la creación de depósitos y la fusión nos impidió simplemente poblar la base de datos con cuentas directamente a través de SQL. Por lo tanto, llevamos a cabo nuestra experimentos para hasta 50.000.000 de cuentas. mientras hay impacto mínimo en las latencias de actualización del consenso y del libro mayor, observamos que el aumento de cuentas crea un gasto general de fusionando cubos, que se hacen más grandes. Tasa de transacción La tasa de transacción afecta la cantidad de multidifusión de tráfico entre validators, el número de transacciones incluidas en cada libro mayor y el tamaño del nivel superior cubos. Comprender los efectos del aumento de las transacciones. carga, realizamos un experimento con 100.000 cuentas y 4 validators. La Figura 10 muestra un lento crecimiento en la latencia del consenso, mientras que la mayor parte del tiempo se dedicó a actualizar el libro mayor. No es sorprendente que a medida que el conjunto de transacciones aumenta de tamaño, lleva más tiempo enviarlo a la base de datos. También notamos que La latencia de actualización del libro mayor depende en gran medida de la implementación. y se ve afectado por la elección de la base de datos. Nodos validadores Para ver cómo aumenta el número de tíone validatorsimpacta el rendimiento, realizamos experimentos con 100.000 cuentas, 100 transacciones por segundo y un número variable de validators de 4 a 43. Aparecieron todos los validators en todos los sectores de quórum de validators; porciones de quórum más pequeñas tienen un menor impacto en el rendimiento.SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá Lokhava et al. 100 150 200 250 300 350 0 500 1.000 1.500 2.000 Carga [transacciones/segundo] Latencia [ms] Actualización del libro mayor votación Nominación Figura 10. Latencia a medida que aumenta la carga de transacciones 10 20 30 40 0 500 1.000 1.500 2.000 Validadores Latencia [ms] Actualización del libro mayor votación Nominación Figura 11. Latencia a medida que aumenta el número de nodos Cambiar el número de nodos de validación en la red afecta la cantidad de mensajes SCP intercambiados, así como el número de valores potenciales durante la nominación. Figura 11 muestra que el tiempo de nominación crece a un ritmo relativamente pequeño. Si bien los datos sugieren que las votaciones son el cuello de botella, Creemos que muchos problemas de escala se pueden abordar mejorando Red superpuesta de Stellar para optimizar el tráfico de red. como Como era de esperar, la latencia de actualización del libro mayor se mantuvo independiente de el número de nodos. Tasa de cierre Por último, queríamos medir el rendimiento de extremo a extremo de Stellar midiendo la frecuencia con la que se confirman los libros de contabilidad y si Stellar cumple su objetivo de 5 segundos sin abandonar cualquier transacción. Observamos un cierre promedio del libro mayor tiempos de 5,03 s, 5,10 s y 5,15 s a medida que aumentamos la cuenta entradas, tasa de transacción y número de nodos, respectivamente. Los resultados sugieren que Stellar puede cerrar libros contables de forma consistente bajo carga alta. 7.4 Ejecutando un validator Una de las características importantes de Stellar es el bajo costo de ejecutando un validator, ya que los anclajes deben ejecutarse (o contraerse) validators para hacer cumplir la finalidad. SDF ejecuta 3 validator de producción, todos en instancias c5.large de AWS, que tienen dos núcleos, 4 GiB de RAM y CPU Intel(R) Xeon(R) Platinum 8124M @ Procesadores de 3,00 GHz. Inspeccionar el uso de recursos en uno de estas máquinas, observamos el proceso Stellar usando alrededor del 7% de la CPU y 300 MiB de memoria. En términos de tráfico de red, con 28 conexiones a pares y un tamaño de quórum de 34, las velocidades entrantes y salientes fueron de 2,78 Mbit/s y 2,56 Mbit/s, respectivamente. Hardware necesario para ejecutar tal El proceso es económico. En nuestro caso, el coste es de 0,054$/hora. o alrededor de $40/mes. 7.5 Trabajo futuro Estos experimentos sugieren que Stellar puede escalar fácilmente entre 1 y 2 pedidos de magnitud más allá del uso actual de la red. porque el Las demandas de rendimiento han sido tan modestas hasta la fecha, Stellar deja espacio para muchas optimizaciones sencillas utilizando técnicas bien conocidas. Por ejemplo, transacciones y SCP los mensajes son transmitidos por validators usando una inundación ingenua protocolo, pero idealmente debería utilizar métodos más eficientes y estructurados. multidifusión punto a punto [30]. Además, con muchas bases de datos El tiempo de actualización del libro mayor se puede mejorar mediante técnicas estándar de procesamiento por lotes y captación previa.

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

Conclusión

Los pagos internacionales son caros y tardan días. Fondo la custodia pasa a través de múltiples instituciones financieras, incluidos bancos corresponsales y servicios de transferencia de dinero. Debido a que se debe confiar plenamente en cada salto, es difícil para los nuevos nuevos participantes ganen cuota de mercado y compitan. Stellar muestra cómo enviar dinero a todo el mundo de forma económica en segundos. el La innovación clave es un nuevo protocolo de acuerdo bizantino de membresía abierta, SCP, que aprovecha la estructura de igual a igual. de la red financiera para lograr un consenso global bajo un Nueva hipótesis de Internet. SCP permite que Stellar se comprometa atómicamente transacciones irreversibles entre participantes arbitrarios que no se conocen ni confían el uno en el otro. Esto, a su vez, garantiza a los nuevos participantes el acceso a los mismos mercados establecidos. jugadores, hace que sea seguro obtener el mejor intercambio disponible tasas incluso de creadores de mercado que no son de confianza, y dramáticamente Reduce la latencia de pago. Agradecimientos Stellar no estaría donde está hoy sin el temprano liderazgo de Joyce Kim o las tremendas contribuciones de Scott Fleckenstein y Bartek Nowotarski en la construcción y manteniendo horizonte, el SDK Stellar y otras piezas clave del ecosistema Stellar. También agradecemos a Kolten Bergeron, Henry Corrigan-Gibbs, Candace Kelly, Kapil K. Jain, Boris Reznikov, Jeremy Rubin, Christian Rudder, Eric Saunders, Torsten Stüber, Tomer Weller, los revisores anónimos y nuestra pastora Justine Sherry por sus útiles comentarios sobre borradores anteriores. Descargo de responsabilidad La contribución del profesor Mazières a esta publicación fue como consultor remunerado y no formó parte de su Deberes o responsabilidades de la Universidad de Stanford.

Pagos globales rápidos y seguros con Stellar SOSP ’19, 27 al 30 de octubre de 2019, Huntsville, ON, Canadá