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

Tóm tắt

Thanh toán quốc tế chậm và tốn kém, một phần là do định tuyến thanh toán nhiều bước thông qua các mạng không đồng nhất. các hệ thống ngân hàng. Stellar là mạng thanh toán toàn cầu mới có thể chuyển trực tiếp tiền kỹ thuật số đến bất kỳ đâu trên thế giới thế giới trong vài giây. Sự đổi mới quan trọng là một giao dịch an toàn cơ chế thông qua các trung gian không đáng tin cậy, sử dụng một cơ chế mới Giao thức thỏa thuận Byzantine được gọi là SCP. Với SCP, mỗi tổ chức chỉ định các tổ chức khác sẽ ở lại đồng ý; thông qua sự kết nối toàn cầu của hệ thống tài chính, toàn bộ mạng lưới sau đó đồng ý về nguyên tử giao dịch trải rộng trên các tổ chức tùy ý, không có rủi ro về khả năng thanh toán hoặc tỷ giá hối đoái từ các tổ chức phát hành tài sản trung gian hoặc các nhà tạo lập thị trường. Chúng tôi trình bày mô hình, giao thức và xác minh chính thức; mô tả mạng thanh toán Stellar; và cuối cùng đánh giá Stellar theo kinh nghiệm thông qua điểm chuẩn và kinh nghiệm của chúng tôi với nhiều năm sử dụng sản xuất. Khái niệm CCS • Bảo mật và quyền riêng tư → Phân tán bảo mật hệ thống; • Tổ chức hệ thống máy tính → Kiến trúc ngang hàng; • Hệ thống thông tin → Chuyển tiền điện tử. Từ khóa blockchain, BFT, số đại biểu, thanh toán Định dạng tham chiếu ACM: Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, Jed McCaleb. 2019. Thanh toán toàn cầu nhanh chóng và an toàn với Stellar. trong SOSP '19: Hội nghị chuyên đề về Nguyên tắc hệ điều hành, ngày 27–30 tháng 10, 2019, Huntsville, ON, Canada. ACM, New York, NY, Mỹ, 17 trang. 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.

Giới thiệu

Thanh toán quốc tế nổi tiếng là chậm và tốn kém [32]. Hãy xem xét tính phi thực tế của việc gửi 0,5 đô la từ Hoa Kỳ tới *Galois, Inc. †UCLA Quyền tạo bản sao kỹ thuật số hoặc bản cứng của tất cả hoặc một phần tác phẩm này cho việc sử dụng cá nhân hoặc lớp học được cấp miễn phí với điều kiện là các bản sao không được thực hiện hoặc phân phối vì lợi nhuận hoặc lợi ích thương mại và các bản sao đó mang thông báo này và trích dẫn đầy đủ ở trang đầu tiên. Bản quyền cho các thành phần tác phẩm này thuộc sở hữu của người khác ngoài ACM phải được tôn vinh. Trừu tượng hóa với tín dụng được cho phép. Sao chép theo cách khác hoặc xuất bản lại để đăng trên máy chủ hoặc phân phối lại vào danh sách, cần có sự cho phép cụ thể trước và/hoặc phải trả phí. Yêu cầu quyền từ [email protected]. SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada © 2019 Hiệp hội Máy tính. ACM ISBN 978-1-4503-6873-5/19/10...$15,00 https://doi.org/10.1145/3341301.3359636 Mexico, hai nước láng giềng. Người dùng cuối phải trả gần 9 USD đối với mức chuyển khoản trung bình như vậy [32] và thỏa thuận song phương được môi giới bởi ngân hàng trung ương của các nước chỉ có thể làm giảm chi phí ngân hàng cơ bản lên tới 0,67 USD cho mỗi mặt hàng [2]. Ngoài phí, độ trễ của thanh toán quốc tế thường được tính trong vài ngày, khiến cho việc chuyển tiền ra nước ngoài nhanh chóng trong trường hợp khẩn cấp. Ở những nước mà hệ thống ngân hàng không làm việc hoặc không phục vụ mọi công dân hoặc khi mức phí không thể chấp nhận được, mọi người chuyển sang gửi thanh toán bằng xe buýt [38], bằng thuyền [19] và thỉnh thoảng bây giờ là Bitcoin [55], tất cả đều như vậy phải chịu rủi ro, độ trễ hoặc sự bất tiện. Mặc dù sẽ luôn có chi phí tuân thủ nhưng bằng chứng cho thấy tổn thất một khoản đáng kể do thiếu cạnh tranh [21], càng trở nên trầm trọng hơn do công nghệ kém hiệu quả. Nơi mọi người có thể đổi mới, giá cả và độ trễ giảm xuống. Chẳng hạn, chuyển tiền từ tài khoản ngân hàng trong quý 2 năm 2019 có chi phí trung bình là 6,99%, trong khi con số về tiền di động chỉ là 4,88% [13]. Mạng thanh toán toàn cầu mở thu hút sự đổi mới và sự cạnh tranh từ các tổ chức phi ngân hàng có thể làm giảm chi phí và độ trễ ở tất cả các lớp, bao gồm cả việc tuân thủ [83]. Bài viết này trình bày Stellar, khoản thanh toán dựa trên blockchain mạng được thiết kế đặc biệt để tạo thuận lợi cho sự đổi mới và cạnh tranh trong thanh toán quốc tế. Stellar là lần đầu tiên thống để đáp ứng cả ba mục tiêu sau (theo một “Giả thuyết Internet” mới lạ nhưng có giá trị thực nghiệm: 1. Tư cách thành viên mở – Bất kỳ ai cũng có thể phát hành được hỗ trợ bằng tiền tệ token kỹ thuật số có thể được trao đổi giữa những người dùng. 2. Quyết định cuối cùng do nhà phát hành thực thi – Nhà phát hành của token có thể ngăn chặn các giao dịch trong token không bị đảo ngược hoặc hoàn tác. 3. Tính nguyên tử của nhà phát hành chéo – Người dùng có thể trao đổi nguyên tử và giao dịch token từ nhiều tổ chức phát hành. Đạt được hai điều đầu tiên thật dễ dàng. Bất kỳ công ty nào cũng có thể đơn phương cung cấp một sản phẩm như Paypal, Venmo, WeChat Thanh toán hoặc Alipay và đảm bảo tính cuối cùng của thanh toán trong tiền ảo mà họ đã tạo ra. Thật không may, giao dịch nguyên tử giữa các loại tiền tệ này là không thể. Trên thực tế, mặc dù Paypal đã mua lại công ty mẹ của Venmo vào năm 2013, người dùng cuối vẫn không thể gửi Venmo đô la cho người dùng Paypal [78]. Chỉ gần đây các thương nhân mới có thể thậm chí chấp nhận cả hai với một sự tích hợp duy nhất. Mục tiêu 2 và 3 có thể đạt được trong một hệ thống khép kín. Đặc biệt, một số nước đã có thanh toán nội địa hiệu quả mạng, thường được giám sát bởi một cơ quan quản lý đáng tin cậy trên toàn cầu. Tuy nhiên, tư cách thành viên được giới hạn ở mức đóng tập hợp các ngân hàng đặc quyền và mạng lưới được giới hạn ở tầm với của cơ quan quản lý của một quốc gia.SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. Mục tiêu 1 và 3 đã đạt được trong blockchain giây được khai thác, đáng chú ý nhất là ở dạng ERC20 tokens trên Ethereum [3]. Ý tưởng chính của những blockchain này là tạo ra một loại tiền điện tử mới để thưởng cho mọi người vì đã thanh toán giao dịch khó hoàn nguyên. Thật không may, điều này có nghĩa là nhà phát hành token không kiểm soát tính cuối cùng của giao dịch. Nếu phần mềm lỗi khiến lịch sử giao dịch bị sắp xếp lại [26, 73], hoặc khi chiến lợi phẩm của việc lừa gạt người khác vượt quá chi phí sắp xếp lại lịch sử [74, 97], nhà phát hành có thể phải chịu trách nhiệm về tokens họ đã đổi lấy tiền thật. Stellar blockchain có hai thuộc tính phân biệt. Đầu tiên, nó thực sự hỗ trợ thị trường hiệu quả trong khoảng token giây từ các tổ chức phát hành khác nhau. Cụ thể, bất kỳ ai cũng có thể phát hành token, blockchain cung cấp sổ đặt hàng tích hợp để giao dịch giữa bất kỳ cặp token nào và người dùng có thể phát hành thanh toán đường dẫn giao dịch nguyên tử trên một số cặp tiền tệ trong khi đảm bảo giá giới hạn từ đầu đến cuối. Thứ hai, Stellar giới thiệu thỏa thuận Byzantine mới giao thức, SCP (Stellar Giao thức đồng thuận), thông qua đó token nhà phát hành chỉ định máy chủ validator cụ thể để thực thi sự cuối cùng của giao dịch. Miễn là không ai xâm phạm validator của nhà phát hành (và các chữ ký số cơ bản và mật mã hash vẫn được bảo mật), nhà phát hành biết chính xác giao dịch nào đã xảy ra và tránh rủi ro về tổn thất từ blockchain việc sắp xếp lại lịch sử. Ý tưởng chính của SCP là hầu hết các nhà phát hành tài sản đều được hưởng lợi từ thị trường thanh khoản và muốn tạo điều kiện thuận lợi cho các giao dịch nguyên tử với các tài sản khác. Do đó, quản trị viên validator định cấu hình máy chủ của họ đồng ý chính xác với các validator khác lịch sử của tất cả các giao dịch trên tất cả các tài sản. validator v1 có thể được cấu hình để đồng ý với v2 hoặc v2 có thể được cấu hình để đồng ý với v1 hoặc cả hai có thể được cấu hình để đồng ý với nhau; trong mọi trường hợp, sẽ không cam kết về lịch sử giao dịch cho đến khi nó biết người kia không thể cam kết với một lịch sử khác. Theo tính bắc cầu, nếu v1 không thể không đồng ý với v2 và v2 không thể không đồng ý với v3 (hoặc ngược lại) thì v1 không thể không đồng ý với v3, v3 có đại diện cho tài sản v1 hay không thì đã nghe nói rồi của. Theo giả thuyết rằng các mối quan hệ thỏa thuận này kết nối liên tục toàn bộ mạng, SCP đảm bảo thỏa thuận toàn cầu, biến nó thành một thỏa thuận Byzantine toàn cầu giao thức với tư cách thành viên mở. Chúng tôi gọi giả định kết nối mới này là giả thuyết Internet và lưu ý rằng nó nắm giữ cả “Internet” (điều mà mọi người đều hiểu có nghĩa là mạng IP được kết nối bắc cầu lớn nhất) và thanh toán quốc tế truyền thống (được thực hiện theo từng bước phi nguyên tử, nhưng tận dụng một kết nối xuyên suốt, toàn cầu mạng lưới các tổ chức tài chính). Stellar đã được đưa vào sử dụng sản xuất từ tháng 9 năm 2015. Để duy trì độ dài blockchain có thể quản lý được, hệ thống sẽ chạy SCP trong khoảng thời gian 5 giây—nhanh theo tiêu chuẩn blockchain, nhưng chậm hơn nhiều so với các ứng dụng điển hình của thỏa thuận Byzantine. Mặc dù mục đích sử dụng chính là thanh toán, Stellar cũng có đã được chứng minh là hấp dẫn đối với những token có thể thay thế được bằng tiền và được hưởng lợi từ thị trường thứ cấp trực tiếp (xem Phần 7.1). Phần tiếp theo thảo luận về công việc liên quan. Phần 3 trình bày SCP. Phần 4 mô tả xác minh chính thức của chúng tôi về SCP. Phần 5 mô tả lớp thanh toán của Stellar. Mục 6 liên quan một số kinh nghiệm triển khai và bài học kinh nghiệm của chúng tôi. Phần 7 đánh giá hệ thống. Phần 8 kết thúc.

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.

Công việc liên quan

Hệ thống được mô tả trong bài viết này là hệ thống thứ ba của chúng tôi cố gắng hiện thực hóa một mạng lưới thanh toán phi tập trung. các nỗ lực đầu tiên của một trong các tác giả đã dẫn đến Ripple blockchain. Mặc dù vẫn còn tồn tại, chúng tôi tin rằng Ripple không thể hiện thực hóa tầm nhìn về một mạng thanh toán mở thực sự cho cả lý do quản trị và kỹ thuật. Nguyên nhân quản trị xuất phát từ sự căng thẳng giữa lợi ích của cổ đông và người dùng mạng, nhưng nằm ngoài phạm vi của bài viết này. các vấn đề kỹ thuật là giao thức thỏa thuận Byzantine của Ripple [89] yêu cầu tư cách thành viên gần như đóng [33], khiến nó có chức năng tương tự như thỏa thuận Byzantine thông thường. Lần thử thứ hai, một đợt phân nhánh ngắn hạn của mã Ripple căn cứ có tên Stellad, đi vào hoạt động vào tháng 7 năm 2014. Chúng tôi đã lên kế hoạch phát triển SCP và đưa nó vào Stellad khi sẵn sàng, nhưng thay vào đó quyết định xây dựng một hệ thống mới từ đầu xung quanh SCP, được gọi là lõi sao và được mô tả trong bài báo này. lõi sao đã được phát hành cùng với mô tả và bằng chứng về SCP [68] vào tháng 4 năm 2015 và đưa vào sử dụng sản xuất 5 tháng sau đó. Một bản nháp trên Internet [20] sau đó đã mô tả SCP cho những người triển khai. Động cơ và cấu trúc của SCP tương tự như niềm tin bất đối xứng trong tính toán nhiều bên [40], mặc dù mô hình đó yêu cầu các nút phải có cái nhìn tổng thể về cấu trúc đối thủ. Bằng cách giới thiệu khái niệm về các lát cắt đại biểu, SCP thích khả năng khám phá và tư cách thành viên năng động rất quan trọng đối với việc triển khai của Stellar. Nhóm túc số Byzantine cá nhân hệ thống [47] và độ tin cậy phân tán bất đối xứng [29] khái quát hóa số đại biểu của SCP và đơn giản hóa việc so sánh với truyền thống hệ thống. Trong bối cảnh hạn chế hơn, Gotsman et al. [49] cũng vậy nghiên cứu tổng quát về số đại biểu của Stellar. Một số blockchain khác đã sử dụng SCP, bao gồm MobileCoin [7] và NCNT. Ripple gần đây cũng đã đề xuất một giao thức thỏa thuận Byzantine có tư cách thành viên mở được gọi là Coban [66]. Sự an toàn của SCP là tối ưu, vì vậy SCP được an toàn trong bất kỳ kịch bản thất bại nào có Cobalt, trong khi ngược lại là không rõ ràng. Tuy nhiên, Cobalt khẳng định điều kiện an toàn của nó dễ hiểu hơn và do đó ít bị cấu hình sai hơn, sẽ rất thú vị để đánh giá xem Cobalt có được triển khai hay không. 2.1 Hệ thống không có thành viên mở Giống như nhiều giao thức đồng thuận, SCP dựa trên việc bỏ phiếu [50, 94] trong một hệ thống đại biểu. Công việc trước đây về hệ thống đại biểu [52, 67, 72], đôi khi được gọi là “tập hợp người sống sót” [57], nghiên cứu các hệ thống đại biểu tĩnh, tức là, cố định xuyên suốt thực thi hệ thống và thống nhất, tức là trong đó tất cả các nút đều có cùng một khái niệm về đại biểu là gì. Cài đặt của SCP khác ở chỗ rằng các nút khác nhau chấp nhận các đại biểu khác nhau và đang phát triển.Thanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Sự đồng thuận nhanh không đồng nhất [91] cho phép nhiều sắc thái hơn khái niệm về sự tin cậy được thể hiện thông qua các nhãn trong một mạng lưới và tận dụng điều này để tối ưu hóa giao tiếp, nhưng nó giả định thành viên đóng. Những nỗ lực khác để điều chỉnh các giao thức thỏa thuận Byzantine tới các cài đặt giống như Blockchain, bao gồm HoneyBadger [70], SBFT [53] và HotStuff [99] đã tập trung vào khả năng mở rộng cho nhiều người tham gia và hiệu suất trên các mạng diện rộng, vẫn giữ nguyên mô hình thành viên đóng truyền thống. Blockchain nhắm mục tiêu thành viên đóng đã tận dụng các giao thức như vậy, bao gồm cả Libra gần đây nhất [11]. 2.2 Các hệ thống không có quyết định cuối cùng do nhà phát hành thực thi Bitcoin [71] là tài sản kỹ thuật số có thể thay thế đầu tiên không có cơ quan đáng tin cậy để theo dõi số dư. Nó đồng thời giải quyết hai vấn đề: làm thế nào để phân phối một tài sản mới để mọi người tin tưởng nó có giá trị và cách cung cấp các giao dịch không thể đảo ngược ngăn chặn các cuộc tấn công chi tiêu gấp đôi. Bitcoin tạo nội dung thông qua proof-of-work [43], được tác giả so sánh với việc những người khai thác vàng đầu tư nguồn lực để tăng nguồn cung vàng. các công việc đã được chứng minh phụ thuộc vào lịch sử giao dịch, điều này cản trở các cuộc tấn công chi tiêu gấp đôi vì việc khôi phục các giao dịch đòi hỏi công việc tương đương với việc tạo lịch sử ban đầu. Các cuộc tấn công vào proof-of-work blockchain trở nên khả thi một khi kẻ tấn công kiểm soát 1/3 sức mạnh khai thác [46, 48]. Bằng chứng công việc đặc biệt rủi ro đối với blockchains mới hoặc nhỏ hơn [15, 23]; các công ty khai thác được thành lập đã được biết là chuyển hướng khai thác cung cấp năng lượng cho các chuỗi nhỏ hơn để kiếm lợi nhuận [10, 54, 74, 97, 98] hoặc chỉ để tạo ra vấn đề [25, 37] (được gọi là “cuộc tấn công Goldfinger” [60]). Đôi khi, những người khai thác đã nhân từ thực hiện “các cuộc tấn công 51%” như vậy để đẩy lùi những tác động không mong muốn của lỗi [95]. Mới blockchains có thể được bảo vệ khỏi các cuộc tấn công 51% bằng cách tận dụng blockchain đã được thiết lập nhiều hơn với hoạt động khai thác hợp nhất [6] hoặc bằng chứng đốt cháy [79]. Theo văn bản này, một cuộc tấn công 51% được ước tính trị giá 823.000 USD/ giờ vào Bitcoin, $93,000/hour on Ethereum, and under $20.000/ giờ cho tất cả blockchains [12] được theo dõi khác. Cuối cùng, những điều này chi phí phụ thuộc vào giá trị của tiền điện tử khuyến khích khai thác, độc lập với giá trị phát hành tài sản. Ngược lại, chi phí xâm phạm Stellar validators phần nào nằm trong tầm kiểm soát của quản trị viên của họ; SCP có thể tuân theo các triển khai có độ đảm bảo cao, chẳng hạn như sử dụng mô-đun bảo mật phần cứng để ngăn chặn validator ký các tin nhắn trái ngược nhau Là một lợi ích bổ sung, Stellar không có chi phí khai thác để hoàn lại thông qua giao dịch phí hoặc quyền sở hữu. Mức tiêu thụ năng lượng khổng lồ của Bitcoin [76] đã thúc đẩy các biến thể tiết kiệm năng lượng hơn của bằng chứng công việc chẳng hạn như bằng chứng về không gian [16, 17, 44, 87], bằng chứng về việc lưu trữ [18, 56, 86, 90], và bằng chứng về thời gian đã trôi qua [4]. Bằng chứng công việc có thể chậm, với các khối giao dịch mất vài phút để xác nhận và cần nhiều khối để bảo mật mạnh mẽ hơn. Tuy nhiên, công việc khai thác một khối có thể được khấu hao theo một loạt giao dịch có quy mô tùy ý, chỉ bị ràng buộc bởi các vấn đề chính trị và khả năng tương thích. BitcoinNG [45] sử dụng bằng chứng công việc để bầu ra người lãnh đạo điều phối một loạt giao dịch lớn hơn. Thunderella [84] có thể sử dụng bằng chứng công việc như một “con đường chậm” dự phòng và xác nhận một cách lạc quan giao dịch nhanh hơn nhiều bằng cách sử dụng sự đồng thuận không đồng bộ giao thức khi một nút tăng tốc và 3/4 ủy ban được bầu là trung thực. Mặc dù SCP nhanh hơn proof-of-work, nó đòi hỏi nhiều thông điệp hơn con đường nhanh chóng của Thunderella, nhưng có khả năng có thể là một con đường chậm hữu ích của Thunderella. Một giải pháp thay thế cho bằng chứng công việc là bằng chứng cổ phần [59], trong đó người khai thác có được ảnh hưởng trực tiếp hoặc gián tiếp từ quyền sở hữu tài sản. Trong một số trường hợp, ảnh hưởng tăng lên theo thời gian nắm giữ tài sản. Một số phương án khuyến khích sự trung thực bằng cách tịch thu cổ phần của thợ mỏ nếu họ cư xử không đúng mực [27, 28, 41]. Được ủy quyền proof-of-stake [9, 61] có các nút bỏ phiếu cổ phần của họ để bầu ra người đại diện cho giao thức thỏa thuận Byzantine thông thường, chẳng hạn như PBFT [31]. Algorand [51] sử dụng các hàm ngẫu nhiên có thể xác minh để bầu các nút đại diện một cách giả ngẫu nhiên, với xác suất tỷ lệ thuận đến việc nắm giữ tiền điện tử. Bạch Tuyết [39] chính thức hóa các thuộc tính bảo mật được yêu cầu trong bằng chứng cổ phần, hỗ trợ các nút “ngủ yên” tiếp tục vàngoại tuyến. Mặc dù hầu hết các kế hoạch proof-of-stake không thể bị ép buộc bằng tính toán tốn kém, nhưng chi phí để có được cổ phần hoặc những người khai thác hối lộ vẫn liên quan đến giá trị của tiền điện tử cơ bản và nằm ngoài tầm kiểm soát của nhà phát hành tài sản. Ngay cả khi không có công cụ khai thác độc hại, lỗi cũng có thể gây ra blockchain tổ chức lại [26, 73]. Do đó, không giống như SCP, nhà phát hành không có cách nào để đảm bảo blockchain tính cuối cùng trước đổi token trên chuỗi để chuyển khoản ngân hàng trong thế giới thực hoặc rút tiền mặt.

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 giao thức đồng thuận

Giao thức đồng thuận Stellar (SCP) là giao thức dựa trên đại biểu Giao thức thỏa thuận Byzantine với tư cách thành viên mở. Số đại biểu xuất hiện từ các quyết định cấu hình cục bộ kết hợp của các nút riêng lẻ. Tuy nhiên, các nút chỉ nhận ra số đại biểu mà họ thuộc về, và chỉ sau khi tìm hiểu cấu hình cục bộ của tất cả các thành viên trong nhóm túc số khác. Một lợi ích của phương pháp này là SCP vốn đã chấp nhận các quan điểm không đồng nhất về những nút nào tồn tại. Do đó, các nút có thể tham gia và rời đi một cách đơn phương mà không cần Giao thức "xem thay đổi" để điều phối thành viên. 3.1 Thỏa thuận Byzantine liên bang Bài toán thỏa thuận Byzantine truyền thống bao gồm một hệ thống khép kín gồm N nút, một số trong đó bị lỗi và có thể hành xử tùy tiện. Các nút nhận giá trị đầu vào và trao đổi thông báo để quyết định giá trị đầu ra trong số các đầu vào. Giao thức thỏa thuận Byzantine là an toàn khi không có hai nút hoạt động tốt nào đưa ra các quyết định khác nhau và địa chỉ duy nhất quyết định là một đầu vào hợp lệ (đối với một số định nghĩa về thỏa thuận hợp lệSOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. trước đó). Một giao thức hoạt động khi nó đảm bảo rằng mọi nút trung thực cuối cùng đều đưa ra quyết định. Thông thường, các giao thức giả định N = 3f + 1 đối với một số nguyên f > 0 thì đảm bảo an toàn và một dạng sống động nào đó miễn là nhiều nhất f nút bị lỗi. Ở một giai đoạn nào đó trong số này giao thức, các nút bỏ phiếu cho các giá trị được đề xuất và một đề xuất nhận được 2f + 1 phiếu bầu, gọi là số phiếu đại biểu, trở thành quyết định. Với N = 3f + 1 nút, hai số đại biểu bất kỳ của kích thước 2f + 1 chồng lên nhau ở ít nhất các nút f + 1; ngay cả khi f trong số này các nút chồng chéo bị lỗi thì ít nhất hai đại biểu chia sẻ một nút không bị lỗi, ngăn chặn các quyết định trái ngược nhau. Tuy nhiên, cách tiếp cận này chỉ hoạt động nếu tất cả các nút đồng ý những gì tạo nên số đại biểu, điều này là không thể trong SCP khi hai nút thậm chí có thể không biết đến sự tồn tại của nhau. Với SCP, mỗi nút v đơn phương khai báo các tập hợp nút, được gọi là các lát đại biểu của nó, sao cho (a) v tin rằng nếu tất cả các thành viên của một lát đồng ý về trạng thái của hệ thống, sau đó họ đúng, và (b) v tin rằng ít nhất một trong các lát cắt của nó sẵn sàng cung cấp thông tin kịp thời về trạng thái của hệ thống. Chúng tôi gọi hệ thống kết quả, bao gồm của các nút và các lát cắt của chúng, một Thỏa thuận Byzantine Liên bang (FBA) hệ thống. Như chúng ta sẽ thấy tiếp theo, một hệ thống đại biểu xuất hiện từ các lát cắt của nút. Một cách không chính thức, các lát cắt của nút FBA thể hiện ai nút yêu cầu sự đồng ý. Ví dụ: một nút có thể yêu cầu thỏa thuận với 4 tổ chức cụ thể, mỗi tổ chức điều hành 3 nút; để để phù hợp với thời gian ngừng hoạt động, nó có thể đặt các lát cắt của nó thành tất cả các bộ bao gồm 2 nút từ mỗi tổ chức. Nếu điều này “yêu cầu thỏa thuận với” mối quan hệ liên kết bắc cầu với hai nút bất kỳ, chúng tôi có được thỏa thuận toàn cầu. Ngược lại, chúng ta có thể có được sự phân kỳ, mà chỉ giữa các tổ chức không yêu cầu thỏa thuận với người kia. Với cấu trúc liên kết ngày nay thống tài chính, chúng tôi đưa ra giả thuyết rằng sự hội tụ rộng rãi sẽ tiếp tục tạo ra một lịch sử sổ cái duy nhất mà mọi người gọi là “mạng Stellar,” giống như cách chúng ta nói về Internet. Số đại biểu phát sinh từ các lát cắt như sau. Mỗi nút chỉ định số đại biểu của nó bị cắt trong mỗi tin nhắn nó gửi. Gọi S là tập hợp các nút mà từ đó một tập hợp các thông điệp bắt nguồn. A nút coi tập hợp các tin nhắn đã đạt đến số đại biểu ngưỡng khi mọi thành viên của S đều có một lát nằm trong S. Bằng cách xây dựng, tập S như vậy, nếu nhất trí, thỏa mãn điều kiện yêu cầu thoả thuận của mỗi thành viên. Một thiết bị ngang hàng bị lỗi có thể quảng cáo các lát cắt được tạo ra để thay đổi những gì các nút hoạt động tốt sẽ xem xét số đại biểu. Vì mục đích phân tích giao thức, chúng tôi xác định số đại biểu trong FBA là không trống tập S gồm các nút bao gồm ít nhất một lát đại biểu của từng thành viên không có lỗi. Sự trừu tượng này là âm thanh, như bất kỳ tập hợp nào của các thông điệp có ý đại diện cho một số đại biểu nhất trí thực sự có (ngay cả khi nó chứa thông báo từ các nút bị lỗi), và nó chính xác khi S chỉ chứa các nút hoạt động tốt. trong phần này, chúng tôi cũng giả định rằng các lát cắt của nút không thay đổi. Tuy nhiên, kết quả của chúng tôi chuyển sang trường hợp lát cắt thay đổi bởi vì một hệ thống trong đó các lát thay đổi không kém an toàn hơn một hệ thống lát cắt cố định trong đó các lát cắt của nút bao gồm tất cả các các lát cắt mà nó từng sử dụng trong trường hợp các lát cắt thay đổi (xem Định lý 13 trong [68]). Như đã giải thích ở Phần 4, tính sống động phụ thuộc vào các nút hoạt động tốt cuối cùng sẽ loại bỏ các nút không đáng tin cậy từ lát cắt của họ. Bởi vì các nút khác nhau có các yêu cầu thỏa thuận khác nhau nên FBA loại trừ định nghĩa toàn cầu về an toàn. Chúng tôi nói các nút không bị lỗi v1 và v2 được đan xen khi mỗi nút số đại biểu của v1 cắt mọi số đại biểu của v2 tại ít nhất một nút không bị lỗi. Một giao thức FBA có thể đảm bảo sự đồng thuận chỉ giữa các nút đan xen; vì SCP làm như vậy nên lỗi của nó dung sai cho sự an toàn là tối ưu. Giả thuyết về Internet thiết kế cơ bản của Stellar, nêu rõ rằng các nút mà mọi người quan tâm về sẽ được đan xen. Chúng ta nói một tập hợp các nút I còn nguyên vẹn nếu I là một đại biểu không bị lỗi thống nhất sao cho mỗi hai thành viên của I đều gắn bó với nhau ngay cả khi mọi nút bên ngoài I đều bị lỗi. Một cách trực quan, thì tôi nên tránh xa những hành động không còn nguyên vẹn nút. SCP đảm bảo cả tính sống động không bị chặn [93] và an toàn cho các tập hợp nguyên vẹn, mặc dù bản thân các nút không cần để biết (và có thể không biết) bộ nào còn nguyên vẹn. Hơn nữa, hợp của hai tập hợp nguyên vẹn giao nhau là một bộ còn nguyên vẹn. Do đó, các bộ nguyên vẹn xác định một phân vùng của các nút hoạt động tốt, trong đó mỗi phân vùng đều an toàn và hoạt động (trong một số điều kiện), nhưng các phân vùng khác nhau có thể xuất ra những quyết định khác nhau. 3.1.1 Cân nhắc về an toàn và tính sống động trong FBA Với các ngoại lệ hạn chế [64], hầu hết các giao thức thỏa thuận Byzantine đóng đều được điều chỉnh đến điểm cân bằng tại đó sự an toàn và sự sống động có khả năng chịu lỗi như nhau. Trong FBA, điều đó có nghĩa là các cấu hình trong đó, bất kể lỗi, tất cả các bộ đan xen cũng còn nguyên vẹn. Cho rằng FBA xác định số đại biểu theo cách phi tập trung, khó có khả năng các lựa chọn lát cắt riêng lẻ sẽ dẫn đến trạng thái cân bằng này. Hơn nữa, tại ít nhất là trong Stellar, trạng thái cân bằng là không mong muốn: hậu quả về lỗi an toàn (cụ thể là tiền kỹ thuật số được chi tiêu hai lần) là tệ hơn nhiều so với những trường hợp hỏng hóc về khả năng hoạt động (cụ thể là sự chậm trễ trong các khoản thanh toán dù sao cũng phải mất vài ngày trước Stellar). mọi người do đó nên và nên chọn các lát đại biểu lớn sao cho các nút của chúng có nhiều khả năng vẫn gắn liền với nhau hơn là nguyên vẹn. Nghiêng hơn nữa, việc phục hồi sau đó sẽ dễ dàng hơn các lỗi hoạt động điển hình trong hệ thống FBA so với hệ thống đóng truyền thống. Trong các hệ thống đóng, tất cả các thông điệp phải được được giải thích đối với cùng một tập hợp các đại biểu. Do đó, việc thêm và xóa các nút để phục hồi sau lỗi yêu cầu đạt được sự đồng thuận về một sự kiện cấu hình lại, điều này rất khó khăn khi sự đồng thuận không còn tồn tại. Ngược lại, với FBA, bất kỳ nút nào cũng có thể đơn phương điều chỉnh các lát cắt đại biểu của nó bất kỳ lúc nào thời gian. Để ứng phó với sự cố mất điện tại một điểm quan trọng mang tính hệ thống tổ chức, quản trị viên nút có thể điều chỉnh các lát cắt của họ để giải quyết vấn đề, hơi giống như điều phối các phản ứng tới thảm họa BGP [63] (mặc dù không có ràng buộc về định tuyến qua các liên kết mạng vật lý).

Thanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada 3.1.2 Định lý tầng SCP tuân theo khuôn mẫu của mô hình tròn cơ bản [42]; các nút tiến triển thông qua một loạt các phiếu bầu được đánh số, mỗi nút cố gắng thực hiện ba nhiệm vụ: (1) xác định giá trị “an toàn” không mâu thuẫn với bất kỳ quyết định nào trong cuộc bỏ phiếu trước đó (thường được gọi là chuẩn bị phiếu), (2) thống nhất về giá trị an toàn, và (3) phát hiện thỏa thuận đã thành công. Tuy nhiên, FBA mở cửa tư cách thành viên cản trở một số kỹ thuật phổ biến, khiến nó không thể “chuyển” các giao thức đóng truyền thống sang FBA mô hình bằng cách thay đổi định nghĩa về số đại biểu. Một kỹ thuật được nhiều giao thức sử dụng là xoay vòng thông qua các nút dẫn đầu theo kiểu quay vòng sau khi hết thời gian chờ. Trong một hệ thống khép kín, việc lựa chọn người lãnh đạo theo vòng tròn đảm bảo rằng cuối cùng một nhà lãnh đạo trung thực duy nhất sẽ đạt được thỏa thuận điều phối về một giá trị duy nhất. Thật không may, vòng tròn không thể hoạt động trong hệ thống FBA với tư cách thành viên không xác định. Một kỹ thuật phổ biến khác không thành công với FBA là giả sử một số đại biểu cụ thể có thể thuyết phục được tất cả các nút. Ví dụ, nếu mọi người nhận ra bất kỳ nút 2f + 1 nào là số đại biểu thì Chữ ký 2f + 1 đủ để chứng minh trạng thái giao thức cho tất cả các nút. Tương tự, nếu một nút nhận được số lượng tin nhắn giống hệt nhau thông qua chương trình phát sóng đáng tin cậy [24], nút có thể cho rằng tất cả các nút không bị lỗi cũng sẽ thấy số đại biểu. Ngược lại, trong FBA, một đại biểu không có ý nghĩa gì đối với các nút bên ngoài đại biểu. Cuối cùng, các hệ thống không liên kết thường sử dụng “ngược” lý luận về an toàn: nếu nút f + 1 bị lỗi, tất cả đều an toàn bảo lãnh bị mất. Do đó, nếu nút v nghe thấy tất cả các nút f + 1 nêu một sự thật nào đó F, v có thể cho rằng ít nhất một người đang nói với sự thật (và do đó F đúng) mà không mất đi sự an toàn. Như vậy lý luận thất bại trong FBA vì an toàn là thuộc tính của các cặp của các nút, do đó, một nút đã mất đi sự an toàn đối với một số nút ngang hàng có thể luôn mất đi sự an toàn đối với nhiều nút hơn bằng cách giả định các sự kiện xấu. Tuy nhiên, FBA có thể lý giải ngược lại về tính sống động. Xác định tập v-blocking là tập hợp các nút giao nhau lát của v. Nếu tập chặn v B bị lỗi nhất trí, B có thể từ chối nút và số đại biểu và khiến nó mất đi sự sống động. Do đó, nếu B nhất trí nêu sự thật F, khi đó v biết rằng F là đúng hoặc v không còn nguyên vẹn. Tuy nhiên v vẫn cần xem đầy đủ đủ số đại biểu để biết rằng các nút đan xen sẽ không mâu thuẫn với F, dẫn đến vòng giao tiếp cuối cùng trong SCP và các giao thức FBA khác [47] không bắt buộc tương tự giao thức thành viên đóng. Kết quả là chúng ta có ba mức độ tin cậy có thể có đối với các sự kiện tiềm ẩn: không xác định, an toàn để giả định giữa các nút nguyên vẹn (chúng tôi sẽ thuật ngữ được chấp nhận thực tế), và an toàn để giả định giữa đan xen các nút (mà chúng tôi sẽ gọi là sự thật đã được xác nhận). Nút v có thể xác định một cách hiệu quả liệu một tập hợp B có bị vblocking hay không bằng cách kiểm tra xem B có giao nhau với tất cả các lát cắt của nó hay không. Điều thú vị là nếu các nút luôn thông báo các câu lệnh mà chúng chấp nhận và đủ số đại biểu chấp nhận một tuyên bố, nó sẽ khởi động một quá trình xếp tầng theo đó các tuyên bố được lan truyền xuyên suốt bộ còn nguyên vẹn. Chúng tôi gọi thực tế quan trọng đằng sau sự truyền bá này định lý tầng, trong đó thỏa mãn điều sau: Nếu tôi là một tập nguyên vẹn, Q là số đại biểu của bất kỳ phần tử nào của I, và S là bất kỳ tập siêu của Q thì S ⊇I hoặc có thành viên v ∈I sao cho v < S và I ∩S bị chặn v. Bằng trực giác, liệu đây có phải là không phải như vậy, phần bù của S sẽ chứa đại biểu cắt I nhưng không cắt Q, vi phạm giao điểm đại biểu. Lưu ý rằng nếu chúng ta bắt đầu với S = Q và liên tục mở rộng S thành bao gồm tất cả các nút mà nó chặn, chúng tôi có được hiệu ứng xếp tầng cho đến khi, cuối cùng, S bao gồm tất cả I. 3.2 Mô tả giao thức SCP là một giao thức đồng thuận đồng bộ một phần [42] bao gồm một loạt các nỗ lực nhằm đạt được sự đồng thuận được gọi là phiếu bầu. Phiếu bầu sử dụng thời gian chờ với thời lượng tăng dần. A giao thức đồng bộ hóa lá phiếu đảm bảo rằng các nút luôn hoạt động cùng một lá phiếu trong khoảng thời gian tăng dần cho đến khi các lá phiếu được đồng bộ một cách hiệu quả. Việc chấm dứt không được đảm bảo cho đến khi các lá phiếu được đồng bộ, nhưng có hai lá phiếu đồng bộ trong đó các thành viên bị lỗi của các lát cắt của nút hoạt động tốt không can thiệp là đủ để SCP chấm dứt. Một giao thức bỏ phiếu chỉ định các hành động được thực hiện trong mỗi lá phiếu. Một cuộc bỏ phiếu bắt đầu bằng giai đoạn chuẩn bị, trong đó các nút cố gắng xác định một giá trị để đề xuất không mâu thuẫn quyết định nào trước đó. Sau đó, trong giai đoạn cam kết, các nút sẽ thử để đưa ra quyết định về giá trị đã chuẩn bị. Việc bỏ phiếu sử dụng một giao thức con thỏa thuận được gọi là bỏ phiếu liên kết, tôin nút nào bỏ phiếu cho các câu lệnh trừu tượng điều đó cuối cùng có thể được xác nhận hoặc bị mắc kẹt. Một số tuyên bố có thể được coi là mâu thuẫn và sự an toàn đảm bảo cho việc bỏ phiếu liên bang là không có hai thành viên của một tập hợp đan xen xác nhận các tuyên bố trái ngược nhau. Việc xác nhận một tuyên bố không được đảm bảo ngoại trừ một bản còn nguyên vẹn tập hợp mà tất cả các thành viên đều bỏ phiếu theo cùng một cách. Tuy nhiên, nếu một thành viên của một tập hợp nguyên vẹn xác nhận một tuyên bố, được liên kết việc bỏ phiếu đảm bảo rằng tất cả các thành viên của tập hợp nguyên vẹn cuối cùng sẽ xác nhận tuyên bố đó. Do đó, thực hiện các bước không thể đảo ngược để đáp lại những tuyên bố xác nhận sẽ duy trì sự sống động cho các nút còn nguyên vẹn. Các nút ban đầu đề xuất các giá trị thu được từ một đề cử giao thức làm tăng cơ hội của tất cả các thành viên trong một mạng lưới nguyên vẹn tập đề xuất cùng một giá trị và cuối cùng hội tụ (mặc dù không có cách nào để xác định sự hội tụ đã hoàn tất). Đề cử kết hợp bỏ phiếu liên bang với lựa chọn người lãnh đạo. Vì FBA không thể thực hiện vòng tròn tính điểm nên việc đề cử sẽ được sử dụng một kế hoạch lựa chọn người lãnh đạo theo xác suất. Định lý xếp tầng đóng một vai trò quan trọng cả trong việc bỏ phiếu đồng bộ hóa và tránh các trạng thái bị chặn từ đó việc chấm dứt là không thể được nữa. 3.2.1 Bỏ phiếu Các nút SCP tiến hành thông qua một loạt các lá phiếu được đánh số, sử dụng biểu quyết liên đoàn để thống nhất các tuyên bố về cái nào giá trị được quyết định hay không trong lá phiếu nào. Nếu không đồng bộ hoặc hành vi sai sót ngăn cản việc đưa ra quyết định trong lá phiếu n, các nút hết thời gian chờ và thử lại trong lá phiếu n + 1.

SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. Hãy nhớ lại việc bỏ phiếu liên bang có thể không chấm dứt. Do đó, một số các tuyên bố về lá phiếu có thể bị kẹt vĩnh viễn trạng thái không xác định trong đó các nút không bao giờ có thể xác định liệu chúng có vẫn đang được tiến hành hoặc bị mắc kẹt. Bởi vì các nút không thể loại trừ khả năng những tuyên bố không xác định sau này được chứng minh là đúng, họ không bao giờ được cố gắng bỏ phiếu liên bang cho các tuyên bố mới mâu thuẫn với những cái không xác định. Trong mỗi lá phiếu n, các nút sử dụng biểu quyết liên kết trên hai loại của tuyên bố: • chuẩn bị ⟨n,x⟩– cho biết không có giá trị nào khác ngoài x đã hoặc sẽ được quyết định trong bất kỳ cuộc bỏ phiếu nào ≤n. • cam kết ⟨n,x⟩– nêu x được quyết định trong lá phiếu n. Điều quan trọng, lưu ý rằng chuẩn bị ⟨n,x⟩contradicts cam kết ⟨n′,x ′⟩khi n ≥n′ và x , x ′. Một nút bắt đầu bỏ phiếu n bằng cách thử bỏ phiếu liên bang trên một câu lệnh chuẩn bị ⟨n,x⟩. Nếu có tuyên bố chuẩn bị trước đó đã được xác nhận thành công thông qua bỏ phiếu liên đoàn, nút chọn x từ sự chuẩn bị đã được xác nhận của lá phiếu cao nhất. Mặt khác, nút đặt x thành đầu ra của thức đề cử được mô tả trong tiểu mục tiếp theo. Nếu và chỉ khi một nút xác nhận thành công, hãy chuẩn bị ⟨n,x⟩ trong lá phiếu n, nó cố gắng bỏ phiếu liên kết theo cam kết ⟨n,x⟩. Nếu thành công, điều đó có nghĩa là SCP đã quyết định, do đó nút xuất ra giá trị từ tuyên bố cam kết được xác nhận. Xét một tập S đan xen. Vì có nhiều nhất một giá trị có thể được xác nhận bởi các thành viên của S trong một lá phiếu nhất định, không được xác nhận hai giá trị khác nhau do thành viên của S trong một lá phiếu nhất định. Hơn nữa, nếu cam kết ⟨n,x⟩ được xác nhận, sau đó chuẩn bị ⟨n,x⟩cũng được xác nhận; kể từ khi chuẩn bị ⟨n,x⟩trái ngược với bất kỳ cam kết nào trước đó về một giá trị khác, bằng thỏa thuận đảm bảo về bỏ phiếu liên bang chúng tôi hiểu rằng không có giá trị khác nào có thể được quyết định sớm hơn phiếu bầu của các thành viên của S. Bằng cách quy nạp số phiếu bầu, chúng tôi do đó hãy chắc chắn rằng SCP vẫn an toàn. Để có sự sống động, hãy xem xét một tập I nguyên vẹn và đủ dài lá phiếu đồng bộ n. Nếu các nút bị lỗi xuất hiện trong các lát của các nút hoạt động tốt không can thiệp vào n, sau đó bằng cách bỏ phiếu n + 1 tất cả các thành viên của I đều đã xác nhận cùng một tập P của các câu lệnh chuẩn bị. Nếu P = ∅ và lá phiếu n đủ dài thì giao thức đề cử sẽ hội tụ về một số giá trị x. Mặt khác, đặt x là giá trị từ lượt chuẩn bị có phiếu bầu cao nhất ở P. Dù thế nào đi nữa, tôi sẽ thống nhất thử liên kết bỏ phiếu chuẩn bị ⟨n + 1,x⟩trong lần bỏ phiếu tiếp theo. Vì vậy, nếu n + 1 cũng đồng bộ nên quyết định về x tất yếu sẽ xảy ra sau đó. 3.2.2 Đề cử Đề cử đòi hỏi phải bỏ phiếu liên bang về các tuyên bố: • đề cử x – cho biết x là ứng cử viên quyết định hợp lệ. Các nút có thể bỏ phiếu để đề cử nhiều giá trị—khác nhau các tuyên bố đề cử không mâu thuẫn nhau. Tuy nhiên, một lần một nút xác nhận bất kỳ tuyên bố đề cử nào, nó sẽ dừng bỏ phiếu đề cử các giá trị mới. Bỏ phiếu liên kết vẫn cho phép một nút xác nhận các tuyên bố đề cử mới mà họ không bỏ phiếu, bỏ phiếu hoặc chấp nhận một từ đại biểu chấp nhận một từ đại biểu a là hợp lệ chấp nhận từ bộ chặn không cam kết đã bình chọn một chấp nhận một đã xác nhận một đã bình chọn -a Hình 1. Các giai đoạn bỏ phiếu liên bang cho phép các thành viên của một tập hợp nguyên vẹn xác nhận ý kiến của nhau các giá trị được đề cử trong khi vẫn giữ lại phiếu bầu mới. Kết quả (đang phát triển) của việc đề cử là sự kết hợp mang tính quyết định của tất cả các giá trị trong các tuyên bố đề cử đã được xác nhận. Nếu x đại diện cho một tập hợp các giao dịch, các nút có thể kết hợp trong số các bộ, bộ lớn nhất hoặc bộ có hash cao nhất, vì vậy miễn là tất cả các nút đều làm như vậy. Bởi vì các nút giữ lại cái mới phiếu bầu sau khi xác nhận một tuyên bố đề cử, tập hợp các các câu lệnh được xác nhận chỉ có thể chứa hữu hạn nhiều giá trị. Thực tế là các tuyên bố đã được xác nhận được lan truyền một cách đáng tin cậy thông qua tập hợp nguyên vẹn có nghĩa là các nút nguyên vẹn cuối cùng hội tụ trên cùng một tập hợp các giá trị được đề cử và do đó kết quả đề cử, mặc dù tại một điểm không xác định, tùy ý bị trễ trong giao thức. Các nút sử dụng lựa chọn lãnh đạo liên kết để giảm số lượng các giá trị khác nhau trong các câu lệnh đề cử. Chỉ một nhà lãnh đạo chưa bỏ phiếu cho tuyên bố đề cử có thể giới thiệu một x mới. Các nút khác đang chờ phản hồi từ lãnh đạo và chỉ sao chép phiếu đề cử (hợp lệ) của lãnh đạo họ. Để đối phó với thất bại, đội ngũ lãnh đạo không ngừng phát triển xảy ra thời gian chờ, mặc dù trong thực tế chỉ có một số nút đưa ra các giá trị mới của x. 3.2.3 Bỏ phiếu liên bang Bỏ phiếu liên bang sử dụng giao thức ba giai đoạn được hiển thị trong Hình 1. Các nút cố gắng thống nhất các câu lệnh trừu tượng trước tiên bỏ phiếu, sau đó chấp nhận và cuối cùng là xác nhận các tuyên bố. Nút v có thể bỏ phiếu cho bất kỳ câu lệnh a hợp lệ nào mà không mâu thuẫn với cái khác của nósố phiếu còn tồn đọng và các tuyên bố được chấp nhận. Nó làm như vậy bằng cách phát đi một tin nhắn biểu quyết đã ký. v sau đó chấp nhận a nếu a phù hợp với các phát biểu được chấp nhận khác và (trường hợp 1)v là thành viên của một đại biểu trong đó mỗi nút hoặc bỏ phiếu cho a hoặc chấp nhận a hoặc (trường hợp 2) ngay cả khi v không bỏ phiếu cho a, tập hợp chặn v chấp nhận a. Trường hợp 2, v có thể trước đây đã bỏ phiếu mâu thuẫn với a, hiện đã bỏ phiếu bị bác bỏ. v được phép quên đi những phiếu bầu bị bác bỏ và giả vờ như nó chưa bao giờ sử dụng chúng vì ifv còn nguyên vẹn, nó biết phiếu bị bác bỏ không thể hoàn thành số đại biểu thông qua trường hợp 1. v thông báo rằng nó chấp nhận a, sau đó xác nhận a khi nó ở trong số đại biểu nhất trí chấp nhận a. Hình 2 cho thấy ảnh hưởng của tập chặn v và định lý xếp tầng trong bỏ phiếu liên bang. Hai nút đan xen nhau không thể xác nhận các tuyên bố trái ngược nhau, vì hai số đại biểu bắt buộc sẽ phải chia sẻ mộtThanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada 3 4 2 1 5 7

Vote X

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

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

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

Bình chọn X

Bầu Y (a) 3 4 2 1 5 7 6 Bình chọn X Bình chọn X Bình chọn X Bình chọn Y Bình chọn X Bình chọn Y Bình chọn Y (b) 3 4 2 1 5 7 6 Chấp nhận X Bình chọn X Chấp nhận X Bình chọn Y Chấp nhận X Bình chọn Y Bình chọn Y (c) 3 4 2 1 5 7 6 Chấp nhận X Chấp nhận X Chấp nhận X Bình chọn Y Chấp nhận X Chấp nhận X Bình chọn Y (d) 3 4 2 1 5 7 6 Chấp nhận X Bình chọn X Chấp nhận X Chấp nhận X Chấp nhận X Chấp nhận X Chấp nhận X (e) Hình 2. Hiệu ứng xếp tầng trong bỏ phiếu liên bang. Mỗi nút có một lát đại biểu được biểu thị bằng các mũi tên tới các thành viên của lát. (a) Các phát biểu mâu thuẫn X và Y được đưa ra. (b) Các nút bỏ phiếu cho các phát biểu hợp lệ. (c) Nút 1 chấp nhận X sau đại biểu của nó {1, 2, 3, 4} nhất trí bỏ phiếu cho X. (d) Các nút 1, 2, 3 và 4 đều chấp nhận X; tập {1} là 5-blocking, vì vậy nút 5 chấp nhận X, ghi đè phiếu bầu trước đó của nó cho Y. (e) Tập {5} là 6- và 7-chặn, vì vậy cả 6 và 7 đều chấp nhận X. nút không bị lỗi không thể chấp nhận các câu lệnh mâu thuẫn. Việc xác nhận một tuyên bố không được đảm bảo: trong trường hợp biểu quyết chia rẽ, cả hai tuyên bố có thể có hiệu lực vĩnh viễn bị mắc kẹt khi chờ số đại biểu trong giai đoạn bỏ phiếu. Tuy nhiên, nếu một nút trong một tập nguyên vẹn Tôi xác nhận một câu lệnh, tầng định lý và chấp nhận trường hợp 2 đảm bảo rằng tất cả I cuối cùng sẽ xác nhận tuyên bố đó. 3.2.4 Đồng bộ hóa phiếu bầu Nếu các nút không thể xác nhận một tuyên bố cam kết cho lá phiếu hiện tại, họ sẽ bỏ cuộc sau khi hết thời gian chờ. Thời gian chờ được dài hơn với mỗi lá phiếu để điều chỉnh theo giới hạn tùy ý về độ trễ mạng. Tuy nhiên, chỉ thời gian chờ là không đủ để đồng bộ hóa phiếu bầu của các nút không bắt đầu cùng lúc hoặc đã không đồng bộ hóa vì các lý do khác. Để đạt được sự đồng bộ hóa, các nút chỉ khởi động bộ đếm thời gian khi chúng là một phần của số đại biểu có ở lá phiếu hiện tại (hoặc sau này) n. Cái này làm chậm các nút bắt đầu sớm và đảm bảo rằng không có thành viên của một nhóm nguyên vẹn luôn dẫn đầu nhóm quá xa. Hơn nữa, nếu một nút v nhận thấy một tập hợp chặn v sau đó. lá phiếu, nó ngay lập tức chuyển sang lá phiếu thấp nhất sao cho không còn như vậy nữa, bất kể bất kỳ bộ tính giờ nào. thác nước định lý sau đó đảm bảo rằng tất cả những người đi sau đều bắt kịp. kết quả là các lá phiếu gần như được đồng bộ hóa xuyên suốt một cách nguyên vẹn được thiết lập khi hệ thống trở nên đồng bộ. 3.2.5 Lựa chọn lãnh đạo liên bang Lựa chọn người lãnh đạo cho phép mỗi nút chọn những người lãnh đạo theo cách như vậy theo cách mà các nút thường chỉ chọn một hoặc một số nhỏ của các nhà lãnh đạo. Để khắc phục sự thất bại của người lãnh đạo, việc lựa chọn người lãnh đạo tiến hành qua các vòng. Nếu người dẫn đầu vòng hiện tại dường như không hoàn thành trách nhiệm của mình thì sau một thời gian các nút trong khoảng thời gian chờ nhất định sẽ chuyển sang vòng tiếp theo để mở rộng nhóm lãnh đạo mà họ theo đuổi. Mỗi vòng sử dụng hai hàm mật mã hash duy nhất, H0 và H1, xuất ra các số nguyên trong phạm vi [0,hmax). Ví dụ: Stellar sử dụng Hi(m) = SHA256(i∥b∥r ∥m), trong đó b là phiên bản SCP tổng thể (số khối hoặc sổ cái), r là số vòng lựa chọn người lãnh đạo và hmax = 2256. Trong một vòng, chúng tôi xác định mức độ ưu tiên của nút v là: mức độ ưu tiên(v) = H1(v) Mỗi nút sẽ chọn một người làm ống hút làm người lãnh đạo nút có mức độ ưu tiên cao nhất (v). Cách tiếp cận này hoạt động tốt với các lát đại biểu gần như giống hệt nhau, nhưng không đúng cách nắm bắt được tầm quan trọng của các nút trong cấu hình không cân bằng. Ví dụ: nếu Châu Âu và Trung Quốc mỗi nước đóng góp 3 các nút theo mọi đại biểu, nhưng Trung Quốc chạy 1.000 nút và Châu Âu 4, thì Trung Quốc sẽ có nút ưu tiên cao nhất 99,6% của thời đại. Do đó chúng tôi giới thiệu một khái niệm về trọng lượng lát cắt, trong đó trọng lượng(u,v) ∈[0, 1] là một phần của các lát đại biểu của nút u chứa nút v. Khi nút u đang chọn người lãnh đạo mới, nó chỉ xem xét hàng xóm, được xác định như sau: hàng xóm(u) = { v | H0(v) < hmax · trọng lượng(u,v) } Sau đó, một nodeu bắt đầu với một tập hợp các nhà lãnh đạo trống và tại mỗi vòng thêm vào đó nút v trong hàng xóm (u) có giá trị cao nhất ưu tiên(v). Nếu tập hàng xóm trống trong bất kỳ vòng nào, thay vào đó, u sẽ thêm nút có giá trị thấp nhất là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.

Xác minh chính thức của SCP

Để loại bỏ các lỗi thiết kế, chúng tôi đã chính thức xác minh tính an toàn của SCP và các thuộc tính sống động (xem [65]). Cụ thể, chúng tôi đã xác minh các nút đan xen đó không bao giờ bất đồng ý kiến và rằng, trong các điều kiện được thảo luận dưới đây, mọi thành viên của một tập hợp nguyên vẹn cuối cùng sẽ quyết định. Điều thú vị là việc xác minh cho thấy rằng những điều kiện mà SCP đảm bảo sự sống rất tinh tế, và mạnh mẽ hơn suy nghĩ ban đầu [68]: như được thảo luận bên dưới, các nút độc hại thao túng thời gian mà không có cách nào khác đi chệch khỏi giao thức có thể cần phải được gỡ bỏ bằng tay từ các lát đại biểu.

SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. Để đảm bảo rằng các tài sản đã được chứng minh có giá trị nhất có thể cấu hình và thực thi FBA, chúng tôi xem xét tùy ý số nút có cấu hình cục bộ tùy ý. Cái này bao gồm các kịch bản với các bộ nguyên vẹn rời rạc, cũng như các lần thực thi có thể kéo dài vô tận. Nhược điểm là chúng ta phải đối mặt với vấn đề đầy thách thức trong việc xác minh một tham số hệ thống trạng thái vô hạn. Để duy trì việc xác minh dễ dàng, chúng tôi đã lập mô hình SCP theo logic bậc nhất (FOL) bằng cách sử dụng Ivy [69] và phương pháp của [82]. Quá trình xác minh bao gồm việc cung cấp các phỏng đoán quy nạp theo cách thủ công, sau đó được kiểm tra tự động bởi Cây thường xuân. Mô hình FOL của SCP tóm tắt một số khía cạnh của Các hệ thống FBA khó xử lý trong FOL (ví dụ: định lý tầng được coi là một tiên đề), vì vậy chúng tôi xác minh tính đúng đắn của sự trừu tượng hóa bằng cách sử dụng Isabelle/HOL [75]. Sau khi trình bày vấn đề xác minh trong FOL, chúng tôi xác minh tính an toàn bằng cách cung cấp một bất biến quy nạp. quy nạp bất biến bao gồm hàng tá phỏng đoán một dòng cho khoảng 150 dòng đặc tả giao thức. Sau đó, chúng tôi chỉ định các thuộc tính sống của SCP trong Logic Thời gian Tuyến tính của Ivy và sử dụng giảm độ sống để an toàn [80, 81] để giảm độ sống bài toán xác minh cho bài toán tìm biểu thức quy nạp bất biến. Mặc dù sự an toàn của SCP tương đối dễ thực hiện chứng minh, lập luận về sự sống của SCP phức tạp hơn nhiều và bao gồm khoảng 150 bất biến một dòng. Việc chứng minh tính sống động đòi hỏi một sự hình thức hóa chính xác của giả định theo đó SCP đảm bảo chấm dứt. Ban đầu chúng tôi nghĩ rằng một bộ nguyên vẹn sẽ luôn chấm dứt nếu tất cả các thành viên đã loại bỏ các nút bị lỗi khỏi lát cắt của họ [68]. Tuy nhiên, điều này hóa ra vẫn chưa đủ: một người cư xử tốt (nhưng không còn nguyên vẹn) nút trong số đại biểu thành viên của I can, theo ảnh hưởng của các nút bị lỗi, ngăn chặn việc chấm dứt bằng cách hoàn thành đủ số đại biểu ngay trước khi kết thúc cuộc bỏ phiếu, do đó gây ra thành viên của I chọn các giá trị khác nhau của x trong lần bỏ phiếu tiếp theo. Do đó, chúng ta phải giả định thêm rằng, một cách không chính thức, cuối cùng mỗi nút trong số đại biểu của một thành viên của tôi trở nên kịp thời hoặc không gửi tin nhắn nào trong một khoảng thời gian vừa đủ. Trong thực tế, điều này có nghĩa là các thành viên của tôi có thể cần điều chỉnh các lát cắt của chúng cho đến khi điều kiện được giữ nguyên. Cái này vấn đề không phải là cố hữu của hệ thống FBA: Losa et al. [47] có mặt một giao thức mà sự tồn tại của nó phụ thuộc vào điểm yếu hơn giả định về sự đồng bộ hóa cuối cùng và sự lựa chọn lãnh đạo cuối cùng mà không cần phải loại bỏ các nút bị lỗi khỏi các lát cắt.

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.

Mạng thanh toán

Phần này mô tả mạng thanh toán của Stellar, được triển khai dưới dạng máy trạng thái được sao chép [88] trên SCP. 5.1 Mô hình sổ cái Sổ cái của Stellar được thiết kế dựa trên sự trừu tượng hóa tài khoản (trong tương phản với sản lượng giao dịch chưa chi tiêu tập trung vào tiền xu hơn hoặc mẫu UTXO của Bitcoin). Nội dung sổ cái bao gồm một tập hợp các mục sổ cái gồm bốn loại riêng biệt: tài khoản, đường tin cậy, ưu đãi và dữ liệu tài khoản. Tài khoản là người chủ sở hữu và phát hành tài sản. Mỗi tài khoản được đặt tên theo khóa công khai. Theo mặc định, khóa riêng tương ứng có thể ký giao dịch cho tài khoản. Tuy nhiên, các tài khoản có thể được cấu hình lại để thêm những người ký khác và hủy cấp phép khóa đặt tên cho tài khoản, bằng một Tùy chọn “multisig” để yêu cầu nhiều người ký. Mỗi tài khoản cũng chứa: số thứ tự (có trong giao dịch để tránh phát lại), một số cờ và số dư trong "bản địa" tiền điện tử được khai thác trước có tên là XLM, nhằm giảm thiểu một số cuộc tấn công từ chối dịch vụ và tạo điều kiện thuận lợi cho việc tạo lập thị trường như một loại tiền tệ trung lập. Trustlines theo dõi quyền sở hữu các tài sản đã phát hành, được đặt tên bởi một cặp bao gồm tài khoản phát hành và một tài khoản ngắn hạn mã tài sản (ví dụ: “USD” hoặc “EUR”). Mỗi đường dây tin cậy chỉ định một tài khoản, một tài sản, số dư của tài khoản trong tài sản đó, một vượt quá giới hạn mà số dư không thể tăng lên và một số cờ. Một tài khoản phải đồng ý rõ ràng để nắm giữ một tài sản bằng cách tạo ra một đường dây tin cậy, ngăn chặn những kẻ gửi thư rác tài khoản có tài sản không mong muốn. Quy định về nhận biết khách hàng (KYC) yêu cầu nhiều tổ chức tài chính phải biết họ đang nắm giữ tiền gửi của ai, ví dụ bằng cách kiểm tra ID ảnh. Để tuân thủ, tổ chức phát hành có thể thiết lập cờ auth_reqired tùy chọn trên tài khoản của họ, hạn chế quyền sở hữu tài sản mà họ cấp cho các tài khoản được ủy quyền. Để cấp phép như vậy, người phát hành thiết lập một ủy quyền gắn cờ trên đường tin cậy của khách hàng. Ưu đãi tương ứng với sự sẵn sàng giao dịch của tài khoản một số lượng nhất định của một tài sản cụ thể cho một tài sản khác tại một thời điểm nhất định giá trên sổ lệnh; chúng được tự động khớp và được lấp đầy khi giá mua/bán giao nhau. Cuối cùng, dữ liệu tài khoản bao gồm bộ ba tài khoản, khóa, giá trị, cho phép chủ tài khoản để xuất bản các giá trị siêu dữ liệu nhỏ. Để ngăn chặn thư rác sổ cái, cần có số dư XLM tối thiểu, gọi là dự trữ. Dự trữ của tài khoản tăng lên theo từng mục sổ cái liên quan và giảm khi mục sổ cái biến mất (ví dụ: khi một đơn hàng được thực hiện hoặc bị hủy, hoặc khi một đường dây tin cậy sẽ bị xóa). Hiện tại dự trữ tăng thêm 0,5 XLM (∼$0,03) cho mỗi mục sổ cái. Bất kể dự trữ là gì, nó là có thể lấy lại toàn bộ giá trị của tài khoản bằng cách xóa nó bằng thao tác AccountMerge. Tiêu đề sổ cái, được hiển thị trong Hình 3, lưu trữ các thuộc tính chung: số sổ cái, các thông số như số dư dự trữ trên mỗi mục sổ cái, hash của tiêu đề sổ cái trước đó (thực tế là một số hashes tạo thành danh sách bỏ qua), đầu ra SCP bao gồm hash giao dịch mới được áp dụng vào sổ cái này, hash trong số kết quả của các giao dịch đó (ví dụ: thành công hay thất bại đối với từng mục) và ảnh chụp nhanh hash của tất cả các mục trong sổ cái. Bởi vì ảnh chụp nhanh hash bao gồm tất cả nội dung sổ cái, validator không cần giữ lại lịch sử để xác thực giao dịch. Tuy nhiên, để mở rộng quy mô lên tới hàng trăm triệu dự kiến tài khoản, chúng tôi không thể rehash tất cả các bảng nhập sổ cái trên mỗi sổ cái đóng lại. Hơn nữa, việc chuyển sổ cáiThanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada sổ cái # = 4 H(HDR trước) Đầu ra SCP H∗(kết quả) H∗(ảnh chụp nhanh) ... tiêu đề sổ cái # = 5 H(HDR trước) Đầu ra SCP H∗(kết quả) H∗(ảnh chụp nhanh) ... tiêu đề . . . Hình 3. Nội dung sổ cái. H là SHA-256, trong khi H ∗ thể hiện ứng dụng phân cấp hoặc đệ quy của đầu ra H. SCP cũng phụ thuộc vào tiêu đề trước hash. Tạo tài khoản Tạo và nạp tiền vào sổ cái tài khoản mới Hợp nhất tài khoản Xóa mục nhập sổ cái tài khoản Đặt tùy chọn Thay đổi cờ tài khoản và người ký Thanh toán Trả số lượng tài sản cụ thể cho đích. tài khoản. Đường dẫnThanh toán Giống như Thanh toán, nhưng thanh toán bằng nội dung khác (tối đa hạn chế); chỉ định tối đa 5 tài sản trung gian Quản lý ưu đãi Tạo/xóa/thay đổi mục nhập sổ cái ưu đãi, -Ưu đãi thụ động với biến thể thụ động để cho phép lan truyền bằng không Quản lý dữ liệu Tạo/xóa/thay đổi tài khoản. nhập sổ cái dữ liệu Thay đổi tin cậy Tạo/xóa/thay đổi đường dây tin cậy AllowTrust Đặt hoặc xóa cờ được ủy quyền trên đường dây tin cậy Trình tự va chạm Tăng thứ tự số trên tài khoản Hình 4. Hoạt động sổ cái chính có kích thước đó mỗi khi một nút bị ngắt kết nối khỏi mạng quá lâu. Do đó, ảnh chụp nhanh hash là được thiết kế để tối ưu hóa cả hashing và điều chỉnh trạng thái. Cụ thể, ảnh chụp nhanh phân loại các mục sổ cái theo thời gian sửa đổi cuối cùng trong một tập hợp các thùng chứa có kích thước theo cấp số nhân gọi là xô. Bộ sưu tập các thùng được gọi là thùng danh sách và có một số điểm tương đồng với cây hợp nhất có cấu trúc nhật ký (LSM-cây) [77]. Danh sách nhóm không được đọc trong quá trình xử lý giao dịch (xem Phần 5.4). Do đó, thiết kế nhất định các khía cạnh của cây LSM có thể được nới lỏng. Đặc biệt, ngẫu nhiên không cần truy cập bằng khóa và các nhóm chỉ được đọc tuần tự như một phần của các cấp độ hợp nhất. Băm xô danh sách được thực hiện bằng cách hashing từng nhóm khi nó được hợp nhất và tính toán hash tích lũy mới của nhóm hashes (nhỏ, chỉ số tham chiếu cố định hashes) khi đóng mỗi sổ cái. Điều chỉnh danh sách nhóm sau khi ngắt kết nối yêu cầu tải xuống chỉ có các thùng khác nhau. 5.2 Mô hình giao dịch Một giao dịch bao gồm một tài khoản nguồn, tiêu chí hợp lệ, một bản ghi nhớ và danh sách một hoặc nhiều thao tác. Hình 4 liệt kê các hoạt động có sẵn. Mỗi hoạt động có một tài khoản nguồn, tài khoản này mặc định cho giao dịch tổng thể. Một giao dịch phải được ký bằng các khóa tương ứng với mọi tài khoản nguồn trong một cuộc phẫu thuật. Tài khoản Multisig có thể yêu cầu chữ ký cao hơn trọng lượng cho một số thao tác (chẳng hạn như SetOptions) và thấp hơn cho những người khác (chẳng hạn như AllowTrust). Giao dịch là nguyên tử—nếu bất kỳ thao tác nào thất bại, không có thao tác nào họ thực thi. Điều này đơn giản hóa các giao dịch đa chiều. Giả sử một nhà phát hành tạo ra một tài sản để đại diện cho chứng thư đất đai và người dùng A muốn đổi một thửa đất nhỏ cộng thêm 10.000 USD lấy một thửa đất lớn hơn thuộc sở hữu của B. Hai người sử dụng đều có thể ký một giao dịch duy nhất bao gồm ba hoạt động: hai đất thanh toán và thanh toán một đô la. Tiêu chí hiệu lực chính của giao dịch là số thứ tự của nó, số này phải lớn hơn số thứ tự của giao dịch. mục nhập sổ cái tài khoản nguồn. Thực hiện một giao dịch hợp lệ (thành công hay không) tăng số thứ tự, ngăn chặn việc phát lại. Số thứ tự ban đầu chứa sổ cái số ở bit cao để tránh phát lại ngay cả sau khi xóa và tạo lại tài khoản. Tiêu chí hợp lệ khác là giới hạn tùy chọn khi một giao dịch có thể thực hiện. Trở về đất và đô la hoán đổi trên, nếu A ký giao dịch trước B thì A không được muốn B tham gia giao dịch trong một năm trước khi nộp đơn nó và do đó có thể đặt ra giới hạn thời gian làm mất hiệu lực giao dịch sau một vài ngày. Tài khoản Multisig cũng có thể được cấu hình để tạo sức thuyết phục cho việc tiết lộ hình ảnh trước hash, kết hợp với giới hạn thời gian, cho phép giao dịch chuỗi chéo nguyên tử [1]. Tài khoản nguồn của giao dịch trả một khoản phí nhỏ bằng XLM, 10−5 XLM trừ khi có tắc nghẽn. Dưới tình trạng tắc nghẽn, chi phí hoạt động được thiết lập bởi đấu giá Hà Lan. Trình xác nhận là không được trả phí vì validator tương tự tới Bitcoin nút đầy đủ, không phải công cụ khai thác. Thay vì phá hủy XLM, phí được tái chế và phân bổ theo tỷ lệ bằng phiếu bầu của những người nắm giữ XLM hiện có, mà nhìn lại có thể hoặc có thể không có giá trị phức tạp. 5.3 Giá trị đồng thuận Đối với mỗi sổ cái, Stellar sử dụng SCP để thống nhất về cấu trúc dữ liệu với ba trường: bộ giao dịch hash (bao gồm hash của tiêu đề sổ cái trước đó), thời gian đóng,d nâng cấp. Khi nhiều giá trị được xác nhận đề cử, Stellar sẽ thực hiện tập hợp giao dịch có nhiều hoạt động nhất (phá vỡ mối quan hệ theo tổng phí, sau đó là tập giao dịch hash), liên minh của tất cả nâng cấp và thời gian đóng cao nhất. Một thời gian gần gũi chỉ là hợp lệ nếu nó nằm trong khoảng thời gian đóng của sổ cái cuối cùng và hiện tại, do đó các nút không chỉ định thời gian không hợp lệ. Các bản nâng cấp điều chỉnh các tham số chung như số dư dự trữ, phí hoạt động tối thiểu và phiên bản giao thức. Khi nào được kết hợp trong quá trình đề cử, mức phí cao hơn và số phiên bản giao thức sẽ thay thế mức phí thấp hơn. Nâng cấp hiệu quả quản trị thông qua không gian tranh chấp biểu quyết liên bang [34], cũng không bình đẳng và không tập trung. Mỗi validator được định cấu hình là quản lý hoặc không quản lý (mặc định), theo liệu người điều hành nó có muốn tham gia quản trị hay không. validator quản trị xem xét ba loại nâng cấp: mong muốn, hợp lệ và không hợp lệ (bất cứ điều gì validator không

SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. validator cốt lõi chân trời FS cơ sở dữ liệu cơ sở dữ liệu nộp khách hàng khách hàng validator khác Hình 5. Kiến trúc Stellar validator biết cách thực hiện). Các nâng cấp mong muốn được cấu hình để kích hoạt tại một thời điểm cụ thể, nhằm mục đích phối hợp giữa các nhà khai thác. Các nút quản trị luôn bỏ phiếu để đề cử mong muốn nâng cấp, chấp nhận nhưng không bỏ phiếu để đề cử nâng cấp hợp lệ (tức là tuân theo số đại biểu chặn) và không bao giờ bỏ phiếu cho hoặc chấp nhận nâng cấp không hợp lệ. Tiếng vang validators không quản lý bất kỳ phiếu bầu nào họ thấy cho một bản nâng cấp hợp lệ, về cơ bản là ủy quyền quyết định về những nâng cấp mong muốn đối với những người lựa chọn cho vai trò quản trị. 5,4 Thực hiện Hình 5 hiển thị kiến trúc validator của Stellar. Một con quỷ được gọi là Stellar-core (∼92k dòng C++, không tính thư viện của bên thứ ba) triển khai giao thức SCP và máy trạng thái được sao chép. Việc tạo ra các giá trị cho SCP yêu cầu giảm số lượng lớn các mục sổ cái thành các mật mã nhỏ hashes. Ngược lại, việc xác nhận và thực hiện giao dịch yêu cầu tra cứu trạng thái tài khoản và khớp lệnh tại giá tốt nhất. Để phục vụ cả hai chức năng một cách hiệu quả, Stellar-core giữ hai cách trình bày của sổ cái: một cách trình bày bên ngoài chứa danh sách nhóm, được lưu trữ dưới dạng tệp nhị phân có thể được cập nhật một cách hiệu quả và được rehashed tăng dần, và một biểu diễn nội bộ trong cơ sở dữ liệu SQL (PostgreSQL cho các nút sản xuất). Stellar-core tạo kho lưu trữ lịch sử chỉ ghi có chứa mỗi bộ giao dịch đã được xác nhận và ảnh chụp nhanh của xô. Kho lưu trữ cho phép các nút mới tự khởi động khi tham gia mạng. Nó cũng cung cấp một bản ghi sổ cái lịch sử—cần có một nơi nào đó để người ta có thể tra cứu giao dịch từ hai năm trước. Vì lịch sử chỉ được thêm vào và được truy cập không thường xuyên, nó có thể được giữ ở những nơi rẻ tiền chẳng hạn như Amazon Glacier hoặc bất kỳ dịch vụ nào cho phép một người lưu trữ và truy xuất các tập tin phẳng. Máy chủ xác thực thường không lưu trữ tài liệu lưu trữ của riêng họ để tránh bất kỳ tác động nào đến việc xác thực hiệu suất từ lịch sử phục vụ. Để giữ cho lõi sao đơn giản, nó không được thiết kế để sử dụng trực tiếp bởi các ứng dụng và chỉ hiển thị một giao diện rất hẹp để gửi các giao dịch mới. Để hỗ trợ khách hàng, hầu hết validator đều chạy một daemon có tên là Horizon (∼18k dòng Go) cung cấp giao diện HTTP để gửi và tìm hiểu các giao dịch. Horizon có quyền truy cập chỉ đọc vào cơ sở dữ liệu SQL của Stellar-core, giảm thiểu rủi ro về chân trời làm mất ổn định lõi sao. Các tính năng như tìm đường dẫn thanh toán được triển khai hoàn toàn trong thời gian ngắn và có thể được nâng cấp đơn phương mà không phối hợp với validator khác. Một số daemon lớp cao hơn tùy chọn là ứng dụng khách ở đường chân trời, hoàn thiện hệ sinh thái. Một máy chủ cầu nối tạo điều kiện thuận lợi tích hợp Stellar với các hệ thống hiện có, ví dụ: đăng thông báo về tất cả các khoản thanh toán mà một tài khoản cụ thể nhận được. A máy chủ tuân thủ cung cấp các kết nối cho các tổ chức tài chính để trao đổi và phê duyệt thông tin người gửi và người thụ hưởng về thanh toán, để tuân thủ danh sách trừng phạt. Cuối cùng, một máy chủ liên kết thực hiện cách đặt tên mà con người có thể đọc được hệ thống cho các tài khoản. 6 Kinh nghiệm triển khai Stellar đã phát triển trong vài năm thành một tiểu bang có mức độ phát triển vừa phải số lượng nhà khai thác nút đầy đủ có độ tin cậy hợp lý. Tuy nhiên, cấu hình của các nút sao cho có tính sống động (mặc dù không an toàn) phụ thuộc vào chúng tôi, Quỹ Phát triển Stellar (SDF); SDF đột nhiên biến mất, các nhà khai thác nút khác sẽ cần phải can thiệp và loại bỏ chúng tôi theo cách thủ công từ các lát đại biểu để mạng tiếp tục. Trong khi chúng tôi và nhiều người khác muốn giảm tầm quan trọng mang tính hệ thống của SDF, mục tiêu này ngày càng được ưu tiên hơn sau các nhà nghiên cứu [58] đã định lượng và công khai tính tập trung của mạng mà không phân biệt các rủi ro đối với sự an toàn và sự sống động. Một số nhà khai thác đã phản ứng bằng các điều chỉnh cấu hình tích cực, chủ yếu là tăng kích thước cắt giảm số đại biểu trong nỗ lực làm giảm tầm quan trọng của SDF; Trớ trêu thay, điều này chỉ làm tăng nguy cơ ảnh hưởng đến sự sống. Hai vấn đề làm trầm trọng thêm tình hình. Đầu tiên, một phổ biến công cụ giám sát Stellar của bên thứ ba [5] được thực hiện một cách có hệ thống đánh giá quá cao validator thời gian hoạt động do không thực sự xác minh lõi sao đó đang chạy; điều này khiến mọi người bao gồm các nút không đáng tin cậy trong các lát đại biểu của chúng. Thứ hai, một lỗi trong lõi sao có nghĩa là khi validator được chuyển sang sổ cái tiếp theo, nó không giúp ích đầy đủ cho các nút còn lại hoàn thành giai đoạn trướcsổ cái trong trường hợp mất tin nhắn. Kết quả là, mạng đã trải qua 67 phút ngừng hoạt động và được yêu cầu quản trị viên validator phối hợp thủ công để khởi động lại. Tệ hơn nữa, trong khi cố gắng khởi động lại mạng, việc cấu hình lại vội vàng đồng thời trên nhiều nút đã dẫn đến kết quả là trong một cấu hình sai tập thể cho phép một số nút phân kỳ, yêu cầu tắt thủ công các nút đó và gửi lại các giao dịch được chấp nhận trong thời gian phân kỳ. May mắn thay, sự khác biệt này đã được phát hiện và khắc phục nhanh chóng và không chứa các giao dịch xung đột, nhưng nguy cơ mạng không đạt được giao điểm đại biểu— chia rẽ trong khi vẫn tiếp tục chấp nhận những xung đột tiềm ẩn giao dịch, đơn giản là do cấu hình sai—đã được thực hiện rất cụ thể về sự việc này. Việc xem xét lại những kinh nghiệm này dẫn đến hai kết luận chính và các hành động khắc phục tương ứng.Thanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Quan trọng, 100% 51% 51% Cao, 67% 51% Trung bình, 67% 51% Thấp, 67% 51% 51% ... ... ... 51% ... 51% Hình 6. Phân cấp chất lượng của trình xác thực. Các nút chất lượng cao nhất yêu cầu ngưỡng cao nhất là 100%, trong khi chất lượng thấp hơn được định cấu hình ở ngưỡng 67%. Các nút trong một tổ chức yêu cầu đa số đơn giản là 51%. 6.1 Cấu hình phức tạp và dễ vỡ Stellar biểu thị các lát cắt đại biểu dưới dạng tập hợp đại biểu lồng nhau bao gồm n mục nhập và ngưỡng k trong đó bất kỳ tập hợp k mục nào tạo thành một lát đại biểu. Mỗi mục trong số n mục sau đó là một khóa công khai validator hoặc theo cách đệ quy, một tập đại biểu khác. Mặc dù linh hoạt và nhỏ gọn, chúng tôi đã nhận ra số đại biểu lồng nhau đặt đồng thời các toán tử nút có quá nhiều tính linh hoạt và quá ít hướng dẫn: rất dễ viết không an toàn (hoặc thậm chí là cấu hình vô nghĩa). Tiêu chí phân nhóm các nút thành các tập hợp, để tổ chức các tập hợp con thành một hệ thống phân cấp và để lựa chọn các ngưỡng đều không đủ rõ ràng và góp phần gây ra những thất bại trong hoạt động. Không rõ liệu có nên coi một “cấp độ” trong hệ thống phân cấp lồng nhau là một mức độ tin cậy, hoặc một tổ chức, hoặc cả hai; nhiều cấu hình trong lĩnh vực này trộn lẫn các khái niệm này, ngoài việc xác định mức độ nguy hiểm hoặc ngưỡng vô nghĩa. Do đó chúng tôi đã thêm một cơ chế cấu hình đơn giản hơn phân tách hai khía cạnh của các nhóm đại biểu lồng nhau: nhóm các nút lại với nhau theo tổ chức và gắn nhãn cho mỗi tổ chức bằng một phân loại tin cậy đơn giản (thấp, trung bình, cao hoặc quan trọng). Các tổ chức ở cấp cao trở lên được yêu cầu phải xuất bản kho lưu trữ lịch sử. Hệ thống mới tổng hợp các tập hợp đại biểu lồng nhau trong đó mỗi tổ chức được biểu diễn dưới dạng Đã đặt ngưỡng 51% và các tổ chức được nhóm thành các nhóm với ngưỡng 67% hoặc 100% (tùy chất lượng nhóm). Mỗi nhóm là một mục duy nhất trong nhóm tiếp theo (chất lượng cao hơn), như minh họa trong Hình 6. Mô hình đơn giản hóa này làm giảm khả năng cấu hình sai, cả về mặt cấu trúc của các tập hợp lồng nhau được tổng hợp và các ngưỡng được chọn cho mỗi bộ. 6.2 Chủ động phát hiện cấu hình sai Thứ hai, chúng tôi nhận ra rằng việc phát hiện hành vi cấu hình sai tập thể bằng cách chờ quan sát tác động tiêu cực của nó là quá muộn. Đặc biệt đối với các cấu hình sai có thể khác nhau—a chế độ lỗi nghiêm trọng hơn là tạm dừng—mạng cần có thể phát hiện cấu hình sai ngay lập tức để người vận hành có thể hoàn nguyên cấu hình đó trước khi bất kỳ sự khác biệt nào thực sự xảy ra. Để giải quyết nhu cầu này, chúng tôi đã xây dựng một cơ chế trong phần mềm validator để liên tục thu thập trạng thái cấu hình chung của tất cả các nút ngang hàng trong quá trình đóng chuyển tiếp của nút và phát hiện khả năng phân kỳ—tức là rời rạc nhóm túc số—trong cấu hình tập thể đó. 6.2.1 Kiểm tra giao lộ đại biểu Mặc dù việc thu thập các nhóm đại biểu là điều dễ dàng nhưng việc tìm ra các nhóm túc số rời rạc trong số đó là việc khó [62]. Tuy nhiên, chúng tôi đã thông qua một tập hợp các phương pháp chẩn đoán thuật toán và quy tắc loại bỏ trường hợp được đề xuất bởi Lachowski [62] để kiểm tra các trường hợp điển hình của vấn đề nhanh hơn nhiều bậc so với chi phí trong trường hợp xấu nhất. Thực tế mà nói, mạng hiện tại các lần đóng chuyển tiếp lát cắt đại biểu theo thứ tự 20–30 các nút và, với sự tối ưu hóa của Lachowski, thường kiểm tra chỉ trong vài giây trên một CPU. Nếu có nhu cầu phát sinh để nâng cao hiệu suất, chúng tôi có thể thực hiện tìm kiếm song song. 6.2.2 Kiểm tra cấu hình rủi ro Phát hiện mạng thừa nhận các đại biểu rời rạc là một bước đi đúng hướng nhưng báo nguy hiểm muộn một cách khó chịu đối với một vấn đề quan trọng như vậy. Lý tưởng nhất là chúng tôi muốn các nhà khai thác nút nhận được cảnh báo khi cấu hình chung của mạng chỉ đang tiến đến một trạng thái rủi ro. Do đó, chúng tôi đã mở rộng trình kiểm tra giao điểm đại biểu để phát hiện một điều kiện mà chúng tôi gọi là tới hạn: khi dòng điện cấu hình tập thể chỉ là một cấu hình sai một tiểu bang thừa nhận số đại biểu rời rạc. Để phát hiện mức độ nghiêm trọng, trình kiểm tra liên tục thay thế cấu hình của mỗi tổ chức bằng cấu hình sai mô phỏng trong trường hợp xấu nhất, sau đó chạy lại trình kiểm tra giao điểm đại biểu bên trong trên kết quả. Nếu có bất kỳ cấu hình sai nghiêm trọng nào như vậy tồn tại thì chỉ còn một bước nữa là từ trạng thái hiện tại, phần mềm sẽ đưa ra cảnh báo và báo cáo tổ chức gây ra rủi ro cấu hình sai. Những thay đổi này cung cấp cho cộng đồng các nhà khai thác hai lớp thông báo và hướng dẫn cách ly chống lại các hình thức tồi tệ nhất của việc cấu hình sai tập thể.

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.

Sự đánh giá

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

Để hiểu sự phù hợp của Stellar với tư cách là phương thức thanh toán toàn cầu và mạng lưới giao dịch, chúng tôi đã đánh giá trạng thái của mạng công cộng và chạy các thí nghiệm có kiểm soát trên một phòng thí nghiệm riêng mạng. Chúng tôi tập trung vào các câu hỏi sau: • Cấu trúc liên kết mạng sản xuất trông như thế nào? Trung bình có bao nhiêu tin nhắn được phát đi và SCP trải qua thời gian chờ như thế nào? • Độ trễ đồng thuận và cập nhật sổ cái có còn độc lập với số lượng tài khoản không?SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. • Độ trễ bị ảnh hưởng như thế nào khi tăng (a) giao dịch trên giây (và do đó, giao dịch trên mỗi giây) sổ cái) và (b) số nút validator? • Chi phí chạy một nút tính theo CPU là bao nhiêu, bộ nhớ và băng thông mạng? Mạng thanh toán có tỷ lệ giao dịch thấp so với với các loại hệ thống phân tán khác. blockchain hàng đầu, Bitcoin và Ethereum, xác nhận tối đa 15 giao dịch/giây, nhỏ hơn Stellar. Hơn nữa, các hệ thống này mất vài phút để một giờ để xác nhận giao dịch một cách an toàn, vì bằng chứng công việc yêu cầu phải chờ một số khối được khai thác. các mạng không phảiblockchain SWIFT chỉ đạt trung bình 420 giao dịch mỗi giây vào ngày cao điểm [14]. Do đó chúng tôi đã chọn để so sánh số đo của chúng tôi với mục tiêu 5 giây khoảng thời gian sổ cái, một mục tiêu tích cực hơn. Kết quả của chúng tôi cho thấy độ trễ ở dưới mức giới hạn này một cách thoải mái ngay cả với một số tối ưu hóa chưa được thực hiện vẫn đang được thực hiện. 7.1 Neo Các tài sản được giao dịch nhiều nhất theo khối lượng bao gồm tiền tệ (ví dụ: 3 USD neo, 2 CNY), neo Bitcoin, chứng khoán được hỗ trợ bởi bất động sản token [92] và tiền tệ trong ứng dụng [8]. Các neo khác nhau có chính sách khác nhau. Ví dụ: một mỏ neo USD, Stronghold, đặt auth_reqired và yêu cầu quy trình xác định khách hàng (KYC) cho mọi tài khoản nắm giữ tài sản. Một cái khác, AnchorUSD, để mọi người nhận và giao dịch USD của họ (làm cho việc gửi 0,50 USD đến Mexico theo đúng nghĩa đen là có thể trong 5 giây với mức phí 0,000001 USD). Tuy nhiên, AnchorUSD không yêu cầu KYC và phí để mua hoặc đổi USD của họ với chuyển khoản thông thường. Ở Philippines, nơi các quy định của ngân hàng lỏng lẻo hơn đối với các khoản thanh toán đến, coins.ph hỗ trợ rút tiền PHP tại bất kỳ máy ATM nào [36]. Ngoài bảo mật token và đơn vị tiền tệ trong ứng dụng nói trên, còn có nhiều loại token phi tiền tệ khác nhau, từ trái phiếu thương mại [22] và tín chỉ carbon [85, 96] trở lên nội dung bí truyền chẳng hạn như token khuyến khích cộng tác thu hồi xe [35]. 7.2 Mạng công cộng Tính đến thời điểm viết bài này, có 126 nút đầy đủ đang hoạt động, 66 trong số đó tham gia thống nhất bằng cách ký vào tin nhắn biểu quyết. Hình 7 (được tạo bởi [5]) trực quan hóa mạng, với một đường giữa hai nút nếu một nút xuất hiện trong các lát đại biểu của nút kia và một đường màu xanh đậm hơn để hiển thị sự phụ thuộc hai chiều. Tại trung tâm là một cụm gồm 17 “cấp một validators” trên thực tế được điều hành bởi SDF, SatoshiPay, LOBSTR, COINQVEST và Keybase. Bốn tháng trước, trước sự kiện ở Phần 6, có có 15 nút quan trọng về mặt hệ thống: 3 từ dường như các tổ chức cấp một và một số đơn vị ngẫu nhiên. các biểu đồ cũng trông kém đều đặn hơn nhiều. Do đó, cơ chế cấu hình mới và/hoặc các quyết định vận hành tốt hơn dường như để góp phần tạo nên cấu trúc liên kết mạng lành mạnh hơn. không có nguồn tài chính lớn (và cổ đông tương ứng Hình 7. Bản đồ lát cắt đại biểu nghĩa vụ), sẽ rất khó để tuyển dụng 5 cấp một Tuy nhiên, các tổ chức ngay từ đầu. Điều này cho thấy số đại biểu các lát cắt đóng một vai trò hữu ích trong quá trình khởi động mạng: bất kỳ ai cũng có thể tham gia với mục tiêu trở thành một người chơi quan trọng bởi vì không có người gác cổng để thỏa thuận theo cặp. Hiện có hơn 3,3 triệu tài khoản trong sổ cái. Kết thúc trong khoảng thời gian 24 giờ gần đây, Stellar trung bình có 4,5 giao dịch và 15,7 hoạt động mỗi giây. Xem lại sổ cái gần đây, hầu hết các giao dịch dường như chỉ có một thao tác duy nhất, trong khi cứ một vài giao dịch sổ cái chúng ta thấy các giao dịch chứa nhiều hoạt động dường như đến từ việc các nhà tạo lập thị trường quản lý các chào hàng. các thời gian cần thiết để đạt được sự đồng thuận và cập nhật sổ cái là lần lượt là 1061 ms và 46 ms. Phân vị thứ 99 là 2252 ms và 142 ms (trước đây phản ánh thời gian chờ 1 giây trong việc lựa chọn lãnh đạo đề cử). Lưu ý hiệu suất của SCP là hầu như độc lập với các giao dịch mỗi giây, vì SCP đồng ý với hash nhiều giao dịch tùy ý. Nút thắt có nhiều khả năng phát sinh từ việc tuyên truyền ứng cử viên giao dịch trong quá trình đề cử, thực hiện và xác nhận giao dịch và nhóm hợp nhất. Chúng tôi vẫn chưa cần để song song quá trình xử lý giao dịch của Stellar-Core trên nhiều lõi CPU hoặc ổ đĩa. Chúng tôi cũng đã đánh giá số lượng tin nhắn SCP được phát đi trên mạng sản xuất. Trong trường hợp bình thường với một lãnh đạo được bầu để đề cử một giá trị, chúng tôi mong đợi bảy hợp lý tin nhắn được phát sóng: hai tin nhắn để bỏ phiếu và chấp nhận một nomituyên bố nate, hai tin nhắn để chấp nhận và xác nhận một tuyên bố chuẩn bị, hai tin nhắn để chấp nhận và xác nhận một tuyên bố cam kết và cuối cùng là một thông báo bên ngoài (được gửi sau khi ghi một sổ cái mới vào đĩa để giúp những người đi lạc bắt kịp). Việc thực hiện kết hợp xác nhận cam kết và hiển thị các thông điệp như một sự tối ưu hóa, vì nó an toàn để đưa ra ngoài một giá trị sau khi nó được cam kết. Sau đó, chúng tôi phân tích các số liệu được thu thập trong quá trình sản xuất Stellar validator. Kết thúc trong 68 giờ, 1,3 tin nhắn/giây được phát ra, trung bình có 6-7 tin nhắn trên mỗi sổ cái. Chúng tôi lưu ý rằng tổng

Thanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Phần trăm Số lần hết giờ Đề cử Bỏ phiếu 75% 0 0 99% 1 0 Tối đa 4 1 Hình 8. Thời gian chờ trên mỗi sổ cái hơn 68 giờ số lượng tin nhắn được phát bởi validators lớn hơn vì trong Ngoài các tin nhắn biểu quyết liên kết, các nút còn phát sóng bất kỳ giao dịch nào họ tìm hiểu. Hình 8 cho thấy thời gian chờ của quá trình sản xuất validator trong khoảng thời gian 68 giờ. Thời gian chờ đề cử là thước đo tính hiệu quả (trong) của chức năng bầu cử người lãnh đạo, trong khi thời gian chờ bỏ phiếu phụ thuộc nhiều vào mạng và sự chậm trễ của tin nhắn có thể xảy ra. Thời gian chờ nhất quán với số lượng tin nhắn được phát ra: sáu tin nhắn trong trường hợp tốt nhất và ít nhất bảy tin nhắn nếu cần một vòng đề cử bổ sung. 7.3 Thí nghiệm có kiểm soát Chúng tôi đã tiến hành các thí nghiệm có kiểm soát trong các thùng chứa được đóng gói trên Phiên bản Amazon EC2 c5d.9xlarge có RAM 72 GiB, 900 GB SSD NVMe và 36 vCPU. Mỗi trường hợp nằm trong cùng vùng EC2 và có băng thông cố định 10 Gbps. Chúng tôi đã sử dụng SQLite làm cửa hàng. (Stellar cũng hỗ trợ PostgreSQL, nhưng nó có các tác vụ không đồng bộ gây nhiễu vào các phép đo.) Stellar cung cấp truy vấn thời gian chạy tích hợp, tạo tải, cho phép tạo tải tổng hợp tại một mục tiêu cụ thể giao dịch/tỷ lệ thứ hai. Mặc dù Stellar hỗ trợ nhiều các tính năng giao dịch, chẳng hạn như sổ đặt hàng và đường dẫn tài sản chéo thanh toán, chúng tôi tập trung vào thanh toán đơn giản. Việc xác nhận giao dịch bao gồm nhiều bước, vì vậy chúng tôi ghi lại các phép đo cho mỗi trường hợp sau: • Đề cử: thời gian từ khi đề cử đến khi chuẩn bị lần đầu • Bỏ phiếu: thời gian từ khi chuẩn bị lần đầu đến khi xác nhận phiếu cam kết • Cập nhật sổ cái: thời gian áp dụng giá trị đồng thuận • Số lượng giao dịch: số giao dịch được xác nhận trên mỗi sổ cái Mỗi thử nghiệm của chúng tôi được xác định bởi ba tham số: số lượng tài khoản trong sổ cái, số tiền tải (dưới dạng thanh toán XLM) được gửi mỗi giây, và số lượng validator giây. Chúng tôi đã định cấu hình mọi validator biết về mọi validator khác (trường hợp xấu nhất cho SCP), với các lát đại biểu được đặt thành bất kỳ phần lớn đơn giản nào các nút (để tối đa hóa số lượng đại biểu khác nhau). Đường cơ sở Thử nghiệm cơ bản của chúng tôi đã đo Stellar bằng 100.000 tài khoản, bốn validator và tạo tải tốc độ 100 giao dịch/giây. Chúng tôi quan sát thấy trung bình 507 giao dịch trên mỗi sổ cái, với độ lệch chuẩn là 49. (9,7%). Lưu ý rằng không có giao dịch nào bị hủy; sự nhẹ nhàng 105 106 107 0 500 1.000 1.500 2.000 Tài khoản Độ trễ [ms] Cập nhật sổ cái Bỏ phiếu Đề cử Hình 9. Độ trễ khi số lượng tài khoản tăng lên phương sai là do các hạn chế về lịch trình của bộ tạo tải. Chúng tôi quan sát thấy rằng số lượng giao dịch trên mỗi sổ cái phù hợp với tốc độ tạo tải của chúng tôi, dựa trên sổ cái đóng mỗi 5 giây. Đề cử, bỏ phiếu và sổ cái bản cập nhật cho thấy độ trễ trung bình là 82,53 ms, 95,96 ms và tương ứng là 174,08 ms. Chúng tôi quan sát thấy độ trễ đề cử Phân vị thứ 99 luôn dưới 61 mili giây, thỉnh thoảng tăng đột biến khoảng 1 giây, tương ứng với bước đầu tiên trong chức năng hết thời gian của việc lựa chọn người lãnh đạo. Dựa trên hiệu suất cơ bản, chúng tôi đã xem xét tác động thay đổi từng thông số thiết lập thử nghiệm. Tài khoản Dữ liệu trong Hình 9 gợi ý rằng thang đo Stellar cũng như số lượng tài khoản tăng lên. Tạo thử nghiệm tài khoản đã trở thành một quá trình kéo dài vì việc tạo nhóm và việc hợp nhất đã ngăn cản chúng tôi điền vào cơ sở dữ liệu với các tài khoản trực tiếp qua SQL. Vì vậy, chúng tôi đã tiến hành thử nghiệm cho tối đa 50.000.000 tài khoản. Trong khi có tác động tối thiểu đến sự đồng thuận và độ trễ cập nhật sổ cái, chúng tôi lưu ý rằng việc tăng tài khoản sẽ tạo ra chi phí chung các thùng hợp nhất sẽ lớn hơn. Tỷ giá giao dịch Tỷ giá giao dịch ảnh hưởng đến số lượng lưu lượng truy cập đa hướng giữa validator, số lượng giao dịch có trong mỗi sổ cái và kích thước của cấp cao nhất xô. Để hiểu tác động của việc tăng giao dịch tải, chúng tôi đã chạy thử nghiệm với 100.000 tài khoản và 4 validators. Hình 10 cho thấy độ trễ đồng thuận tăng chậm, trong khi phần lớn thời gian được dành để cập nhật sổ cái. Không có gì ngạc nhiên khi tập giao dịch tăng kích thước, nó mất nhiều thời gian hơn để đưa nó vào cơ sở dữ liệu. Chúng tôi cũng lưu ý rằng độ trễ cập nhật sổ cái phụ thuộc rất nhiều vào việc thực hiện, và bị ảnh hưởng bởi việc lựa chọn cơ sở dữ liệu. Các nút xác thực Để xem số cấp bậc validators tăng như thế nàotác động đến hiệu suất, chúng tôi đã chạy thử nghiệm với 100.000 tài khoản, 100 giao dịch/giây và số lượng validator khác nhau từ 4 đến 43. Tất cả validator đều xuất hiện trong tất cả các phần đại biểu của validator; lát đại biểu nhỏ hơn sẽ có tác động ít hơn đến hiệu suất.SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada Lokhava và cộng sự. 100 150 200 250 300 350 0 500 1.000 1.500 2.000 Tải [giao dịch/giây] Độ trễ [ms] Cập nhật sổ cái Bỏ phiếu Đề cử Hình 10. Độ trễ khi tải giao dịch tăng lên 10 20 30 40 0 500 1.000 1.500 2.000 Trình xác nhận Độ trễ [ms] Cập nhật sổ cái Bỏ phiếu Đề cử Hình 11. Độ trễ khi số lượng nút tăng lên Thay đổi số lượng nút xác thực trên mạng ảnh hưởng đến số lượng tin nhắn SCP được trao đổi cũng như số lượng giá trị tiềm năng trong quá trình đề cử. Hình 11 cho thấy thời gian đề cử tăng với tốc độ tương đối nhỏ. Mặc dù dữ liệu cho thấy việc bỏ phiếu là điểm nghẽn, chúng tôi tin rằng nhiều vấn đề về quy mô có thể được giải quyết bằng cách cải thiện Mạng lớp phủ của Stellar để tối ưu hóa lưu lượng truy cập mạng. Như dự kiến, độ trễ cập nhật sổ cái vẫn độc lập với số lượng nút. Tỷ lệ đóng Cuối cùng, chúng tôi muốn đo lường hiệu suất từ đầu đến cuối của Stellar bằng cách đo tần suất các sổ cái được xác nhận và liệu Stellar có đáp ứng được mục tiêu 5 giây của nó mà không bỏ bất kỳ giao dịch nào. Chúng tôi quan sát thấy sổ cái trung bình đóng lần 5,03 giây, 5,10 giây và 5,15 giây khi chúng tôi tăng tài khoản các mục nhập, tỷ lệ giao dịch và số lượng nút tương ứng. Kết quả cho thấy Stellar có thể đóng sổ cái một cách nhất quán dưới tải cao. 7.4 Đang chạy validator Một trong những tính năng quan trọng của Stellar là chi phí thấp đang chạy validator, vì các neo sẽ chạy (hoặc ký hợp đồng với) validators để thực thi quyết định cuối cùng. SDF chạy 3 validator sản xuất, tất cả đều trên phiên bản AWS c5.large có hai lõi, RAM 4 GiB và CPU Intel(R) Xeon(R) Platinum 8124M @ Bộ xử lý 3.00GHz. Kiểm tra việc sử dụng tài nguyên trên một trong số các máy này, chúng tôi đã quan sát quy trình Stellar bằng cách sử dụng khoảng 7% CPU và 300 MiB bộ nhớ. Về lưu lượng mạng, với 28 kết nối tới các thiết bị ngang hàng và quy mô đại biểu trong số 34, tốc độ đến và đi là 2,78 Mbit/s và tương ứng là 2,56 Mbit/s. Phần cứng cần thiết để chạy như vậy quá trình là không tốn kém. Trong trường hợp của chúng tôi, chi phí là 0,054 USD/giờ hoặc khoảng $40/tháng. 7,5 Công việc tương lai Những thử nghiệm này cho thấy Stellar có thể dễ dàng mở rộng quy mô từ 1–2 đơn hàng có tầm quan trọng vượt xa mức sử dụng mạng ngày nay. Bởi vì nhu cầu về hiệu suất cho đến nay vẫn rất khiêm tốn, Stellar nhường chỗ cho nhiều cách tối ưu hóa đơn giản bằng cách sử dụng những kỹ thuật nổi tiếng. Ví dụ: giao dịch và SCP tin nhắn được phát bởi validator bằng cách sử dụng tính năng tràn ngập đơn giản giao thức, nhưng lý tưởng nhất là nên sử dụng hiệu quả hơn, có cấu trúc hơn phát đa hướng ngang hàng [30]. Ngoài ra, cơ sở dữ liệu nặng Thời gian cập nhật sổ cái có thể được cải thiện thông qua các kỹ thuật phân nhóm và tìm nạp trước tiêu chuẩn.

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

Phần kết luận

Thanh toán quốc tế rất tốn kém và mất nhiều ngày. Quỹ quyền giám hộ đi qua nhiều tổ chức tài chính bao gồm các ngân hàng đại lý và dịch vụ chuyển tiền. Bởi vì mỗi bước nhảy phải được tin cậy hoàn toàn nên rất khó cho các bước nhảy mới. những người tham gia để giành thị phần và cạnh tranh. Stellar trình chiếu cách gửi tiền khắp thế giới với chi phí rẻ chỉ trong vài giây. các cải tiến quan trọng là giao thức thỏa thuận Byzantine dành cho thành viên mở mới, SCP, thúc đẩy cấu trúc ngang hàng của mạng lưới tài chính để đạt được sự đồng thuận toàn cầu theo một giả thuyết Internet mới lạ. SCP cho phép Stellar cam kết nguyên tử giao dịch không thể đảo ngược giữa những người tham gia tùy ý không biết hoặc tin tưởng lẫn nhau. Điều đó đảm bảo cho những người mới tham gia tiếp cận được các thị trường giống như đã được thiết lập người chơi, đảm bảo an toàn để có được trao đổi tốt nhất hiện có ngay cả từ những nhà tạo lập thị trường không đáng tin cậy, và đáng kể giảm độ trễ thanh toán. Lời cảm ơn Stellar sẽ không có được ngày hôm nay nếu không sớm sự lãnh đạo của Joyce Kim hay những đóng góp to lớn của Scott Fleckenstein và Bartek Nowotarski trong việc xây dựng và duy trì chân trời, Stellar SDK và các phần quan trọng khác của hệ sinh thái Stellar. Chúng tôi cũng cảm ơn Kolten Bergeron, Henry Corrigan-Gibbs, Candace Kelly, Kapil K. Jain, Boris Reznikov, Jeremy Rubin, Christian Rudder, Eric Saunders, Torsten Stüber, Tomer Weller, những người đánh giá ẩn danh, và người chăn cừu Justine Sherry của chúng tôi vì những nhận xét hữu ích của họ về những bản thảo trước đó. Tuyên bố từ chối trách nhiệm Đóng góp của Giáo sư Mazières cho ấn phẩm này là một nhà tư vấn được trả lương chứ không phải là một phần trong công việc của ông. Nhiệm vụ hoặc trách nhiệm của Đại học Stanford.

Thanh toán toàn cầu nhanh chóng và an toàn với Stellar SOSP '19, ngày 27–30 tháng 10 năm 2019, Huntsville, ON, Canada