Stellar コンセンサス プロトコルは、最初に説明されました。 科学論文 デビッド・マジアー、2015年。 これは、分散型のリーダーレス コンピューティング ネットワークが決定に関して効率的に合意に達することを可能にする「連邦ビザンチン協定システム」です。 Stellar 決済ネットワークは、Stellar Consensus Protocol (SCP) を使用して、すべての参加者が閲覧できる一貫した取引履歴を維持します。

コンセンサスプロトコルは理解することが難しいと考えられています。 SCP は他のほとんどのものよりも単純ですが、依然としてこの評判を共有しています。これは、科学記事の前半の主題である「連合投票」が SCP であるという誤った考えが原因の XNUMX つです。 しかし、それは真実ではありません！ これは、記事の後半で作成するために使用する重要な構成要素にすぎません。 実際の ステラコンセンサスプロトコル。

この記事では、「協定制度」とは何か、それを「ビザンチン」にするもの、そしてビザンチン制度を「連邦」にする理由について簡単に説明します。 次に、SCP 記事で説明されている連合投票手順について説明し、最後に SCP プロトコル自体について説明します。

協定制度

合意システムを使用すると、参加者のグループが、ランチに何を注文するかなどのトピックについて合意に達することができます。

インターステラーでは、独自の食事契約システムを導入しています。つまり、オペレーション マネージャーのジョンの言うとおりに注文します。 これはシンプルかつ効果的な契約システムです。 私たちは皆ジョンを信頼しており、彼が毎日何か面白くて栄養のあるものを見つけてくれると信じています。

しかし、ジョンが私たちの信頼を悪用したらどうなるでしょうか? 彼は私たち全員がヴィーガンになるべきだと独断で決めることができます。 XNUMX、XNUMX週間以内に、我々はおそらく彼を打倒し、エリザベスに権力を引き渡すだろう。 しかし突然、彼女はアンチョビ入りのアボカドが大好きになり、誰もがそうあるべきだと考えました。 権力は腐敗する。 したがって、より民主的な方法を見つけたほうがよいでしょう。タイムリーで明確な結果を確保しながら、さまざまな好みが確実に考慮されるようにする方法です。そうすれば、誰もランチを注文しなくなったり、XNUMX 人が別々の注文をしたり、議論が終わったりすることはありません。夕方まで長引く。

解決策は簡単そうに思えます。投票を続けることです。 しかし、これは誤解を招く印象です。 誰が投票用紙を集めて結果を報告するのでしょうか? そして、なぜ他の人が彼の言うことを信じなければならないのでしょうか？ おそらくできるでしょう 最初 投票を主導すると信頼できるリーダーに投票する - しかし誰が主導するのか первым 投票することで？ リーダーについて合意できない場合はどうすればよいでしょうか? あるいは、合意には達したものの、このリーダーが会議に参加できなくなったり、病気休暇に入ったりしたらどうなるでしょうか?

同様の問題は分散コンピュータ ネットワークでも発生します。 すべての参加者またはノードは、共有ファイルを更新する順番や処理キューからタスクを削除する順番など、何らかの決定に同意する必要があります。 暗号通貨ネットワークでは、ノードは、可能性のあるいくつかのバージョンから完全なストーリーがどのようになるかを繰り返し選択する必要があり、それらは時には矛盾します。 このネットワーク契約は、コインが (a) 有効である (偽造されていない)、および (b) まだ他の場所で使用されていないことを受信者に保証します。 これにより、新しい受取人も同じ理由で同じ保証を受けるため、将来的にコインを使用できることが保証されます。

分散コンピューティング ネットワーク内のコンセンサス システムはフォールト トレラントである必要があります。低速リンク、応答しないノード、不正なメッセージ順序などのエラーにもかかわらず、一貫した結果を生成する必要があります。 ビザンチン さらに、合意システムは「ビザンチン」エラー、つまりエラーによるものであろうと、システムを弱体化させたり何らかの利点を得ようとする意図的な試みによるものであろうと、誤った情報を与えるノードに対する耐性があります。 「ビザンチン」耐障害性 - グループのメンバーの一部が嘘をついたり、意思決定のルールに従わない場合でも、グループの決定を信頼する能力 - と呼ばれます ビザンツ帝国の将軍についての寓話攻撃を調整しようとした人。 良い説明 アンソニー・スティーブンスで。

ボブからおいしいアイスクリームを買うか、キャロルの借金を返済するかの選択を迫られる暗号通貨の所有者アリスのことを考えてみましょう。 おそらくアリスは、同じコインを不正に使って、両方を一度に支払おうとしているのでしょう。 これを行うには、彼女はコインが決してキャロルに支払われなかったことをボブのコンピュータに納得させ、また、キャロルのコンピュータにコインがボブに決して支払われなかったことを納得させなければなりません。 ビザンチンの協定システムでは、と呼ばれる多数決の形式を使用して、これを事実上不可能にしています。 定足数。 このようなネットワーク内のノードは、十分な数のピア (クォーラム) がそのような移行に同意することが確認されるまで、履歴の特定のバージョンへの移行を拒否します。 これが起こると、残りのネットワーク ノードにその決定への同意を強制するのに十分な大きさの投票ブロックが形成されます。 アリスは一部のノードに自分に代わって嘘をつくよう強制できますが、ネットワークが十分に大きい場合、アリスの試みは正直なノードの投票によって圧倒されてしまいます。

クォーラムにはノードがいくつ必要ですか? 少なくとも過半数、あるいは過半数が間違いや不正行為と闘う資格のある過半数を獲得する必要があります。 ただし、過半数を数えるには、参加者の総数を知る必要があります。 インターステラーのオフィスや選挙区で、これらの数字は簡単に調べられます。 ただし、グループが、センターの承認なしにノードが自由に出入りできる、大まかに定義されたネットワークの場合は、次のことが必要です。 連邦政府 あらかじめ決められたノードのリストからではなく、常に変化し、必然的に不完全になる特定の時点でのノードのスナップショットから動的にクォーラムを決定できるビザンチン協定システム。

広大なネットワーク内の単一ノードの観点からクォーラムを作成することは不可能に思えるかもしれませんが、それは可能です。 このような定足数は、分散投票の結果を保証することさえできます。 SCP ホワイトペーパーには、と呼ばれる手順を使用してこれを行う方法が示されています。 連邦投票による.

辛抱強い

この記事の残りの部分では、連合投票と Stellar コンセンサス プロトコルについて詳しく説明します。 詳細に興味がない場合は、プロセスの概要をここで説明します。

1. ノードは「候補者」に対する連邦投票を実施します。 連邦投票ラウンドとは次のことを意味します。
   • ノードは、たとえば「V の値を提案します」などのステートメントに投票します。
   • ノードは、「受信」できるピアが見つかるまで、ピアの音声を聞きます。
   • ノードは、このアサーションの「クォーラム」を探します。 定足数は候補者を「承認」します。
2. ノードが XNUMX 人以上の候補者を確認できると、数ラウンドの連合投票を通じて「投票」を「準備」しようとします。
3. ノードは、投票用紙の準備ができていることを確認できると、さらに多くのフェデレーテッド投票ラウンドを通じて投票用紙をコミットしようとします。
4. ノードが投票のコミットを確認できると、その投票の価値をコンセンサス結果として使用して「外部化」できます。

これらのステップには複数ラウンドの連合投票が含まれており、それらが集合して XNUMX つの SCP ラウンドを形成します。 各ステップで何が起こるかを詳しく見てみましょう。

連合投票

連合投票は、ネットワークが提案に同意できるかどうかを判断する手順です。 投票ラウンドでは、各ノードは潜在的に多くの可能な値の中から XNUMX つを選択する必要があります。 ネットワーク内の他のノードが異なる結果を選択しないという確信がない限り、これを行うことはできません。 これを確認するために、ノードは大量のメッセージをやり取りし、すべてのノードが 確認されたその 定足数 結び目 受け入れる 同じもの 決定。 このセクションの残りの部分では、この文の用語と手順全体がどのように発生するかについて説明します。

クォーラムとクォーラム スライス

クォーラムを定義することから始めましょう。 上で説明したように、動的なメンバーシップを備えた分散型ネットワークでは、ノードの数を事前に知ることは不可能であり、したがって大多数に必要なノードの数を知ることはできません。 連合投票は、新しいアイデアを導入することでこの問題を解決します。 定足数の削減 (クォーラム スライス): ネットワークの残りの部分に投票ステータス情報を伝達するためにノードが信頼するピアの小さなセット。 各ノードは独自のクォーラム スライス (その事実上のメンバーになります) を定義します。

定足数の形成は、定足数の削減から始まります。 各ノードについて、そのカット ノードが追加されます。 次にスライス項が追加されます これらのノード 等々。 続行すると、すでにスライスに含まれているために追加できないノードが増えていきます。 追加する新しいノードがなくなると、プロセスは停止します。最初のノードのクォーラム スライスの「推移的閉包」によってクォーラムが形成されました。

特定のノードからクォーラムを見つけるには...

...そのスライスのメンバーを追加します...

...次に、これらのノードのスライス メンバーを追加します。

追加するノードがなくなるまで続行します。

追加するノードはもうありません。 これは定足数です。

実際、各ノードは複数のスライスに出現する可能性があります。 クォーラムを形成するには、スライスを XNUMX つだけ選択し、メンバーを追加します。 次に、各メンバーの任意のスライスを選択し、メンバーを追加します この カットなど。 これは、各ノードが多くの可能なクォーラムのメンバーであることを意味します。

各ステップでクォーラム スライスを XNUMX つだけ選択します。

可能な定足数は XNUMX つです。 それとも代替案...

...他のスライスを選択...

…（可能な場合）…

... 別のクォーラムを作成します。

ノードは他のノードがどのスライスに属しているかをどのようにして知るのでしょうか? 他のノードに関する他の情報と同様に、投票状態が変化したときに各ノードがネットワークにブロードキャストする送信から取得されます。 各ブロードキャストには、送信ノードのスライスに関する情報が含まれます。 SCP ホワイトペーパーでは通信メカニズムについては規定されていません。 実装では通常、 ゴシッププロトコル ネットワーク全体でのメッセージのブロードキャストを保証します。

非連邦政府のビザンチン協定システムでは、定足数はすべてのノードの過半数として定義されていることを思い出してください。 ビザンチン協定システムは、「システムはどれだけの不誠実なノードを許容できるか?」という問題の観点から設計されています。 f 個の障害に耐えるように設計された N ノードのシステムでは、そのうちの f 個がダウンしている可能性があるため、ノードは N-f 個のピアからフィードバックを受信することで進歩できるはずです。 しかし、N-f 個のピアから応答を受信したので、すべての f 個のピア (ノードが応答を受信しなかった) が実際に誠実であると仮定できます。 したがって、N-f 個のピア (応答の受信元) のうち f 個は悪意のあるものになります。 ノードが同じ合意に達するには、残りのノードの大部分が正直である必要があります。つまり、N−f が 2f より大きいか、N > 3f である必要があります。 したがって、通常、f 回の障害に耐えるように設計されたシステムには、合計 N=3f+1 ノードと 2f+1 のクォーラム サイズがあります。 プロポーザルがクォーラムしきい値を超えると、ネットワークの残りの部分は、競合するプロポーザルは失敗すると確信します。 これが、ネットワークが結果に収束する方法です。

しかし、連邦ビザンチン協定システムでは、過半数が存在できないだけでなく（ネットワークの合計サイズが誰もわからないため）、過半数という概念はまったく役に立ちません。 システム内のメンバーシップがオープンな場合、誰かがいわゆるシビル攻撃を実行するだけで過半数を獲得できます。つまり、複数のノードにわたって繰り返しネットワークに参加することになります。 では、なぜ推移的スライスクロージャを呼び出すことができるのでしょうか 定足数、そして競合する提案をどのようにして抑制できるのでしょうか?

技術的には無理です！ XNUMX つのトリプレットが互いのクォーラム スライス内で分離されている XNUMX つのノードからなるネットワークを想像してください。 最初のサブグループは、XNUMX 番目のサブグループが決して聞かない決定を下す可能性があり、その逆も同様です。 このネットワークが合意に達する方法はありません（偶然を除いて）。

したがって、SCP では、連合投票 (および論文の重要な定理が適用されること) のために、ネットワークに次のプロパティが必要です。 定足数の交差点。 この特性を持つネットワークでは、構築できる XNUMX つのクォーラムは常に少なくとも XNUMX つのノードでオーバーラップします。 ネットワークの一般的な感情を判断するには、これは過半数を獲得するのと同じくらい良いです。 直観的には、これは、いずれかのクォーラムがステートメント X に同意した場合、他のクォーラムは他の内容に同意できないことを意味します。これは、X に既に投票した最初のクォーラムの何らかのノードが必然的に含まれるためです。

ネットワーク内にクォーラムの交差がある場合...

...その後、構築できる任意の XNUMX つのクォーラム...

...必ず交差します。

(もちろん、重複するノードがビザンチンに存在するか、その他の点で問題があることが判明する可能性があります。この場合、クォーラム交差はネットワークの一致にまったく役に立ちません。このため、SCP ホワイト ペーパーの結果の多くは、以下に基づいています。明示的な仮定（ネットワーク クォーラム超過に何が残っているかなど） 不良ノードを削除した後でも。 話を簡単にするために、これらの仮定はそのままにしておきます 暗黙 記事の残りの部分で説明します)。

独立したノードのネットワークで信頼性の高いクォーラム超過が可能であると期待するのは不合理に思えるかもしれません。 しかし、これには XNUMX つの理由があります。

第一の理由は、インターネットそのものの存在です。 インターネットは、交差するクォーラムを持つ独立したノードのネットワークの好例です。 インターネット上のほとんどのノードは、他の少数のローカル ノードにのみ接続しますが、これらの小さなセットは十分に重なり合っているため、あるルートに沿って他のすべてのノードからすべてのノードに到達できます。

XNUMX 番目の理由は、Stellar 支払いネットワーク (SCP の最も一般的な用途) に特有のものです。 Stellar ネットワーク上のすべての資産には発行者があり、Stellar のガイドラインでは、各発行者が引き換えリクエストを処理するネットワーク上の XNUMX つ以上のノードを指定することを要求しています。 関心のある各アセットのクォーラム スライスにこれらのノードを直接的または間接的に含めることが最も有益です。 特定の資産に関心のあるすべてのノードのクォーラムは、少なくともそれらの償還ノードで重複します。 複数の資産に関心のあるノードには、それぞれの発行者のすべての償還ノードがクォーラム スライスに含まれ、すべての資産を一緒にプールしようとします。 さらに、この方法でネットワーク上の他の資産にリンクされていない資産、および 接続してはいけません - これは、このネットワークにクォーラムの重複がないように設計されています (たとえば、ドル圏の銀行は、ユーロ圏の銀行やペソ圏の銀行と取引したい場合があるため、同じネットワーク上にありますが、いずれも存在しません)彼らのうち、野球カードを販売する子供たちの別のネットワークを気にしている人たちです）。

もちろん、 ожидание 定足数を超えていない 保証。 他のビザンチン協定システムは、その複雑さの多くを定足数の保証に負っています。 SCP の重要な革新は、コンセンサス アルゴリズム自体からクォーラムを作成する責任を取り除き、それをアプリケーション レベルに持ってくることです。 したがって、連合投票はあらゆる問題について投票できるほど一般的ですが、実際にはその信頼性はこれらの意味のより広い意味に決定的に依存します。 一部の仮想的な使用法は、他の使用法ほど適切に接続されたネットワークの作成に役立たない場合があります。

投票、承認、確認

連合投票ラウンドでは、ノードはオプションで値 V への投票を開始します。これは、「私はノード N、クォーラム スライスは Q、そして V に投票します。」というメッセージをネットワークにブロードキャストすることを意味します。 ノードがこの方法で投票する場合、ノードは V に反対票を投じたことはなく、今後も投票しないことを約束します。

ピアツーピア ブロードキャストでは、各ノードは他のノードがどのように投票するかを確認します。 ノードがこれらのメッセージを十分に収集すると、クォーラム スライスを追跡し、クォーラムの検索を試みることができます。 V に投票する同僚の定足数を確認した場合は、次の手順に進むことができます。 可決 V を実行し、次の新しいメッセージをネットワークにブロードキャストします。「私はノード N、私のクォーラム スライスは Q、そして私は V を受け入れます。」 承認は、単純な投票よりも強力な保証を提供します。 ノードが V に投票する場合、他のオプションに投票することはできません。 しかし、ノードが V を受け入れる場合、ネットワーク上のどのノードも他のオプションを受け入れることはありません (SCP ホワイトペーパーの定理 8 がこれを証明しています)。

もちろん、V に同意するノードの定足数が直ちに満たされない可能性が高くなります。他のノードが他の値に投票する可能性があります。 しかし、ノードが単純な投票から承認に移行する別の方法があります。 N は、たとえそれに投票しなかったとしても、またその定足数を満たしていなかったとしても、W の別の値を受け入れることができます。 投票を変更する場合は、次を参照してください。 ブロッキングセット W を受け入れたノード。ブロッキング セットは、各クォーラム スライス N からの XNUMX つのノードです。名前が示すように、次のことができます。 ブロックする 他の意味。 そのようなセット内のすべてのノードが W を受け入れる場合、(定理 8 により) 異なる値を取るクォーラムを形成することは決して不可能になるため、N が W を受け入れることも安全です。

XNUMX つのクォーラム スライスを持つノード N。

BDF は N のブロッキング セットです。BDF には、N の各スライスからの XNUMX つのノードが含まれます。

E は N の XNUMX つのスライスに現れるため、BE は N のブロッキング セットでもあります。

ただし、ブロッキング セットはクォーラムではありません。 N の各スライスの 11 つのノードだけをハッキングするだけで十分であれば、ノード N を騙して目的の値を受け入れるように仕向けるのは簡単すぎます。したがって、値を受け入れるだけで投票が終了するわけではありません。 代わりに、N は値を確認する必要があります。つまり、その値を受け入れるノードのクォーラムを確認する必要があります。 そこまで到達すると、SCP ホワイトペーパーが証明しているように (定理 XNUMX で)、ネットワークの残りの部分も最終的に同じ値を確認するため、N は結果として特定の値で連合投票を終了します。

連合投票。

投票、承認、確認のプロセスは、連合投票の XNUMX 回の完全なラウンドを構成します。 Stellar コンセンサス プロトコルは、これらのラウンドの多くを組み合わせて、完全なコンセンサス システムを作成します。

ステラコンセンサスプロトコル

コンセンサスシステムのXNUMXつの最も重要な特性は次のとおりです- セキュリティ и 生存率。 コンセンサスアルゴリズムは、異なる参加者に決して異なる結果を与えることがない場合には「安全」です（ボブの歴史のコピーは決してキャロルと矛盾しません）。 「生存性」とは、アルゴリズムが常に結果を生成すること、つまりアルゴリズムが行き詰らないことを意味します。

連邦投票手順の説明 安全 あるノードが V の値を確認すると、他のノードは他の値を確認しないという意味です。 しかし、「別の意味を確認しない」ということは、必ずしも何かを確認するという意味ではありません。 参加者は非常に多くの異なる値に投票できるため、受け入れしきい値に達するものはありません。 これは、連邦議会の投票には、 生存率.

Stellar コンセンサス プロトコルは、セキュリティと存続可能性の両方を保証する方法で連合投票を使用します。 (SCP のセキュリティと生存可能性の保証には理論上の限界があります。設計では非常に強力なセキュリティ保証が選択され、生存可能性の軽減がわずかに犠牲になりますが、十分な時間があれば、合意に達する可能性が高くなります。) 一言で言えば、そのアイデアは、そのうちの XNUMX つが以下で説明するすべての SCP 投票フェーズを通過するまで、複数の値について複数の連合投票を行うことです。

SCP が合意を求める価値観は、取引履歴、ランチの注文、その他のものである可能性がありますが、これらは受け入れられたり確認されたりする価値観ではないことに注意することが重要です。 代わりに、連邦投票は以下に従って行われます。 これらの値に関するステートメント.

連邦投票の最初のラウンドは次の日に行われます。 推薦段階 （指名フェーズ）では、おそらく V のさまざまな価値観に合わせて、「私は V を指名します」のような一連のステートメントについて説明します。指名の目的は、承認と確認を経た XNUMX つ以上のステートメントを見つけることです。

検証可能な候補者を見つけた後、SCP は投票フェーズに進みます。そこでの目標は、特定の候補者を見つけることです。 速報 (つまり、提案された値のコンテナ) と宣言できるクォーラム 専念 それのために（コミット）。 定足数が投票をコミットすると、その値がコンセンサスとして受け入れられます。 ただし、ノードが投票コミットに投票できる前に、まず確認する必要があります。 キャンセル より低いカウンター値を持つすべての投票用紙。 これらの手順 (投票用紙をキャンセルしてコミットできる投票用紙を見つける) には、複数の投票用紙請求に対する複数ラウンドの連合投票が含まれます。

次のセクションでは、指名と投票について詳しく説明します。

指名

指名フェーズの開始時に、各ノードは自発的に V の値を選択し、「V を指名します」というステートメントに投票できます。 この段階の目標は、連合投票を通じて何らかの価値ある人物の指名を確認することです。

おそらく、十分な数のノードが十分に異なる提案に投票し、どの推薦も受け入れ閾値に達することができないでしょう。 したがって、ノードは自身の指名投票をブロードキャストするだけでなく、ピアの指名を「反映」します。 エコーとは、ノードが候補 V に投票しているが、候補 W に投票している近隣ノードからのメッセージを見た場合、そのノードは V と W の両方に投票することを意味します (指名中にすべてのピア投票がエコーされるわけではありません。これは、投票数の急増につながる可能性があるためです)。 SCP には、これらの投票を規制するメカニズムが含まれています。つまり、ノードの観点からピアの「優先度」を決定するための式があり、優先度の高いノードの投票のみが反映されます。かかるとしきい値が低くなり、ノードは投票を反映するピアのセットを拡張します。優先度の計算式には入力の XNUMX つとしてスロット番号が含まれるため、あるスロットの優先度の高いピアは、スロットの優先度が低いピアになる可能性があります。別のもの、またはその逆)。

概念的には、指名は平行しており、V と W は両方とも別々の連邦投票であり、それぞれ個別に承認または確認を達成することができます。 実際には、SCP プロトコル メッセージはこれらの個々の投票をまとめてパッケージ化します。

V の指名に投票することは、V の指名に決して反対しないという約束ですが、「反対」が何を意味するかはアプリケーション レベル (この場合は SCP) で決定されます。 SCP は、「X を指名する」という投票に矛盾するステートメントを認識しません。つまり、「X を指名することに反対します」というメッセージがないため、ノードは任意の値を指名するために投票できます。 これらの候補の多くは無駄になりますが、最終的にはノードは XNUMX つ以上の値を受け入れるか確認できるようになります。 候補者が確認されると、彼は次のようになります。 候補者.

連合投票を使用した SCP の指名。 ピアによって送信され、ノードによって「反映」される「B」値が多数存在する可能性があります。

推薦により複数の候補者が確定する場合があります。 したがって、SCP では、アプリケーション層が候補を XNUMX つに結合する何らかの方法を提供する必要があります。 コンポジット （複合）。 結合方法は何でも構いません。 重要なことは、この方法が決定論的である場合、各ノードは同じ候補を組み合わせるということです。 ランチ投票システムでは、「統一」とは単に XNUMX 人の候補者のうちの XNUMX 人を拒否することを意味する場合があります。 (ただし、決定論的な方法で: 各ノードはリセットする同じ値を選択する必要があります。たとえば、アルファベット順で前の選択)。 トランザクション履歴が投票される Stellar 決済ネットワークでは、提案された XNUMX つの候補者を統合するには、それらに含まれるトランザクションとその XNUMX つのタイムスタンプのうちの最新のものを統合する必要があります。

SCP ホワイトペーパーは、拡張フェーズの終わりまでにネットワークが最終的に単一の複合体に収束することを証明しています (定理 12)。 しかし、問題があります。連合投票は (SCP のような) 非同期プロトコルです。 言い換えれば、ノードは時間によって調整されるのではなく、ノードが送信するメッセージによってのみ調整されます。 ノードの観点からは、いつになるかは不明です。 終了しました 延長段階。 また、すべてのノードは最終的には同じコンポジットに到達しますが、途中で異なるルートをたどり、途中で異なるコンポジット候補が作成される可能性があり、どれが最終候補であるかを決して知ることができません。

でも普通だよ。 指名はあくまで準備です。 重要なことは、コンセンサスを達成するために候補者の数を制限することであり、これはプロセスで発生します。 ランニング （投票）。

ランニング

速報はカップルですここで、counter は 1 から始まる整数、value は指名段階からの候補です。 これは、ノード自体の候補、またはそのノードによって受け入れられた隣接ノードの候補にすることができます。 大まかに言えば、投票には、投票明細書に対して潜在的に多くの連合投票を保持することによって、ネットワークが特定の投票について特定の候補者について合意に達するよう強制する繰り返しの試みが含まれます。 投票用紙のカウンターは行われた試みを追跡し、カウントの高い投票用紙がカウントの低い投票用紙より優先されます。 ニュースレターなら行き詰まった、新しい投票が始まる、現在投票中。

区別することが重要です 意味 (たとえば、ランチの注文はピザかサラダか)、 ニュースレター (カウンター値のペア) および 文 投票用紙について。 SCP ラウンドには、特に以下の声明に関する連邦投票が数ラウンド含まれています。

• 「投票用紙 B をコミットする準備ができています」および
• 「投票用紙 B のコミットを発表します」

特定のノードの観点から見ると、「私は投票 B をコミットします」というステートメントを確認できる (つまり、受け入れる定足数を見つけた) 投票 B が見つかったときに、コンセンサスが得られます。 この時点から、B で指定された値に基づいて行動しても安全です。たとえば、ランチにこの注文をするなどです。 いわゆる 外部化 意味。 投票の受理が確認されると、ノードは、他のノードが同じ値を外部化したか、または将来外部化するであろうことを確認できます。

多くの連合投票は概念的にはさまざまな投票用紙の請求に基づいて行われますが、各メッセージが多数の投票用紙をカプセル化するため、それほど多くのメッセージは交換されません。 したがって、XNUMX つのメッセージは、一度に多くの連合投票の状態を促進します。たとえば、「私は以下の範囲のコミット投票を受け入れます」 前に」

「準備済み」と「コミット」という用語は何を意味しますか?

他のノードが異なる値の投票用紙をコミットしないと確信している場合、ノードは投票用紙をコミットするために投票します。 これを納得させることが申請書を準備する目的です。 「投票用紙 B をコミットする準備ができています」という投票は、B より小さい投票用紙、つまり少数の投票用紙を決してコミットしないという約束です (SCP では、投票用紙の値が特定の順序である必要があります。したがって、ニュースレター少ない、N1の場合

「私は投票用紙 B をコミットする準備ができています」が「投票用紙 B よりも小さい投票用紙を決してコミットしないことを約束します」を意味するのはなぜですか? SCP ではアボートがコミットの反対であると定義されているためです。 投票用紙を作成するための投票には、他の投票用紙を失格にする投票も含まれます。先ほど説明したように、ある事柄に投票するということは、その事柄には決して反対しないという約束となります。

コミットをブロードキャストする前に、ノードはまず準備済みであることを確認できる通知を見つける必要があります。 言い換えれば、定足数を受け入れる投票用紙が見つかるまで、「投票用紙 B をコミットする準備ができています」というテーマについて、場合によってはさまざまな投票用紙に対して連合投票を実行します。

投票を準備するための投票用紙はどこから来ますか? まず、ノードは <1,C> に投票する準備をブロードキャストします。ここで、C は指名段階で生成された複合候補です。 ただし、投票の準備が始まった後でも、指名により追加の候補者が新たな投票用紙となる可能性があります。 一方、ピアは異なる候補者を持つことができ、「B2 投票をコミットする準備ができています」を受け入れるブロッキング セットを形成することができ、これによりノードもそれを受け入れるように説得されます。 最後に、現在の投票用紙が行き詰まった場合に、より高いカウントの新しい投票用紙に対して新しい連合投票を生成するタイムアウト メカニズムがあります。

ノードは、準備済みであることを確認できる投票用紙 B を見つけるとすぐに、新しいメッセージ「投票用紙 B をコミットする」をブロードキャストします。 この投票は、ノードが B を決して放棄しないことをピアに伝えます。実際、B が投票の場合、次に「投票をコミットする」 「」は、各投票用紙の準備が整っているかどうかについて投票することに無条件で同意することを意味します。 <∞、s>まで。 この追加の値は、他のピアがまだプロトコルの初期段階にある場合に、コミット ピアに追いつくのに役立ちます。

この段階では、これらが非同期プロトコルであることをもう一度強調する価値があります。 XNUMX つのノードがコミットに対して賛成票を送信したからといって、そのノードのピアも賛成票を送信するとは限りません。 彼らの中には、投票の準備でまだ声明に投票している人もいるかもしれないし、すでにその意味を外在化している人もいるかもしれない。 SCP は、フェーズに関係なく、ノードが各タイプのピア メッセージをどのように処理すべきかを説明します。

「コミットを発表しました」というメッセージが表示された場合» 受信または確認できない、つまりメッセージが受け入れられるか確認される可能性または- または、いずれの場合でも、ノードは決してキャンセルしないことをすでに約束しているため、値 C を持つ投票用紙であり、他の投票用紙ではありません。 。 ノードがコミットへの投票をブロードキャストするまでに、コンセンサスがどこまで進むかに応じて、C になるか何もないことになります。 ただし、これはノードが C を外部化するにはまだ十分ではありません。一部のビザンチン ピア (セキュリティの前提に基づくと、クォーラム未満を構成する) がノードに嘘をつく可能性があります。 一部の投票用紙 (または投票用紙の範囲) を受け入れて確認することで、最終的に C を外部化する自信がノードに与えられます。

連合投票による SCP 投票。 図示されていない: タイマーはいつでも作動し、投票用紙の数が増加する可能性があります (さらに追加の指名候補者の新しい複合体が生成される可能性もあります)。

そしてそれだけです！ ネットワークは一度合意に達すると、それを何度でも行う準備ができています。 Stellar 決済ネットワークでは、これは約 5 秒に XNUMX 回発生します。これは、SCP によって保証されたセキュリティと生存可能性の両方を必要とする偉業です。

SCP は、複数ラウンドの連合投票に依存することでこれを達成できます。 連合投票は、クォーラム スライスの概念によって可能になります。クォーラム スライスとは、各ノードがその (主観的な) クォーラムの一部として信頼することを決定したピアのセットです。 この構成は、オープンなメンバーシップとビザンチンの欺瞞があるネットワークでも合意に達することができることを意味します。

参考文献

• オリジナルの SCP ホワイトペーパーはこちらでご覧いただけます ここでと ここで 実装のための仕様草案。
• SCP プロトコルの最初の作成者である David Mazier は、SCP プロトコルを簡略化された (ただし技術的な) 方法で説明しています。 ここで.
• この記事に「マイニング」や「プルーフ・オブ・ワーク」という用語が見つからないことに驚いたかもしれません。 SCP はこれらのメソッドを使用しませんが、他のいくつかのコンセンサス アルゴリズムは使用します。 ゼーン・ウィザースプーンがアクセス可能に書いた コンセンサスアルゴリズムの概要.
• ステップバイステップの説明 SCP の XNUMX ラウンドで合意に達する単純なネットワーク。
• SCP の実装に興味のある読者は: を参照してください。 C++ コード、Stellar 決済ネットワークによって使用される、または Goコード、SCPをよりよく理解するために書きました。

出所： habr.com