Stellar コンセンサスプロトコル
Аннотация
Международные платежи медленны и дороги, отчасти из-за многошаговой маршрутизации платежей через разнородные сети. банковские системы. Stellar — новая глобальная платежная сеть который может напрямую переводить цифровые деньги в любую точку мира. мир за секунды. Ключевое нововведение — безопасная транзакция механизм через ненадежных посредников, используя новый Протокол византийского соглашения под названием SCP. С помощью SCP каждый учреждение указывает другие учреждения, в которых можно остаться по согласию; благодаря глобальной взаимосвязанности финансовой системы, вся сеть затем соглашается на атомную транзакции, охватывающие произвольные учреждения, без риска платежеспособности или валютного курса со стороны промежуточных эмитентов активов или маркет-мейкеры. Мы представляем модель, протокол и формальная проверка; описать платежную сеть Stellar; и, наконец, оценить Stellar эмпирически с помощью тестов и наш опыт нескольких лет производственного использования. Концепции CCS • Безопасность и конфиденциальность → Распределенный безопасность систем; • Организация компьютерных систем → Одноранговые архитектуры; • Информационные системы → Электронный перевод средств. Ключевые слова blockchain, BFT, кворумы, выплаты Справочный формат ACM: Марта Лохава, Джулиано Лоса, Дэвид Мазьер, Грэйдон Хоар, Николас Бэрри, Эли Гафни, Джонатан Джоув, Рафал Малиновский, Джед Маккалеб. 2019. Быстрые и безопасные глобальные платежи с Stellar. В СОСП ’19: Симпозиум по принципам операционных систем, 27–30 октября, 2019, Хантсвилл, Онтарио, Канада. ACM, Нью-Йорк, Нью-Йорк, США, 17 страниц. https://doi.org/10.1145/3341301.3359636
概要
国際決済は遅くて高価ですが、その理由の 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
Введение
Международные платежи, как известно, медленные и дорогостоящие [32]. Подумайте о непрактичности отправки 0,50 доллара США из США в *Галуа, Инк. † Калифорнийский университет в Лос-Анджелесе Разрешение на создание цифровых или печатных копий всей или части этой работы для использование в личных целях или в классе предоставляется бесплатно при условии, что копии не изготовлены или распространены с целью получения прибыли или коммерческой выгоды, и что копии несут это уведомление и полная цитата на первой странице. Авторские права на компоненты этой работы, принадлежащей не ACM, необходимо уважать. Абстрагирование с помощью кредит разрешен. Копировать иным образом или повторно публиковать, размещать на серверах или повторное распространение по спискам требует предварительного специального разрешения и/или платы. Запрос разрешения от [email protected]. SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада © 2019 Ассоциация вычислительной техники. ISBN ACM 978-1-4503-6873-5/19/10...$15,00 https://doi.org/10.1145/3341301.3359636 Мексика, две соседние страны. Конечные пользователи платят почти 9 долларов. в среднем такая передача [32] и двустороннее соглашение при посредничестве центральных банков стран может лишь сократить стоимость базового банка составляет 0,67 доллара США за единицу [2]. Помимо сборов, обычно учитывается задержка международных платежей в сутках, что делает невозможным быстрое получение денег за границу в чрезвычайные ситуации. В странах, где банковская система не работают или не обслуживают всех граждан, или там, где плата невыносима, люди прибегают к отправке платежей автобусом [38], лодка [19], а иногда и Bitcoin [55], и все это несут риск, задержки или неудобства. Несмотря на то, что затраты на соблюдение требований будут всегда, данные свидетельствуют о том, что значительная сумма теряется из-за отсутствия конкуренции [21], что усугубляется неэффективными технологиями. Где люди могут внедрять инновации, цены и задержки снижаются. Например, денежные переводы с банковских счетов во втором квартале 2019 года стоили в среднем 6,99%, тогда как показатель мобильных денег составил всего 4,88% [13]. Открытая глобальная платежная сеть, привлекающая инновации и конкуренция со стороны небанковских организаций может привести к снижению затраты и задержки на всех уровнях, включая соответствие [83]. В этом документе представлен Stellar, платеж на основе blockchain. сеть, специально созданная для содействия инновациям и конкуренция в международных платежах. Stellar — первый систему для достижения всех трех следующих целей (в рамках новая, но эмпирически обоснованная «интернет-гипотеза»): 1. Открытое членство. Любой может выпускать облигации, обеспеченные валютой. цифровые token, которыми могут обмениваться пользователи. 2. Окончательность, обеспечиваемая эмитентом. Эмитент token может предотвратить транзакции в token от отмены или отмены. 3. Атомарность между эмитентами. Пользователи могут атомарно обмениваться и торгуйте token от нескольких эмитентов. Достичь первых двух несложно. Любая компания может в одностороннем порядке предложить такой продукт, как Paypal, Venmo, WeChat. Pay или Alipay и обеспечьте окончательность платежей в виртуальные валюты, которые они создали. К сожалению, атомарные транзакции между этими валютами невозможны. Фактически, несмотря на то, что Paypal приобрела материнскую компанию Venmo в 2013 году конечные пользователи по-прежнему не могут отправлять Venmo долларов пользователям Paypal [78]. Только в последнее время торговцы могут даже принять оба с одной интеграцией. Цели 2 и 3 могут быть достигнуты в закрытой системе. В частности, в ряде стран действуют эффективные внутренние платежные системы. сети, обычно контролируемые регулирующим органом, пользующимся универсальным доверием. Однако членство ограничивается закрытым набор зарегистрированных банков, а сети ограничены досягаемость регулирующего органа страны.SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Цели 1 и 3 были достигнуты за добытые blockchains, особенно в форме ERC20 tokens на Ethereum [3]. Основная идея этих blockchain — создать новую криптовалюту, с помощью которой можно будет вознаграждать людей за поселение. транзакции трудно отменить. К сожалению, это означает, что эмитенты token не контролируют завершенность транзакций. Если программное обеспечение ошибки приводят к реорганизации истории транзакций [26, 73], или когда трофеи от обмана людей превышают стоимость реорганизации истории [74, 97], эмитенты могут нести ответственность за tokens они уже выкуплены за реальные деньги. Stellar blockchain имеет два отличительных свойства. Во-первых, он изначально поддерживает эффективные рынки между tokens от разных эмитентов. В частности, любой может выдать token, blockchain предоставляет встроенную книгу заказов для торговли между любой парой token, и пользователи могут осуществлять платежи по пути которые атомарно торгуют несколькими валютными парами, в то время как гарантия сквозной лимитной цены. Во-вторых, Stellar представляет новое византийское соглашение. протокол SCP (Stellar Протокол консенсуса), посредством которого Эмитенты token назначают определенные серверы validator для обеспечения соблюдения завершенность сделки. Пока никто не скомпрометирует validator эмитента (а также лежащие в его основе цифровые подписи и криптографические hashе остаются в безопасности), эмитент точно знает, какие транзакции произошли, и избегает риска убытков от blockchain истории реорганизации. Ключевая идея SCP заключается в том, что большинство эмитентов активов получают выгоду от ликвидные рынки и хотят облегчить атомарные транзакции с другими активами. Следовательно, администраторы validator настраивают свои серверы, чтобы договориться с другими validator о точном история всех транзакций по всем активам. validator v1 может быть настроено на согласие с версией 2, или v2 можно настроить на согласие с v1 или оба могут быть настроены для согласования друг с другом; во всех случаях ни один из них не будет сохранять историю транзакций до тех пор, пока он знает, что другой не может принять участие в другой истории. По транзитивности, если v1 не может не согласиться с v2, а v2 не может не согласиться с v3 (или наоборот), v1 не может не согласиться с v1. v3, независимо от того, представляет ли v3 активы, о которых v1 вообще слышал оф. Предполагая, что эти отношения соглашения транзитивно подключить всю сеть, SCP гарантирует глобальное соглашение, что делает его глобальным византийским соглашением протокол с открытым членством. Мы называем это новое предположение о связности гипотезой Интернета и отмечаем, что оно касается как «Интернета» (который всем понятен, означают единственную крупнейшую транзитивно подключенную IP-сеть) и устаревшие международные платежи (которые выполняются поэтапно неатомарны, но используют транзитивно связанную глобальную сеть финансовых учреждений). Stellar используется с сентября 2015 г. Чтобы длина blockchain оставалась управляемой, система запускает SCP с интервалом в 5 секунд — быстро по стандартам blockchain, но гораздо медленнее, чем типичное применение византийского соглашения. Хотя основным использованием были платежи, Stellar также доказанная привлекательность для неденежных взаимозаменяемых token, которые приносят пользу с непосредственных вторичных рынков (см. раздел 7.1). В следующем разделе обсуждаются соответствующие работы. В разделе 3 представлены SCP. Раздел 4 описывает нашу формальную проверку SCP. В разделе 5 описан уровень оплаты Stellar. Раздел 6 касается наш опыт развертывания и извлеченные уроки. В разделе 7 оценивается система. Раздел 8 завершается.
導入
国際支払いは遅くて費用がかかることで有名です[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 は終了です。
Stellar консенсусный протокол
Протокол консенсуса Stellar (SCP) основан на кворуме. Протокол Византийского соглашения с открытым членством. Кворумы возникают в результате объединения решений по локальной конфигурации отдельных узлов. Однако узлы распознают только кворумам, к которым они принадлежат сами, и только после изучение локальных конфигураций всех остальных членов кворума. Одним из преимуществ этого подхода является то, что SCP по своей сути допускает неоднородные представления о том, какие узлы существуют. Следовательно, узлы могут присоединяться и выходить в одностороннем порядке без необходимости Протокол «просмотра изменений» для координации членства. 3.1 Федеративное византийское соглашение Традиционная проблема византийского соглашения состоит из замкнутая система из N узлов, часть из которых неисправна и может вести себя произвольно. Узлы получают входные значения и обмениваются сообщения для выбора выходного значения среди входных. Протокол византийского соглашения безопасен, когда никакие два узла с хорошим поведением не выдают разные решения и уникальный решение было действительным вкладом (для некоторого определения действительного согласованногоSOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. заранее). Протокол активен, если он гарантирует, что каждый честный узел в конечном итоге выдает решение. Обычно протоколы предполагают N = 3f + 1 для некоторого целого числа. f > 0, то гарантируйте безопасность и некоторую форму жизнеспособности, поэтому пока не более f узлов неисправны. На каком-то этапе этих протоколы, узлы голосуют за предложенные значения и предложение получение 2f + 1 голосов, называемое кворумом голосов, становится решение. При N = 3f + 1 узлах любые два кворума размер 2f+1 перекрывается не менее чем в f+1 узлах; даже если f из этих перекрывающиеся узлы неисправны, два кворума имеют как минимум общий доступ один исправный узел, предотвращающий противоречивые решения. Однако этот подход работает только в том случае, если все узлы согласны с что представляет собой кворум, что невозможно в SCP, где два узла могут даже не знать о существовании друг друга. При использовании SCP каждый узел v в одностороннем порядке объявляет наборы узлов, называемые его срезами кворума, такие, что (a) v считает, что если все члены среза договариваются о состоянии системы, затем они правы, и (b) v считает, что хотя бы один из его срезов будет доступен для своевременного предоставления информации о состояние системы. Назовем полученную систему, состоящую узлов и их срезов, Федеративное Византийское соглашение (ФБА). Как мы увидим далее, возникает система кворума. из срезов узлов. Неформально, срезы узла FBA выражают, с кем узел требует согласия. Например, для узла может потребоваться соглашение с 4 конкретными организациями, в каждой из которых имеется по 3 узла; чтобы учесть время простоя, он может установить свои срезы как все наборы состоящий из 2 узлов от каждой организации. Если это «требует отношение «согласие с» транзитивно связывает любые два узла, мы получаем глобальное соглашение. В противном случае мы можем получить расхождение, но только между организациями, ни одна из которых не требует соглашение с другим. Учитывая топологию сегодняшней финансовой системы, мы предполагаем, что широкая конвергенция будет продолжать создавать единую историю реестра, которую люди называют «сеть Stellar», как мы говорим об Интернете. Кворумы возникают из срезов следующим образом. Каждый узел определяет его кворум распределяется в каждом отправляемом им сообщении. Пусть S будет набор узлов, из которых исходил набор сообщений. А узел считает, что набор сообщений достиг кворума порог, когда каждый член S имеет срез, включенный в S. По построению такой набор S, если он единогласен, удовлетворяет условию требования соглашения каждого из его участников. Неисправный узел может рекламировать фрагменты, созданные для изменения того, что узлы с хорошим поведением учитывают кворумы. Для анализа протокола мы определяем кворум в FBA как непустой набор S узлов, охватывающий хотя бы один срез кворума каждый исправный член. Эта абстракция обоснована, как и любое множество сообщений, якобы представляющих единогласный кворум на самом деле так и есть (даже если оно содержит сообщения от неисправных узлов), и это точно, когда S содержит только узлы с хорошим поведением. В в этом разделе мы также предполагаем, что срезы узлов не изменяются. Тем не менее, наши результаты переносятся на случай меняющегося среза. потому что система, в которой меняются слайсы, не менее безопасна, чем система с фиксированными срезами, в которой срезы узла состоят из всех срезы, которые он когда-либо использует в случае меняющихся срезов (см. теорему 13 в [68]). Как поясняется в разделе 4, жизнеспособность зависит от хорошо работающие узлы со временем удаляют ненадежные узлы из своих кусочков. Поскольку разные узлы имеют разные требования к соглашению, FBA исключает глобальное определение безопасности. Мы говорим исправные узлы v1 и v2 переплетаются, когда каждый кворум v1 пересекает каждый кворум v2 хотя бы в одном исправный узел. Протокол FBA может гарантировать соглашение только между переплетенными узлами; раз SCP так делает, то это его вина допуск по безопасности оптимален. Гипотеза Интернета, лежащий в основе дизайна Stellar, утверждает, что узлы заботятся о людях. о будет переплетаться. Мы говорим, что набор узлов I неповреждён, если I представляет собой равномерно исправный кворум, в котором каждые два члена I переплетены, даже если каждый узел вне I неисправен. Интуитивно, тогда я должен оставаться невосприимчивым к действиям неповрежденных узлы. SCP гарантирует как неблокирующую работоспособность [93], так и безопасность неповрежденных наборов, хотя сами узлы не нуждаются в знать (а может и не знать), какие наборы целы. Более того, объединение двух пересекающихся целых множеств есть целый комплект. Следовательно, неповрежденные множества определяют разбиение узлы с хорошим поведением, где каждый раздел безопасен и работоспособен (при некоторых условиях), но разные разделы могут выводить разные решения. 3.1.1 Соображения безопасности и жизнеспособности в FBA За редким исключением [64], большинство протоколов закрытых византийских соглашений настроены на точку равновесия, в которой безопасность и живучесть имеют одинаковую отказоустойчивость. В ФБА, это означает конфигурации, в которых, независимо от сбоев, все переплетенные множества также целы. Учитывая, что ФБА определяет кворумы децентрализованно, маловероятно, что индивидуальный выбор срезов приведет к такому равновесию. Более того, на по крайней мере, в Stellar равновесие нежелательно: последствия сбоя безопасности (а именно двойного расходования цифровых денег) гораздо хуже, чем при сбое работоспособности (а именно задержки в платежах, которые в любом случае произошли за несколько дней до Stellar). Люди поэтому следует и следует выбирать большие фрагменты кворума, такие, чтобы их узлы, скорее всего, останутся переплетенными, чем нетронутыми. Чем больше чаша весов склоняется, тем легче оправиться от типичные сбои живучести в системе ФБА, чем в традиционной закрытой. В закрытых системах все сообщения должны быть интерпретируются относительно одного и того же набора кворумов. Следовательно, добавление и удаление узлов для восстановления после сбоя требует достижение консенсуса по вопросу реконфигурации, что становится затруднительным, если консенсуса больше нет. В отличие от ФБА, любой узел может в одностороннем порядке корректировать свои доли кворума в любой момент. время. В ответ на отключение системно важного объекта организации, администраторы узлов могут настраивать свои фрагменты в соответствии с обойти проблему, что-то вроде координации ответов к катастрофам BGP [63] (хотя и без ограничений маршрутизация по физическим сетевым каналам).
Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада 3.1.2 Каскадная теорема SCP следует шаблону базовой круглой модели [42]; узлы проходят через серию пронумерованных бюллетеней, каждый пытаясь выполнить три задачи: (1) определить «безопасное» значение, не противоречащее никакому решению предыдущего голосования (часто называемое подготовка бюллетеня), (2) согласовать безопасное значение и (3) обнаружить, что соглашение было успешным. Тем не менее, открытый ФБА членство блокирует несколько распространенных методов, что делает его невозможно «портировать» традиционные закрытые протоколы на ФБА модель, просто изменив определение кворума. Одним из методов, используемых во многих протоколах, является ротация. через ведущие узлы в циклическом порядке после таймаутов. В закрытой системе циклический выбор лидера обеспечивает что в конечном итоге единственный честный лидер в конечном итоге согласовывает соглашение по единой ценности. К сожалению, круговой не может работать в системе FBA с неизвестным членством. Другой распространенный метод, который не работает с FBA, заключается в предположении, что определенный кворум может убедить все узлы. Например, если все признают любые 2f + 1 узлов кворумом, то 2f + 1 подписей достаточно, чтобы подтвердить состояние протокола для всех узлов. Аналогично, если узел получает кворум идентичных сообщений посредством надежной широковещательной рассылки [24] узел может предположить, что все исправные узлы также увидят кворум. В FBA, напротив, кворум ничего не значит для узлов вне кворума. Наконец, нефедеративные системы часто используют «обратный» подход. рассуждения о безопасности: если f+1 узлов неисправны, то вся безопасность гарантии теряются. Следовательно, если узел v слышит f + 1 узел, все констатировать некоторый факт F, v может предположить, что по крайней мере один из них говорит истина (и, следовательно, F истинно) без потери безопасности. такой рассуждения терпят неудачу в FBA, потому что безопасность - это свойство пар узлов, поэтому узел, потерявший безопасность для некоторых узлов, может всегда теряйте безопасность из-за большего количества узлов, предполагая неверные факты. Однако FBA может рассуждать наоборот о жизнеспособности. Определите набор v-блокировок как набор узлов, пересекающих каждую срез v. Если v-блокирующее множество B единогласно ошибочно, B может лишить узел v кворума и лишить его жизнеспособности. Следовательно, если B единогласно констатирует факт F, тогда v знает, что либо F является true или v не поврежден. Тем не менее, Ви все еще нужно увидеть полную картину. кворум знать, что переплетенные узлы не будут противоречить F, что приводит к заключительному раунду общения в SCP и другие протоколы FBA [47], которые не требуются в аналогичных протоколы закрытого членства. В результате мы имеем три возможных уровня уверенности в потенциальных фактах: неопределенный, безопасный для неповрежденных узлов (который мы будем общепринятые факты), и можно с уверенностью предположить среди переплетенных узлы (которые мы будем называть подтвержденными фактами). Узел v может эффективно определить, является ли набор B блокирующим, проверив, пересекает ли B все его срезы. Интересно, что если узлы всегда объявляют утверждения, которые они Accept и полный кворум принимает утверждение, это запускает каскадный процесс, посредством которого утверждения распространяются по всему целые комплекты. Мы называем ключевой факт, лежащий в основе этого распространения каскадная теорема, которая утверждает следующее: если I — неповреждённое множество, Q — кворум любого члена I, а S — любой надмножество Q, то либо S ⊇I, либо существует элемент v ∈I такой, что v < S и I ∩S является v-блокирующим. Интуитивно, было ли это это не так, дополнение S будет содержать кворум который пересекает I, но не Q, что нарушает пересечение кворума. Обратите внимание: если мы начнем с S = Q и неоднократно расширим S до включаем все узлы, которые он блокирует, мы получаем каскадный эффект до тех пор, пока: в конечном итоге S охватывает все I. 3.2 Описание протокола SCP — это частично синхронный протокол консенсуса [42], состоящий из серии попыток достижения консенсуса, называемых бюллетени. В бюллетенях используются тайм-ауты увеличивающейся продолжительности. А протокол синхронизации голосования гарантирует, что узлы остаются включенными один и тот же бюллетень в течение увеличивающихся периодов времени, пока бюллетени эффективно синхронны. Прекращение действия не гарантировано пока бюллетени не будут синхронными, но два синхронных голосования в котором неисправные члены срезов узлов с хорошим поведением «Не вмешиваться» достаточно для завершения SCP. Протокол голосования определяет действия, предпринимаемые в ходе каждого голосование. Голосование начинается с этапа подготовки, на котором узлы попытаться определить предлагаемую ценность, которая не противоречит любое предыдущее решение. Затем, на этапе фиксации, узлы пытаются принять решение по подготовленному значению. При голосовании используется подпротокол соглашения, называемый федеративным голосованием, т.е.n какие узлы голосуют за абстрактные утверждения это может в конечном итоге подтвердиться или застрять. Некоторые утверждения могут быть названы противоречивыми, а безопасность гарантия федеративного голосования заключается в том, что никакие два члена переплетенное множество подтверждает противоречивые утверждения. Подтверждение заявления не гарантируется, за исключением неповрежденного набор, все члены которого голосуют одинаково. Однако, если член неповрежденного набора подтверждает утверждение, федеративно голосование гарантирует, что все члены целого множества в конечном итоге подтвердят это утверждение. Поэтому предпринимаются необратимые шаги в ответ на подтверждающие высказывания сохраняет живость в течение неповрежденные узлы. Узлы первоначально предлагают значения, полученные в результате номинации. протокол, который увеличивает шансы всех членов неповрежденного множество, предлагающее одно и то же значение, и оно в конечном итоге сходится (хотя и без возможности определить полную сходимость). Выдвижение сочетает в себе федеративное голосование и выбор лидера. Поскольку в FBA циклическая система невозможна, для номинации используются вероятностная схема выбора лидера. Каскадная теорема играет решающую роль как при голосовании, так и при голосовании. синхронизации и во избежание заблокированных состояний, из которых расторжение уже невозможно. 3.2.1 Голосование Узлы SCP проходят серию пронумерованных бюллетеней, используя федеративное голосование для согласования утверждений, относительно которых значения определяются или не определяются в ходе голосования. Если асинхронность или неправильное поведение препятствует принятию решения в бюллетене n, тайм-аут узлов и повторите попытку в бюллетене n + 1.
SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Напомним, федеративное голосование может не прекратиться. Следовательно, некоторые заявления по поводу избирательных бюллетеней могут навсегда застрять в неопределенное состояние, в котором узлы никогда не могут определить, являются ли они все еще выполняются или застряли. Поскольку узлы не могут исключить возможность неопределенных утверждений, которые впоследствии окажутся истинными, они никогда не должны пытаться проводить федеративное голосование по новым заявлениям противоречащие неопределенным. В каждом бюллетене n узлы используют федеративное голосование по двум типам. заявления: • подготовить ⟨n,x⟩– утверждает, что никакое значение, кроме x было или когда-либо будет решено в любом голосовании ≤n. • commit ⟨n,x⟩– утверждает, что x определяется в бюллетене n. Важно отметить, что подготовка ⟨n,x⟩ противоречит коммиту. ⟨n′,x ′⟩, когда n ≥n′ и x , x ′. Узел начинает голосование n, пытаясь провести федеративное голосование на заявление подготовить ⟨n,x⟩. Если какой-либо предыдущий оператор подготовки был успешно подтвержден посредством федеративного голосования, узел выбирает x из подтвержденной подготовки высшего бюллетеня. В противном случае узел устанавливает x в выходной сигнал Протокол номинации описан в следующем подразделе. Тогда и только тогда, когда узел успешно подтверждает подготовку ⟨n,x⟩ в бюллетене n он пытается провести федеративное голосование по фиксации ⟨n,x⟩. Если если это удалось, это означает, что SCP принял решение, поэтому узел выводит значение из подтвержденного оператора фиксации. Рассмотрим переплетенное множество S. Поскольку не более одного значения могут быть подтверждены подготовленными членами S в данном бюллетене, никакие два разных значения не могут быть подтверждены совершенными члены S в данном бюллетене. Более того, если совершить ⟨n,x⟩ подтверждено, то подготовка ⟨n,x⟩ тоже подтверждена; с тех пор подготовка ⟨n,x⟩ противоречит любому предыдущему коммиту для другого значения, по соглашению гарантирует федеративное голосование мы понимаем, что никакое другое значение не может быть принято ранее голосование членов S. Индукцией по номерам бюллетеней мы поэтому убедитесь, что SCP безопасен. Для живости рассмотрим неповрежденный набор I и достаточно длинный синхронное голосование n. Если в срезах появляются неисправные узлы хорошо себя ведущих узлов не вмешиваются, то голосованием n + 1 все члены I подтвердили один и тот же набор P операторов подготовки. Если P = ∅ и бюллетень n был достаточно длинным, протокол номинации сойдётся на некотором значении x. В противном случае, пусть x будет значением из подготовки с наибольшим числом голосов в P. В любом случае, я буду равномерно пытаться объединить голосование по подготовке ⟨n + 1,x⟩ в следующем туре голосования. Следовательно, если n + 1 также синхронно, неизбежно следует решение по x. 3.2.2 Номинация Выдвижение предполагает федеративное голосование по заявлениям: • Номинировать x – утверждает, что x является действительным кандидатом на решение. Узлы могут голосовать за назначение нескольких значений — разных высказывания номинантов не противоречат друг другу. Однако однажды узел подтверждает любое заявление о назначении, он прекращает голосование за номинировать новые ценности. Федеративное голосование по-прежнему позволяет узлу подтвердить новые заявления о выдвижении кандидатов, за которые он не голосовал, которые голосуй или принимай из кворума принять из кворума а действителен принять от блокирующий набор незафиксированный проголосовал за принял подтвердил проголосовал за Рисунок 1. Этапы федеративного голосования позволяет членам неповрежденного набора подтверждать друг друга номинированные ценности, при этом отказываясь от новых голосов. (Развивающийся) результат номинации — это детерминированная комбинация всех значений в подтвержденных номинирующих заявлениях. Если x представляет собой набор транзакций, узлы могут объединяться наборов, самый большой набор или набор с наибольшим hash, поэтому пока все узлы делают то же самое. Поскольку узлы не содержат новых голосов после подтверждения одного заявления о выдвижении кандидатуры, набор подтвержденные утверждения могут содержать только конечное число значений. Тот факт, что подтвержденные заявления надежно распространялись через неповрежденные множества означают, что неповрежденные узлы в конечном итоге сходятся на тот же набор номинированных ценностей и, следовательно, результат номинации, хотя и в неизвестном месте, в произвольном конце протокола. Узлы используют федеративный выбор лидеров, чтобы уменьшить количество различных значений в номинирующих утверждениях. Только лидер, который еще не проголосовал за выдвижение кандидатуры, может ввести новый x. Другие узлы ждут вестей от лидеров и просто копировать (действительные) голоса их лидеров. Чтобы приспособиться к неудаче, набор лидеров продолжает расти по мере того, как происходят тайм-ауты, хотя на практике только несколько узлов вводят новые значения x. 3.2.3 Федеративное голосование Федеративное голосование использует трехэтапный протокол, показанный на рис. Рисунок 1. Узлы сначала пытаются договориться об абстрактных утверждениях голосование, затем принятие и, наконец, подтверждение заявлений. Узел v может голосовать за любое допустимое утверждение a, которое не соответствует противоречить другомувыдающиеся голоса и принятые заявления. Это делается путем трансляции подписанного сообщения о голосовании. Затем v принимает a, если a согласуется с другими принятыми утверждениями и либо (случай 1) v является членом кворума, в котором каждый узел либо голосует за a, либо принимает a, либо (случай 2), даже если v не голосовал за a, набор v-blocking принимает a. В случае 2 v может ранее отдали голоса, противоречащие а, которые теперь было отменено. v разрешено забыть об отклоненных голосах и притвориться, что никогда их не применял, потому что если v цел, он знает отмененные голоса не могут обеспечить кворум в случае 1. v сообщает, что принимает a, а затем подтверждает, когда оно находится в кворум, который единогласно принимает а. На рисунке 2 показано эффект v-блокирующих множеств и каскадная теорема во время федеративное голосование. Два переплетенных узла не могут подтвердить противоречивые утверждения, поскольку два необходимых кворума должны будут иметь общийБыстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада 3 4 2 1 5 7
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
Голосуйте Х
Голосуйте за (а) 3 4 2 1 5 7 6 Голосовать Х Голосовать Х Голосовать Х Голосовать Да Голосовать Х Голосовать Да Голосовать Да (б) 3 4 2 1 5 7 6 Принять Х Голосовать Х Принять Х Голосовать Да Принять Х Голосовать Да Голосовать Да (с) 3 4 2 1 5 7 6 Принять Х Принять Х Принять Х Голосовать Да Принять Х Принять Х Голосовать Да (г) 3 4 2 1 5 7 6 Принять Х Голосовать Х Принять Х Принять Х Принять Х Принять Х Принять Х (е) Рисунок 2. Каскадный эффект при федеративном голосовании. Каждый узел имеет один срез кворума, обозначенный стрелками, указывающими на членов среза. (a) Вводятся противоречивые утверждения X и Y. (b) Узлы голосуют за действительные утверждения. (c) Узел 1 принимает X после наличия кворума {1, 2, 3, 4} единогласно голосуют за X. (d) Все узлы 1, 2, 3 и 4 принимают X; набор {1} блокирует 5, поэтому узел 5 принимает X, отменяя его предыдущий голос за Y. (e) Набор {5} блокирует 6 и 7, поэтому оба 6 и 7 принимают X. исправный узел, который не смог принять противоречивые утверждения. Подтверждение заявления не гарантируется: в В случае разделения голосов оба заявления могут быть навсегда застрял в ожидании кворума на этапе голосования. Однако, если узел в неповрежденном множестве подтверждаю утверждение, каскад теорему и принять случай 2, гарантируя, что все I в конечном итоге подтвердите это утверждение. 3.2.4 Синхронизация бюллетеней Если узлы не могут подтвердить оператор фиксации для текущем голосовании, они сдаются после тайм-аута. Тайм-аут получает дольше с каждым бюллетенем, чтобы приспособиться к произвольным границам о задержке сети. Однако одних таймаутов недостаточно для синхронизации бюллетеней узлов, которые не запустились одновременно или рассинхронизировался по другим причинам. Чтобы добиться синхронизации, узлы запускают таймер только тогда, когда они являются частью кворум то есть весь на текущем (или более позднем) голосовании. Это замедляет узлы, которые запустились раньше, и гарантирует, что никакие член интактной группы остается слишком далеко впереди группы. Более того, если узел v когда-либо заметит установку v-блокировки позднее, бюллетень, он немедленно переходит к низшему бюллетеню, так что это это больше не так, независимо от каких-либо таймеров. Каскад Тогда теорема гарантирует, что все отстающие догонят. Результат заключается в том, что избирательные бюллетени примерно синхронизированы на всем протяжении устанавливается, как только система становится синхронной. 3.2.5 Выбор федеративного лидера Выбор лидера позволяет каждому узлу выбирать лидеров в таком способ, которым узлы обычно выбирают только один или небольшое количество лидеров. Чтобы справиться с неудачей лидера, выбор лидера проходит через раунды. Если лидеры текущего тура кажутся не выполняющими своих обязанностей, то после некоторого узлы определенного периода таймаута переходят к следующему раунду, чтобы расширить круг лидеров, за которыми они следуют. В каждом раунде используются две уникальные криптографические функции hash, H0 и H1, которые выводят целые числа в диапазоне [0,hmax). Например, Stellar использует Hi(m) = SHA256(i∥b∥r ∥m), где b — общий экземпляр SCP (номер блока или реестра), r — номер раунда выбора лидера, hmax = 2256. В пределах за раунд мы определяем приоритет узла v как: приоритет(v) = H1(v) Для каждого узла будет выбран один подставной человек в качестве лидера. узел с наивысшим приоритетом (v). Этот подход работает хорошо с почти идентичными фрагментами кворума, но не правильно отразить важность узлов в несбалансированных конфигурациях. Например, если Европа и Китай вносят по 3 узлов в каждый кворум, но в Китае используется 1000 узлов, а в Европе — 4, тогда у Китая будет узел с наивысшим приоритетом 99,6% того времени. Поэтому мы вводим понятие веса среза, где вес(u,v) ∈[0, 1] — это доля срезов кворума узла u содержащий узел v. Когда узел u выбирает нового лидера, он учитывает только соседей, определенных следующим образом: соседи (и) = { v | H0(v) < hmax · вес(u,v) } Затем узел нодеу начинается с пустого набора лидеров, и в каждом round добавляет к нему узел v из соседей(u) с наивысшим приоритет(v). Если набор соседей пуст в каком-либо раунде, вместо этого u добавляет узел с наименьшим значением H0(v)/weight(u,v).
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 を追加します。
Формальная проверка SCP
Чтобы исключить ошибки проектирования, мы официально подтвердили безопасность SCP. и свойства живучести (см. [65]). В частности, мы проверили что переплетенные узлы никогда не расходятся во мнениях и что в условиях, обсуждаемых ниже, в конечном итоге решение принимает каждый член целого множества. Интересно, что проверка показала, что условия, при которых SCP гарантирует жизнеспособность, являются тонкими, и сильнее, чем первоначально предполагалось [68]: как обсуждается ниже, вредоносные узлы, которые манипулируют временем без иного при отклонении от протокола может потребоваться выселение вручную из срезов кворума.
SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. Чтобы гарантировать, что свойства будут сохранены во всех возможных Конфигурации и исполнения ФБА мы рассматриваем произвольные. количество узлов с произвольными локальными конфигурациями. Это включает сценарии с непересекающимися неповрежденными множествами, а также потенциально бесконечно длинные выполнения. Недостаток в том, что мы сталкиваются со сложной проблемой проверки параметризованного система с бесконечными состояниями. Чтобы обеспечить удобство проверки, мы смоделировали SCP в логике первого порядка (FOL), используя Ivy [69] и методологию [82]. Процесс проверки состоит из ручного создания индуктивных предположений, которые затем автоматически проверяются Айви. FOL-модель SCP абстрагируется от некоторых аспектов Системы FBA, с которыми сложно работать на ВОЛС (например, каскадная теорема принимается за аксиому), поэтому проверяем справедливость обоснованность абстракции с использованием Isabelle/HOL [75]. После выражения проблемы проверки в FOL мы проверяем безопасность, предоставляя индуктивный инвариант. Индуктивный инвариант состоит из дюжины однострочных гипотез примерно 150 строк спецификации протокола. Затем мы указываем свойства жизнеспособности SCP в линейной временной логике Айви и используем метод жизнеспособность для снижения безопасности [80, 81] для снижения живучести задача проверки к задаче нахождения индуктивного инвариант. Хотя безопасность SCP относительно легко обеспечить доказать, что аргумент жизнеспособности SCP гораздо более сложен и состоит примерно из 150 однострочных инвариантов. Доказательство живучести потребовало точной формализации предположения, при которых SCP обеспечивает прекращение действия. Сначала мы думали, что нетронутый набор я всегда закрою, если все участники удалили неисправные узлы из своих срезов [68]. Однако этого оказалось недостаточно: воспитанный (но не исправен) узел в кворуме члена I can, под влияние неисправных узлов, предотвратить завершение, выполнив кворума непосредственно перед окончанием голосования, тем самым вызывая члены I выберут другие значения x в следующем туре голосования. Поэтому мы должны дополнительно предположить, что неформально каждый узел в кворуме члена I в конечном итоге либо становится своевременным или вообще не отправляет сообщения в течение достаточного периода времени. На практике это означает, что члены I могут необходимо корректировать свои срезы до тех пор, пока условие не выполнится. Это проблема не свойственна системам FBA: Losa et al. [47] присутствует протокол, жизнеспособность которого зависит от строго более слабого предположения о возможной синхронности и возможном выборе лидера без необходимости удалять неисправные узлы из срезов.
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] 現在 活性が厳密に弱いプロトコルに依存するプロトコル スライスから障害のあるノードを削除する必要がなく、最終的には同期が行われ、最終的にはリーダーが選出されると仮定します。
Платежная сеть
В этом разделе описывается платежная сеть Stellar, реализованная как реплицированный конечный автомат PH_0000 поверх SCP. 5.1 Модель бухгалтерской книги Регистр Stellar построен на абстракции счета (в в отличие от более ориентированного на монеты вывода неизрасходованных транзакций или UTXO модель Bitcoin). Содержимое реестра состоит из набор записей бухгалтерской книги четырех различных типов: счета, линии доверия, предложения и данные учетной записи. Счета — это принципалы, которые владеют и выпускают активы. Каждый учетная запись называется по открытому ключу. По умолчанию соответствующий закрытый ключ может подписывать транзакции для учетной записи. Однако учетные записи можно перенастроить, чтобы добавить других подписывающих лиц и деавторизовать ключ, который называет учетную запись, с помощью опция «multisig», требующая нескольких подписывающих лиц. Каждый аккаунт также содержит: порядковый номер (включенный в транзакции для предотвращения повтора), некоторые флаги и баланс в «родном» предварительно добытая криптовалюта под названием XLM, предназначенная для смягчения последствий некоторые атаки типа «отказ в обслуживании» и способствуют созданию рынка как нейтральная валюта. Линии доверия отслеживают право собственности на выпущенные активы, которые именуется парой, состоящей из эмиссионного счета и короткого код актива (например, «USD» или «EUR»). Каждая линия доверия определяет счет, актив, баланс счета в этом активе, предел, выше которого баланс не может подняться, и некоторые флаги. Учетная запись должна дать явное согласие на хранение актива путем создание линии доверия, предотвращающей обременение спамеров аккаунты с нежелательными активами. Правила «Знай своего клиента» (KYC) требуют, чтобы многие финансовые учреждения знали, чьи депозиты они держат. например, проверив удостоверение личности с фотографией. Для соблюдения требований эмитенты могут установить дополнительный флаг auth_reqired в их учетных записях, ограничивающий право собственности на активы, которые они выдают, авторизованным учетным записям. Для предоставления такого разрешения эмитент устанавливает авторизованный пометить на линиях доверия клиентов. Предложения соответствуют готовности аккаунта торговать вверх. на определенное количество определенного актива в обмен на другой при данном цена в книге заказов; они автоматически сопоставляются и заполняется при пересечении цен покупки/продажи. Наконец, данные учетной записи состоят из троек учетной записи, ключа и значения, что позволяет владельцам учетных записей публиковать небольшие значения метаданных. Чтобы предотвратить спам в реестре, существует минимальный баланс XLM. называется резервом. Резерв счета увеличивается с каждым связанная запись в бухгалтерской книге и уменьшается, когда запись в бухгалтерской книге исчезает (например, когда ордер исполнен или отменен, или когда линия доверия удалена). На данный момент резерв увеличивается на 0,5 XLM. (∼0,03 доллара США) за запись в бухгалтерской книге. Независимо от резерва, это можно вернуть всю стоимость учетной записи, удалив это с помощью операции AccountMerge. Заголовок реестра, показанный на рисунке 3, хранит глобальные атрибуты: номер бухгалтерской книги, такие параметры, как резервный баланс на запись в бухгалтерской книге, hash предыдущего заголовка бухгалтерской книги (фактически несколько hashes, образующих список пропуска), выходные данные SCP, включая hash новых транзакций, примененных в этом реестре, hash результаты этих транзакций (например, успех или неудача для каждый), а также снимок hash всех записей бухгалтерской книги. Поскольку снимок hash включает в себя все содержимое бухгалтерской книги, validator не требуется сохранять историю для проверки транзакций. Однако для масштабирования до сотен миллионов ожидаемых счетов, мы не можем повторно hash все таблицы записей главной книги на каждом бухгалтерскую книгу закрыть. Кроме того, передавать реестр непрактично.Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада регистр № = 4 H(предыдущий hdr) Выход SCP H∗(результаты) H∗(снимок) ... заголовок регистр № = 5 H(предыдущий hdr) Выход SCP H∗(результаты) H∗(снимок) ... заголовок . . . Рисунок 3. Содержимое реестра. H — это SHA-256, а H * представляет собой иерархическое или рекурсивное применение вывода H. SCP. также зависит от предыдущего заголовка hash. Создать аккаунт Создайте и профинансируйте новую запись в книге счетов Слияние учетных записей Удалить запись в книге учета счетов Установить параметры Изменение флагов учетной записи и подписантов Оплата Выплатите определенное количество актива в пользу dest. акт. ПутьОплата Как оплата, но оплата в другом активе (вверх). ограничить); укажите до 5 промежуточных активов Управление предложением Создать/удалить/изменить запись в книге предложений, -Пассивное предложение с пассивным вариантом, обеспечивающим нулевой спред Управление данными Создать/удалить/изменить аккаунт. запись в книге данных ИзменениеДоверие Создать/удалить/изменить линию доверия Разрешить доверие Установить или снять флаг авторизации на линии доверия BumpSequence Увеличение сек. номер на счету Рисунок 4. Основные операции реестра такого размера каждый раз, когда узел отключался от сети слишком долго. Таким образом, снимок hash предназначен для оптимизации как hashing, так и согласования состояний. В частности, моментальный снимок стратифицирует записи реестра по времени. последней модификации в наборе контейнеров экспоненциального размера называются ведрами. Совокупность ведер называется ведром. список и имеет некоторое сходство с деревьями слияния с логарифмической структурой. (LSM-деревья) [77]. Список желаний не читается во время обработки транзакции (см. раздел 5.4). Следовательно, определенный дизайн аспекты LSM-деревьев можно ослабить. В частности, случайный доступ по ключу не требуется, а сегменты доступны только для чтения последовательно в рамках слияния уровней. Хеширование ведра список создается путем hash обработки каждого сегмента по мере его объединения и расчета нового совокупного значения hash сегмента hashes (небольшого, фиксированный справочный индекс hashes) при каждом закрытии бухгалтерской книги. Для согласования списка желаний после отключения требуется загрузка различаются только ведра. 5.2 Модель транзакции Транзакция состоит из исходного счета, критериев действительности, памятка и список одной или нескольких операций. На рис. 4 перечислены доступные операции. Каждая операция имеет исходный аккаунт, который по умолчанию соответствует значению всей транзакции. Транзакция должна быть подписан ключами, соответствующими каждой исходной учетной записи в операция. Учетные записи с мультиподписью могут потребовать более высокого уровня подписи. вес для некоторых операций (например, SetOptions) и ниже для других (например, AllowTrust). Транзакции являются атомарными: если какая-либо операция завершается неудачно, ни одна из их казнят. Это упрощает многосторонние сделки. Предположим, эмитент создает актив для представления земельных документов, а пользователь А хочет обменять небольшой земельный участок плюс 10 000 долларов на больший земельный участок, принадлежащий Б. Оба пользователя могут подписать одна сделка, содержащая три операции: две земельные платежи и платеж в один доллар. Основным критерием действительности транзакции является ее порядковый номер, который должен быть на единицу больше, чем номер транзакции. запись в книге учета исходных счетов. Выполнение действительной транзакции (успешно или нет) увеличивает порядковый номер, предотвращая повтор. Начальные порядковые номера содержат реестр номер в старших битах, чтобы предотвратить повтор даже после удаления и повторное создание учетной записи. Другим критерием достоверности является необязательное ограничение на то, когда транзакция может быть выполнена. Возвращение к земле и доллару своп выше, если A подписывает транзакцию раньше B, A не может хочу, чтобы B участвовал в транзакции в течение года, прежде чем отправить ее это, и поэтому может установить ограничение по времени, делающее транзакцию недействительной через несколько дней. Учетные записи с мультиподписью также могут быть настроены. чтобы придать вес подписи обнаружению прообраза hash, что в сочетании с ограничениями по времени позволяет осуществлять атомарную кроссчейн-торговлю [1]. С исходного счета транзакции взимается небольшая комиссия в XLM. 10−5 XLM, если нет перегрузок. В условиях заторов, Стоимость операций устанавливается на голландском аукционе. Валидаторы не компенсируется комиссией, поскольку validators аналогичны на Bitcoin полные узлы, а не майнеры. Вместо того, чтобы уничтожить XLM, сборы перерабатываются и распределяются пропорционально голосованием существующие держатели XLM, которые, оглядываясь назад, могут или могут не стоили такой сложности. 5.3 Консенсусные ценности Для каждого реестра Stellar использует SCP для согласования структуры данных. с тремя полями: набор транзакций hash (включая hash предыдущего заголовка книги), время закрытия,д обновления. Если подтверждено назначение нескольких значений, Stellar принимает набор транзакций с наибольшим количеством операций (разрыв связей по общей сумме комиссий, затем набор транзакций hash), объединение всех обновления и максимальное время закрытия. Близкое время только действительно, если это происходит между временем закрытия последнего реестра и присутствует, поэтому узлы не указывают недопустимое время. Обновления настраивают глобальные параметры, такие как резервный баланс, минимальная комиссия за операцию и версия протокола. Когда При объединении во время номинации более высокие сборы и номера версий протокола заменяют более низкие. Обновления влияют на управление через пространство федеративного голосования [34], ни эгалитарный и централизованный. Каждый validator настроен как либо управляющий, либо неуправляющий (по умолчанию), в зависимости от от того, хочет ли его оператор участвовать в управлении. Управляющие validators рассматривают три типа обновления: желаемый, действительный и недействительный (все, что validator не делает
SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. validator ядро горизонт ФС БД БД отправить клиент клиент другие validators Рисунок 5. Архитектура Stellar validator знаю, как реализовать). Желаемые обновления настроены на запуск в определенное время, предназначенный для координации между операторы. Управляющие узлы всегда голосуют за выдвижение желаемых обновления: принимайте, но не голосуйте за назначение действительных обновлений (т. е. соглашайтесь с блокирующим кворумом) и никогда не голосуйте за или принять недействительные обновления. Неуправляющее эхо validators любой голос, который они видят за действительное обновление, по сути делегируя решение о том, какие обновления желательны для тех, кто выбирает на руководящую роль. 5.4 Реализация На рис. 5 показана архитектура validator Stellar. Демон называемый stellar-core (~92 тыс. строк C++, не считая сторонних библиотек), реализует протокол SCP и реплицируемый конечный автомат. Создание значений для SCP требует сокращения большого количества записей реестра до небольших криптографических операций. hashes. Напротив, проверка и выполнение транзакции требует просмотра состояния учетной записи и сопоставления заказов на лучшая цена. Чтобы эффективно выполнять обе функции, звездное ядро хранит два представления реестра: внешнее представление, содержащее список сегментов, хранящееся в виде двоичных файлов, которые могут быть эффективно обновлены и постепенно измененыhash, а также внутреннее представление в базе данных SQL (PostgreSQL для производственных узлов). Stellar-core создает архив истории, доступный только для записи, содержащий каждый подтвержденный набор транзакций и снимки ведра. Архив позволяет новым узлам загружаться самостоятельно. при подключении к сети. Он также обеспечивает запись в бухгалтерской книге история — должно быть место, где можно найти сделка двухлетней давности. Поскольку история доступна только для добавления и доступ к нему нечастый, его можно хранить в дешевых местах например Amazon Glacier или любой сервис, позволяющий хранить и получить плоские файлы. Хосты-валидаторы обычно не размещают свои собственные архивы, чтобы избежать какого-либо влияния на проверку производительность из истории обслуживания. Чтобы сохранить простоту звездного ядра, оно не предназначено для использования непосредственно приложениями и предоставляет лишь очень узкий интерфейс для отправки новых транзакций. Поддержать клиентов, большинство validator используют демон под названием Horizon (~18 тыс. строки Go), который предоставляет HTTP-интерфейс для отправки и изучение транзакций. Horizon имеет доступ только для чтения к База данных SQL stellar-core, сводящая к минимуму риск горизонта дестабилизирующее звездное ядро. Такие функции, как поиск пути платежа, будут полностью реализованы в перспективе и могут быть обновлены. в одностороннем порядке без согласования с другими validators. Несколько дополнительных демонов более высокого уровня являются клиентами горизонта, дополняя экосистему. Сервер-мост облегчает интеграция Stellar с существующими системами, например, публикация уведомлений обо всех платежах, полученных на определенный счет. А сервер соответствия предоставляет финансовым учреждениям возможность обмен и утверждение информации об отправителе и получателе по выплатам, за соблюдением санкционных списков. Наконец, сервер федерации реализует удобочитаемое именование система для аккаунтов. 6 Опыт внедрения Stellar за несколько лет перерос в состояние с умеренным количество достаточно надежных операторов полного узла. Однако, конфигурации узлов были таковы, что работоспособность (хотя и не безопасность) зависела от нас, Фонда развития Stellar (СДС); если бы SDF внезапно исчез, другие операторы узлов пришлось бы вмешаться и удалить нас вручную из фрагментов кворума, чтобы сеть могла продолжить работу. Хотя мы и многие другие хотим снизить системную значимость СДС, эта цель получила все больший приоритет после исследователи [58] количественно оценили и обнародовали централизацию сети, не дифференцируя риски для безопасности и живость. Ряд операторов отреагировали активными изменениями конфигурации, в первую очередь увеличением размера своих дробление кворума в попытке ослабить важность SDF; по иронии судьбы это только увеличило риск для жизни. Ситуацию усугубили две проблемы. Во-первых, популярный сторонний инструмент мониторинга Stellar [5] систематически переоценка времени безотказной работы validator без фактической проверки это звездное ядро работало; это побуждает людей включать ненадежные узлы в своих срезах кворума. Во-вторых, ошибка в звездное ядро означало, что как только validator перейдет в следующий реестр, это не помогло должным образом остальным узлам завершить предыдущеесобственный реестр на случай потери сообщений. В результате сеть испытала 67 минут простоя и потребовала координация вручную администраторами validator для перезапуска. Хуже того, попытка перезапустить сеть привела к одновременным поспешным реконфигурациям на нескольких узлах. в коллективной неправильной конфигурации, которая позволила некоторым узлам расходятся, что требует ручного отключения этих узлов и повторная отправка сделок, принятых во время расхождения. К счастью, это расхождение было обнаружено и исправлено. быстро и не содержало конфликтующих транзакций, но риск того, что сеть не сможет воспользоваться пересечением кворума — расщепление, продолжая при этом принимать потенциально конфликтующие транзакций, просто из-за неправильной конфигурации — было сделано очень конкретен в этом инциденте. Анализ этого опыта привел к двум важным выводам. и соответствующие корректирующие действия.Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Критический, 100% 51% 51% Высокий, 67% 51% Средний, 67% 51% Низкий, 67% 51% 51% ... ... ... 51% ... 51% Рисунок 6. Иерархия качества валидатора. Узлы высочайшего качества требуется самый высокий порог 100 %, тогда как более низкие качества настроены на порог 67 %. Узлы внутри одного организации требуется простое большинство в 51%. 6.1 Сложность и хрупкость конфигурации Stellar выражает фрагменты кворума как вложенные наборы кворума, состоящие из n записей и порога k, где любой набор из k записей составляет срез кворума. Тогда каждая из n записей либо открытый ключ validator или, рекурсивно, другой набор кворума. Несмотря на гибкость и компактность, мы реализовали вложенный кворум. наборы одновременно предоставляли операторам узлов слишком большую гибкость и слишком мало указаний: было легко написать небезопасное (или даже бессмысленные) конфигурации. Критерии группировки узлы в наборы для организации подмножеств в иерархию и все пороговые значения для выбора были недостаточно ясными и способствовали сбоям в работе. Было не ясно, стоит ли рассматривать «уровень» в иерархии вложенных множеств как уровень доверия, или организация, или и то, и другое; множество конфигураций в полевых условиях смешали эти понятия, помимо указания опасных или бессмысленные пороги. Поэтому мы добавили более простой механизм настройки. который разделяет два аспекта вложенных наборов кворума: группировку узлы вместе по организациям и маркируя каждую организацию простой классификацией доверия (низкое, среднее, высокое или критично). Организации уровня и выше обязаны публиковать исторические архивы. Новая система синтезирует наборы вложенных кворумов, в которых каждая организация представлена как Установлен порог 51%, и организации сгруппированы в наборы с порогом 67% или 100% (в зависимости от качества группы). Каждая группа представляет собой отдельную запись в следующей (более качественной) группе. как показано на рисунке 6. Эта упрощенная модель уменьшает вероятность неправильной конфигурации, как с точки зрения структуры синтезированных вложенных наборов и порогов, выбранных для каждый набор. 6.2 Упреждающее обнаружение неправильной конфигурации Во-вторых, мы поняли, что обнаруживать коллективную неправильную конфигурацию, ожидая наблюдения за ее негативными последствиями, уже слишком поздно. Особенно в отношении неправильных конфигураций, которые могут расходиться. более серьезный режим отказа, чем остановка — сети необходимо чтобы иметь возможность немедленно обнаружить неправильную конфигурацию, чтобы операторы могли исправить ее до того, как действительно произойдет какое-либо расхождение. Чтобы удовлетворить эту потребность, мы встроили в программное обеспечение validator механизм, который непрерывно собирает состояние коллективной конфигурации всех узлов в транзитивном замыкании узла и обнаруживает возможность расхождения, т. е. непересекающихся кворумы — внутри этой коллективной конфигурации. 6.2.1 Проверка пересечения кворума Хотя собрать фрагменты кворума легко, найти среди них непересекающиеся кворумы — задача со-NP-сложная [62]. Однако мы приняли набор алгоритмических эвристик и правил исключения регистров предложено Лачовски [62], которое проверяет типичные экземпляры решения проблемы на несколько порядков быстрее, чем стоимость в худшем случае. Практически говоря, нынешняя сеть транзитивных замыканий среза кворума порядка 20–30. узлы и, с помощью оптимизации Лаховски, обычно проверяют за считанные секунды на одном процессоре. Если возникнет необходимость для повышения производительности мы можем распараллелить поиск. 6.2.2 Проверка рискованных конфигураций Обнаружение того, что сеть допускает непересекающиеся кворумы, является шагом в правильном направлении, но сигнализирует об опасности неприятно поздно по столь критичному вопросу. В идеале мы хотим, чтобы операторы узлов получали предупреждения, когда коллективная конфигурация сети просто приближается к опасному состоянию. Поэтому мы расширили проверку пересечения кворума чтобы обнаружить состояние, которое мы называем критичностью: когда текущий коллективная конфигурация находится на расстоянии одной неправильной конфигурации от государство, допускающее непересекающиеся кворумы. Чтобы обнаружить критичность, программа проверки неоднократно заменяет конфигурацию каждой организации смоделированной наихудшей ошибкой конфигурации, а затем повторно запускает проверку пересечения внутреннего кворума для результата. Если такая критическая неправильная конфигурация существует в одном шаге из текущего состояния, программное обеспечение выдает предупреждение и сообщает об организации, представляющей риск неправильной конфигурации. Эти изменения дают сообществу операторов два уровня. уведомлений и указаний для защиты от наихудших форм коллективной неправильной конфигурации.
決済ネットワーク
このセクションでは、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 つの層が与えられます。 最悪の事態を防ぐための通知と指導 集団的な設定ミス。
Оценка
Чтобы понять пригодность Stellar в качестве глобального платежа и торговой сети, мы оценили состояние публичной сети и проводил контролируемые эксперименты на частном экспериментальном сеть. Мы сосредоточились на следующих вопросах: • Как выглядит топология производственной сети? Сколько сообщений в среднем передается в эфир, и как SCP испытывает тайм-ауты? • Остаются ли задержки консенсуса и обновления реестра независимыми от количества учетных записей?SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. • Как на задержки влияет увеличение (а) транзакций в секунду (и, следовательно, количества транзакций в секунду) реестр) и (б) количество узлов validator? • Какова стоимость эксплуатации узла с точки зрения ЦП, память и пропускная способность сети? Платежные сети имеют низкую скорость транзакций по сравнению к другим типам распределенных систем. Ведущие blockchains, Bitcoin и Ethereum, подтверждают до 15 транзакций в секунду, менее Stellar. Более того, этим системам требуется несколько минут, чтобы час для безопасного подтверждения транзакции, поскольку доказательство работы требует ожидания нескольких блоков для майнинга. Сеть SWIFT, не относящаяся к blockchain, в пиковый день PH_0000 в среднем совершала всего 420 транзакций в секунду. Поэтому мы выбрали чтобы сравнить наши измерения с целевым показателем в 5 секунд интервал реестра, более агрессивная цель. Наши результаты показывают что задержки комфортно ниже этого предела даже при несколько нереализованных оптимизаций все еще находятся в стадии разработки. 7.1 Якоря В число наиболее торгуемых активов по объему входит валюта (например, 3 доллара США). якоря, 2 юаня), якоря Bitcoin, ценных бумаг, обеспеченных недвижимостью token [92] и валюты приложения [8]. У разных якорей разные политики. Например, один якорь в долларах США, Stronghold устанавливает auth_reqired и требует прохождения процедуры «знай своего клиента» (KYC) для каждой учетной записи, в которой хранятся их активы. Еще один, AnchorUSD, пусть кто угодно получает и торгует их доллары США (что делает буквально возможным отправить 0,50 доллара США в Мексику за 5 секунд с комиссией $0,000001). Однако AnchorUSD требует KYC и комиссий для покупки или погашения своих долларов США с помощью обычных банковских переводов. На Филиппинах, где банковские правила более мягкие в отношении входящих платежей, coin.ph поддерживает обналичивание PHP в любом банкомате [36]. Помимо вышеупомянутой безопасности token и валюты в приложении, существует ряд невалютных token от коммерческие облигации [22] и углеродные кредиты [85, 96] и более эзотерические активы, такие как token, стимулирующие совместную работу изъятие автомобиля [35]. 7.2 Публичная сеть На момент написания статьи имеется 126 активных полных узлов, 66 из которых участвовать в консенсусе, подписывая сообщения для голосования. Рисунок 7 (созданный [5]) визуализирует сеть с линией между два узла, если один из них присутствует в срезах кворума другого, и более темная синяя линия показывает двунаправленную зависимость. На центр представляет собой кластер из 17 де-факто «validator» первого уровня, управляемых SDF, SatoshiPay, LOBSTR, COINQVEST и Keybase. Четыре месяца назад, до событий Раздела 6, было 15 системообразующих узлов: 3 из казалось бы организации первого уровня и несколько случайных одиночек. график также выглядел гораздо менее регулярным. Следовательно, новый механизм конфигурации и/или более эффективные решения оператора кажутся чтобы внести вклад в более здоровую топологию сети. Без большие финансовые ресурсы (и соответствующий акционер Рисунок 7. Карта среза кворума обязательства), было бы сложно набрать 5 человек первого уровня однако организации с самого начала. Это предполагает кворум срезы играют полезную роль в начальной загрузке сети: каждый может присоединиться к цели стать важным игроком, потому что нет никаких привратников к парному соглашению. В настоящее время в реестре зарегистрировано более 3,3 миллиона учетных записей. Кончено за последние 24 часа Stellar в среднем совершало 4,5 транзакций и 15,7 операций в секунду. Анализируя последние бухгалтерские книги, большинство транзакции, кажется, имеют одну операцию, в то время как каждые несколько В реестрах мы видим транзакции, содержащие множество операций, которые похоже, исходят от маркет-мейкеров, управляющих предложениями. среднее время достижения консенсуса и обновления реестра составило 1061 мс и 46 мс соответственно. 99-й процентиль был 2252 мс и 142 мс (первое соответствует тайм-ауту в 1 секунду). в выборе лидера номинации). Обратите внимание, что производительность SCP в основном не зависит от транзакций в секунду, поскольку SCP соглашается на hash произвольного количества транзакций. Узкие места чаще возникают из-за распространения кандидата операции во время номинации, исполнения и проверки транзакции и объединение сегментов. Нам пока не нужно для распараллеливания обработки транзакций stellar-core на нескольких ядрах ЦП или дисках. Мы также оценили количество транслируемых SCP-сообщений. в производственной сети. В обычном случае с одним лидер, избранный для выдвижения ценности, мы ожидаем семь логических сообщения для трансляции: два сообщения для голосования и принятия номизаявление Nate, два сообщения для принятия и подтверждения заявление о подготовке, два сообщения для принятия и подтверждения оператор фиксации и, наконец, сообщение о внешнем виде (отправляется после записи нового реестра на диск, чтобы помочь отставшим догнать). Реализация сочетает в себе подтверждение фиксации и экспортировать сообщения в качестве оптимизации, поскольку это безопасно экспортировать значение после его фиксации. Затем мы анализируем показатели, собранные на производстве Stellar validator. Кончено в течение 68 часов было отправлено 1,3 сообщения в секунду, в среднем до 6-7 сообщений на реестр. Отметим, что общая сумма
Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада процентиль Количество таймаутов Номинация Голосование 75% 0 0 99% 1 0 Макс 4 1 Рисунок 8. Таймауты для каждого реестра более 68 часов количество сообщений, переданных validators, больше, поскольку в Помимо сообщений федеративного голосования, узлы также транслируют любые транзакции, о которых они узнают. На рис. 8 показаны тайм-ауты, с которыми сталкивается производственная система. validator в течение 68 часов. Тайм-ауты для выдвижения мера (не)эффективности функции выбора лидера, в то время как тайм-ауты голосования сильно зависят от сети и потенциальные задержки сообщений. Таймауты совпадают с количеством отправленных сообщений: шесть сообщений в в лучшем случае и не менее семи сообщений, если потребуется дополнительный раунд выдвижения. 7.3 Контролируемые эксперименты Мы проводили контролируемые эксперименты в контейнерах, упакованных на Инстансы Amazon EC2 c5d.9xlarge с 72 ГиБ ОЗУ, 900 ГБ твердотельного накопителя NVMe и 36 виртуальных ЦП. Каждый экземпляр находился в том же регионе EC2 и имел фиксированную пропускную способность 10 Гбит/с. В качестве хранилища мы использовали SQLite. (Stellar также поддерживает PostgreSQL, но здесь есть асинхронные задачи, которые вносят шум в измерения.) Stellar предоставляет встроенный запрос времени выполнения,generload, что позволяет генерировать синтетическую нагрузку на конкретную цель транзакция/второй курс. Хотя Stellar поддерживает различные торговые функции, такие как книга заказов и путь кросс-активов платежей, мы сосредоточились на простых платежах. Подтверждение транзакций состоит из нескольких этапов, поэтому мы записал измерения для каждого из следующих показателей: • Номинация: время от номинации до первой подготовки. • Голосование: время от первой подготовки до подтверждения голосование совершено • Обновление реестра: пришло время применить консенсусную ценность • Количество транзакций: подтвержденные транзакции по реестру. Каждый из наших экспериментов определялся тремя параметрами: количество счетных записей в книге учета, сумма нагрузка (в виде платежей XLM), отправляемая в секунду, и количество validators. Мы настраивали каждые validator знать обо всех остальных validator (наихудший сценарий для SCP), с срезами кворума, установленными на любое простое большинство узлов (чтобы максимизировать количество различных кворумов). Базовый уровень В нашем базовом эксперименте было измерено Stellar с 100 000 аккаунтов, четыре validator и генерация нагрузки Скорость 100 транзакций в секунду. В среднем мы наблюдали 507 транзакций на каждый реестр со стандартным отклонением 49. (9,7%). Обратите внимание, что ни одна транзакция не была отменена; легкий 105 106 107 0 500 1000 1500 2000 Счета Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 9. Задержка при увеличении количества учетных записей Отклонение связано с ограничениями планирования генератора нагрузки. Мы заметили, что количество транзакций в реестре соответствовало нашей скорости генерации нагрузки, согласно данным реестра закрывается каждые 5 секунд. Выдвижение, голосование и учет Обновление показало средние задержки 82,53 мс, 95,96 мс и 174,08 мс соответственно. Мы заметили, что задержка номинации 99-й процентиль постоянно ниже 61 мс, с редкими всплески длительностью примерно 1 секунду, что соответствует первому шагу в функции таймаута выбора лидера. Учитывая базовую производительность, мы рассмотрели эффекты варьирования каждого из параметров испытательной установки. Счета Данные на рисунке 9 показывают, что Stellar масштабируется а количество аккаунтов увеличивается. Генерация теста учетных записей стали длительным процессом, поскольку создание корзин и слияние не позволило нам просто заполнить базу данных с учетными записями напрямую через SQL. Поэтому мы провели нашу эксперименты до 50 000 000 аккаунтов. Пока есть минимальное влияние на консенсус и задержки обновления реестра, мы отмечаем, что увеличение счетов создает накладные расходы в размере объединение ведер, которые становятся больше. Скорость транзакции Скорость транзакций влияет на сумму многоадресная рассылка трафика между validator, количество транзакций, включенных в каждый реестр, и размер верхнего уровня ведра. Чтобы понять последствия увеличения транзакций load мы провели эксперимент со 100 000 аккаунтами и 4 validator. На рисунке 10 показан медленный рост задержки консенсуса. в то время как большая часть времени была потрачена на обновление реестра. Неудивительно, что по мере увеличения размера набора транзакций требуется больше времени, чтобы зафиксировать его в базе данных. Мы также отмечаем, что задержка обновления реестра сильно зависит от реализации, и зависит от выбора базы данных. Узлы валидатора Чтобы увидеть, как увеличивается количество тиронов validatorsвлияет на производительность, мы провели эксперименты со 100 000 учетных записей, 100 транзакциями в секунду и различным количеством validator от 4 до 43. Появились все validator. во всех слоях кворума validators; меньшие фрагменты кворума будут оказывают меньшее влияние на производительность.SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада Лохава и др. 100 150 200 250 300 350 0 500 1000 1500 2000 Нагрузка [транзакций/секунду] Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 10. Задержка при увеличении транзакционной нагрузки 10 20 30 40 0 500 1000 1500 2000 Валидаторы Задержка [мс] Обновление бухгалтерской книги Голосование Номинация Рисунок 11. Задержка при увеличении количества узлов Изменение количества проверяющих узлов в сети влияет на количество обмениваемых SCP-сообщений, а также количество потенциальных значений при номинации. Рисунок 11 показывает, что время выдвижения кандидатур растет относительно небольшими темпами. Хотя данные показывают, что голосование является узким местом, мы считают, что многие проблемы масштабирования можно решить, улучшив Оверлейная сеть Stellar для оптимизации сетевого трафика. Как ожидаемо, задержка обновления реестра оставалась независимой от количество узлов. Закрыть курс Наконец, мы хотели измерить сквозную производительность Stellar, измеряя, как часто регистры подтверждаются и достигает ли Stellar своего 5-секундного целевого показателя без отмена любых транзакций. Мы наблюдали среднее закрытие книги раз 5,03 с, 5,10 с и 5,15 с по мере увеличения счета записи, скорость транзакций и количество узлов соответственно. Результаты показывают, что Stellar может последовательно закрывать реестры. под высокой нагрузкой. 7.4 Запуск validator Одной из важных особенностей Stellar является низкая стоимость. запуск validator, поскольку якоря должны работать (или заключать контракт с) validators для обеспечения окончательности. SDF запускает 3 производственных validator, все на экземплярах AWS c5.large, которые имеют два ядра, 4 ГБ ОЗУ и процессор Intel(R) Xeon(R) Platinum 8124M Процессоры @ 3,00 ГГц. Проверка использования ресурсов на одном из этих машин мы наблюдали процесс Stellar, используя около 7% процессора и 300 МБ памяти. С точки зрения сетевого трафика: 28 подключений к узлам и размер кворума. из 34 входящие и исходящие скорости составляли 2,78 Мбит/с, а 2,56 Мбит/с соответственно. Аппаратное обеспечение, необходимое для запуска такого процедура недорогая. В нашем случае стоимость составляет $0,054/час. или около 40 долларов в месяц. 7,5 Будущая работа Эти эксперименты показывают, что Stellar может легко масштабироваться на 1–2 порядка. масштабов, превосходящих сегодняшнее использование сети. Потому что Требования к производительности на сегодняшний день настолько скромны, что Stellar оставляет место для многих простых оптимизаций с использованием известные методики. Например, транзакции и SCP сообщения транслируются validators с использованием наивного флуда протокол, но в идеале следует использовать более эффективный, структурированный одноранговая многоадресная рассылка [30]. Кроме того, большая база данных Время обновления реестра можно сократить с помощью стандартных методов пакетной обработки и предварительной выборки.
評価
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]。さらに、データベースを多用する 台帳の更新時間は、標準のバッチ処理およびプリフェッチ技術によって改善できます。
Заключение
Международные платежи стоят дорого и занимают несколько дней. Фонд хранение проходит через несколько финансовых учреждений, включая банки-корреспонденты и службы денежных переводов. Поскольку каждому переходу необходимо полностью доверять, новым пользователям сложно абитуриентам, чтобы завоевать долю рынка и конкурировать. Stellar шоу как дешево отправить деньги по всему миру за считанные секунды. Ключевым нововведением является новый протокол Византийского соглашения с открытым членством, SCP, который использует одноранговую структуру. финансовой сети для достижения глобального консенсуса под новая гипотеза Интернета. SCP позволяет Stellar атомарно зафиксировать необратимые транзакции между произвольными участниками, которые не знают друг друга и не доверяют друг другу. Это, в свою очередь, гарантирует новым участникам доступ к тем же рынкам, что и существующие. игроков, позволяет безопасно получить лучший доступный обмен ставки даже у ненадежных маркет-мейкеров, и резко уменьшает задержку платежа. Благодарности Stellar не был бы тем, чем он является сегодня, без раннего лидерство Джойс Ким или огромный вклад Скотт Флекенштейн и Бартек Новотарски в строительстве и поддержание горизонта, Stellar SDK и другие ключевые элементы экосистемы Stellar. Мы также благодарим Колтена Бержерона, Генри Корриган-Гиббс, Кэндис Келли, Капил К. Джайн, Борис Резников, Джереми Рубин, Кристиан Раддер, Эрик Сондерс, Торстен Штюбер, Томер Веллер, анонимные рецензенты и нашему пастуху Жюстин Шерри за полезные комментарии более ранние черновики. Отказ от ответственности Вклад профессора Мазьера в эту публикацию был сделан в качестве платного консультанта и не был частью его работы. Обязанности или ответственность Стэнфордского университета.
Быстрые и безопасные международные платежи с Stellar SOSP '19, 27–30 октября 2019 г., Хантсвилл, Онтарио, Канада
結論
国際決済は高額で日数もかかります。基金 保管はコルレス銀行や送金サービスを含む複数の金融機関を経由します。 各ホップは完全に信頼される必要があるため、新しいホップは困難です。 参入者は市場シェアを獲得し、競争します。 Stellar の番組 数秒で世界中に安く送金する方法。の 主要な革新は、ピアツーピア構造を活用した新しいオープンメンバーシップのビザンチン協定プロトコルである SCP です。 世界的なコンセンサスを達成するための金融ネットワークの構築 新しいインターネット仮説。 SCP は Stellar をアトミックにコミットさせます 任意の参加者間の不可逆的なトランザクション。 お互いのことを知らないし信頼もしていない。これにより、新規参入者が既存の市場と同じ市場にアクセスできることが保証されます。 プレーヤーは、利用可能な最高の交換を安全に入手できます 信頼できないマーケットメーカーからのレートであっても、劇的に上昇します。 支払いの待ち時間を短縮します。 謝辞 Stellar は、初期の ジョイス・キムのリーダーシップまたは多大な貢献 スコット・フレッケンシュタインとバルテック・ノヴォタルスキーが建築と Horizon、Stellar SDK、およびその他の重要な要素の維持 Stellar エコシステムの。コルテン・ベルジェロンにも感謝します。 ヘンリー・コリガン＝ギブス、キャンディス・ケリー、カピル・K・ジェイン、ボリス レズニコフ、ジェレミー・ルービン、クリスチャン・ラダー、エリック・サンダース、 Torsten Stüber、Tomer Weller、匿名の査読者、 私たちの羊飼いのジャスティン・シェリーさんに有益なコメントをいただきました 以前の草案。 免責事項 マジエール教授のこの出版物への貢献は有償コンサルタントとしてのものであり、教授の活動の一部ではありませんでした。 スタンフォード大学の義務または責任。
Stellar による高速かつ安全なグローバル支払い SOSP ’19、2019 年 10 月 27 ～ 30 日、カナダ、オンタリオ州ハンツビル