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

Аннотация

Международные платежи медленны и дороги, отчасти из-за многошаговой маршрутизации платежей через разнородные сети. банковские системы. Stellar — новая глобальная платежная сеть который может напрямую переводить цифровые деньги в любую точку мира. мир за секунды. Ключевое нововведение — безопасная транзакция механизм через ненадежных посредников, используя новый Протокол византийского соглашения под названием SCP. С помощью SCP каждый учреждение указывает другие учреждения, в которых можно остаться по согласию; благодаря глобальной взаимосвязанности финансовой системы, вся сеть затем соглашается на атомную транзакции, охватывающие произвольные учреждения, без риска платежеспособности или валютного курса со стороны промежуточных эмитентов активов или маркет-мейкеры. Мы представляем модель, протокол и формальная проверка; описать платежную сеть Stellar; и, наконец, оценить Stellar эмпирически с помощью тестов и наш опыт нескольких лет производственного использования. Концепции CCS • Безопасность и конфиденциальность → Распределенный безопасность систем; • Организация компьютерных систем → Одноранговые архитектуры; • Информационные системы → Электронный перевод средств. Ключевые слова blockchain, BFT, кворумы, выплаты Справочный формат ACM: Марта Лохава, Джулиано Лоса, Дэвид Мазьер, Грэйдон Хоар, Николас Бэрри, Эли Гафни, Джонатан Джоув, Рафал Малиновский, Джед Маккалеб. 2019. Быстрые и безопасные глобальные платежи с Stellar. В СОСП ’19: Симпозиум по принципам операционных систем, 27–30 октября, 2019, Хантсвилл, Онтарио, Канада. ACM, Нью-Йорк, Нью-Йорк, США, 17 страниц. 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.

Введение

Международные платежи, как известно, медленные и дорогостоящие [32]. Подумайте о непрактичности отправки 0,50 доллара США из США в *Галуа, Инк. † Калифорнийский университет в Лос-Анджелесе Разрешение на создание цифровых или печатных копий всей или части этой работы для использование в личных целях или в классе предоставляется бесплатно при условии, что копии не изготовлены или распространены с целью получения прибыли или коммерческой выгоды, и что копии несут это уведомление и полная цитата на первой странице. Авторские права на компоненты этой работы, принадлежащей не ACM, необходимо уважать. Абстрагирование с помощью кредит разрешен. Копировать иным образом или повторно публиковать, размещать на серверах или повторное распространение по спискам требует предварительного специального разрешения и/или платы. Запрос разрешения от [email protected]. SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада © 2019 Ассоциация вычислительной техники. ISBN ACM 978-1-4503-6873-5/19/10...$15,00 https://doi.org/10.1145/3341301.3359636 Мексика, две соседние страны. Конечные пользователи платят почти 9 долларов. в среднем такая передача [32] и двустороннее соглашение при посредничестве центральных банков стран может лишь сократить стоимость базового банка составляет 0,67 доллара США за единицу [2]. Помимо сборов, обычно учитывается задержка международных платежей в сутках, что делает невозможным быстрое получение денег за границу в чрезвычайные ситуации. В странах, где банковская система не работают или не обслуживают всех граждан, или там, где плата невыносима, люди прибегают к отправке платежей автобусом [38], лодка [19], а иногда и Bitcoin [55], и все это несут риск, задержки или неудобства. Несмотря на то, что затраты на соблюдение требований будут всегда, данные свидетельствуют о том, что значительная сумма теряется из-за отсутствия конкуренции [21], что усугубляется неэффективными технологиями. Где люди могут внедрять инновации, цены и задержки снижаются. Например, денежные переводы с банковских счетов во втором квартале 2019 года стоили в среднем 6,99%, тогда как показатель мобильных денег составил всего 4,88% [13]. Открытая глобальная платежная сеть, привлекающая инновации и конкуренция со стороны небанковских организаций может привести к снижению затраты и задержки на всех уровнях, включая соответствие [83]. В этом документе представлен Stellar, платеж на основе blockchain. сеть, специально созданная для содействия инновациям и конкуренция в международных платежах. Stellar — первый систему для достижения всех трех следующих целей (в рамках новая, но эмпирически обоснованная «интернет-гипотеза»): 1. Открытое членство. Любой может выпускать облигации, обеспеченные валютой. цифровые token, которыми могут обмениваться пользователи. 2. Окончательность, обеспечиваемая эмитентом. Эмитент token может предотвратить транзакции в token от отмены или отмены. 3. Атомарность между эмитентами. Пользователи могут атомарно обмениваться и торгуйте token от нескольких эмитентов. Достичь первых двух несложно. Любая компания может в одностороннем порядке предложить такой продукт, как Paypal, Venmo, WeChat. Pay или Alipay и обеспечьте окончательность платежей в виртуальные валюты, которые они создали. К сожалению, атомарные транзакции между этими валютами невозможны. Фактически, несмотря на то, что Paypal приобрела материнскую компанию Venmo в 2013 году конечные пользователи по-прежнему не могут отправлять Venmo долларов пользователям Paypal [78]. Только в последнее время торговцы могут даже принять оба с одной интеграцией. Цели 2 и 3 могут быть достигнуты в закрытой системе. В частности, в ряде стран действуют эффективные внутренние платежные системы. сети, обычно контролируемые регулирующим органом, пользующимся универсальным доверием. Однако членство ограничивается закрытым набор зарегистрированных банков, а сети ограничены досягаемость регулирующего органа страны.SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Цели 1 и 3 были достигнуты за добытые blockchains, особенно в форме ERC20 tokens на Ethereum [3]. Основная идея этих blockchain — создать новую криптовалюту, с помощью которой можно будет вознаграждать людей за поселение. транзакции трудно отменить. К сожалению, это означает, что эмитенты token не контролируют завершенность транзакций. Если программное обеспечение ошибки приводят к реорганизации истории транзакций [26, 73], или когда трофеи от обмана людей превышают стоимость реорганизации истории [74, 97], эмитенты могут нести ответственность за tokens они уже выкуплены за реальные деньги. Stellar blockchain имеет два отличительных свойства. Во-первых, он изначально поддерживает эффективные рынки между tokens от разных эмитентов. В частности, любой может выдать token, blockchain предоставляет встроенную книгу заказов для торговли между любой парой token, и пользователи могут осуществлять платежи по пути которые атомарно торгуют несколькими валютными парами, в то время как гарантия сквозной лимитной цены. Во-вторых, Stellar представляет новое византийское соглашение. протокол SCP (Stellar Протокол консенсуса), посредством которого Эмитенты token назначают определенные серверы validator для обеспечения соблюдения завершенность сделки. Пока никто не скомпрометирует validator эмитента (а также лежащие в его основе цифровые подписи и криптографические hashе остаются в безопасности), эмитент точно знает, какие транзакции произошли, и избегает риска убытков от blockchain истории реорганизации. Ключевая идея SCP заключается в том, что большинство эмитентов активов получают выгоду от ликвидные рынки и хотят облегчить атомарные транзакции с другими активами. Следовательно, администраторы validator настраивают свои серверы, чтобы договориться с другими validator о точном история всех транзакций по всем активам. validator v1 может быть настроено на согласие с версией 2, или v2 можно настроить на согласие с v1 или оба могут быть настроены для согласования друг с другом; во всех случаях ни один из них не будет сохранять историю транзакций до тех пор, пока он знает, что другой не может принять участие в другой истории. По транзитивности, если v1 не может не согласиться с v2, а v2 не может не согласиться с v3 (или наоборот), v1 не может не согласиться с v1. v3, независимо от того, представляет ли v3 активы, о которых v1 вообще слышал оф. Предполагая, что эти отношения соглашения транзитивно подключить всю сеть, SCP гарантирует глобальное соглашение, что делает его глобальным византийским соглашением протокол с открытым членством. Мы называем это новое предположение о связности гипотезой Интернета и отмечаем, что оно касается как «Интернета» (который всем понятен, означают единственную крупнейшую транзитивно подключенную IP-сеть) и устаревшие международные платежи (которые выполняются поэтапно неатомарны, но используют транзитивно связанную глобальную сеть финансовых учреждений). Stellar используется с сентября 2015 г. Чтобы длина blockchain оставалась управляемой, система запускает SCP с интервалом в 5 секунд — быстро по стандартам blockchain, но гораздо медленнее, чем типичное применение византийского соглашения. Хотя основным использованием были платежи, Stellar также доказанная привлекательность для неденежных взаимозаменяемых token, которые приносят пользу с непосредственных вторичных рынков (см. раздел 7.1). В следующем разделе обсуждаются соответствующие работы. В разделе 3 представлены SCP. Раздел 4 описывает нашу формальную проверку SCP. В разделе 5 описан уровень оплаты Stellar. Раздел 6 касается наш опыт развертывания и извлеченные уроки. В разделе 7 оценивается система. Раздел 8 завершается.

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.

Связанная работа

Система, описанная в этой статье, является нашей третьей попытка реализовать децентрализованную платежную сеть. первая попытка одного из авторов привела к появлению Ripple blockchain. Несмотря на то, что Ripple все еще существует, мы считаем, что он не сможет реализовать концепцию по-настоящему открытой платежной сети для как управленческие, так и технические причины. Причины управления вытекают из противоречия между интересами акционеров и пользователей сети, но выходят за рамки данной статьи. техническая проблема заключается в том, что протокол византийского соглашения Ripple [89] требует почти закрытого членства [33], что делает его функционально аналогично обычному византийскому соглашению. Вторая попытка, недолговечный форк кода Ripple база под названием «Стеллард» была запущена в эксплуатацию в июле 2014 года. Мы планировали разработайте SCP и по мере готовности вставьте его в Stellar, но вместо этого решил построить новую систему с нуля вокруг SCP, называется звездным ядром и описывается в этой статье. звездное ядро был выпущен вместе с описанием и доказательством SCP [68]. в апреле 2015 г. и поступил в серийное производство 5 месяцев спустя. В интернет-проекте [20] позже был описан SCP для разработчиков. Мотивация и структура SCP подобны асимметричному доверию в многосторонних вычислениях [40], хотя эта модель требует, чтобы узлы имели глобальное представление о структуре противника. Введя понятие срезов кворума, SCP получает возможность обнаружения и динамическое членство, которые важны для развертывания Stellar. Личный византийский кворум системы [47] и асимметричное распределенное доверие [29] обобщают кворумы SCP и упрощают сравнение с традиционными системы. В более ограниченных условиях Gotsman et al. [49] также изучите обобщение кворумов Stellar. Несколько других blockchain переняли SCP, в том числе MobileCoin [7] и NCNT. Ripple также недавно предложила протокол Византийского соглашения об открытом членстве. под названием Кобальт [66]. Безопасность SCP оптимальна, поэтому SCP безопасен в любой сценарий отказа, в котором присутствует кобальт, а наоборот неясно. Однако Cobalt утверждает, что его условия безопасности легче понять и, следовательно, менее подвержены неправильной настройке. будет интересно оценить, будет ли Cobalt развернут. 2.1 Системы без открытого членства Как и многие протоколы консенсуса, SCP основан на голосовании [50, 94] в системе кворума. Предыдущие работы по системам кворума [52, 67, 72], иногда называемые «наборами выживших» [57], изучают системы кворума, которые являются статическими, т.е. системное исполнение и единообразное, т. е. где все узлы имеют такое же представление о том, что такое кворум. Настройки SCP отличаются что разные узлы принимают разные и развивающиеся кворумы.Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Гетерогенный быстрый консенсус [91] позволяет детализировать понятия доверия должны быть выражены через ярлыки в решетке и использует это для оптимизации коммуникации, но предполагает закрытое членство. Другие попытки адаптировать протоколы византийских соглашений к настройкам, подобным блокчейну, включая HoneyBadger [70], SBFT [53] и HotStuff [99] сосредоточились на масштабируемости. для многих участников и производительности в глобальных сетях, сохраняя традиционную модель закрытого членства. Блокчейны, нацеленные на закрытое членство, использовали такие протоколы, включая последний Libra [11]. 2.2 Системы без окончательности, навязанной эмитентом Bitcoin [71] был первым взаимозаменяемым цифровым активом без доверенный орган для отслеживания остатков. Одновременно было решено две проблемы: как распространить новый актив, чтобы люди поверили оно имеет ценность и как обеспечить необратимые транзакции, которые предотвратить атаки двойного расходования. Bitcoin создает активы посредством proof-of-work [43], которую автор сравнивает с золотодобытчиками, инвестирующими ресурсы для увеличения предложения золота. доказанная работа зависит от истории транзакций, что мешает атаки двойного расходования, поскольку откат транзакций требует работы, сравнимой с созданием исходной истории. Атаки на proof-of-work blockchains стали возможными как только злоумышленник контролирует 1/3 мощности майнинга [46, 48]. Проверка работоспособности особенно рискованна для новых или небольших blockchain [15, 23]; известно, что авторитетные майнеры отвлекают добычу полезных ископаемых власти более мелким цепочкам ради прибыли [10, 54, 74, 97, 98] или просто для создают проблемы [25, 37] (так называемые «атаки Голдфингера» [60]). Время от времени майнеры благосклонно применяли такие «атаки 51%», чтобы устранить нежелательные последствия ошибок [95]. Новый blockchains могут получить некоторую защиту от атак 51%, использование более известных blockchain с объединенным майнингом [6] или доказательством сжигания [79]. На момент написания этой статьи стоимость атаки 51% оценивалась в 823 000 долларов США. час Bitcoin, $93,000/hour on Ethereum, and under $20,000/ час для всех остальных отслеживаемых blockchains [12]. В конечном итоге эти затраты зависят от стоимости криптовалюты, стимулирующей майнинг, которая не зависит от стоимости выпущенных активы. Напротив, стоимость компрометации Stellar validators в некоторой степени находится под контролем их администраторов; SCP допускает реализации с высокой степенью надежности, такие как использование аппаратных модулей безопасности для предотвращения validator от подписывая противоречивые сообщения. В качестве дополнительного преимущества, Stellar не имеет затрат на майнинг, которые можно было бы окупить за счет транзакции. пошлины или сеньораж. Огромное потребление энергии Bitcoin [76] мотивировало более энергоэффективные варианты доказательства работы, такие как доказательство пространства [16, 17, 44, 87], доказательство хранения [18, 56, 86, 90], и подтверждение прошедшего времени [4]. Доказательство работы может быть медленным из-за блоков транзакций. требуются минуты для подтверждения и несколько блоков, необходимых для более сильная безопасность. Однако работа по добыче блока может быть амортизируется в течение пакета транзакций произвольного размера, ограниченного только политическими проблемами и совместимостью. BitcoinNG [45] использует подтверждение работы, чтобы выбрать руководителя, который координирует больший пакет транзакций. Thunderella [84] может использовать доказательство работы в качестве запасного «медленного пути» и оптимистично подтверждать транзакции намного быстрее с использованием асинхронного консенсуса протокол, когда узел акселератора и 3/4 избранного комитета честны. Хотя SCP быстрее, чем proof-of-work, для этого требуется больше сообщений, чем для быстрого пути Thunderella, но потенциально может быть полезным медленным путем Thunderella. Альтернативой доказательству работы является доказательство доли [59], в котором майнеры получают влияние прямо или косвенно от владения активами. В некоторых случаях влияние увеличивается со временем владения активами. Некоторые схемы поощрять честность, конфискуя долю майнеров, если они плохо себя вести [27, 28, 41]. Делегированный proof-of-stake [9, 61] имеет узлы голосуют за свою долю при выборе представителей по обычному протоколу византийского соглашения, например PBFT [31]. Algorand [51] использует проверяемые случайные функции для псевдослучайного выбора репрезентативных узлов с вероятностью, пропорциональной в криптовалютные холдинги. Белоснежка [39] официально оформляет свойства безопасности, необходимые для доказательства доли, включая «сонные» узлы, которые продолжают работать иофлайн. Хотя большинство схем proof-of-stake невозможно перебрать с помощью дорогостоящих вычислений, стоимость приобретения доли или взятка майнерам по-прежнему связана со стоимостью базовой криптовалюты и находится вне контроля эмитента активов. Даже при отсутствии злонамеренных майнеров ошибки также могут вызывать blockchain реорганизация [26, 73]. Следовательно, в отличие от SCP, эмитенты не имеют возможности гарантировать окончательность blockchain до погашение внутрисетевых tokens для реального банковского перевода или снятие наличных.

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 консенсусный протокол

Протокол консенсуса Stellar (SCP) основан на кворуме. Протокол Византийского соглашения с открытым членством. Кворумы возникают в результате объединения решений по локальной конфигурации отдельных узлов. Однако узлы распознают только кворумам, к которым они принадлежат сами, и только после изучение локальных конфигураций всех остальных членов кворума. Одним из преимуществ этого подхода является то, что SCP по своей сути допускает неоднородные представления о том, какие узлы существуют. Следовательно, узлы могут присоединяться и выходить в одностороннем порядке без необходимости Протокол «просмотра изменений» для координации членства. 3.1 Федеративное византийское соглашение Традиционная проблема византийского соглашения состоит из замкнутая система из N узлов, часть из которых неисправна и может вести себя произвольно. Узлы получают входные значения и обмениваются сообщения для выбора выходного значения среди входных. Протокол византийского соглашения безопасен, когда никакие два узла с хорошим поведением не выдают разные решения и уникальный решение было действительным вкладом (для некоторого определения действительного согласованногоSOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. заранее). Протокол активен, если он гарантирует, что каждый честный узел в конечном итоге выдает решение. Обычно протоколы предполагают N = 3f + 1 для некоторого целого числа. f > 0, то гарантируйте безопасность и некоторую форму жизнеспособности, поэтому пока не более f узлов неисправны. На каком-то этапе этих протоколы, узлы голосуют за предложенные значения и предложение получение 2f + 1 голосов, называемое кворумом голосов, становится решение. При N = 3f + 1 узлах любые два кворума размер 2f+1 перекрывается не менее чем в f+1 узлах; даже если f из этих перекрывающиеся узлы неисправны, два кворума имеют как минимум общий доступ один исправный узел, предотвращающий противоречивые решения. Однако этот подход работает только в том случае, если все узлы согласны с что представляет собой кворум, что невозможно в SCP, где два узла могут даже не знать о существовании друг друга. При использовании SCP каждый узел v в одностороннем порядке объявляет наборы узлов, называемые его срезами кворума, такие, что (a) v считает, что если все члены среза договариваются о состоянии системы, затем они правы, и (b) v считает, что хотя бы один из его срезов будет доступен для своевременного предоставления информации о состояние системы. Назовем полученную систему, состоящую узлов и их срезов, Федеративное Византийское соглашение (ФБА). Как мы увидим далее, возникает система кворума. из срезов узлов. Неформально, срезы узла FBA выражают, с кем узел требует согласия. Например, для узла может потребоваться соглашение с 4 конкретными организациями, в каждой из которых имеется по 3 узла; чтобы учесть время простоя, он может установить свои срезы как все наборы состоящий из 2 узлов от каждой организации. Если это «требует отношение «согласие с» транзитивно связывает любые два узла, мы получаем глобальное соглашение. В противном случае мы можем получить расхождение, но только между организациями, ни одна из которых не требует соглашение с другим. Учитывая топологию сегодняшней финансовой системы, мы предполагаем, что широкая конвергенция будет продолжать создавать единую историю реестра, которую люди называют «сеть Stellar», как мы говорим об Интернете. Кворумы возникают из срезов следующим образом. Каждый узел определяет его кворум распределяется в каждом отправляемом им сообщении. Пусть S будет набор узлов, из которых исходил набор сообщений. А узел считает, что набор сообщений достиг кворума порог, когда каждый член S имеет срез, включенный в S. По построению такой набор S, если он единогласен, удовлетворяет условию требования соглашения каждого из его участников. Неисправный узел может рекламировать фрагменты, созданные для изменения того, что узлы с хорошим поведением учитывают кворумы. Для анализа протокола мы определяем кворум в FBA как непустой набор S узлов, охватывающий хотя бы один срез кворума каждый исправный член. Эта абстракция обоснована, как и любое множество сообщений, якобы представляющих единогласный кворум на самом деле так и есть (даже если оно содержит сообщения от неисправных узлов), и это точно, когда S содержит только узлы с хорошим поведением. В в этом разделе мы также предполагаем, что срезы узлов не изменяются. Тем не менее, наши результаты переносятся на случай меняющегося среза. потому что система, в которой меняются слайсы, не менее безопасна, чем система с фиксированными срезами, в которой срезы узла состоят из всех срезы, которые он когда-либо использует в случае меняющихся срезов (см. теорему 13 в [68]). Как поясняется в разделе 4, жизнеспособность зависит от хорошо работающие узлы со временем удаляют ненадежные узлы из своих кусочков. Поскольку разные узлы имеют разные требования к соглашению, FBA исключает глобальное определение безопасности. Мы говорим исправные узлы v1 и v2 переплетаются, когда каждый кворум v1 пересекает каждый кворум v2 хотя бы в одном исправный узел. Протокол FBA может гарантировать соглашение только между переплетенными узлами; раз SCP так делает, то это его вина допуск по безопасности оптимален. Гипотеза Интернета, лежащий в основе дизайна Stellar, утверждает, что узлы заботятся о людях. о будет переплетаться. Мы говорим, что набор узлов I неповреждён, если I представляет собой равномерно исправный кворум, в котором каждые два члена I переплетены, даже если каждый узел вне I неисправен. Интуитивно, тогда я должен оставаться невосприимчивым к действиям неповрежденных узлы. SCP гарантирует как неблокирующую работоспособность [93], так и безопасность неповрежденных наборов, хотя сами узлы не нуждаются в знать (а может и не знать), какие наборы целы. Более того, объединение двух пересекающихся целых множеств есть целый комплект. Следовательно, неповрежденные множества определяют разбиение узлы с хорошим поведением, где каждый раздел безопасен и работоспособен (при некоторых условиях), но разные разделы могут выводить разные решения. 3.1.1 Соображения безопасности и жизнеспособности в FBA За редким исключением [64], большинство протоколов закрытых византийских соглашений настроены на точку равновесия, в которой безопасность и живучесть имеют одинаковую отказоустойчивость. В ФБА, это означает конфигурации, в которых, независимо от сбоев, все переплетенные множества также целы. Учитывая, что ФБА определяет кворумы децентрализованно, маловероятно, что индивидуальный выбор срезов приведет к такому равновесию. Более того, на по крайней мере, в Stellar равновесие нежелательно: последствия сбоя безопасности (а именно двойного расходования цифровых денег) гораздо хуже, чем при сбое работоспособности (а именно задержки в платежах, которые в любом случае произошли за несколько дней до Stellar). Люди поэтому следует и следует выбирать большие фрагменты кворума, такие, чтобы их узлы, скорее всего, останутся переплетенными, чем нетронутыми. Чем больше чаша весов склоняется, тем легче оправиться от типичные сбои живучести в системе ФБА, чем в традиционной закрытой. В закрытых системах все сообщения должны быть интерпретируются относительно одного и того же набора кворумов. Следовательно, добавление и удаление узлов для восстановления после сбоя требует достижение консенсуса по вопросу реконфигурации, что становится затруднительным, если консенсуса больше нет. В отличие от ФБА, любой узел может в одностороннем порядке корректировать свои доли кворума в любой момент. время. В ответ на отключение системно важного объекта организации, администраторы узлов могут настраивать свои фрагменты в соответствии с обойти проблему, что-то вроде координации ответов к катастрофам BGP [63] (хотя и без ограничений маршрутизация по физическим сетевым каналам).

Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада 3.1.2 Каскадная теорема SCP следует шаблону базовой круглой модели [42]; узлы проходят через серию пронумерованных бюллетеней, каждый пытаясь выполнить три задачи: (1) определить «безопасное» значение, не противоречащее никакому решению предыдущего голосования (часто называемое подготовка бюллетеня), (2) согласовать безопасное значение и (3) обнаружить, что соглашение было успешным. Тем не менее, открытый ФБА членство блокирует несколько распространенных методов, что делает его невозможно «портировать» традиционные закрытые протоколы на ФБА модель, просто изменив определение кворума. Одним из методов, используемых во многих протоколах, является ротация. через ведущие узлы в циклическом порядке после таймаутов. В закрытой системе циклический выбор лидера обеспечивает что в конечном итоге единственный честный лидер в конечном итоге согласовывает соглашение по единой ценности. К сожалению, круговой не может работать в системе FBA с неизвестным членством. Другой распространенный метод, который не работает с FBA, заключается в предположении, что определенный кворум может убедить все узлы. Например, если все признают любые 2f + 1 узлов кворумом, то 2f + 1 подписей достаточно, чтобы подтвердить состояние протокола для всех узлов. Аналогично, если узел получает кворум идентичных сообщений посредством надежной широковещательной рассылки [24] узел может предположить, что все исправные узлы также увидят кворум. В FBA, напротив, кворум ничего не значит для узлов вне кворума. Наконец, нефедеративные системы часто используют «обратный» подход. рассуждения о безопасности: если f+1 узлов неисправны, то вся безопасность гарантии теряются. Следовательно, если узел v слышит f + 1 узел, все констатировать некоторый факт F, v может предположить, что по крайней мере один из них говорит истина (и, следовательно, F истинно) без потери безопасности. такой рассуждения терпят неудачу в FBA, потому что безопасность - это свойство пар узлов, поэтому узел, потерявший безопасность для некоторых узлов, может всегда теряйте безопасность из-за большего количества узлов, предполагая неверные факты. Однако FBA может рассуждать наоборот о жизнеспособности. Определите набор v-блокировок как набор узлов, пересекающих каждую срез v. Если v-блокирующее множество B единогласно ошибочно, B может лишить узел v кворума и лишить его жизнеспособности. Следовательно, если B единогласно констатирует факт F, тогда v знает, что либо F является true или v не поврежден. Тем не менее, Ви все еще нужно увидеть полную картину. кворум знать, что переплетенные узлы не будут противоречить F, что приводит к заключительному раунду общения в SCP и другие протоколы FBA [47], которые не требуются в аналогичных протоколы закрытого членства. В результате мы имеем три возможных уровня уверенности в потенциальных фактах: неопределенный, безопасный для неповрежденных узлов (который мы будем общепринятые факты), и можно с уверенностью предположить среди переплетенных узлы (которые мы будем называть подтвержденными фактами). Узел v может эффективно определить, является ли набор B блокирующим, проверив, пересекает ли B все его срезы. Интересно, что если узлы всегда объявляют утверждения, которые они Accept и полный кворум принимает утверждение, это запускает каскадный процесс, посредством которого утверждения распространяются по всему целые комплекты. Мы называем ключевой факт, лежащий в основе этого распространения каскадная теорема, которая утверждает следующее: если I — неповреждённое множество, Q — кворум любого члена I, а S — любой надмножество Q, то либо S ⊇I, либо существует элемент v ∈I такой, что v < S и I ∩S является v-блокирующим. Интуитивно, было ли это это не так, дополнение S будет содержать кворум который пересекает I, но не Q, что нарушает пересечение кворума. Обратите внимание: если мы начнем с S = Q и неоднократно расширим S до включаем все узлы, которые он блокирует, мы получаем каскадный эффект до тех пор, пока: в конечном итоге S охватывает все I. 3.2 Описание протокола SCP — это частично синхронный протокол консенсуса [42], состоящий из серии попыток достижения консенсуса, называемых бюллетени. В бюллетенях используются тайм-ауты увеличивающейся продолжительности. А протокол синхронизации голосования гарантирует, что узлы остаются включенными один и тот же бюллетень в течение увеличивающихся периодов времени, пока бюллетени эффективно синхронны. Прекращение действия не гарантировано пока бюллетени не будут синхронными, но два синхронных голосования в котором неисправные члены срезов узлов с хорошим поведением «Не вмешиваться» достаточно для завершения SCP. Протокол голосования определяет действия, предпринимаемые в ходе каждого голосование. Голосование начинается с этапа подготовки, на котором узлы попытаться определить предлагаемую ценность, которая не противоречит любое предыдущее решение. Затем, на этапе фиксации, узлы пытаются принять решение по подготовленному значению. При голосовании используется подпротокол соглашения, называемый федеративным голосованием, т.е.n какие узлы голосуют за абстрактные утверждения это может в конечном итоге подтвердиться или застрять. Некоторые утверждения могут быть названы противоречивыми, а безопасность гарантия федеративного голосования заключается в том, что никакие два члена переплетенное множество подтверждает противоречивые утверждения. Подтверждение заявления не гарантируется, за исключением неповрежденного набор, все члены которого голосуют одинаково. Однако, если член неповрежденного набора подтверждает утверждение, федеративно голосование гарантирует, что все члены целого множества в конечном итоге подтвердят это утверждение. Поэтому предпринимаются необратимые шаги в ответ на подтверждающие высказывания сохраняет живость в течение неповрежденные узлы. Узлы первоначально предлагают значения, полученные в результате номинации. протокол, который увеличивает шансы всех членов неповрежденного множество, предлагающее одно и то же значение, и оно в конечном итоге сходится (хотя и без возможности определить полную сходимость). Выдвижение сочетает в себе федеративное голосование и выбор лидера. Поскольку в FBA циклическая система невозможна, для номинации используются вероятностная схема выбора лидера. Каскадная теорема играет решающую роль как при голосовании, так и при голосовании. синхронизации и во избежание заблокированных состояний, из которых расторжение уже невозможно. 3.2.1 Голосование Узлы SCP проходят серию пронумерованных бюллетеней, используя федеративное голосование для согласования утверждений, относительно которых значения определяются или не определяются в ходе голосования. Если асинхронность или неправильное поведение препятствует принятию решения в бюллетене n, тайм-аут узлов и повторите попытку в бюллетене n + 1.

SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Напомним, федеративное голосование может не прекратиться. Следовательно, некоторые заявления по поводу избирательных бюллетеней могут навсегда застрять в неопределенное состояние, в котором узлы никогда не могут определить, являются ли они все еще выполняются или застряли. Поскольку узлы не могут исключить возможность неопределенных утверждений, которые впоследствии окажутся истинными, они никогда не должны пытаться проводить федеративное голосование по новым заявлениям противоречащие неопределенным. В каждом бюллетене n узлы используют федеративное голосование по двум типам. заявления: • подготовить ⟨n,x⟩– утверждает, что никакое значение, кроме x было или когда-либо будет решено в любом голосовании ≤n. • commit ⟨n,x⟩– утверждает, что x определяется в бюллетене n. Важно отметить, что подготовка ⟨n,x⟩ противоречит коммиту. ⟨n′,x ′⟩, когда n ≥n′ и x , x ′. Узел начинает голосование n, пытаясь провести федеративное голосование на заявление подготовить ⟨n,x⟩. Если какой-либо предыдущий оператор подготовки был успешно подтвержден посредством федеративного голосования, узел выбирает x из подтвержденной подготовки высшего бюллетеня. В противном случае узел устанавливает x в выходной сигнал Протокол номинации описан в следующем подразделе. Тогда и только тогда, когда узел успешно подтверждает подготовку ⟨n,x⟩ в бюллетене n он пытается провести федеративное голосование по фиксации ⟨n,x⟩. Если если это удалось, это означает, что SCP принял решение, поэтому узел выводит значение из подтвержденного оператора фиксации. Рассмотрим переплетенное множество S. Поскольку не более одного значения могут быть подтверждены подготовленными членами S в данном бюллетене, никакие два разных значения не могут быть подтверждены совершенными члены S в данном бюллетене. Более того, если совершить ⟨n,x⟩ подтверждено, то подготовка ⟨n,x⟩ тоже подтверждена; с тех пор подготовка ⟨n,x⟩ противоречит любому предыдущему коммиту для другого значения, по соглашению гарантирует федеративное голосование мы понимаем, что никакое другое значение не может быть принято ранее голосование членов S. Индукцией по номерам бюллетеней мы поэтому убедитесь, что SCP безопасен. Для живости рассмотрим неповрежденный набор I и достаточно длинный синхронное голосование n. Если в срезах появляются неисправные узлы хорошо себя ведущих узлов не вмешиваются, то голосованием n + 1 все члены I подтвердили один и тот же набор P операторов подготовки. Если P = ∅ и бюллетень n был достаточно длинным, протокол номинации сойдётся на некотором значении x. В противном случае, пусть x будет значением из подготовки с наибольшим числом голосов в P. В любом случае, я буду равномерно пытаться объединить голосование по подготовке ⟨n + 1,x⟩ в следующем туре голосования. Следовательно, если n + 1 также синхронно, неизбежно следует решение по x. 3.2.2 Номинация Выдвижение предполагает федеративное голосование по заявлениям: • Номинировать x – утверждает, что x является действительным кандидатом на решение. Узлы могут голосовать за назначение нескольких значений — разных высказывания номинантов не противоречат друг другу. Однако однажды узел подтверждает любое заявление о назначении, он прекращает голосование за номинировать новые ценности. Федеративное голосование по-прежнему позволяет узлу подтвердить новые заявления о выдвижении кандидатов, за которые он не голосовал, которые голосуй или принимай из кворума принять из кворума а действителен принять от блокирующий набор незафиксированный проголосовал за принял подтвердил проголосовал за Рисунок 1. Этапы федеративного голосования позволяет членам неповрежденного набора подтверждать друг друга номинированные ценности, при этом отказываясь от новых голосов. (Развивающийся) результат номинации — это детерминированная комбинация всех значений в подтвержденных номинирующих заявлениях. Если x представляет собой набор транзакций, узлы могут объединяться наборов, самый большой набор или набор с наибольшим hash, поэтому пока все узлы делают то же самое. Поскольку узлы не содержат новых голосов после подтверждения одного заявления о выдвижении кандидатуры, набор подтвержденные утверждения могут содержать только конечное число значений. Тот факт, что подтвержденные заявления надежно распространялись через неповрежденные множества означают, что неповрежденные узлы в конечном итоге сходятся на тот же набор номинированных ценностей и, следовательно, результат номинации, хотя и в неизвестном месте, в произвольном конце протокола. Узлы используют федеративный выбор лидеров, чтобы уменьшить количество различных значений в номинирующих утверждениях. Только лидер, который еще не проголосовал за выдвижение кандидатуры, может ввести новый x. Другие узлы ждут вестей от лидеров и просто копировать (действительные) голоса их лидеров. Чтобы приспособиться к неудаче, набор лидеров продолжает расти по мере того, как происходят тайм-ауты, хотя на практике только несколько узлов вводят новые значения x. 3.2.3 Федеративное голосование Федеративное голосование использует трехэтапный протокол, показанный на рис. Рисунок 1. Узлы сначала пытаются договориться об абстрактных утверждениях голосование, затем принятие и, наконец, подтверждение заявлений. Узел v может голосовать за любое допустимое утверждение a, которое не соответствует противоречить другомувыдающиеся голоса и принятые заявления. Это делается путем трансляции подписанного сообщения о голосовании. Затем v принимает a, если a согласуется с другими принятыми утверждениями и либо (случай 1) v является членом кворума, в котором каждый узел либо голосует за a, либо принимает a, либо (случай 2), даже если v не голосовал за a, набор v-blocking принимает a. В случае 2 v может ранее отдали голоса, противоречащие а, которые теперь было отменено. v разрешено забыть об отклоненных голосах и притвориться, что никогда их не применял, потому что если v цел, он знает отмененные голоса не могут обеспечить кворум в случае 1. v сообщает, что принимает a, а затем подтверждает, когда оно находится в кворум, который единогласно принимает а. На рисунке 2 показано эффект v-блокирующих множеств и каскадная теорема во время федеративное голосование. Два переплетенных узла не могут подтвердить противоречивые утверждения, поскольку два необходимых кворума должны будут иметь общийБыстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада 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)$.

Голосуйте Х

Голосуйте за (а) 3 4 2 1 5 7 6 Голосовать Х Голосовать Х Голосовать Х Голосовать Да Голосовать Х Голосовать Да Голосовать Да (б) 3 4 2 1 5 7 6 Принять Х Голосовать Х Принять Х Голосовать Да Принять Х Голосовать Да Голосовать Да (с) 3 4 2 1 5 7 6 Принять Х Принять Х Принять Х Голосовать Да Принять Х Принять Х Голосовать Да (г) 3 4 2 1 5 7 6 Принять Х Голосовать Х Принять Х Принять Х Принять Х Принять Х Принять Х (е) Рисунок 2. Каскадный эффект при федеративном голосовании. Каждый узел имеет один срез кворума, обозначенный стрелками, указывающими на членов среза. (a) Вводятся противоречивые утверждения X и Y. (b) Узлы голосуют за действительные утверждения. (c) Узел 1 принимает X после наличия кворума {1, 2, 3, 4} единогласно голосуют за X. (d) Все узлы 1, 2, 3 и 4 принимают X; набор {1} блокирует 5, поэтому узел 5 принимает X, отменяя его предыдущий голос за Y. (e) Набор {5} блокирует 6 и 7, поэтому оба 6 и 7 принимают X. исправный узел, который не смог принять противоречивые утверждения. Подтверждение заявления не гарантируется: в В случае разделения голосов оба заявления могут быть навсегда застрял в ожидании кворума на этапе голосования. Однако, если узел в неповрежденном множестве подтверждаю утверждение, каскад теорему и принять случай 2, гарантируя, что все I в конечном итоге подтвердите это утверждение. 3.2.4 Синхронизация бюллетеней Если узлы не могут подтвердить оператор фиксации для текущем голосовании, они сдаются после тайм-аута. Тайм-аут получает дольше с каждым бюллетенем, чтобы приспособиться к произвольным границам о задержке сети. Однако одних таймаутов недостаточно для синхронизации бюллетеней узлов, которые не запустились одновременно или рассинхронизировался по другим причинам. Чтобы добиться синхронизации, узлы запускают таймер только тогда, когда они являются частью кворум то есть весь на текущем (или более позднем) голосовании. Это замедляет узлы, которые запустились раньше, и гарантирует, что никакие член интактной группы остается слишком далеко впереди группы. Более того, если узел v когда-либо заметит установку v-блокировки позднее, бюллетень, он немедленно переходит к низшему бюллетеню, так что это это больше не так, независимо от каких-либо таймеров. Каскад Тогда теорема гарантирует, что все отстающие догонят. Результат заключается в том, что избирательные бюллетени примерно синхронизированы на всем протяжении устанавливается, как только система становится синхронной. 3.2.5 Выбор федеративного лидера Выбор лидера позволяет каждому узлу выбирать лидеров в таком способ, которым узлы обычно выбирают только один или небольшое количество лидеров. Чтобы справиться с неудачей лидера, выбор лидера проходит через раунды. Если лидеры текущего тура кажутся не выполняющими своих обязанностей, то после некоторого узлы определенного периода таймаута переходят к следующему раунду, чтобы расширить круг лидеров, за которыми они следуют. В каждом раунде используются две уникальные криптографические функции hash, H0 и H1, которые выводят целые числа в диапазоне [0,hmax). Например, Stellar использует Hi(m) = SHA256(i∥b∥r ∥m), где b — общий экземпляр SCP (номер блока или реестра), r — номер раунда выбора лидера, hmax = 2256. В пределах за раунд мы определяем приоритет узла v как: приоритет(v) = H1(v) Для каждого узла будет выбран один подставной человек в качестве лидера. узел с наивысшим приоритетом (v). Этот подход работает хорошо с почти идентичными фрагментами кворума, но не правильно отразить важность узлов в несбалансированных конфигурациях. Например, если Европа и Китай вносят по 3 узлов в каждый кворум, но в Китае используется 1000 узлов, а в Европе — 4, тогда у Китая будет узел с наивысшим приоритетом 99,6% того времени. Поэтому мы вводим понятие веса среза, где вес(u,v) ∈[0, 1] — это доля срезов кворума узла u содержащий узел v. Когда узел u выбирает нового лидера, он учитывает только соседей, определенных следующим образом: соседи (и) = { v | H0(v) < hmax · вес(u,v) } Затем узел нодеу начинается с пустого набора лидеров, и в каждом round добавляет к нему узел v из соседей(u) с наивысшим приоритет(v). Если набор соседей пуст в каком-либо раунде, вместо этого u добавляет узел с наименьшим значением H0(v)/weight(u,v).

Formal verification of SCP

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

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

Формальная проверка SCP

Чтобы исключить ошибки проектирования, мы официально подтвердили безопасность SCP. и свойства живучести (см. [65]). В частности, мы проверили что переплетенные узлы никогда не расходятся во мнениях и что в условиях, обсуждаемых ниже, в конечном итоге решение принимает каждый член целого множества. Интересно, что проверка показала, что условия, при которых SCP гарантирует жизнеспособность, являются тонкими, и сильнее, чем первоначально предполагалось [68]: как обсуждается ниже, вредоносные узлы, которые манипулируют временем без иного при отклонении от протокола может потребоваться выселение вручную из срезов кворума.

SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Чтобы гарантировать, что свойства будут сохранены во всех возможных Конфигурации и исполнения ФБА мы рассматриваем произвольные. количество узлов с произвольными локальными конфигурациями. Это включает сценарии с непересекающимися неповрежденными множествами, а также потенциально бесконечно длинные выполнения. Недостаток в том, что мы сталкиваются со сложной проблемой проверки параметризованного система с бесконечными состояниями. Чтобы обеспечить удобство проверки, мы смоделировали SCP в логике первого порядка (FOL), используя Ivy [69] и методологию [82]. Процесс проверки состоит из ручного создания индуктивных предположений, которые затем автоматически проверяются Айви. FOL-модель SCP абстрагируется от некоторых аспектов Системы FBA, с которыми сложно работать на ВОЛС (например, каскадная теорема принимается за аксиому), поэтому проверяем справедливость обоснованность абстракции с использованием Isabelle/HOL [75]. После выражения проблемы проверки в FOL мы проверяем безопасность, предоставляя индуктивный инвариант. Индуктивный инвариант состоит из дюжины однострочных гипотез примерно 150 строк спецификации протокола. Затем мы указываем свойства жизнеспособности SCP в линейной временной логике Айви и используем метод жизнеспособность для снижения безопасности [80, 81] для снижения живучести задача проверки к задаче нахождения индуктивного инвариант. Хотя безопасность SCP относительно легко обеспечить доказать, что аргумент жизнеспособности SCP гораздо более сложен и состоит примерно из 150 однострочных инвариантов. Доказательство живучести потребовало точной формализации предположения, при которых SCP обеспечивает прекращение действия. Сначала мы думали, что нетронутый набор я всегда закрою, если все участники удалили неисправные узлы из своих срезов [68]. Однако этого оказалось недостаточно: воспитанный (но не исправен) узел в кворуме члена I can, под влияние неисправных узлов, предотвратить завершение, выполнив кворума непосредственно перед окончанием голосования, тем самым вызывая члены I выберут другие значения x в следующем туре голосования. Поэтому мы должны дополнительно предположить, что неформально каждый узел в кворуме члена I в конечном итоге либо становится своевременным или вообще не отправляет сообщения в течение достаточного периода времени. На практике это означает, что члены I могут необходимо корректировать свои срезы до тех пор, пока условие не выполнится. Это проблема не свойственна системам FBA: Losa et al. [47] присутствует протокол, жизнеспособность которого зависит от строго более слабого предположения о возможной синхронности и возможном выборе лидера без необходимости удалять неисправные узлы из срезов.

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.

Платежная сеть

В этом разделе описывается платежная сеть Stellar, реализованная как реплицированный конечный автомат PH_0000 поверх SCP. 5.1 Модель бухгалтерской книги Регистр Stellar построен на абстракции счета (в в отличие от более ориентированного на монеты вывода неизрасходованных транзакций или UTXO модель Bitcoin). Содержимое реестра состоит из набор записей бухгалтерской книги четырех различных типов: счета, линии доверия, предложения и данные учетной записи. Счета — это принципалы, которые владеют и выпускают активы. Каждый учетная запись называется по открытому ключу. По умолчанию соответствующий закрытый ключ может подписывать транзакции для учетной записи. Однако учетные записи можно перенастроить, чтобы добавить других подписывающих лиц и деавторизовать ключ, который называет учетную запись, с помощью опция «multisig», требующая нескольких подписывающих лиц. Каждый аккаунт также содержит: порядковый номер (включенный в транзакции для предотвращения повтора), некоторые флаги и баланс в «родном» предварительно добытая криптовалюта под названием XLM, предназначенная для смягчения последствий некоторые атаки типа «отказ в обслуживании» и способствуют созданию рынка как нейтральная валюта. Линии доверия отслеживают право собственности на выпущенные активы, которые именуется парой, состоящей из эмиссионного счета и короткого код актива (например, «USD» или «EUR»). Каждая линия доверия определяет счет, актив, баланс счета в этом активе, предел, выше которого баланс не может подняться, и некоторые флаги. Учетная запись должна дать явное согласие на хранение актива путем создание линии доверия, предотвращающей обременение спамеров аккаунты с нежелательными активами. Правила «Знай своего клиента» (KYC) требуют, чтобы многие финансовые учреждения знали, чьи депозиты они держат. например, проверив удостоверение личности с фотографией. Для соблюдения требований эмитенты могут установить дополнительный флаг auth_reqired в их учетных записях, ограничивающий право собственности на активы, которые они выдают, авторизованным учетным записям. Для предоставления такого разрешения эмитент устанавливает авторизованный пометить на линиях доверия клиентов. Предложения соответствуют готовности аккаунта торговать вверх. на определенное количество определенного актива в обмен на другой при данном цена в книге заказов; они автоматически сопоставляются и заполняется при пересечении цен покупки/продажи. Наконец, данные учетной записи состоят из троек учетной записи, ключа и значения, что позволяет владельцам учетных записей публиковать небольшие значения метаданных. Чтобы предотвратить спам в реестре, существует минимальный баланс XLM. называется резервом. Резерв счета увеличивается с каждым связанная запись в бухгалтерской книге и уменьшается, когда запись в бухгалтерской книге исчезает (например, когда ордер исполнен или отменен, или когда линия доверия удалена). На данный момент резерв увеличивается на 0,5 XLM. (∼0,03 доллара США) за запись в бухгалтерской книге. Независимо от резерва, это можно вернуть всю стоимость учетной записи, удалив это с помощью операции AccountMerge. Заголовок реестра, показанный на рисунке 3, хранит глобальные атрибуты: номер бухгалтерской книги, такие параметры, как резервный баланс на запись в бухгалтерской книге, hash предыдущего заголовка бухгалтерской книги (фактически несколько hashes, образующих список пропуска), выходные данные SCP, включая hash новых транзакций, примененных в этом реестре, hash результаты этих транзакций (например, успех или неудача для каждый), а также снимок hash всех записей бухгалтерской книги. Поскольку снимок hash включает в себя все содержимое бухгалтерской книги, validator не требуется сохранять историю для проверки транзакций. Однако для масштабирования до сотен миллионов ожидаемых счетов, мы не можем повторно hash все таблицы записей главной книги на каждом бухгалтерскую книгу закрыть. Кроме того, передавать реестр непрактично.Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада регистр № = 4 H(предыдущий hdr) Выход SCP H∗(результаты) H∗(снимок) ... заголовок регистр № = 5 H(предыдущий hdr) Выход SCP H∗(результаты) H∗(снимок) ... заголовок . . . Рисунок 3. Содержимое реестра. H — это SHA-256, а H * представляет собой иерархическое или рекурсивное применение вывода H. SCP. также зависит от предыдущего заголовка hash. Создать аккаунт Создайте и профинансируйте новую запись в книге счетов Слияние учетных записей Удалить запись в книге учета счетов Установить параметры Изменение флагов учетной записи и подписантов Оплата Выплатите определенное количество актива в пользу dest. акт. ПутьОплата Как оплата, но оплата в другом активе (вверх). ограничить); укажите до 5 промежуточных активов Управление предложением Создать/удалить/изменить запись в книге предложений, -Пассивное предложение с пассивным вариантом, обеспечивающим нулевой спред Управление данными Создать/удалить/изменить аккаунт. запись в книге данных ИзменениеДоверие Создать/удалить/изменить линию доверия Разрешить доверие Установить или снять флаг авторизации на линии доверия BumpSequence Увеличение сек. номер на счету Рисунок 4. Основные операции реестра такого размера каждый раз, когда узел отключался от сети слишком долго. Таким образом, снимок hash предназначен для оптимизации как hashing, так и согласования состояний. В частности, моментальный снимок стратифицирует записи реестра по времени. последней модификации в наборе контейнеров экспоненциального размера называются ведрами. Совокупность ведер называется ведром. список и имеет некоторое сходство с деревьями слияния с логарифмической структурой. (LSM-деревья) [77]. Список желаний не читается во время обработки транзакции (см. раздел 5.4). Следовательно, определенный дизайн аспекты LSM-деревьев можно ослабить. В частности, случайный доступ по ключу не требуется, а сегменты доступны только для чтения последовательно в рамках слияния уровней. Хеширование ведра список создается путем hash обработки каждого сегмента по мере его объединения и расчета нового совокупного значения hash сегмента hashes (небольшого, фиксированный справочный индекс hashes) при каждом закрытии бухгалтерской книги. Для согласования списка желаний после отключения требуется загрузка различаются только ведра. 5.2 Модель транзакции Транзакция состоит из исходного счета, критериев действительности, памятка и список одной или нескольких операций. На рис. 4 перечислены доступные операции. Каждая операция имеет исходный аккаунт, который по умолчанию соответствует значению всей транзакции. Транзакция должна быть подписан ключами, соответствующими каждой исходной учетной записи в операция. Учетные записи с мультиподписью могут потребовать более высокого уровня подписи. вес для некоторых операций (например, SetOptions) и ниже для других (например, AllowTrust). Транзакции являются атомарными: если какая-либо операция завершается неудачно, ни одна из их казнят. Это упрощает многосторонние сделки. Предположим, эмитент создает актив для представления земельных документов, а пользователь А хочет обменять небольшой земельный участок плюс 10 000 долларов на больший земельный участок, принадлежащий Б. Оба пользователя могут подписать одна сделка, содержащая три операции: две земельные платежи и платеж в один доллар. Основным критерием действительности транзакции является ее порядковый номер, который должен быть на единицу больше, чем номер транзакции. запись в книге учета исходных счетов. Выполнение действительной транзакции (успешно или нет) увеличивает порядковый номер, предотвращая повтор. Начальные порядковые номера содержат реестр номер в старших битах, чтобы предотвратить повтор даже после удаления и повторное создание учетной записи. Другим критерием достоверности является необязательное ограничение на то, когда транзакция может быть выполнена. Возвращение к земле и доллару своп выше, если A подписывает транзакцию раньше B, A не может хочу, чтобы B участвовал в транзакции в течение года, прежде чем отправить ее это, и поэтому может установить ограничение по времени, делающее транзакцию недействительной через несколько дней. Учетные записи с мультиподписью также могут быть настроены. чтобы придать вес подписи обнаружению прообраза hash, что в сочетании с ограничениями по времени позволяет осуществлять атомарную кроссчейн-торговлю [1]. С исходного счета транзакции взимается небольшая комиссия в XLM. 10−5 XLM, если нет перегрузок. В условиях заторов, Стоимость операций устанавливается на голландском аукционе. Валидаторы не компенсируется комиссией, поскольку validators аналогичны на Bitcoin полные узлы, а не майнеры. Вместо того, чтобы уничтожить XLM, сборы перерабатываются и распределяются пропорционально голосованием существующие держатели XLM, которые, оглядываясь назад, могут или могут не стоили такой сложности. 5.3 Консенсусные ценности Для каждого реестра Stellar использует SCP для согласования структуры данных. с тремя полями: набор транзакций hash (включая hash предыдущего заголовка книги), время закрытия,д обновления. Если подтверждено назначение нескольких значений, Stellar принимает набор транзакций с наибольшим количеством операций (разрыв связей по общей сумме комиссий, затем набор транзакций hash), объединение всех обновления и максимальное время закрытия. Близкое время только действительно, если это происходит между временем закрытия последнего реестра и присутствует, поэтому узлы не указывают недопустимое время. Обновления настраивают глобальные параметры, такие как резервный баланс, минимальная комиссия за операцию и версия протокола. Когда При объединении во время номинации более высокие сборы и номера версий протокола заменяют более низкие. Обновления влияют на управление через пространство федеративного голосования [34], ни эгалитарный и централизованный. Каждый validator настроен как либо управляющий, либо неуправляющий (по умолчанию), в зависимости от от того, хочет ли его оператор участвовать в управлении. Управляющие validators рассматривают три типа обновления: желаемый, действительный и недействительный (все, что validator не делает

SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. validator ядро горизонт ФС БД БД отправить клиент клиент другие validators Рисунок 5. Архитектура Stellar validator знаю, как реализовать). Желаемые обновления настроены на запуск в определенное время, предназначенный для координации между операторы. Управляющие узлы всегда голосуют за выдвижение желаемых обновления: принимайте, но не голосуйте за назначение действительных обновлений (т. е. соглашайтесь с блокирующим кворумом) и никогда не голосуйте за или принять недействительные обновления. Неуправляющее эхо validators любой голос, который они видят за действительное обновление, по сути делегируя решение о том, какие обновления желательны для тех, кто выбирает на руководящую роль. 5.4 Реализация На рис. 5 показана архитектура validator Stellar. Демон называемый stellar-core (~92 тыс. строк C++, не считая сторонних библиотек), реализует протокол SCP и реплицируемый конечный автомат. Создание значений для SCP требует сокращения большого количества записей реестра до небольших криптографических операций. hashes. Напротив, проверка и выполнение транзакции требует просмотра состояния учетной записи и сопоставления заказов на лучшая цена. Чтобы эффективно выполнять обе функции, звездное ядро хранит два представления реестра: внешнее представление, содержащее список сегментов, хранящееся в виде двоичных файлов, которые могут быть эффективно обновлены и постепенно измененыhash, а также внутреннее представление в базе данных SQL (PostgreSQL для производственных узлов). Stellar-core создает архив истории, доступный только для записи, содержащий каждый подтвержденный набор транзакций и снимки ведра. Архив позволяет новым узлам загружаться самостоятельно. при подключении к сети. Он также обеспечивает запись в бухгалтерской книге история — должно быть место, где можно найти сделка двухлетней давности. Поскольку история доступна только для добавления и доступ к нему нечастый, его можно хранить в дешевых местах например Amazon Glacier или любой сервис, позволяющий хранить и получить плоские файлы. Хосты-валидаторы обычно не размещают свои собственные архивы, чтобы избежать какого-либо влияния на проверку производительность из истории обслуживания. Чтобы сохранить простоту звездного ядра, оно не предназначено для использования непосредственно приложениями и предоставляет лишь очень узкий интерфейс для отправки новых транзакций. Поддержать клиентов, большинство validator используют демон под названием Horizon (~18 тыс. строки Go), который предоставляет HTTP-интерфейс для отправки и изучение транзакций. Horizon имеет доступ только для чтения к База данных SQL stellar-core, сводящая к минимуму риск горизонта дестабилизирующее звездное ядро. Такие функции, как поиск пути платежа, будут полностью реализованы в перспективе и могут быть обновлены. в одностороннем порядке без согласования с другими validators. Несколько дополнительных демонов более высокого уровня являются клиентами горизонта, дополняя экосистему. Сервер-мост облегчает интеграция Stellar с существующими системами, например, публикация уведомлений обо всех платежах, полученных на определенный счет. А сервер соответствия предоставляет финансовым учреждениям возможность обмен и утверждение информации об отправителе и получателе по выплатам, за соблюдением санкционных списков. Наконец, сервер федерации реализует удобочитаемое именование система для аккаунтов. 6 Опыт внедрения Stellar за несколько лет перерос в состояние с умеренным количество достаточно надежных операторов полного узла. Однако, конфигурации узлов были таковы, что работоспособность (хотя и не безопасность) зависела от нас, Фонда развития Stellar (СДС); если бы SDF внезапно исчез, другие операторы узлов пришлось бы вмешаться и удалить нас вручную из фрагментов кворума, чтобы сеть могла продолжить работу. Хотя мы и многие другие хотим снизить системную значимость СДС, эта цель получила все больший приоритет после исследователи [58] количественно оценили и обнародовали централизацию сети, не дифференцируя риски для безопасности и живость. Ряд операторов отреагировали активными изменениями конфигурации, в первую очередь увеличением размера своих дробление кворума в попытке ослабить важность SDF; по иронии судьбы это только увеличило риск для жизни. Ситуацию усугубили две проблемы. Во-первых, популярный сторонний инструмент мониторинга Stellar [5] систематически переоценка времени безотказной работы validator без фактической проверки это звездное ядро работало; это побуждает людей включать ненадежные узлы в своих срезах кворума. Во-вторых, ошибка в звездное ядро означало, что как только validator перейдет в следующий реестр, это не помогло должным образом остальным узлам завершить предыдущеесобственный реестр на случай потери сообщений. В результате сеть испытала 67 минут простоя и потребовала координация вручную администраторами validator для перезапуска. Хуже того, попытка перезапустить сеть привела к одновременным поспешным реконфигурациям на нескольких узлах. в коллективной неправильной конфигурации, которая позволила некоторым узлам расходятся, что требует ручного отключения этих узлов и повторная отправка сделок, принятых во время расхождения. К счастью, это расхождение было обнаружено и исправлено. быстро и не содержало конфликтующих транзакций, но риск того, что сеть не сможет воспользоваться пересечением кворума — расщепление, продолжая при этом принимать потенциально конфликтующие транзакций, просто из-за неправильной конфигурации — было сделано очень конкретен в этом инциденте. Анализ этого опыта привел к двум важным выводам. и соответствующие корректирующие действия.Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Критический, 100% 51% 51% Высокий, 67% 51% Средний, 67% 51% Низкий, 67% 51% 51% ... ... ... 51% ... 51% Рисунок 6. Иерархия качества валидатора. Узлы высочайшего качества требуется самый высокий порог 100 %, тогда как более низкие качества настроены на порог 67 %. Узлы внутри одного организации требуется простое большинство в 51%. 6.1 Сложность и хрупкость конфигурации Stellar выражает фрагменты кворума как вложенные наборы кворума, состоящие из n записей и порога k, где любой набор из k записей составляет срез кворума. Тогда каждая из n записей либо открытый ключ validator или, рекурсивно, другой набор кворума. Несмотря на гибкость и компактность, мы реализовали вложенный кворум. наборы одновременно предоставляли операторам узлов слишком большую гибкость и слишком мало указаний: было легко написать небезопасное (или даже бессмысленные) конфигурации. Критерии группировки узлы в наборы для организации подмножеств в иерархию и все пороговые значения для выбора были недостаточно ясными и способствовали сбоям в работе. Было не ясно, стоит ли рассматривать «уровень» в иерархии вложенных множеств как уровень доверия, или организация, или и то, и другое; множество конфигураций в полевых условиях смешали эти понятия, помимо указания опасных или бессмысленные пороги. Поэтому мы добавили более простой механизм настройки. который разделяет два аспекта вложенных наборов кворума: группировку узлы вместе по организациям и маркируя каждую организацию простой классификацией доверия (низкое, среднее, высокое или критично). Организации уровня и выше обязаны публиковать исторические архивы. Новая система синтезирует наборы вложенных кворумов, в которых каждая организация представлена как Установлен порог 51%, и организации сгруппированы в наборы с порогом 67% или 100% (в зависимости от качества группы). Каждая группа представляет собой отдельную запись в следующей (более качественной) группе. как показано на рисунке 6. Эта упрощенная модель уменьшает вероятность неправильной конфигурации, как с точки зрения структуры синтезированных вложенных наборов и порогов, выбранных для каждый набор. 6.2 Упреждающее обнаружение неправильной конфигурации Во-вторых, мы поняли, что обнаруживать коллективную неправильную конфигурацию, ожидая наблюдения за ее негативными последствиями, уже слишком поздно. Особенно в отношении неправильных конфигураций, которые могут расходиться. более серьезный режим отказа, чем остановка — сети необходимо чтобы иметь возможность немедленно обнаружить неправильную конфигурацию, чтобы операторы могли исправить ее до того, как действительно произойдет какое-либо расхождение. Чтобы удовлетворить эту потребность, мы встроили в программное обеспечение validator механизм, который непрерывно собирает состояние коллективной конфигурации всех узлов в транзитивном замыкании узла и обнаруживает возможность расхождения, т. е. непересекающихся кворумы — внутри этой коллективной конфигурации. 6.2.1 Проверка пересечения кворума Хотя собрать фрагменты кворума легко, найти среди них непересекающиеся кворумы — задача со-NP-сложная [62]. Однако мы приняли набор алгоритмических эвристик и правил исключения регистров предложено Лачовски [62], которое проверяет типичные экземпляры решения проблемы на несколько порядков быстрее, чем стоимость в худшем случае. Практически говоря, нынешняя сеть транзитивных замыканий среза кворума порядка 20–30. узлы и, с помощью оптимизации Лаховски, обычно проверяют за считанные секунды на одном процессоре. Если возникнет необходимость для повышения производительности мы можем распараллелить поиск. 6.2.2 Проверка рискованных конфигураций Обнаружение того, что сеть допускает непересекающиеся кворумы, является шагом в правильном направлении, но сигнализирует об опасности неприятно поздно по столь критичному вопросу. В идеале мы хотим, чтобы операторы узлов получали предупреждения, когда коллективная конфигурация сети просто приближается к опасному состоянию. Поэтому мы расширили проверку пересечения кворума чтобы обнаружить состояние, которое мы называем критичностью: когда текущий коллективная конфигурация находится на расстоянии одной неправильной конфигурации от государство, допускающее непересекающиеся кворумы. Чтобы обнаружить критичность, программа проверки неоднократно заменяет конфигурацию каждой организации смоделированной наихудшей ошибкой конфигурации, а затем повторно запускает проверку пересечения внутреннего кворума для результата. Если такая критическая неправильная конфигурация существует в одном шаге из текущего состояния, программное обеспечение выдает предупреждение и сообщает об организации, представляющей риск неправильной конфигурации. Эти изменения дают сообществу операторов два уровня. уведомлений и указаний для защиты от наихудших форм коллективной неправильной конфигурации.

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.

Оценка

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

Чтобы понять пригодность Stellar в качестве глобального платежа и торговой сети, мы оценили состояние публичной сети и проводил контролируемые эксперименты на частном экспериментальном сеть. Мы сосредоточились на следующих вопросах: • Как выглядит топология производственной сети? Сколько сообщений в среднем передается в эфир, и как SCP испытывает тайм-ауты? • Остаются ли задержки консенсуса и обновления реестра независимыми от количества учетных записей?SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. • Как на задержки влияет увеличение (а) транзакций в секунду (и, следовательно, количества транзакций в секунду) реестр) и (б) количество узлов validator? • Какова стоимость эксплуатации узла с точки зрения ЦП, память и пропускная способность сети? Платежные сети имеют низкую скорость транзакций по сравнению к другим типам распределенных систем. Ведущие blockchains, Bitcoin и Ethereum, подтверждают до 15 транзакций в секунду, менее Stellar. Более того, этим системам требуется несколько минут, чтобы час для безопасного подтверждения транзакции, поскольку доказательство работы требует ожидания нескольких блоков для майнинга. Сеть SWIFT, не относящаяся к blockchain, в пиковый день PH_0000 в среднем совершала всего 420 транзакций в секунду. Поэтому мы выбрали чтобы сравнить наши измерения с целевым показателем в 5 секунд интервал реестра, более агрессивная цель. Наши результаты показывают что задержки комфортно ниже этого предела даже при несколько нереализованных оптимизаций все еще находятся в стадии разработки. 7.1 Якоря В число наиболее торгуемых активов по объему входит валюта (например, 3 доллара США). якоря, 2 юаня), якоря Bitcoin, ценных бумаг, обеспеченных недвижимостью token [92] и валюты приложения [8]. У разных якорей разные политики. Например, один якорь в долларах США, Stronghold устанавливает auth_reqired и требует прохождения процедуры «знай своего клиента» (KYC) для каждой учетной записи, в которой хранятся их активы. Еще один, AnchorUSD, пусть кто угодно получает и торгует их доллары США (что делает буквально возможным отправить 0,50 доллара США в Мексику за 5 секунд с комиссией $0,000001). Однако AnchorUSD требует KYC и комиссий для покупки или погашения своих долларов США с помощью обычных банковских переводов. На Филиппинах, где банковские правила более мягкие в отношении входящих платежей, coin.ph поддерживает обналичивание PHP в любом банкомате [36]. Помимо вышеупомянутой безопасности token и валюты в приложении, существует ряд невалютных token от коммерческие облигации [22] и углеродные кредиты [85, 96] и более эзотерические активы, такие как token, стимулирующие совместную работу изъятие автомобиля [35]. 7.2 Публичная сеть На момент написания статьи имеется 126 активных полных узлов, 66 из которых участвовать в консенсусе, подписывая сообщения для голосования. Рисунок 7 (созданный [5]) визуализирует сеть с линией между два узла, если один из них присутствует в срезах кворума другого, и более темная синяя линия показывает двунаправленную зависимость. На центр представляет собой кластер из 17 де-факто «validator» первого уровня, управляемых SDF, SatoshiPay, LOBSTR, COINQVEST и Keybase. Четыре месяца назад, до событий Раздела 6, было 15 системообразующих узлов: 3 из казалось бы организации первого уровня и несколько случайных одиночек. график также выглядел гораздо менее регулярным. Следовательно, новый механизм конфигурации и/или более эффективные решения оператора кажутся чтобы внести вклад в более здоровую топологию сети. Без большие финансовые ресурсы (и соответствующий акционер Рисунок 7. Карта среза кворума обязательства), было бы сложно набрать 5 человек первого уровня однако организации с самого начала. Это предполагает кворум срезы играют полезную роль в начальной загрузке сети: каждый может присоединиться к цели стать важным игроком, потому что нет никаких привратников к парному соглашению. В настоящее время в реестре зарегистрировано более 3,3 миллиона учетных записей. Кончено за последние 24 часа Stellar в среднем совершало 4,5 транзакций и 15,7 операций в секунду. Анализируя последние бухгалтерские книги, большинство транзакции, кажется, имеют одну операцию, в то время как каждые несколько В реестрах мы видим транзакции, содержащие множество операций, которые похоже, исходят от маркет-мейкеров, управляющих предложениями. среднее время достижения консенсуса и обновления реестра составило 1061 мс и 46 мс соответственно. 99-й процентиль был 2252 мс и 142 мс (первое соответствует тайм-ауту в 1 секунду). в выборе лидера номинации). Обратите внимание, что производительность SCP в основном не зависит от транзакций в секунду, поскольку SCP соглашается на hash произвольного количества транзакций. Узкие места чаще возникают из-за распространения кандидата операции во время номинации, исполнения и проверки транзакции и объединение сегментов. Нам пока не нужно для распараллеливания обработки транзакций stellar-core на нескольких ядрах ЦП или дисках. Мы также оценили количество транслируемых SCP-сообщений. в производственной сети. В обычном случае с одним лидер, избранный для выдвижения ценности, мы ожидаем семь логических сообщения для трансляции: два сообщения для голосования и принятия номизаявление Nate, два сообщения для принятия и подтверждения заявление о подготовке, два сообщения для принятия и подтверждения оператор фиксации и, наконец, сообщение о внешнем виде (отправляется после записи нового реестра на диск, чтобы помочь отставшим догнать). Реализация сочетает в себе подтверждение фиксации и экспортировать сообщения в качестве оптимизации, поскольку это безопасно экспортировать значение после его фиксации. Затем мы анализируем показатели, собранные на производстве Stellar validator. Кончено в течение 68 часов было отправлено 1,3 сообщения в секунду, в среднем до 6-7 сообщений на реестр. Отметим, что общая сумма

Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада процентиль Количество таймаутов Номинация Голосование 75% 0 0 99% 1 0 Макс 4 1 Рисунок 8. Таймауты для каждого реестра более 68 часов количество сообщений, переданных validators, больше, поскольку в Помимо сообщений федеративного голосования, узлы также транслируют любые транзакции, о которых они узнают. На рис. 8 показаны тайм-ауты, с которыми сталкивается производственная система. validator в течение 68 часов. Тайм-ауты для выдвижения мера (не)эффективности функции выбора лидера, в то время как тайм-ауты голосования сильно зависят от сети и потенциальные задержки сообщений. Таймауты совпадают с количеством отправленных сообщений: шесть сообщений в в лучшем случае и не менее семи сообщений, если потребуется дополнительный раунд выдвижения. 7.3 Контролируемые эксперименты Мы проводили контролируемые эксперименты в контейнерах, упакованных на Инстансы Amazon EC2 c5d.9xlarge с 72 ГиБ ОЗУ, 900 ГБ твердотельного накопителя NVMe и 36 виртуальных ЦП. Каждый экземпляр находился в том же регионе EC2 и имел фиксированную пропускную способность 10 Гбит/с. В качестве хранилища мы использовали SQLite. (Stellar также поддерживает PostgreSQL, но здесь есть асинхронные задачи, которые вносят шум в измерения.) Stellar предоставляет встроенный запрос времени выполнения,generload, что позволяет генерировать синтетическую нагрузку на конкретную цель транзакция/второй курс. Хотя Stellar поддерживает различные торговые функции, такие как книга заказов и путь кросс-активов платежей, мы сосредоточились на простых платежах. Подтверждение транзакций состоит из нескольких этапов, поэтому мы записал измерения для каждого из следующих показателей: • Номинация: время от номинации до первой подготовки. • Голосование: время от первой подготовки до подтверждения голосование совершено • Обновление реестра: пришло время применить консенсусную ценность • Количество транзакций: подтвержденные транзакции по реестру. Каждый из наших экспериментов определялся тремя параметрами: количество счетных записей в книге учета, сумма нагрузка (в виде платежей XLM), отправляемая в секунду, и количество validators. Мы настраивали каждые validator знать обо всех остальных validator (наихудший сценарий для SCP), с срезами кворума, установленными на любое простое большинство узлов (чтобы максимизировать количество различных кворумов). Базовый уровень В нашем базовом эксперименте было измерено Stellar с 100 000 аккаунтов, четыре validator и генерация нагрузки Скорость 100 транзакций в секунду. В среднем мы наблюдали 507 транзакций на каждый реестр со стандартным отклонением 49. (9,7%). Обратите внимание, что ни одна транзакция не была отменена; легкий 105 106 107 0 500 1000 1500 2000 Счета Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 9. Задержка при увеличении количества учетных записей Отклонение связано с ограничениями планирования генератора нагрузки. Мы заметили, что количество транзакций в реестре соответствовало нашей скорости генерации нагрузки, согласно данным реестра закрывается каждые 5 секунд. Выдвижение, голосование и учет Обновление показало средние задержки 82,53 мс, 95,96 мс и 174,08 мс соответственно. Мы заметили, что задержка номинации 99-й процентиль постоянно ниже 61 мс, с редкими всплески длительностью примерно 1 секунду, что соответствует первому шагу в функции таймаута выбора лидера. Учитывая базовую производительность, мы рассмотрели эффекты варьирования каждого из параметров испытательной установки. Счета Данные на рисунке 9 показывают, что Stellar масштабируется а количество аккаунтов увеличивается. Генерация теста учетных записей стали длительным процессом, поскольку создание корзин и слияние не позволило нам просто заполнить базу данных с учетными записями напрямую через SQL. Поэтому мы провели нашу эксперименты до 50 000 000 аккаунтов. Пока есть минимальное влияние на консенсус и задержки обновления реестра, мы отмечаем, что увеличение счетов создает накладные расходы в размере объединение ведер, которые становятся больше. Скорость транзакции Скорость транзакций влияет на сумму многоадресная рассылка трафика между validator, количество транзакций, включенных в каждый реестр, и размер верхнего уровня ведра. Чтобы понять последствия увеличения транзакций load мы провели эксперимент со 100 000 аккаунтами и 4 validator. На рисунке 10 показан медленный рост задержки консенсуса. в то время как большая часть времени была потрачена на обновление реестра. Неудивительно, что по мере увеличения размера набора транзакций требуется больше времени, чтобы зафиксировать его в базе данных. Мы также отмечаем, что задержка обновления реестра сильно зависит от реализации, и зависит от выбора базы данных. Узлы валидатора Чтобы увидеть, как увеличивается количество тиронов validatorsвлияет на производительность, мы провели эксперименты со 100 000 учетных записей, 100 транзакциями в секунду и различным количеством validator от 4 до 43. Появились все validator. во всех слоях кворума validators; меньшие фрагменты кворума будут оказывают меньшее влияние на производительность.SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. 100 150 200 250 300 350 0 500 1000 1500 2000 Нагрузка [транзакций/секунду] Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 10. Задержка при увеличении транзакционной нагрузки 10 20 30 40 0 500 1000 1500 2000 Валидаторы Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 11. Задержка при увеличении количества узлов Изменение количества проверяющих узлов в сети влияет на количество обмениваемых SCP-сообщений, а также количество потенциальных значений при номинации. Рисунок 11 показывает, что время выдвижения кандидатур растет относительно небольшими темпами. Хотя данные показывают, что голосование является узким местом, мы считают, что многие проблемы масштабирования можно решить, улучшив Оверлейная сеть Stellar для оптимизации сетевого трафика. Как ожидаемо, задержка обновления реестра оставалась независимой от количество узлов. Закрыть курс Наконец, мы хотели измерить сквозную производительность Stellar, измеряя, как часто регистры подтверждаются и достигает ли Stellar своего 5-секундного целевого показателя без отмена любых транзакций. Мы наблюдали среднее закрытие книги раз 5,03 с, 5,10 с и 5,15 с по мере увеличения счета записи, скорость транзакций и количество узлов соответственно. Результаты показывают, что Stellar может последовательно закрывать реестры. под высокой нагрузкой. 7.4 Запуск validator Одной из важных особенностей Stellar является низкая стоимость. запуск validator, поскольку якоря должны работать (или заключать контракт с) validators для обеспечения окончательности. SDF запускает 3 производственных validator, все на экземплярах AWS c5.large, которые имеют два ядра, 4 ГБ ОЗУ и процессор Intel(R) Xeon(R) Platinum 8124M Процессоры @ 3,00 ГГц. Проверка использования ресурсов на одном из этих машин мы наблюдали процесс Stellar, используя около 7% процессора и 300 МБ памяти. С точки зрения сетевого трафика: 28 подключений к узлам и размер кворума. из 34 входящие и исходящие скорости составляли 2,78 Мбит/с, а 2,56 Мбит/с соответственно. Аппаратное обеспечение, необходимое для запуска такого процедура недорогая. В нашем случае стоимость составляет $0,054/час. или около 40 долларов в месяц. 7,5 Будущая работа Эти эксперименты показывают, что Stellar может легко масштабироваться на 1–2 порядка. масштабов, превосходящих сегодняшнее использование сети. Потому что Требования к производительности на сегодняшний день настолько скромны, что Stellar оставляет место для многих простых оптимизаций с использованием известные методики. Например, транзакции и SCP сообщения транслируются validators с использованием наивного флуда протокол, но в идеале следует использовать более эффективный, структурированный одноранговая многоадресная рассылка [30]. Кроме того, большая база данных Время обновления реестра можно сократить с помощью стандартных методов пакетной обработки и предварительной выборки.

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

Заключение

Международные платежи стоят дорого и занимают несколько дней. Фонд хранение проходит через несколько финансовых учреждений, включая банки-корреспонденты и службы денежных переводов. Поскольку каждому переходу необходимо полностью доверять, новым пользователям сложно абитуриентам, чтобы завоевать долю рынка и конкурировать. Stellar шоу как дешево отправить деньги по всему миру за считанные секунды. Ключевым нововведением является новый протокол Византийского соглашения с открытым членством, SCP, который использует одноранговую структуру. финансовой сети для достижения глобального консенсуса под новая гипотеза Интернета. SCP позволяет Stellar атомарно зафиксировать необратимые транзакции между произвольными участниками, которые не знают друг друга и не доверяют друг другу. Это, в свою очередь, гарантирует новым участникам доступ к тем же рынкам, что и существующие. игроков, позволяет безопасно получить лучший доступный обмен ставки даже у ненадежных маркет-мейкеров, и резко уменьшает задержку платежа. Благодарности Stellar не был бы тем, чем он является сегодня, без раннего лидерство Джойс Ким или огромный вклад Скотт Флекенштейн и Бартек Новотарски в строительстве и поддержание горизонта, Stellar SDK и другие ключевые элементы экосистемы Stellar. Мы также благодарим Колтена Бержерона, Генри Корриган-Гиббс, Кэндис Келли, Капил К. Джайн, Борис Резников, Джереми Рубин, Кристиан Раддер, Эрик Сондерс, Торстен Штюбер, Томер Веллер, анонимные рецензенты и нашему пастуху Жюстин Шерри за полезные комментарии более ранние черновики. Отказ от ответственности Вклад профессора Мазьера в эту публикацию был сделан в качестве платного консультанта и не был частью его работы. Обязанности или ответственность Стэнфордского университета.

Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада