「非同期」ネットワークのビザンチン フォールト トレランスのしきい値が決定されるのはなぜですか?(障害のあるノードが 1 つでも許容できない場合)

Question

次の回答では (リンク： https://bitcoin.stackexchange.com/a/58908/41513)、次のことが示されています。 非同期ビザンチン協定:

「ノードの1/3以上が不正であることは許されません。そうでなければ、私たちは負けます 安全か、生活かのどちらかです」

この証明のために、次の条件/要件が考慮されています。

1. 私たちのシステムは 非同期.
2. 参加者の中には悪意のある人もいるかもしれません。
3. 私たちは安全を望んでいます。
4. 私たちは活気を求めています。

基本的な疑問は次のとおりです。

次のタイトルの有名な論文を考慮してみましょう。 「1 つのプロセスに欠陥があると分散コンセンサスが不可能になる」 (リンク： https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

次のことを示しています:

完全に非同期のコンセンサス プロトコルは、単一の予告なしのプロセス停止さえも許容できません。,

それでもネットワークが非同期であると仮定できますか?この場合と同様に、ネットワークは 1 つのノードでも障害を許容できません。

Answer 1

その答えは、これらのさまざまな結果で行われた正確な仮定を追跡することに関係しています。つまり、両方の結果は非同期を前提としていますが、「1 つの欠陥のあるプロセスによる分散型コンセンサスの不可能性」には、より強力な形式の稼働性と決定性が必要であり、それがコンセンサスを不可能にしています。

1.1 つの欠陥のあるプロセスによる分散型コンセンサスの不可能性

この独創的な結果 (マイケル フィッシャー、ナンシー リンチ、マイケル パターソン) は、システムが非同期であるだけでなく、次の条件も満たす分散型コンセンサスに関するものです。

• 決定論。 コンセンサス アルゴリズムではランダム性は使用されません。

• メッセージ遅延時の活性度。 メッセージが恣意的に遅延する可能性があるだけでなく、そのような継続的な遅延が存在する場合でもメッセージの生存性を保証する必要があります。

これらの特性が強すぎて分散型合意が不可能になる理由を見てみましょう。

例を考えてみましょう。アリス、ボブ、チャーリーは友達なので、どこで夕食に会うかを決めたいと思っています。そのうちの 1 人が予期せず行動をやめ (または、もう友達になることに興味がないと判断し)、メッセージに応答しなくなる可能性があります。この場合でも、他の 2 人が会う場所を決めることができます。さて、彼らは何をすべきでしょうか？

明らかなアプローチは次のとおりです。

アリスはどこに行くかを決めて、ボブとチャーリーに伝えます。

しかし、Alice が AWOL になる可能性があるため、これは機能しません。したがって、これを修正するには、次に最も明白なアプローチが考えられます。

アリスとボブは二人とも他の人に行き先を告げます。みんながアリスから聞いたら、アリスの言うところへ行きます。そうしないと、ボブの言うところへ行くことになります。

しかし、これには新たな問題が生じます。あなたがチャーリーだとしましょう。アリスから連絡があれば、どこに行けばいいかわかります。どちらからも連絡がない場合は、連絡を待ちます。問題は、ボブから連絡があったが、アリスからは連絡がなかった場合です。任意のメッセージ遅延があるため、ボブが言った場所に進むことを約束することはできません。アリスはどこに行くべきかを言ったのに、あなたはまだそれを受け取っていないだけかもしれません。したがって、あなたは完全に行き詰まっており、アリスが突然行動を失ってしまった場合、あなたはただ永遠に待ち続けることになるでしょう。

ここでの問題は、トランザクションを中止する方法がないことです。「OK、これはうまくいかず、時間がかかりすぎて遅延が発生していないので、もう一度やり直しましょう」と言う方法はありません。現実世界のコンセンサスアルゴリズム(最もよく知られているのはPaxos)は、ネットワーク遅延のためにラウンドが失敗する可能性があり、この場合、ネットワーク遅延が短くなることを期待して再試行するだけです。さらに、ランダム化されたプロトコルを使用することで問題を回避することも可能です。 いつもの 動作し、確率が低い (またはゼロの場合さえある) 場合に限り、永遠に継続します。

2.非同期ビザンチン協定（以下の場合） $1/3$ ノードの一部に障害が発生しました

あなたがリンクした bitcoinSE の投稿では、生存性の問題は曖昧にされており、それは「前進し続ける能力」であるとだけ述べられています。実際、上記の結果は、これの最も強力な形式が不可能であることを示しているため、要件/仮定を緩和する必要があります。

2 つの例を考えてみましょう。Miguel Castro と Barbara Liskov の「実践的なビザンチン フォールト トレランス」では、ノードの 3 分の 1 未満に障害が発生するという実用的な稼働状態を達成しています。 メッセージの遅延が無制限に増加し続けることはないと仮定します。. 。著者らは次のように述べています。

私たちは、クライアントであるライブネスを保証します 最終的に、最大で提供された要求に対する応答を受け取ります $\frac{n-1}{3}$ レプリカには欠陥があり、 $遅延(t)$ しない より速く成長する $t$ 無期限。。。これはかなり弱い同期です 実際のシステムで真である可能性が高い仮定 ネットワーク障害が最終的に修復された場合、 [9] の不可能性の結果を回避することができます。

ここで [9] は、上で説明した不可能な結果です。私たちの例をわかりやすく言えば、弱い形式の同期を要求することで、チャーリーに関する上記の問題を回避します。メッセージの遅延は一時的に増加するだけであり、無期限に増加することはないことがわかっているため、チャーリーは単に永遠に待ち続ける必要はありません。(もちろん、実際のアルゴリズムはさらに複雑になりますが、これは部分的にはライブネスが可能である理由の概念的なアイデアです。)

Ran Canetti と Tal Rabin の「最適な復元力を備えた高速非同期ビザンチン協定」では、ランダム性を使用して、以下の条件でライブ性を実現しています。 $n/3$ ビザンチン ノードの障害。彼らの論文から:

この設定では、 $(\lceil\frac{n}{3} ceil- 1)$-回復力のあるビザンチン協定プロトコル。で 圧倒的な確率で、欠陥のないすべてのプレーヤーがプロトコルの実行を完了します。条件は、 障害のないすべてのプレイヤーが プロトコルの実行は、常に期待される 時間。

ここ $(\lceil\frac{n}{3} ceil- 1)$-resilient は、ノードの 3 分の 1 未満がビザンチンであることを意味します。キーワードに注意してください 圧倒的な確率で。 したがって、彼らは多くの可能な「実行」を備えた確率的アルゴリズムを備えており、圧倒的にそのほとんどが機能します。上記の不可能な結果は、常に存在する必要があることを意味していることに注意してください。 いくつかの 活性が発生しない場所で実行されます。コンセンサスはありません:

フィッシャー、リンチ、およびパターソンの [FLP] 決定論的プロトコルに対する影響力のある不可能性の結果は、BA に到達する (ランダム化された) プロトコルには非終了実行が必要であることを意味します。