ホワイトペーパー ストーリー 図 用語集 グラフ 検索

O Protocolo de Consenso Stellar

著 David Mazières · 2015

単一表示 stellar.org
🇺🇸 English (原文)
🇧🇷 Português (翻訳)

概要

国際決済は遅くて高価ですが、その理由の 1 つは、異種混合を介したマルチホップ決済ルーティングです。 銀行システム。 Stellar は新しいグローバル決済ネットワークです どこにでもデジタルマネーを直接送金できる 秒単位の世界。重要なイノベーションは安全なトランザクションです 新しいメカニズムを使用した、信頼できない仲介者間のメカニズム SCPと呼ばれるビザンチン協定プロトコル。 SCPでは、それぞれ 機関は、所属する他の機関を指定します 同意します。のグローバルな相互接続を通じて、 金融システムでは、ネットワーク全体がアトミックに同意します。 任意の機関にまたがる取引で、仲介資産発行会社による支払い能力や為替リスクがありません またはマーケットメーカー。 SCP のモデル、プロトコル、および 正式な検証。 Stellar 支払いネットワークについて説明します。 そして最後にベンチマークを通じて Stellar を経験的に評価します そして数年間の実稼働環境での使用経験。 CCS の概念 • セキュリティとプライバシー →分散 システムのセキュリティ。 • コンピュータシステムの組織 → ピアツーピアアーキテクチャ。・情報システム → 電子送金。 キーワード blockchain、BFT、定足数、支払い ACM 参照形式: マルタ・ロカバ、ジュリアーノ・ロサ、デビッド・マジエール、グレイドン・ホア、 ニコラス・バリー、イーライ・ガフニ、ジョナサン・ジョーブ、ラファウ・マリノフスキー、ジェド・マッケイレブ。 2019. Stellar による高速かつ安全なグローバル支払い。 SOSPで ’19: オペレーティング システム原則に関するシンポジウム、10 月 27 ～ 30 日 2019年、カナダ、オンタリオ州ハンツビル。 ACM、米国ニューヨーク州ニューヨーク、17 ページ。 https://doi.org/10.1145/3341301.3359636

Resumo

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

導入

国際支払いは遅くて費用がかかることで有名です[32]。 米国から0.50ドルを送金することが非現実的であることを考えてみましょう。 ※株式会社ガロア †カリフォルニア大学ロサンゼルス校 この作品の全部または一部のデジタルコピーまたはハードコピーを作成する許可 個人または教室での使用は、コピーが行われない限り、無料で許可されます。 営利または商業的利益を目的として作成または配布され、そのコピーには この通知と最初のページの引用全文。コンポーネントの著作権 ACM 以外の者が所有するこの作品は尊重されなければなりません。で抽象化する クレジットは許可されています。別の方法でコピーしたり再公開したり、サーバーに投稿したり、 リストに再配布するには、事前の特定の許可および/または料金が必要です。リクエスト 許可は、[email protected] から取得します。 SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル © 2019 コンピューティング機械協会。 ACM ISBN 978-1-4503-6873-5/19/10...$15.00 https://doi.org/10.1145/3341301.3359636 メキシコ、隣り合う2つの国。エンドユーザーは 9 ドル近くを支払います 平均的な転送[32]と二国間協定の場合 各国の中央銀行が仲介するのは、削減することしかできない 基本的な銀行コストはアイテム [2] あたり 0.67 ドルになります。手数料に加えて、 通常、国際決済の遅延は考慮されます 数日かかるため、すぐに海外でお金を得ることができなくなります 緊急事態。銀行システムが整備されていない国では 仕事をしていないか、すべての国民にサービスを提供していない場合、または手数料が耐えられない場合、人々はバス [38] による支払いに頼ることになります。 ボート [19]、そして時々 Bitcoin [55] によって、すべて リスク、遅延、または不便が生じる可能性があります。 コンプライアンスコストは常に発生しますが、競争の欠如により多額の損失が発生することを示す証拠 [21]、 これは非効率なテクノロジーによってさらに悪化します。人がいる場所 イノベーションが可能になり、価格とレイテンシが下がります。たとえば、2019 年第 2 四半期の銀行口座からの送金には平均で次の費用がかかりました。 6.99% であるのに対し、モバイル マネーの数字は 4.88% [13] にすぎませんでした。 イノベーションを呼び込むオープンでグローバルな決済ネットワーク 銀行以外の組織との競争が激化する可能性がある コンプライアンス [83] を含む、すべてのレイヤーでのコストとレイテンシ。 このペーパーでは、Stellar、blockchain ベースの支払いについて説明します。 イノベーションを促進するために特別に設計されたネットワーク 国際決済における競争。 Stellar が最初です 以下の 3 つの目標をすべて満たすシステム ( 新規だが経験的に有効な「インターネット仮説」): 1. オープンメンバーシップ – 誰でも通貨を裏付けとした発行が可能 ユーザー間で交換できるデジタル token。 2. 発行者による強制的なファイナリティ – token の発行者は、これを防ぐことができます token のトランザクションが取り消されたり取り消されたりすることを防ぎます。 3. 発行者間のアトミック性 – ユーザーはアトミックに交換できる 複数の発行者からの token を取引します。 最初の 2 つを達成するのは簡単です。 Paypal、Venmo、WeChat などの製品をどの企業も一方的に提供できる Pay または Alipay を使用して、支払いの最終性を確保します。 彼らが作った仮想通貨。残念ながら、これらの通貨間でアトミックに取引することは不可能です。実際、 PaypalがVenmoの親会社を買収したにもかかわらず 2013 年になっても、エンドユーザーが Venmo を送信することはまだ不可能です Paypal ユーザー [78] にドル。販売者ができるようになったのは最近になってからです 単一の統合で両方を受け入れることもできます。 目標 2 と 3 はクローズド システムで達成できます。特に、多くの国では効率的な国内決済が行われています。 ネットワークは、通常、広く信頼されている規制当局によって監督されています。ただし会員資格は非公開に限ります 一連のチャータード銀行とネットワークは以下に限定されます。 国の規制当局の管轄範囲。SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 目標 1 と 3 はマイニングされた blockchain で達成されました。 最も顕著なのは、Ethereum [3] 上の ERC20 token の形式です。 これらのblockchainの重要なアイデアは、定住した人々に報酬を与える新しい暗号通貨を作成することです。 トランザクションを元に戻すのは困難です。残念ながら、これは、token 発行者がトランザクションのファイナリティを制御していないことを意味します。ソフトウェアの場合 エラーによりトランザクション履歴が再編成される [26、73]、 あるいは、人をだまして得た戦利品がその費用を超えたとき。 歴史の再編成 [74、97]、発行者はtokens について責任を負う可能性がある 彼らはすでに現実世界のお金と引き換えています。 Stellar blockchain には 2 つの特徴的なプロパティがあります。 まず、token 間の効率的な市場をネイティブにサポートします。 さまざまな発行者からのもの。具体的には、誰でもtokenを発行できます。 blockchain は、token の任意のペア間の取引用の組み込みオーダーブックを提供し、ユーザーはパス支払いを発行できます 複数の通貨ペアにわたってアトミックに取引されますが、 エンドツーエンドの制限価格を保証します。 第二に、Stellar は新しいビザンチン協定を導入します プロトコル、SCP (Stellar コンセンサス プロトコル)、これを介して token 発行者は、強制する特定の validator サーバーを指定します トランザクションのファイナリティ。誰も発行者のvalidator（および基礎となるデジタル署名と 暗号 hashes は安全なままです)、発行者はどのトランザクションが発生したかを正確に把握し、リスクを回避します blockchain 履歴の再編成による損失の増加。 SCP の重要な考え方は、ほとんどの資産発行者が次のような恩恵を受けるということです。 流動性の高い市場であり、アトミックな取引を促進したいと考えています 他の資産と一緒に。したがって、validator 管理者は次のように設定します。 サーバーが他の validator と正確に一致するようにします。 すべての資産に対するすべてのトランザクションの履歴。 validator v1 は次のようになります。 v2 と一致するように構成されているか、v2 が一致するように構成できます v1 と、または両方が相互に一致するように構成できます。 どのような場合でも、どちらもトランザクション履歴にコミットすることはありません。 それは、相手が異なる歴史にコミットできないことを知っています。 推移性により、v1 が v2 に同意できず、v2 が v3 に同意できない場合 (またはその逆)、v1 は v3 に同意できません。 v3、v3 が v1 が聞いたアセットを表すかどうか の。これらの合意関係が仮定されると、 ネットワーク全体を推移的に接続することを SCP が保証します 世界的な協定となり、世界的なビザンチン協定となる オープンなメンバーシップを持つプロトコル。私たちはこの新しい接続性の仮定をインターネット仮説と呼びます。 「インターネット」（誰もがそう理解している）の両方が保持されます。 推移的に接続された単一最大の IP ネットワークを意味します) 従来の国際決済（ホップバイホップ） 非アトミックですが、推移的に接続されたグローバルなネットワークを活用します。 金融機関のネットワーク）。 Stellar は、2015 年 9 月から本番環境で使用されています。 blockchain の長さを管理しやすい状態に保つために、システムは 5 秒間隔の SCP - blockchain 標準では高速ですが、 ビザンチン協定の典型的な適用よりもはるかに遅い。 主な用途は支払いですが、Stellar はまた、 利益をもたらす非金銭代替可能tokenにとって魅力的であることが証明されている 即時流通市場からの取引（セクション 7.1 を参照）。 次のセクションでは、関連する作業について説明します。セクション 3 の紹介 SCP。セクション 4 では、SCP の正式な検証について説明します。セクション 5 では、Stellar の支払いレイヤーについて説明します。セクション 6 に関連する 導入の経験と学んだ教訓の一部。 セクション 7 ではシステムを評価します。セクション 8 は終了です。

Introdução

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

Stellar コンセンサスプロトコル

Stellar コンセンサス プロトコル (SCP) はクォーラムベースの オープンメンバーシップを備えたビザンチン協定プロトコル。クォーラムは、個々のノードのローカル構成の決定を組み合わせて生成されます。ただし、ノードは認識するだけです 自分自身が所属する定員会に参加した後のみ、 他のすべての定足数メンバーのローカル構成を学習します。このアプローチの利点の 1 つは、SCP が本質的に どのようなノードが存在するかについての異種のビューを許容します。したがって、 ノードは一方的に参加したり離脱したりできます。 メンバーシップを調整するための「ビュー変更」プロトコル。 3.1 ビザンチン連邦協定 伝統的なビザンチン協定の問題は次のようなもので構成されています。 N 個のノードからなるクローズド システム。そのうちのいくつかには障害があり、 恣意的に行動する。ノードは入力値を受け取り、交換します。 入力の中から出力値を決定するためのメッセージ。 ビザンチン協定プロトコルは、行儀の良い 2 つのノードが異なる決定を出力せず、一意の決定を出力しない場合には安全です。 決定は有効な入力でした（有効な合意の定義にとって）SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 事前に）。プロトコルが有効であることは、それが保証する場合に有効です。 すべての正直なノードは最終的に決定を出力します。 通常、プロトコルは整数に対して N = 3f + 1 を想定します。 f > 0 の場合、安全性と何らかの形の生存性が保証されるため、 最大でも f 個のノードに障害がある限り。これらのある段階で、 プロトコル、ノードは提案された値と提案に投票します 投票の定足数と呼ばれる 2f + 1 票を受け取ると、 決定。 N = 3f + 1 ノードの場合、任意の 2 つのクォーラム サイズ 2f + 1 は少なくとも f + 1 ノードでオーバーラップします。たとえこれらのうちの 重複するノードに障害がある場合、2 つのクォーラムは少なくとも共有します 障害のない 1 つのノードにより、矛盾した決定が防止されます。 ただし、このアプローチは、すべてのノードが同意する場合にのみ機能します。 定足数を構成するものは何ですか。SCP では不可能です。 2 つのノードは互いの存在を知らない場合もあります。 SCP では、各ノード v が一方的にノードのセットを宣言します。 (a) v は、すべての場合に次のように信じます。 スライスのメンバーがシステムの状態について同意すると、 彼らは正しく、(b) v はそのスライスの少なくとも 1 つが、 に関するタイムリーな情報を提供できるようになります。 システムの状態。結果として得られるシステムを次のように呼びます。 ノードとそのスライスの統合ビザンチン協定 （FBA）システム。次に見るように、定足数システムが登場します ノードのスライスから。 非公式には、FBA ノードのスライスは誰との関係を表します。 ノードには同意が必要です。たとえば、ノードには、それぞれ 3 つのノードを実行する 4 つの特定の組織との合意が必要な場合があります。に ダウンタイムに対応するため、スライスをすべてのセットに設定する場合があります 各組織の 2 つのノードで構成されます。これが「必要な場合」 「一致」関係は任意の 2 つのノードを推移的に関連付けます。 世界的な合意が得られます。そうしないと、発散が発生する可能性があります。 ただし組織間のみであり、どちらの組織も必要ありません 相手との合意。今日のトポロジーを考えると、 金融システムでは、広範な収束が人々が呼ぶ単一の元帳履歴を生み出し続けると仮説を立てています。 私たちがインターネットについて話すのと同じように、「Stellar ネットワーク」です。 クォーラムは次のようにスライスから生成されます。すべてのノードが指定します 送信するすべてのメッセージのクォーラム スライスが発生します。 S を 一連のメッセージの発信元となるノードのセット。あ ノードは一連のメッセージがクォーラムに達したとみなします。 S のすべてのメンバーが S に含まれるスライスを持つ場合のしきい値。 構造上、そのような集合 S は、全員一致であれば、次の条件を満たします。 各メンバーの同意要件。 障害のあるピアは、内容を変更するために作成されたスライスをアドバタイズする可能性があります。 正常に動作するノードはクォーラムを考慮します。プロトコル分析のために、FBA のクォーラムは空ではないものとして定義されます。 少なくとも 1 つのクォーラム スライスを含むノードのセット S 欠陥のない各メンバー。他のセットと同様に、この抽象化は健全です 全会一致の定足数を表すと称するメッセージの数 実際には (障害のあるノードからのメッセージが含まれている場合でも)、 そして、S に行儀の良いノードのみが含まれている場合は正確です。で このセクションでは、ノードのスライスは変更されないと仮定します。 それにもかかわらず、私たちの結果はスライス変更の場合に当てはまります。 なぜなら、スライスが変化するシステムは安全であることに劣らないからです。 ノードのスライスがすべての要素で構成される固定スライス システム。 スライス変更の場合に使用するスライス (定理を参照) [68] の 13)。セクション 4 で説明したように、活性度は以下に依存します。 行儀の良いノードは最終的に信頼性の低いノードを削除します 彼らのスライスから。 異なるノードには異なる合意要件があるため、FBA では安全性のグローバルな定義が妨げられます。私たちは言います 障害のないノード v1 と v2 が絡み合っているのは、 v1 のクォーラムが少なくとも 1 つで v2 のすべてのクォーラムと交差します。 障害のないノード。 FBAプロトコルにより合意を保証できる 絡み合ったノード間のみ。 SCP がそうするのですから、SCP のせいです 安全性に対する許容度は最適です。インターネット仮説、 Stellar の設計の根底にあるのは、人々が気にかけているノードであると述べています について絡みます。 I の外側のすべてのノードに障害がある場合でも、I のすべての 2 つのメンバーが絡み合っているような、一様に障害のないクォーラムである場合、ノードのセット I は無傷であると言います。直感的には、 それなら、私は無傷でない者の行為に影響されないようにする必要があります ノード。 SCP は、ノンブロッキングな生存性 [93] と ノード自体は必要ありませんが、無傷のセットに対する安全性 どのセットが無傷であるかを知るためです (また、知ることができない場合もあります)。 さらに、交差する 2 つのそのままのセットの和集合は次のようになります。 無傷のセット。したがって、そのままのセットは、 各パーティションが安全で稼働している、正常に動作するノード (条件によっては)ただし、異なるパーティションが出力する場合があります 異なる決定。 3.1.1 FBA における安全性と生存性の考慮事項 限られた例外 [64] を除いて、ほとんどの終了したビザンチン協定プロトコルは、均衡点に調整されています。 安全性と活性性は同じ耐障害性を持っています。 FBAでは、 つまり、障害に関係なく、すべての 絡み合ったセットもそのままです。 FBAが判断した場合、 分散型のクォーラムでは、個々のスライスの選択がこの均衡につながる可能性は低いです。さらに、 少なくともStellarでは、均衡は望ましくない: その結果 安全上の欠陥（デジタルマネーの二重使用）は、 liveness 障害 (つまり、遅延) よりもはるかに悪いです。 いずれにしても Stellar までに数日かかった支払いの場合）。人々 したがって、次のような大きなクォーラム スライスを選択する必要がありますし、実際に選択する必要があります。 それらのノードは無傷よりも絡み合ったままになる可能性が高くなります。 さらに状況が悪化すると、回復が容易になります。 FBA システムでは、従来のクローズドシステムよりも一般的な liveness 障害が発生します。閉じたシステムでは、すべてのメッセージは次のとおりである必要があります。 同じクォーラムのセットに関して解釈されます。したがって、 障害から回復するためにノードを追加および削除するには、次のことが必要です 再構成イベントについて合意に達することですが、合意が得られなくなると困難になります。それに対してFBAの場合は、 どのノードもクォーラム スライスをいつでも一方的に調整できます。 時間。システム上重要なシステムの停止に対応して 組織では、ノード管理者はスライスを次のように調整できます。 対応を調整するような感じで問題を回避する BGP の大惨事 [63] まで (ただし、次のような制約はありません) 物理ネットワークリンクを介したルーティング）。

Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル 3.1.2 カスケード定理 SCP は、基本的なラウンド モデル [42] のテンプレートに従います。 ノードは一連の番号付き投票を進めていきます。 3 つのタスクを試みます：（1）以前の投票の決定と矛盾しない「安全な」値を特定します（よくこのように呼ばれます） (2) 安全値に同意し、(3) 同意が成功したことを検出します。ただし、FBAは開いています メンバーシップはいくつかの一般的な手法を妨げ、 従来のクローズドプロトコルをFBAに「移植」することは不可能 クォーラムの定義を変更するだけでモデルを構築できます。 多くのプロトコルで採用されている手法の 1 つがローテーションです。 タイムアウト後にラウンドロビン方式でリーダー ノードを経由します。クローズド システムでは、ラウンドロビンのリーダー選択により確実に 最終的には、唯一無二の誠実なリーダーが、単一の価値観についての合意を調整することになるのです。残念ながらラウンドロビン メンバーシップが不明な FBA システムでは機能できません。 FBA で失敗するもう 1 つの一般的なテクニックは、特定のクォーラムがすべてのノードを説得できると想定することです。たとえば、 全員が 2f + 1 ノードをクォーラムとして認識すると、 2f + 1 署名は、すべてのノードに対してプロトコル状態を証明するのに十分です。 同様に、ノードが同一のメッセージのクォーラムを受信した場合、 信頼性の高いブロードキャスト [24] を通じて、ノードは障害のないすべてのノードにもクォーラムがあると想定できます。対照的に、FBA では、 クォーラムは、クォーラム外のノードにとっては何の意味も持ちません。 最後に、非連合システムは「逆方向」を使用することがよくあります。 安全性に関する推論: f + 1 ノードに障害がある場合、すべてが安全である 保証は失われます。したがって、ノード v が f + 1 ノードすべてを聞くと、 何らかの事実を述べる F、v は、少なくとも 1 人が、 安全性を損なうことなく、真実（したがって F は真実）になります。そんな 安全性はペアの特性であるため、FBA では推論が失敗します ノードの数が多いため、一部のピアに対して安全性を失ったノードは、 悪い事実を仮定することにより、常により多くのノードの安全性が失われます。 ただし、FBA はライブ性について逆に推論することができます。 v ブロッキング セットを、すべてのノードと交差するノードのセットとして定義します。 v のスライス。v ブロッキング セット B が満場一致で欠陥がある場合、B ノードとクォーラムを拒否し、活性を損なう可能性があります。したがって、もし B が満場一致で事実 F を述べた場合、v はいずれかの F が true または v はそのままではありません。ただし、v はまだ完全なものを確認する必要があります。 絡み合ったノードが F と矛盾しないことを知るための定足数、 これはSCPでのコミュニケーションの最終ラウンドにつながり、 類似のプロトコルでは必要のない他の FBA プロトコル [47] 非公開メンバーシッププロトコル。その結果、 潜在的な事実に対する信頼度の 3 つの可能なレベル: 不確定、無傷のノード間で想定しても安全 (これについては後で説明します) 用語は受け入れられた事実）、絡み合っていると想定するのが安全です ノード（これを確認された事実と呼びます）。 ノード v は、セット B がそのすべてのスライスと交差するかどうかをチェックすることで、セット B が vblocking かどうかを効率的に判断できます。興味深いことに、ノードが常にステートメントをアナウンスする場合、 accept し、フルクォーラムがステートメントを受け入れると、ステートメントが全体に伝播するカスケード プロセスが開始されます。 無傷のセット。この伝播の根底にある重要な事実を カスケード定理は次のことを述べています。 そのままのセット、Q は I の任意のメンバーの定足数、S は任意のメンバー Q のスーパーセットの場合、S ⊇I か、メンバー v ∈I が存在します。 v < S および I ∩S は v ブロッキングです。直感的には、これでしたか そうでない場合、S の補数には定足数が含まれます。 これは I と交差しますが、Q とは交差せず、クォーラム交差に違反しています。 S = Q から始めて S を繰り返し拡張すると、 ブロックするすべてのノードを含めると、次のようなカスケード効果が得られます。 最終的に、S は I のすべてを包含します。 3.2 プロトコルの説明 SCP は、部分同期コンセンサス プロトコル [42] であり、コンセンサスに達するための一連の試みで構成されます。 投票用紙。投票では、継続時間が長くなるタイムアウトが採用されます。あ 投票同期プロトコルにより、ノードが確実に稼働状態に維持されます。 投票用紙が届くまでの期間が長くなり、同じ投票用紙が使用される 事実上同期しています。終了は保証されません 投票が同期されるまで、ただし 2 つの同期投票 正常に動作するノードのスライスの欠陥のあるメンバーがそうなる SCP が終了するには、干渉しないだけで十分です。 投票プロトコルは、投票ごとに実行されるアクションを指定します。 投票用紙。投票は準備フェーズから始まります。 矛盾しない提案する値を決定してください 以前の決定。次に、コミットフェーズで、ノードは次のことを試みます。 準備された値に基づいて決定を行います。 投票には、連合投票と呼ばれる合意サブプロトコルが使用されます。n どのノードが抽象ステートメントに投票するか それは最終的に確認されるか、行き詰まる可能性があります。一部の記述は矛盾しているとみなされる可能性があり、安全性は 連合投票の保証は、2 人のメンバーが連合投票を行わないことです。 絡み合ったセットは矛盾したステートメントを裏付けます。ステートメントが無傷である場合を除き、ステートメントの確認は保証されません メンバー全員が同じように投票するセット。ただし、 完全なセットのメンバーがステートメントを確認します。フェデレーテッド 投票により、無傷のセットのすべてのメンバーが最終的にそのステートメントを確認することが保証されます。そこで、取り返しのつかない措置を講じる 確認ステートメントに応じて、生存期間を維持します 無傷のノード。 ノードは最初に、候補から取得した値を提案します。 メンバー全員が無傷である可能性を高めるプロトコル 同じ値を提案する集合、そして最終的には収束する (ただし、収束が完了したかどうかを判断する方法はありません)。 指名は、連合による投票とリーダーの選択を組み合わせたものです。 FBAでは総当たりが不可能なため、指名は 確率的なリーダー選択スキーム。 カスケード定理は投票においても重要な役割を果たします。 同期を確立し、ブロック状態を回避します。 終了はもう不可能です。 3.2.1 投票 SCP ノードは一連の番号付き投票を進め、連合投票を利用して以下の声明に同意します。 値はどの投票用紙で決定されるか決定されません。非同期の場合 または、誤った行動により投票番号 n での決定に達することができません。 ノードがタイムアウトになり、投票 n + 1 で再試行します。

SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 連合投票が終了しない可能性があることを思い出してください。したがって、いくつかの 投票用紙に関する発言は永久に固定化される可能性があります ノードがその状態にあるかどうかを決して判断できない不定状態。 まだ進行中か停止中です。ノードは除外できないため 不確定な発言が後で真実であることが判明する可能性、 新しい声明に対する連合投票を決して試みてはなりません 矛盾する不定なもの。 各投票 n では、ノードは 2 つのタイプの連合投票を使用します。 ステートメントの: • prepare ⟨n,x⟩ – x 以外の値がないことを示します n 以内の投票で決定された、または今後決定されることになります。 • commit ⟨n,x⟩ – x が投票 n で決定されると述べます。 重要なのは、prepare ⟨n,x⟩ は commit に矛盾することに注意してください。 ⟨n′,x ′⟩ n ≧ n′かつ x , x ′のとき。 ノードは、投票 n に対して連合投票を試みることによって開始します。 ステートメントは ⟨n,x⟩ を準備します。以前の準備ステートメントがある場合 連合投票により無事確認されました。 ノードは、確認された最高の投票用紙から x を選択します。それ以外の場合、ノードは x を 指名プロトコルについては次のサブセクションで説明します。 ノードが ⟨n,x⟩ の準備を正常に確認した場合にのみ 投票 n では、コミット ⟨n,x⟩ で統合投票を試みます。もし それが成功した場合、SCP が決定したことを意味するため、ノードは次のように出力します。 確認されたコミットステートメントの値。 絡み合った集合 S を考えてみましょう。値は 1 つだけなので、 特定の投票用紙で S のメンバーが作成したものであることを確認できますが、2 つの異なる値がコミットされたことを確認することはできません。 特定の投票用紙に含まれる S のメンバー。さらに、 commit ⟨n,x⟩ の場合 が確認されたら、⟨n,x⟩ を準備することも確認されました。それ以来 prepare ⟨n,x⟩ は、フェデレーション投票の合意保証により、異なる値に対する以前のコミットと矛盾します。 異なる値が以前に決定されることはないことがわかります。 S のメンバーによる投票。投票番号の誘導により、 したがって、SCP は安全であることがわかります。 生存性については、無傷のセット I と十分に長いものを考慮してください。 同期投票 n.スライスに障害のあるノードが現れた場合 行儀の良いノードのうち、n に干渉しないノードは投票によって決定されます n + 1 I のすべてのメンバーは、prepare ステートメントの同じ集合 P を確認しました。 P = ∅で投票用紙 n が十分に長い場合、 指名プロトコルは、ある値 x に収束します。 それ以外の場合、x を P で最も高い投票数を持つ準備からの値とします。いずれにしても、私は一律にフェデレーションを試みます。 次の投票で⟨n + 1,x⟩を準備することに投票します。したがって、もし n + 1 も同期しているため、必然的に x の決定が続きます。 3.2.2 指名 指名には、以下の声明に対する連合投票が必要となります。 • nominate x – x が有効な決定候補であると述べます。 ノードは、複数の値 (異なる値) を指名するために投票することができます。 指名発言は矛盾していない。ただし、一度、 ノードは任意の指名ステートメントを確認すると、投票を停止します。 新しい価値観を提案します。フェデレーション投票により、ノードは引き続き次のことを行うことができます。 投票しなかった新たな指名声明を確認する。 投票または承認 定足数から 受け入れる 定足数から は有効です からのを受け入れる ブロッキングセット コミットされていない に投票した を受け入れました を確認した に投票しました 図 1. 連合投票の段階 完全なセットのメンバーがお互いのことを確認できるようになります。 新たな投票を保留しながら、ノミネートされた値を変更します。 指名の (進化する) 結果は、確認された指名ステートメント内のすべての値の決定論的な組み合わせです。もし x はトランザクションのセットを表し、ノードは和集合を取ることができます セットの中で、最大のセット、または最も高い hash を持つセット、つまり すべてのノードが同じことを行う限り。ノードが新規を保留しているため 1 つの指名発言を確認した後に投票します。 確認されたステートメントには、有限個の値のみを含めることができます。 確認された声明が確実に拡散したという事実 無傷のセットとは、無傷のノードが最終的に 候補値のセットが同じであるため、候補結果が得られます。 ただし、プロトコルの後半の未知の時点で任意に行われました。 ノードはフェデレーテッド リーダー選択を採用して、 nominate ステートメント内の異なる値の数。のみ 指名声明にまだ投票していない指導者は、新しい × を導入することができます。他のノードはメッセージの受信を待機します リーダーの（有効な）指名投票をコピーするだけです。 失敗に対応するために、リーダーのセットは成長し続けます。 タイムアウトが発生しますが、実際には x の新しい値を導入するノードはわずかです。 3.2.3 連合投票 連合投票では、以下に示す 3 段階のプロトコルが採用されています。 図 1. ノードは最初に抽象ステートメントに同意しようとします 投票し、次に承認し、最後に声明を確認します。 ノード v は、有効なステートメント a に投票できます。 他と矛盾する未決の投票数と受け入れられた声明。これは、署名された投票メッセージをブロードキャストすることによって行われます。 v 次に、a が他の受け入れられたステートメントと一致しており、かつ (ケース 1)v が次のクォーラムのメンバーである場合に、a を受け入れます。 各ノードは、a に投票するか、a を受け入れるか、または (ケース 2) v の場合でも a に投票しませんでしたが、v ブロッキング セットは a を受け入れます。ケース 2 の場合、v は 以前に a に反対する票を投じたことがあるが、現在は 却下されました。 v 否決された投票については忘れてもよい そして、もしvが無傷なら、それは知っているので、それらをキャストしなかったふりをします 否決された投票では、ケース 1 によって定足数を満たすことはできません。 v a を受け入れることをブロードキャストし、それが入っているときに a を確認します。 全会一致で承認する定足数。図 2 は、 v ブロック集合とカスケード定理の効果 連合投票。 2 つの必要なクォーラムが共有する必要があるため、絡み合った 2 つのノードは矛盾するステートメントを確認できません。Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル 3 4 2 1 5 7

Stellar protocolo de consenso

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

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

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

X に投票

Yに投票 (a) 3 4 2 1 5 7 6 投票する × 投票する × 投票する × 投票する Y 投票する × 投票する Y 投票する Y (b) 3 4 2 1 5 7 6 受け入れる × 投票する × 受け入れる × 投票する Y 受け入れる × 投票する Y 投票する Y (c) 3 4 2 1 5 7 6 受け入れる × 受け入れる × 受け入れる × 投票する Y 受け入れる × 受け入れる × 投票する Y (d) 3 4 2 1 5 7 6 受け入れる × 投票する × 受け入れる × 受け入れる × 受け入れる × 受け入れる × 受け入れる × (e) 図 2. 連合投票におけるカスケード効果。各ノードには、スライスのメンバーへの矢印で示される 1 つのクォーラム スライスがあります。 (a) 矛盾したステートメント X と Y が導入されます。 (b) ノードは有効なステートメントに投票します。 (c) ノード 1 はクォーラムの後に X を受け入れます {1, 2, 3, 4} は全会一致で X に投票します。(d) ノード 1、2、3、および 4 はすべて X を受け入れます。セット {1} は 5 ブロッキングであるため、ノード 5 は X を受け入れ、これを無効にします。 (e) セット {5} は 6 および 7 ブロックであるため、6 と 7 は両方とも X を受け入れます。 矛盾していないステートメントを受け入れることができない障害のないノード。ステートメントの確認は保証されていません: 投票が分かれた場合、両方の声明が永久に残る可能性がある 投票フェーズで定足数に達するのを待っている状態です。ただし、 無傷のセット内のノード 私はステートメント、カスケードを確認します 定理とケース 2 を受け入れると、最終的にはすべてが確実に その発言を確認します。 3.2.4 投票用紙の同期 ノードがコミットステートメントを確認できない場合、 現在の投票では、タイムアウト後にギブアップします。タイムアウトが発生する 任意の範囲に調整するために投票ごとに長くする ネットワーク遅延について。 ただし、タイムアウトだけでは、同時に開始されなかったノードの投票を同期するには十分ではありません。 他の理由で非同期になりました。同期を実現するために、ノードはノードの一部になったときにのみタイマーを開始します。 現在 (または今後) の投票ですべての定足数 n.これ 早期に起動したノードの速度を低下させ、 無傷のセットのメンバーがグループよりもはるかに先にいる。 さらに、ノード v が後で v-blocking セットに気づいた場合 投票の場合、すぐに最下位の投票にスキップします。 タイマーに関係なく、これはもう当てはまりません。カスケード 定理により、すべての落伍者が確実に追いつきます。結果 投票用紙は無傷の組織全体でほぼ同期されているということです。 システムが同期状態になると設定されます。 3.2.5 連合リーダーの選択 リーダーの選択により、各ノードがそのようなリーダーを選択できるようになります。 ノードが通常 1 つまたは少数の数だけを選択する方法 リーダーたちの。リーダーの失敗に対応するためのリーダーの選択 ラウンドを経て進みます。現在のラウンドのリーダーの場合 責任を果たしていないように見え、その後、 特定のタイムアウト期間のノードは次のラウンドに進みます。 彼らが従うリーダーの集団を拡大します。 各ラウンドでは、[0,hmax) の範囲の整数を出力する 2 つの固有の暗号化関数 hash 関数 H0 と H1 が使用されます。 たとえば、Stellar は Hi(m) = SHA256(i∥b∥r ∥m) を使用します。 b は SCP インスタンス全体 (ブロックまたは台帳番号)、r は リーダー選択ラウンド番号、および hmax = 2256。 ラウンドでは、ノード v の優先順位を次のように定義します。 優先度(v) = H1(v) 各ノードで 1 人のストローマンがリーダーとして選択されます 最も高い優先順位を持つノード (v)。このアプローチは機能します ほぼ同一のクォーラム スライスでは問題ありませんが、正しく動作しません 不均衡な構成におけるノードの重要性を把握します。たとえば、ヨーロッパと中国がそれぞれ 3 を貢献した場合、 すべてのクォーラムにノードを追加しますが、中国が 1,000 ノード、ヨーロッパが 4 ノードを実行すると、中国が 99.6% の優先順位の最も高いノードを持つことになります。 当時の。 したがって、スライス重みの概念を導入します。 Weight(u,v) ∈[0, 1] はノード u のクォーラム スライスの割合です ノード v を含む。ノード u が新しいリーダーを選択するとき、 次のように定義される近傍のみを考慮します。 隣人(u) = { v | H0(v) < hmax · 重み(u,v) } 次に、ノードは空のリーダーのセットから開始され、それぞれのリーダーで ラウンドは、最も高い値を持つneighbors(u)のノードvをそれに追加します。 優先度(v)。いずれかのラウンドで近隣セットが空の場合、u は代わりに H0(v)/weight(u,v) の最小値を持つ nodev を追加します。

Votar X

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

SCPの正式な検証

設計ミスを排除するために、SCP の安全性を正式に検証しました および liveness プロパティ ([65] を参照)。具体的に検証したところ、 絡み合ったノードは決して意見が一致せず、以下で説明する条件下では、無傷のセットのすべてのメンバーが最終的に決定するということです。興味深いことに、検証の結果、 SCPが生存を保証する条件は微妙ですが、 そして当初考えられていたよりも強力です [68]: 以下で説明するように、 意図せずにタイミングを操作する悪意のあるノード プロトコルから逸脱すると、手動で削除する必要がある場合があります クォーラムスライスから。

SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 証明された特性がすべての可能な状況に当てはまることを確認するため FBA の構成と実行については、任意のものを考慮します。 任意のローカル構成を持つノードの数。これ これには、結合されていないそのままのセットを含むシナリオや、無限に長い実行が発生する可能性のあるシナリオが含まれます。欠点は、私たちが パラメータ化されたパラメータを検証するという困難な問題に直面しています 無限状態システム。 検証を扱いやすくするために、Ivy [69] と [82] の方法論を使用して、一次ロジック (FOL) で SCP をモデル化しました。 検証プロセスは、帰納的推測を手動で提供することで構成され、その後、それが自動的にチェックされます。 アイビー。 SCP の FOL モデルは、SCP のいくつかの側面を要約しています。 FOL での取り扱いが難しい FBA システム（例: カスケード定理を公理として採用します）ので、次を検証します。 Isabelle/HOL [75] を使用した抽象化の健全性。 FOLで検証問題を表現した後、帰納的不変量を与えることで安全性を検証します。帰納的 不変式は、約 10 個の 1 行の推測で構成されます 150 行のプロトコル仕様。次に、Ivy の線形時間論理で SCP の活性プロパティを指定し、 生存性を安全性まで減らす [80, 81] の生存性を減らす 検証問題から帰納法を見つける問題へ 不変。 SCP の安全性は比較的簡単ですが、 証明してください、SCP の生存に関する議論ははるかに複雑であり、 約 150 の単一行の不変式で構成されます。 生きていることを証明するには、 SCP が終了を保証する前提。私たちは当初、無傷のセットをすべて削除した場合に常に終了すると考えていました。 メンバーはスライス [68] から障害のあるノードを削除しました。しかし、これでは不十分であることが判明しました。 完全ではありません) I can のメンバーのクォーラム内のノード。 障害ノードの影響、完了による終了を防止 投票終了直前に定足数に満たないため、 I のメンバーは、次の投票で x の異なる値を選択します。 したがって、非公式には次のように仮定する必要があります。 I のメンバーのクォーラム内の各ノードは、最終的に次のいずれかを実行します。 タイムリーになるか、十分な期間メッセージをまったく送信しません。実際には、これは、I のメンバーが 条件が整うまでスライスを調整する必要があります。これ この問題は FBA システムに固有のものではありません: Losa et al. [47] 現在 活性が厳密に弱いプロトコルに依存するプロトコル スライスから障害のあるノードを削除する必要がなく、最終的には同期が行われ、最終的にはリーダーが選出されると仮定します。

Verificação formal do SCP

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

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

決済ネットワーク

このセクションでは、SCP 上に複製されたステート マシン [88] として実装された Stellar の支払いネットワークについて説明します。 5.1 台帳モデル Stellar の台帳は、アカウントの抽象化を中心に設計されています ( よりコイン中心の未使用トランザクション出力とは対照的です または Bitcoin の UTXO モデル)。台帳の内容は次のもので構成されます。 アカウント、トラストライン、 オファー、およびアカウントデータ。 アカウントは、資産を所有および発行する主体です。それぞれ アカウントは公開キーによって名前が付けられます。デフォルトでは、対応する秘密キーでアカウントのトランザクションに署名できます。 ただし、アカウントを再構成して、他の署名者を追加し、アカウントに名前を付けるキーの認証を解除することはできます。 複数の署名者を必要とする「multisig」オプション。各アカウント シーケンス番号 (トランザクションに含まれる) も含まれます。 リプレイを防ぐため）、いくつかのフラグ、および「ネイティブ」のバランス XLM と呼ばれる、事前に採掘された仮想通貨で、被害を軽減することを目的としています。 一部のサービス拒否攻撃を防止し、市場形成を促進します 中立通貨として。 トラストラインは、発行された資産の所有権を追跡します。 発行アカウントと短いアカウントからなるペアで名前が付けられます。 資産コード (例: 「USD」または「EUR」)。各トラストラインは次のように指定します 口座、資産、その資産の口座残高、 それを超えると残高が上昇できない制限と、いくつかのフラグ。 アカウントは、次の方法で資産の保有に明示的に同意する必要があります。 トラストラインを作成し、スパマーのサドルを防止します 不要な資産を含むアカウント。 顧客確認 (KYC) 規制により、多くの金融機関は誰の預金を保有しているかを把握する必要があります。 たとえば写真付き身分証明書を確認することによって。準拠するために、発行者は設定できます アカウントにオプションの auth_reqired フラグを設定し、発行するアセットの所有権を承認されたアカウントに制限します。 このような認可を与えるために、発行者は認可された権限を設定します。 顧客のトラストラインにフラグを立てます。 オファーはアカウントの取引意欲に対応します 特定の資産の一定量を、特定の時点で別の資産に割り当てる 注文簿上の価格。それらは自動的に照合され、 買値と売値がクロスすると約定します。最後に、アカウント データはアカウント、キー、値の 3 つの組み合わせで構成され、アカウント所有者が許可します。 小さなメタデータ値を公開します。 台帳スパムを防ぐために、最小 XLM 残高があり、 予備と呼ばれます。アカウントの準備金は毎回増加します 関連する元帳エントリと元帳エントリが減少すると減少します 消える（注文が約定またはキャンセルされたとき、または注文が完了したときなど） トラストラインは削除されます）。現在、リザーブは 0.5 XLM 増加します 台帳エントリごとに (〜$0.03)。予備力とは関係なく、 アカウントを削除することで、アカウントの価値全体を取り戻すことが可能 AccountMerge オペレーションを使用してこれを実行します。 図 3 に示すレジャー ヘッダーには、グローバル属性が保存されます。 元帳番号、毎の準備金残高などのパラメータ 元帳エントリ、前の元帳ヘッダーの hash (実際には スキップリストを形成するいくつかの hashes)、SCP 出力には以下が含まれます この台帳に適用された新しいトランザクションの hash、 の hash それらのトランザクションの結果 (例: トランザクションの成功または失敗) それぞれ）、およびすべての台帳エントリのスナップショット hash。 スナップショット hash には元帳のすべての内容が含まれているため、 validator は、トランザクションを検証するために履歴を保持する必要はありません。 ただし、予想される数億件にスケールするには アカウントの場合、すべての台帳エントリ テーブルをhash 再設定することはできません。 帳簿を閉じます。また、台帳を移転することは現実的ではありませんStellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル 元帳番号 = 4 H(前のHDR) SCP出力 H(結果) H∗(スナップショット) ... ヘッダー 元帳番号 = 5 H(前のHDR) SCP出力 H(結果) H∗(スナップショット) ... ヘッダー 。 。 。 図 3. 元帳の内容。 H は SHA-256 ですが、H ∗ は H の階層的または再帰的適用を表します。 SCP 出力 前のヘッダー hash にも依存します。 アカウントの作成 新しい口座元帳エントリを作成して資金を投入する アカウントマージ 勘定科目元帳エントリの削除 オプションの設定 アカウントフラグと署名者を変更する お支払い 特定の量の資産を宛先に支払います。アカウント。 パス支払い Payment と同様ですが、別の資産で支払います (上 制限する);最大 5 つの中間資産を指定します オファーの管理 オファー台帳エントリの作成/削除/変更、 -パッシブオファー ゼロスプレッドを可能にするパッシブバリアントを使用 データの管理 アカウントの作成/削除/変更。データ台帳の入力 チェンジトラスト トラストラインの作成/削除/変更 信頼を許可する トラストラインで承認済みフラグを設定またはクリアする バンプシーケンス シーケンスを増加します。アカウントの番号 図 4. 主な台帳操作 ノードが切断されるたびにそのサイズの ネットワークが長すぎます。したがって、スナップショット hash は次のようになります。 hashing と状態調整の両方を最適化するように設計されています。 具体的には、スナップショットは台帳エントリを時間ごとに階層化します。 指数関数的にサイズが大きいコンテナのセットにおける最後の変更の内容 バケットと呼ばれます。バケットの集合はバケットと呼ばれます リストであり、ログ構造のマージツリーとある程度の類似点があります。 (LSM ツリー) [77]。バケット リストはトランザクション処理中に読み取られません (セクション 5.4 を参照)。したがって、特定のデザイン LSM ツリーの側面を緩和することができます。特にランダム キーによるアクセスは必要なく、バケットは読み取られるだけです レベルの結合の一部として順次。バケットのハッシュ化 リストは、マージされる各バケットを hash し、バケット hashes (小さい、 元帳が閉じるたびに参照の固定インデックス hashes)。切断後にバケット リストを調整するにはダウンロードが必要です バケットのみが異なります。 5.2 トランザクションモデル トランザクションは、ソースアカウント、有効性基準、 メモ、および 1 つ以上の操作のリスト。図 4 に、利用可能な操作を示します。各操作にはソース アカウントがあり、 デフォルトはトランザクション全体のデフォルトです。トランザクションは次のことを行う必要があります すべてのソースアカウントに対応するキーで署名されること 手術。マルチシグアカウントではより高度な署名が必要になる場合があります 一部の操作 (SetOptions など) の重み以下 他のもの (AllowTrust など)。 トランザクションはアトミックです。いずれかの操作が失敗した場合、いずれの操作も失敗しません。 彼らは実行します。これにより、多方向の取引が簡素化されます。仮に 発行者は土地権利書を表す資産を作成し、ユーザー A 小さな土地区画と10,000ドルを交換したい B が所有するより大きな土地区画。2 人のユーザーは両方とも署名できます。 3 つの操作を含む 1 つのトランザクション: 2 つのランド 支払いと1ドルの支払い。 トランザクションの主な有効性基準はシーケンス番号であり、これはトランザクションのシーケンス番号より 1 大きい必要があります。 ソースアカウント元帳エントリ。有効なトランザクションの実行 (成功したかどうかに関係なく) シーケンス番号がインクリメントされ、再生が防止されます。初期シーケンス番号には元帳が含まれます 削除した後でも再生を防ぐための上位ビットの数値 そしてアカウントを再作成します。 もう 1 つの有効性基準は、次の場合に関するオプションの制限です。 トランザクションを実行できます。土地とドルへの回帰 上記のスワップでは、A が B より先にトランザクションに署名した場合、A は署名できない可能性があります B が提出する前に 1 年間取引を続けてほしい そのため、トランザクションを無効にする時間制限が設けられる可能性があります 数日後。マルチシグアカウントも設定可能 hash プレイメージの暴露に署名の重要性を与えるため、 これと時間制限を組み合わせることで、アトミックなクロスチェーン取引 [1] が可能になります。 トランザクションのソースアカウントは、XLM でわずかな手数料を支払います。 輻輳がない場合は 10−5 XLM。混雑時には、 運営コストはオランダのオークションによって設定されます。バリデーターは validator は類似しているため、料金による補償はありません マイナーではなく、Bitcoin フルノードに。 XLMを破壊するのではなく、 料金は再利用され、投票によって比例配分されます。 既存の XLM ホルダー、振り返ってみると、 複雑さの価値はありませんでした。 5.3 コンセンサス値 各台帳について、Stellar は SCP を使用してデータ構造に同意します 3 つのフィールド: トランザクション セット hash (hash を含む) 前の元帳ヘッダーの）、終了時間、d アップグレード。 複数の値がノミネートされていることが確認された場合、Stellar はかかります 最も多くの操作を含むトランザクション セット (関係を破る) 合計手数料、次にトランザクション セット hash)、すべての和集合 アップグレード、および最高の終了時間。閉店時間はあくまで 最後の元帳の終了時刻と次の時刻の間の場合に有効です。 存在するため、ノードは無効な時間を指定しません。 アップグレードでは、リザーブ残高、最低運用料金、プロトコル バージョンなどのグローバル パラメーターが調整されます。いつ 指名中に組み合わせた場合、高い料金とプロトコルのバージョン番号が低い料金とプロトコルのバージョン番号に優先します。アップグレードは、連合投票による争奪スペース [34] を通じてガバナンスに影響を与えますが、どちらでもありません 平等主義でも中央集権主義でもありません。各 validator は次のように構成されます 応じて、統治または非統治（デフォルト）のいずれか 運営者がガバナンスに参加したいかどうか。 validator を管理する場合は、次の 3 種類のアップグレードを検討します。 望ましい、有効、および無効 (validator に含まれないもの)

SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 validator コア 地平線 FS DB DB 提出する クライアント クライアント その他のvalidator 図 5. Stellar validator アーキテクチャ 実装方法を知っています）。必要なアップグレードは次のように構成されています 特定の時間にトリガーし、相互に調整することを目的としています。 オペレーター。統治ノードは常に投票して希望するノードを指名します アップグレード、受け入れますが、有効なアップグレードを推薦するために投票はしません (つまり、ブロッキング定足数に従う)、決して投票しないでください。 または無効なアップグレードを受け入れます。非政府validatorのエコー 有効なアップグレードに対する投票、つまり本質的に委任 アップグレードを選択する人がどのようなアップグレードを希望するかについての決定 ガバナンスの役割のために。 5.4 実装 図 5 は、Stellar の validator アーキテクチャを示しています。デーモン stellar-core (約 92k 行の C++、サードパーティ ライブラリを除く) と呼ばれる SCP プロトコルと複製されたステート マシンを実装します。 SCP の値を生成するには、多数の台帳エントリを小さな暗号化に削減する必要があります。 hashes。対照的に、トランザクションの検証と実行 アカウントの状態と注文の照合を検索する必要があります。 最高の価格。両方の機能を効率的に提供するには、ステラコア 台帳の 2 つの表現を保持します。1 つはバケット リストを含む外部表現で、バイナリ ファイルとして保存されます。 効率的に更新し、段階的に再hashすることができます。 SQL データベースの内部表現 (PostgreSQL) 実稼働ノードの場合)。 Stellar-core は、次の内容を含む書き込み専用の履歴アーカイブを作成します。 確認された各トランザクションセットとそのスナップショット バケツ。アーカイブにより、新しいノードが自らブートストラップできるようになります ネットワークに参加するとき。台帳の記録も提供します 歴史 - 歴史を調べることができる場所が必要です ２年前の取引です。履歴は追加専用なので アクセス頻度が低いため、安価な場所に保管できます Amazon Glacier または保存できるサービスなど フラット ファイルを取得します。バリデーターホストは通常、ホストをホストしません。 検証への影響を避けるために独自のアーカイブを作成する 配信履歴からのパフォーマンス。 Stellar-Core をシンプルに保つため、使用することは意図されていません。 アプリケーションによって直接実行され、新しいトランザクションを送信するための非常に狭いインターフェイスのみが公開されます。サポートする クライアントでは、ほとんどの validator が Horizon と呼ばれるデーモンを実行します (〜18k Go の行) を送信するための HTTP インターフェイスを提供します そして取引の学習。 Horizon には読み取り専用アクセス権があります stellar-core の SQL データベース、ホライズンのリスクを最小限に抑える 不安定化する恒星の核。支払い経路検索などの機能はすべて Horizon 内に実装されており、アップグレード可能です 他のvalidatorと調整せずに一方的に。 いくつかのオプションの上位層デーモンがクライアントとなり、エコシステムを完成させます。ブリッジサーバーにより、 Stellar と既存のシステムの統合 (例: 特定のアカウントで受け取ったすべての支払いの通知を投稿する)。あ コンプライアンス サーバーは金融機関にフックを提供します。 送金者と受取人の情報を交換し、承認する 支払いに関して、制裁リストの順守のために。最後に、 フェデレーション サーバーは人間が判読できる名前を実装します。 アカウントのシステム。 6 導入経験 Stellar は数年間で中程度の状態に成長しました 適度に信頼できるフルノードオペレーターの数。ただし、 ノードの構成は、活性を維持するようなものでした（ただし、 安全性) 私たち、Stellar 開発財団に依存していました (自衛隊); SDF が突然失踪した場合、他のノード運営者は 介入して手動で私たちを削除する必要があったでしょう ネットワークを継続するにはクォーラム スライスから削除します。 私たちや他の多くの人々は、SDF の組織的重要性を軽減したいと考えていますが、この目標はその後、ますます優先されるようになりました。 研究者 [58] は、安全性とリスクを区別することなく、ネットワークの集中化を定量化し、公表しました。 活気。多くの通信事業者は積極的な設定調整に対応し、主に通信事業者のサイズを拡大しました。 SDF の重要性を薄めるために定足数を削減する。皮肉なことに、これは生命へのリスクを増大させるだけでした。 2 つの問題が状況を悪化させました。まずは人気の サードパーティの Stellar 監視ツール [5] が体系的に 実際に検証していないため、validator 稼働時間を過大評価しています その恒星コアが稼働していました。これにより、人々は次のことを含めるようになります クォーラム スライス内の信頼性の低いノード。 2番目に、バグです。 ステラコアとは、validator が次の台帳に移動すると、 残りのノードが previ を完了するのに十分に役立ちませんでしたメッセージが失われた場合の台帳。その結果、 ネットワークで 67 分間のダウンタイムが発生し、必要なダウンタイムが発生しました validator 管理者による手動調整で再起動してください。 さらに悪いことに、ネットワークを再起動しようとしているときに、複数のノードで同時に急いで再構成が行われてしまいました。 集団的な構成ミスにより、一部のノードが 分岐すると、それらのノードを手動でシャットダウンする必要があり、 乖離中に受け入れられたトランザクションの再送信。幸いなことに、この相違は発見され、修正されました 迅速に処理され、競合するトランザクションは含まれていませんでしたが、 ネットワークがクォーラム交差を享受できないリスク - 潜在的に矛盾するものを受け入れ続けながら分割する 単に設定ミスによりトランザクションが実行されました この出来事によって、非常に具体的なことが分かりました。 これらの経験を検討すると、2 つの主要な結論が得られました。 および対応する是正措置。Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル クリティカル、100% 51% 51% 高、67% 51% 中、67% 51% 低い、67% 51% 51% ... ... ... 51% ... 51% 図 6. バリデータの品質階層。最高品質のノード 最高のしきい値 100% が必要ですが、それより低い品質は 67% のしきい値に設定されます。単一内のノード 組織には単純に 51% の過半数が必要です。 6.1 構成の複雑さと脆弱性 Stellar は、クォーラム スライスを、n 個のエントリとしきい値 k で構成されるネストされたクォーラム セットとして表現します。ここで、k 個のエントリのセットはどれも同じです。 クォーラム スライスを構成します。 n 個のエントリはそれぞれ次のいずれかになります。 validator 公開キー、または再帰的に別のクォーラム セット。 柔軟かつコンパクトでありながら、ネストされたクォーラムを実現 セットは同時にノード演算子に柔軟性を与えすぎ、ガイダンスが少なすぎるため、安全でない (または たとえ無意味な構成であっても。グループ化の基準 ノードをセットに分割し、サブセットを階層に編成します。 しきい値の選択についてはすべて明確さが不十分であり、運用上の失敗の一因となっていました。するかどうかは不明 ネストされたセット階層内の「レベル」を信頼のレベルとして扱います。 または組織、またはその両方。現場での多くの構成 危険性を特定することに加えて、これらの概念を混合しました。 または無意味なしきい値。 したがって、より単純な構成メカニズムを追加しました。 これは、ネストされたクォーラム セットの 2 つの側面を分離します: グループ化 ノードを組織ごとにまとめ、各組織に単純な信頼分類 (低、中、高、または クリティカル)。高位以上の組織には、次のことが求められます。 歴史アーカイブを公開します。新しいシステムは、各組織が 51% のしきい値が設定され、組織はセットにグループ化されます 67% または 100% のしきい値 (グループの品質に応じて)。 各グループは、次の (高品質) グループの 1 つのエントリです。 図 6 に示すように、この単純化されたモデルにより、 構造の両方の点で構成ミスが発生する可能性 合成されたネストされたセットと選択されたしきい値の 各セット。 6.2 構成ミスのプロアクティブな検出 第 2 に、悪影響を観察するのを待って集団的な設定ミスを検出するのでは遅すぎることに気づきました。特に、分岐する可能性のある構成ミスに関しては、 停止よりも深刻な障害モード - ネットワークが必要とする 構成ミスを即座に検出できるため、オペレーターは実際に相違が発生する前に構成を元に戻すことができます。 このニーズに対処するために、ノードの推移閉包内のすべてのピアの集合的な構成状態を継続的に収集し、発散の可能性、つまり素性を検出するメカニズムを validator ソフトウェアに組み込みました。 クォーラム - その集合的な構成内。 6.2.1 クォーラム交差のチェック クォーラム スライスを収集するのは簡単ですが、それらの間で互いに素なクォーラムを見つけるのは、NP にとって非常に困難です [62]。ただし、私たちが採用したのは、 一連のアルゴリズムヒューリスティックと大文字小文字の区別ルール Lachowski [62] によって提案された、典型的なインスタンスをチェックする 問題の解決は、 最悪の場合のコスト。実際的に言えば、現在のネットワークは クォーラム スライスの推移的クロージャは 20 ～ 30 程度です ノードを作成し、Lachowski の最適化を使用して、通常は次のチェックを行います。 単一の CPU 上で数秒で完了します。必要が生じた場合 パフォーマンスを向上させるために、検索を並列化する場合があります。 6.2.2 危険な構成のチェック ネットワークが素のクォーラムを許可していることを検出することがステップです 正しい方向に進んでいるが、危険を知らせるのが不快なほど遅い このような重大な問題に対して。理想的には、ネットワークの集合的な設定が行われたときにノード オペレータが警告を受け取るようにしたいと考えています。 単に危険な状態に近づいているだけです。 したがって、クォーラム交差チェッカーを拡張しました。 臨界と呼ばれる状態を検出するには、現在の状態が 集合的な設定は、設定ミスが 1 つあるだけです バラバラな定足数を認める州。重大度を検出するには、 チェッカーは、各組織の構成を、シミュレートされた最悪の構成ミスに繰り返し置き換えます。 結果に対して内部クォーラム交差チェッカーを再実行します。 このような重大な構成ミスが一歩手前に存在する場合 現在の状態から、ソフトウェアは警告を発行し、 組織が構成ミスのリスクを引き起こしていると報告しています。 これらの変更により、オペレーターのコミュニティに 2 つの層が与えられます。 最悪の事態を防ぐための通知と指導 集団的な設定ミス。

Rede de pagamento

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

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

評価

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

Stellar のグローバルな支払いとしての適性を理解するため、 取引ネットワーク、パブリック ネットワークの状態を評価しました そして私的な実験で管理された実験を実行しました ネットワーク。私たちは次の質問に焦点を当てました。 • 実稼働ネットワーク トポロジはどのようなものですか? ブロードキャストされるメッセージの平均数、および SCP はどのようにタイムアウトを経験しますか? • コンセンサスと台帳の更新の遅延はアカウントの数に依存しませんか?SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 • (a) 1 秒あたりのトランザクション (したがって、1 あたりのトランザクション数) の増加によってレイテンシはどのような影響を受けるか 台帳)、および (b) validator ノードの数? • CPU の観点から見たノードの実行コストはいくらですか。 メモリとネットワーク帯域幅は? 決済ネットワークは他のものと比べて取引率が低い 他のタイプの分散システムへ。先頭のblockchain、 Bitcoin および Ethereum、最大 15 トランザクション/秒を確認します。 Stellar 未満。さらに、これらのシステムは、 プルーフ・オブ・ワークではいくつかのブロックがマイニングされるのを待つ必要があるため、トランザクションを安全に確認するには 1 時間かかります。の blockchain 以外の SWIFT ネットワークでは、ピーク日 [14] には 1 秒あたり平均 420 トランザクションしかありませんでした。そこで私たちが選んだのは、 測定値を 5 秒の目標と比較するため 元帳間隔、より積極的な目標。私たちの結果は次のことを示しています レイテンシはこの制限を快適に下回っています。 いくつかの未実装の最適化がまだパイプラインにあります。 7.1 アンカー 取引量で上位の資産には通貨が含まれます (例: 3 USD アンカー、2 CNY)、Bitcoin アンカー、不動産担保証券 token [92]、およびアプリ内通貨 [8]。アンカーが異なれば、ポリシーも異なります。たとえば、1 つの USD アンカー、 Stronghold、auth_reqired を設定し、顧客を保持するすべてのアカウントに対して顧客確認 (KYC) プロセスを要求します。 資産。もう 1 つの AnchorUSD は、誰でも受け取って取引できます 彼らの米ドル（文字通り0.50ドルをメキシコに送金することが可能になります） 5 秒で 0.000001 ドルの手数料がかかります）。ただし、アンカーUSD USDの購入または引き換えにはKYCと手数料が必要です 従来の電信送金を使用します。フィリピンでは、 Coins.ph の入金に対する銀行の規制は緩い 任意の ATM マシン [36] での PHP のキャッシュアウトをサポートします。前述のセキュリティ token とアプリ内通貨に加えて、次のようなさまざまな非通貨 token があります。 商業債券 [22] および炭素クレジット [85、96] からその他 協力を促す token などの難解な資産 車の差し押さえ [35]。 7.2 パブリックネットワーク この記事の執筆時点では、126 個のアクティブなフル ノードがあり、そのうち 66 個は 投票メッセージに署名してコンセンサスに参加します。図7 ([5] によって生成) は、ネットワークを視覚化します。 一方が他方のクォーラム スライスに存在する場合は 2 つのノード、もう一方のクォーラム スライスに存在する場合は 2 つのノード 濃い青の線は双方向の依存性を示します。で センターは、17 の事実上の「ティア 1 validators」からなるクラスターであり、以下によって運営されています。 SDF、SatoshiPay、LOBSTR、COINQVEST、および Keybase。 4 か月前、第 6 節の出来事が起こる前に、 システム的に重要なノードは 15 個あり、そのうち 3 個は一見したところからのノードでした 第一層の組織といくつかのランダムなシングルトン。の グラフもかなり規則性が欠けているように見えました。したがって、新しい構成メカニズムおよび/またはより適切なオペレーターの決定が必要と思われます。 より健全なネットワーク トポロジに貢献します。なし 莫大な資金力（そしてそれに対応する株主） 図 7. クォーラム スライス マップ 義務）、ティア1を5人採用するのは困難だったでしょう ただし、組織は最初からそうなっています。これは定足数を示唆しています スライスはネットワーク ブートストラップで便利な役割を果たします。誰でも実行できます。 重要なプレーヤーになるという目標を持って参加するため、 ペアごとの合意の門番は存在しません。 現在、台帳には 330 万を超えるアカウントがあります。終わった 最近 24 時間で、Stellar のトランザクションは平均 4.5 件で、 1 秒あたり 15.7 回の操作。最近の台帳を確認すると、ほとんどの場合、 トランザクションには単一の操作があるように見えますが、数回ごとに 台帳では、多くの操作を含むトランザクションが見られます。 オファーを管理するマーケットメーカーから来ているようです。の 合意形成と台帳の更新にかかる平均時間は それぞれ1061ミリ秒と46ミリ秒。 99 パーセンタイルは次のとおりです。 2252 ミリ秒と 142 ミリ秒 (前者は 1 秒のタイムアウトを反映) 指名リーダーの選択において）。 SCP のパフォーマンスは次のとおりです。 SCP 以来、1 秒あたりのトランザクションにほとんど依存しません。 任意の多数のトランザクションの hash に同意します。ボトルネックは候補の伝播によって発生する可能性が高くなります 指名、実行、検証中のトランザクション トランザクションとバケットのマージ。まだ必要ありません 複数の CPU コアまたはディスク ドライブ上で Stellar-core のトランザクション処理を並列化します。 また、ブロードキャストされた SCP メッセージの数も評価しました。 本番ネットワーク上で。通常のシングルの場合 リーダーが価値を指名するために選出された場合、私たちは 7 つの論理的価値を期待します ブロードキャストされるメッセージ: 投票して承認する 2 つのメッセージ のみnate ステートメント、受け入れて確認する 2 つのメッセージ 準備ステートメント、受け入れと確認のための 2 つのメッセージ commit ステートメント、そして最後に externalize メッセージ (敗者を支援するために新しい台帳をディスクにコミットした後に送信されます) 追いつきます）。実装はコミット確認を組み合わせます そしてメッセージを最適化として外部化します。 コミット後に値を安全に外部化できます。次に、本番環境 Stellar validator で収集されたメトリクスを分析します。終わった 68 時間にわたって、1 秒あたり 1.3 メッセージが送信されました。 台帳あたりのメッセージは平均して 6 ～ 7 件です。合計は

Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル パーセンタイル タイムアウト数 指名 投票 75% 0 0 99% 1 0 マックス 4 1 図 8. 68 時間にわたるレジャーごとのタイムアウト validators によってブロードキャストされるメッセージの数は大きくなります。 フェデレーテッド投票メッセージに加えて、ノードはブロードキャストも行います。 彼らが知ったあらゆる取引。 図 8 は、プロダクションで発生したタイムアウトを示しています。 validator 68 時間にわたって。指名タイムアウトは、 リーダー選出機能の（非）有効性の尺度。投票タイムアウトはネットワークに大きく依存します。 メッセージの遅延の可能性もあります。タイムアウトは一貫しています 発行されるメッセージの数: 6 つのメッセージ 最良のシナリオ、および追加の指名ラウンドが必要な場合は少なくとも 7 つのメッセージ。 7.3 管理された実験 に詰められたコンテナ内で制御された実験を実行しました。 72 GiB の RAM を備えた Amazon EC2 c5d.9xlarge インスタンス、 900 GB の NVMe SSD、および 36 個の vCPU。各インスタンスは 同じ EC2 リージョンにあり、10 Gbps の固定帯域幅がありました。 ストアとして SQLite を使用しました。 (Stellar は PostgreSQL もサポートしています。 ただし、測定にノイズを注入する非同期タスクが含まれます)。 Stellar は、組み込みのランタイム クエリ、generateload、 特定のターゲットで合成負荷を生成できるようにします トランザクション/秒レート。 Stellar はさまざまな機能をサポートしていますが、 オーダーブックやクロスアセットパスなどの取引機能 決済においては、シンプルな決済に注力しました。 トランザクションの確認は複数のステップで構成されているため、 次のそれぞれの測定値を記録しました。 • 指名: 指名から最初の準備までの時間 • 投票: 最初の準備から投票の確認までの時間 投票用紙がコミットされました • 台帳の更新: コンセンサス値を適用する時期 • トランザクション数: 台帳ごとに確認されたトランザクション 私たちの各実験は 3 つのパラメーターによって定義されました。 台帳の口座エントリの数、金額 1 秒あたりに送信される負荷 (XLM 支払いの形式)、 そしてvalidatorの数。 validator ごとに構成しました validator ごとに知るため (最悪のシナリオ) SCP の場合）、クォーラム スライスは単純過半数に設定されます。 (異なるクォーラムの数を最大化するため)。 ベースライン ベースライン実験では Stellar を測定しました 100,000 アカウント、4 つの validator、および負荷生成 100 トランザクション/秒のレート。台帳ごとに平均 507 件のトランザクションが観察され、標準偏差は 49 でした。 (9.7%)。トランザクションがドロップされなかったことに注意してください。わずかな 105 106 107 0 500 1,000 1,500 2,000 アカウント レイテンシ[ミリ秒] 台帳の更新 投票 指名 図 9. アカウント数の増加に伴う待ち時間 差異は、ロード ジェネレーターのスケジュール制限によるものです。台帳ごとのトランザクション数が観察されました。 台帳を考慮すると、負荷生成率と一致していました 5秒ごとに閉まります。指名、投票、台帳 アップデートでは、平均レイテンシが 82.53 ミリ秒、95.96 ミリ秒、 それぞれ174.08ミリ秒。指名のレイテンシーが観察されました 99 パーセンタイルは常に 61 ミリ秒未満ですが、場合によっては 最初のステップに相当する約 1 秒のスパイク リーダー選択のタイムアウト機能で。 ベースラインのパフォーマンスを考慮して、その影響を調べました。 各テスト設定パラメータを変更します。 アカウント 図 9 のデータは、Stellar がスケールすることを示唆しています。 アカウントの数も増えます。テストの生成 バケットの作成と、アカウントの作成に時間がかかるプロセスになりました。 マージにより、単にデータベースにデータを追加することができなくなりました SQL 経由でアカウントを直接使用します。そこで私たちは、 最大 50,000,000 アカウントを対象とした実験。あるうちに コンセンサスと台帳更新の遅延への影響を最小限に抑え、 アカウントを増やすと、次のようなオーバーヘッドが発生することに注意してください。 バケットを結合すると、サイズが大きくなります。 トランザクションレート 取引レートは金額に影響を与えます validator 間のトラフィック マルチキャスト、各台帳に含まれるトランザクションの数、および最上位のサイズ バケツ。トランザクションの増加による影響を理解するため 負荷に応じて、100,000 のアカウントと 4 つの validator を使用して実験を実行しました。 図 10 は、コンセンサス レイテンシーの緩やかな増加を示しています。 一方、大部分の時間は台帳の更新に費やされました。 当然のことですが、トランザクション セットのサイズが大きくなるにつれて、 データベースにコミットするのに時間がかかります。また、 台帳更新の遅延は実装に大きく依存します。 データベースの選択によって影響を受けます。 バリデータノード tierone validators の数がどのように増加するかを確認するにはパフォーマンスに影響を与えるため、実験を実行しました 100,000 のアカウント、100 トランザクション/秒、validator の数は 4 ～ 43 で、すべての validator が表示されました。 すべての validator のクォーラム スライス内。より小さいクォーラム スライスは、 パフォーマンスへの影響が少なくなります。SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル ロカバら。 100 150 200 250 300 350 0 500 1,000 1,500 2,000 ロード [トランザクション/秒] レイテンシ[ミリ秒] 台帳の更新 投票 指名 図 10. トランザクション負荷の増加に伴うレイテンシ 10 20 30 40 0 500 1,000 1,500 2,000 バリデーター レイテンシ[ミリ秒] 台帳の更新 投票 指名 図 11. ノード数の増加に伴うレイテンシ ネットワーク上の検証ノードの数の変更 交換される SCP メッセージの数に影響を与えるだけでなく、 推薦中の潜在的な値の数。図11 は、指名時間の増加率が比較的小さいことを示しています。 データは投票がボトルネックであることを示唆していますが、 スケーリングに関する多くの問題は、改善することで解決できると考えています。 Stellar のオーバーレイ ネットワークを使用してネットワーク トラフィックを最適化します。として 予想通り、台帳更新の遅延は独立したままでした ノードの数。 成約率 最後に、台帳が確認される頻度と、Stellar が 5 秒の目標を達成するかどうかを測定することで、Stellar のエンドツーエンドのパフォーマンスを測定したいと考えました。 トランザクションを削除します。平均的な元帳のクローズが観察されました アカウントの増加に伴い、5.03 秒、5.10 秒、5.15 秒の時間になりました それぞれ、エントリ、トランザクション レート、ノード数です。 結果は、Stellar が元帳を一貫してクローズできることを示唆しています 高負荷時。 7.4 validator を実行しています Stellar の重要な特徴の 1 つは、コストが低いことです。 validator を実行します。アンカーは実行 (または契約) する必要があります。 validators でファイナリティを強制します。 SDF は 3 つの本番 validator を実行し、すべて 2 つのコアを持つ c5.large AWS インスタンス上で実行します。 4 GiB の RAM および Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz プロセッサ。 1 台でのリソース使用状況の検査 これらのマシンのうち、Stellar プロセスを観察しました。 CPU の約 7% とメモリ 300 MiB。ネットワーク トラフィックに関しては、ピアへの接続数が 28、クォーラム サイズが 1 つあります。 34 の場合、受信速度と送信速度は 2.78 Mbit/s でした。 それぞれ2.56Mビット/秒。このようなものを実行するにはハードウェアが必要です プロセスが安価です。この場合、コストは 0.054 ドル/時間です。 または月額約40ドル。 7.5 今後の取り組み これらの実験は、Stellar が 1 ～ 2 個の注文を簡単にスケールできることを示しています 今日のネットワーク使用量を超える規模です。なぜなら、 これまでのところ、パフォーマンスに対する要求は非常に控えめです。Stellar を使用して多くの直接的な最適化の余地を残します。 有名なテクニック。例: トランザクションと SCP メッセージは素朴なフラッディングを使用して validators によってブロードキャストされます プロトコルを使用しますが、理想的には、より効率的で構造化されたプロトコルを使用する必要があります。 ピアツーピア マルチキャスト [30]。さらに、データベースを多用する 台帳の更新時間は、標準のバッチ処理およびプリフェッチ技術によって改善できます。

Avaliação

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

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

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

結論

国際決済は高額で日数もかかります。基金 保管はコルレス銀行や送金サービスを含む複数の金融機関を経由します。 各ホップは完全に信頼される必要があるため、新しいホップは困難です。 参入者は市場シェアを獲得し、競争します。 Stellar の番組 数秒で世界中に安く送金する方法。の 主要な革新は、ピアツーピア構造を活用した新しいオープンメンバーシップのビザンチン協定プロトコルである SCP です。 世界的なコンセンサスを達成するための金融ネットワークの構築 新しいインターネット仮説。 SCP は Stellar をアトミックにコミットさせます 任意の参加者間の不可逆的なトランザクション。 お互いのことを知らないし信頼もしていない。これにより、新規参入者が既存の市場と同じ市場にアクセスできることが保証されます。 プレーヤーは、利用可能な最高の交換を安全に入手できます 信頼できないマーケットメーカーからのレートであっても、劇的に上昇します。 支払いの待ち時間を短縮します。 謝辞 Stellar は、初期の ジョイス・キムのリーダーシップまたは多大な貢献 スコット・フレッケンシュタインとバルテック・ノヴォタルスキーが建築と Horizon、Stellar SDK、およびその他の重要な要素の維持 Stellar エコシステムの。コルテン・ベルジェロンにも感謝します。 ヘンリー・コリガン＝ギブス、キャンディス・ケリー、カピル・K・ジェイン、ボリス レズニコフ、ジェレミー・ルービン、クリスチャン・ラダー、エリック・サンダース、 Torsten Stüber、Tomer Weller、匿名の査読者、 私たちの羊飼いのジャスティン・シェリーさんに有益なコメントをいただきました 以前の草案。 免責事項 マジエール教授のこの出版物への貢献は有償コンサルタントとしてのものであり、教授の活動の一部ではありませんでした。 スタンフォード大学の義務または責任。

Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル

Conclusão

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

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