ビザンチン断層

ビザンチン障害とは、特に分散コンピューティングシステムにおいて、システム コンポーネントが故障したかどうかの情報が不完全であるなど、さまざまな観察者にさまざまな症状が現れる障害が発生するシステムの状態です。この用語は、「ビザンチン将軍問題」^[1]という寓話に由来しています。これは、システムの壊滅的な故障を回避するために、システムのアクターが戦略に同意する必要があるが、これらのアクターの一部が信頼できないために、他の (善良な) アクターが戦略に同意できず、その不一致に気付かない可能性がある状況を説明するために考案されました。

ビザンチン障害は、ビザンチン将軍問題、ビザンチン合意問題、またはビザンチン障害とも呼ばれます。

ビザンチンフォールトトレランス( BFT ) は、フォールトトレラントコンピュータシステムまたは同様のシステムがそのような状況に対して 示す回復力です。

ビザンチン障害とは、観察者によって症状が異なる障害のことです。^{[2]ビザンチン障害とは、複数のコンポーネント間の}合意を必要とするシステムにおいて、ビザンチン障害によってシステムサービスが失われることです。^[3]

ビザンチンの寓話では、要塞を攻撃している数人の将軍が描かれています。将軍たちはグループとして攻撃するか撤退するかを決めなければなりません。攻撃を好む将軍もいれば、撤退を好む将軍もいます。重要なのは、将軍全員が共通の決定に同意することです。なぜなら、数人の将軍による中途半端な攻撃は敗走につながり、協調攻撃や協調撤退よりも悪い結果になるからです。

問題は、最適ではない戦略に投票するだけでなく、選択的に投票する可能性のある裏切り者の将軍の存在によって複雑化します。たとえば、9 人の将軍が投票し、そのうち 4 人が攻撃を支持し、他の 4 人が撤退を支持している場合、9 人目の将軍は撤退を支持する将軍に撤退票を送り、残りの将軍に攻撃票を送ることができます。9 人目の将軍から撤退票を受け取った将軍は撤退し、残りの将軍は攻撃します (攻撃側にとってはうまくいかない可能性があります)。将軍が物理的に離れており、投票をメッセンジャーを介して送る必要があるため、メッセンジャーが投票を届けられなかったり、偽造票を作成したりする可能性があるため、問題はさらに複雑になります。

メッセージ署名がない場合、ビザンチンフォールトトレランスは、将軍の総数が不忠誠な（欠陥のある）将軍の数の3倍を超える場合にのみ達成できます。欠落したメッセージにはデフォルトの投票値を与えることができます。たとえば、欠落したメッセージには「null」値を与えることができます。さらに、null投票が多数派であるという合意があれば、事前に割り当てられたデフォルトの戦略（撤退など）を使用できます。^[4]

この寓話をコンピュータ システムにマッピングすると、コンピュータが将軍で、そのデジタル通信システム リンクがメッセンジャーであることが一般的です。この寓話では、この問題は意思決定とセキュリティの問題として定式化されていますが、電子工学では、誤った電圧などの障害が暗号化プロセスを通じて伝播する可能性があるため、暗号 デジタル署名だけでは解決できません。したがって、誤ったメッセージが送信され、一部の受信者はメッセージが誤り (署名が間違っている) であると検出し、他の受信者は署名が正しいと認識し、3 番目のグループも署名が正しいと認識しますが、2 番目のグループとは異なるメッセージの内容になります。^[2]

ビザンチン合意を得る問題はロバート・ショスタクによって考案され形式化され、彼はそれを対話型一貫性問題と名付けました。この研究は1978年にNASAが後援するSIFT ^{[5]プロジェクトの一環として}SRIインターナショナルのコンピュータサイエンス研究所で行われました。SIFT (Software Implemented Fault Toleranceの略) はジョン・ウェンズリーの発案によるもので、たとえ一部のコンピュータに障害があっても、ペアワイズメッセージングを介して通信する複数の汎用コンピュータを使用して合意に達するというアイデアに基づいています。

プロジェクトの開始時には、 n 台の故障したコンピュータの共謀によって、正常に動作しているコンピュータによる合意形成の努力が「妨害」されないことを保証するために、合計で何台のコンピュータが必要かは明らかではありませんでした。ショスタクは、最低でも 3 n+ 1 台が必要であることを示し、 n =1 の場合に機能する2 ラウンドの 3 n+1メッセージング プロトコルを考案しました。彼の同僚であるマーシャル ピーズは、n > 0 の任意の値に対してアルゴリズムを一般化し、3 n +1 台が必要かつ十分であることを証明しました。これらの結果は、後にレスリー ランポートがデジタル署名を使用して3 n 台で十分であることを証明したものとともに、画期的な論文「故障がある場合の合意形成」に掲載されました。^[6]著者らはこの論文により 2005 年のエドガー W. ダイクストラ賞を受賞しました。

対話的一貫性の問題を理解しやすくするために、ランポートは、軍の将軍たちが都市を攻撃する計画を立てるという色彩豊かな寓話を考案した。オリジナルのバージョンでは、物語では将軍たちがアルバニア軍の指揮官として登場した。名前は変更され、最終的にはジャック・ゴールドバーグの提案により、将来的に攻撃の恐れがないように「ビザンチン」に落ち着いた。 ^[7]この問題の定式化は、いくつかの追加結果とともに、同じ著者によって 1982 年の論文「ビザンチン将軍問題」で発表された。^[4]

ビザンチン フォールト トレランスの目的は、システムの他のコンポーネントが相互に合意に達することを妨げる症状の有無にかかわらず、システム コンポーネントの障害から防御できるようにすることです。このような合意は、システムの正常な動作に必要です。

ビザンチン フォールト トレラント システムの残りの正常な動作コンポーネントは、サービスを維持するために十分な数の正確に動作するコンポーネントが存在すると仮定すると、当初の意図どおりにシステムのサービスを提供し続けることができます。

エラーのみによる障害の伝播を考えると、ビザンチン障害は障害モードの中で最も一般的で最も困難な障害のクラスであると考えられます。いわゆるフェイルストップ障害モードは、スペクトルの最も単純な端を占めます。フェイルストップ障害モードは、障害が発生する唯一の方法が他のノードによって検出されるノードのクラッシュであることを意味しますが、ビザンチン障害は作成できるエラーに制限がないことを意味します。つまり、障害が発生したノードは、他のノードのサブセットに対して機能しているノードのように見えるデータを含め、任意のデータを生成できます。したがって、ビザンチン障害は障害検出システムを混乱させる可能性があり、フォールトトレランスを困難にします。この寓話にもかかわらず、ビザンチン障害は必ずしも敵対的な人間の干渉を伴うセキュリティ問題ではありません。純粋に物理的またはソフトウェアの障害から発生する可能性があります。

ここでの障害と故障という用語は、IEEEコンピュータ協会のディペンダブルコンピューティングとフォールトトレランスに関する技術委員会とIFIPワーキンググループ10.4ディペンダブルコンピューティングとフォールトトレランスによって結成された「基本概念^と用語」に関する合同委員会によって作成された標準定義[8]に従って使用されています。 ^[9]信頼性も参照してください。

ビザンチン フォールト トレランスは、ブロードキャストの一貫性、つまり、コンポーネントが他のすべてのコンポーネントに値をブロードキャストすると、すべてのコンポーネントがまったく同じ値を受信するか、ブロードキャスターが一貫していない場合は、他のコンポーネントが共通の値に同意するという特性のみに関係します。この種のフォールト トレランスは、値自体の正確さを網羅していません。たとえば、敵対的なコンポーネントが故意に誤った値を送信し、すべてのコンポーネントに一貫して同じ値を送信する場合、ビザンチン フォールト トレランス スキームでは捕捉されません。

1982年にラムポート、ショスタク、ピーズによっていくつかの初期の解決策が説明されました^。[4]彼らは、将軍の問題は「指揮官と中尉」の問題を解決することに還元できることに注目することから始めました。その問題とは、指揮官が忠実な場合には、忠実な中尉は全員一致で行動し、彼らの行動は指揮官の命令と一致しなければならないというものです。

• 1 つの解決策は、メッセージが偽造される可能性があるが、不忠な将軍の数が将軍の 3 分の 1 未満である限り、ビザンチン フォールト トレラントとなるシナリオを検討することです。3 分の 1 以上の裏切り者に対処することが不可能であることは、最終的には、司令官が裏切り者である場合、1 人の司令官と 2 人の中尉の問題を解決できないことを証明することに帰着します。これを理解するために、裏切り者の司令官 A と 2 人の中尉 B と C がいると仮定します。A が B に攻撃、C に撤退を指示し、B と C が互いにメッセージを送信して A のメッセージを転送した場合、B も C も誰が裏切り者かわかりません。必ずしも A とは限らないためです。もう 1 人の中尉が A からのメッセージを偽造した可能性があります。将軍の総数をn 、そのn内の裏切り者の数をtとすると、 n > 3 tで通信が同期している (遅延が制限されている)場合にのみ問題の解決策があることが示されます。 ^[10] BFT の完全な要件は次のとおりです。ビザンチン障害の数 F に対して、少なくとも 3F+1 のプレーヤー (障害封じ込めゾーン)、2F+1 の独立した通信パス、および F+1 ラウンドの通信が必要です。良性の (非ビザンチン) 障害とビザンチン障害が同時に存在するハイブリッド障害モデルが存在する可能性があります。許容する必要がある追加の良性障害ごとに、上記の数値を 1 ずつ増やす必要があります。BFT 通信ラウンドが存在しない場合は、ハードウェアに障害がなくてもビザンチン障害が発生する可能性があります。
• 2 つ目の解決策は、偽造不可能なメッセージ署名を必要とする。セキュリティが重要なシステムでは、デジタル署名(現代のコンピュータ システムでは、実際には公開鍵暗号化を使用して実現できる) によって、不特定多数の反逆将軍の存在下でビザンチン フォールト トレランスを実現できる。しかし、安全性が重要なシステム(「セキュリティ」が知的な脅威に対処し、「安全性」が活動やミッションに内在する危険、つまり自然現象による障害に対処するシステム) では、CRCなどのエラー検出コードによって、はるかに低コストで強力なカバレッジが実現できる (CRC は、暗号化では実現できないエラーを保証してカバレッジできる点に注意する必要がある。暗号化方式がメッセージ エラーのカバレッジをある程度保証できるとしたら、その構造は安全ではないものになるだろう。^[11] )。しかし、デジタル署名も CRC などのエラー検出コードも、自然原因によるビザンチン エラーに対する既知のレベルの保護は提供できない。さらに一般的には、セキュリティ対策によって安全性が弱まる場合があり、その逆もある。したがって、暗号デジタル署名方式は、特定のセキュリティ脅威もない限り、安全性が重要なシステムには適していません。^[12] CRCなどのエラー検出コードは暗号化技術よりも優れていますが、どちらも安全性が重要なシステムのアクティブな電子機器を十分にカバーしていません。これは、シュレーディンガーCRCシナリオで示されており、CRCで保護されたメッセージに1つのビザンチン欠陥ビットが含まれていると、異なる観察者に異なるデータが表示され、各観察者は有効なCRCを確認します。^{[2] [3]}
• また、すべての将軍が直接通信できない状況でもビザンチンフォールトトレラントな動作を可能にする最初の2つのソリューションのバリエーションも提示されています。^[1]

上記の最低要件を満たさずに BFT を主張するシステムは数多くあります (例: ブロックチェーン)。これが不可能であるという数学的証明があることを考えると、これらの主張には、BFT の定義が元の定義から逸脱しているという警告を含める必要があります。つまり、ブロックチェーンなどのシステムは合意を保証するものではなく、不一致を高価にするだけです。

1980年頃にはビザンチンフォールトトレランスを実装したシステムアーキテクチャがいくつか設計された。これには、DraperのFTMP、^[13]、 HoneywellのMMFCS、^{[14] 、SRIのSIFT [5]}などがある。

1999年にミゲル・カストロとバーバラ・リスコフは「実用的なビザンチンフォールトトレランス」（PBFT）アルゴリズム^[15]を発表しました。これは、1秒あたり数千のリクエストを1ミリ秒未満の遅延で処理する高性能なビザンチン状態マシンレプリケーションを提供します。

PBFTの後、堅牢性と性能を向上させるためにいくつかのBFTプロトコルが導入されました。たとえば、Q/U ^[16] 、 HQ ^[17] 、 Zyzzyva ^[18]、ABsTRACTs ^[19]はパフォーマンスとコストの問題に対処しました。一方、Aardvark ^[20]やRBFT ^[21]などの他のプロトコルは堅牢性の問題を解決しました。さらに、Adapt ^[22]は、既存のBFTプロトコルを適応的に切り替えて利用し、基礎となる条件の変化に応じてシステムの堅牢性と性能を向上させようとしました。さらに、信頼できるコンポーネントを活用してレプリカの数を減らすBFTプロトコルが導入されました。たとえば、A2M-PBFT-EA ^[23]やMinBFTです。^[24]

ビザンチン失敗のいくつかの事例は、2つの同等のジャーナル論文に掲載されています。^{[2] [3]これらの事例やその他の事例は、} NASA DASHlinkのウェブページで説明されています。^[25]

ビザンチンフォールトトレランスメカニズムは、受信メッセージ（または署名のみ。ノードに自己チェックペアが使用されている場合は、1ビットの情報にまで削減可能）をその受信メッセージの他の受信者に繰り返すコンポーネントを使用します。これらのメカニズムはすべて、メッセージを繰り返す行為がビザンチン症状の伝播をブロックするという仮定に基づいています。安全性やセキュリティの重要性が高いシステムの場合、これらの仮定が許容可能なレベルのフォールトカバレッジで正しいことが証明されなければなりません。テストを通じて証明する場合、1つの困難は、ビザンチン症状を持つ十分に広い範囲の信号を作成することです。 ^[26]このようなテストには、おそらく専用のフォールトインジェクターが必要になります。^{[27] [28]}

ビザンチンエラーは、少なくとも2005年（問題が公表された年）までは、新造されたバージニア級潜水艦の耐久試験中に、不定期に、不規則な時点で観察された。 ^[29]

ビットコインネットワークは並行して動作し、プルーフオブワークを備えたブロックチェーンを生成することで、システムがビザンチン障害を克服し、システムの状態の一貫したグローバルビューに到達できるようにします。^{[30] [31]}一部のプルーフオブステークブロックチェーンもBFTアルゴリズムを使用しています。^[32]

ビザンチンフォールトトレランス（BFT）はブロックチェーン技術において重要な概念であり、一部のノード^[33] （参加者）が故障したり悪意を持って行動したりした場合でもネットワークが機能し続けることを保証します。ブロックチェーンは中央権限のない分散型システムであるため、この耐性は必須であり、たとえ一部の人がプロセスを妨害しようとしたとしても、ノード間で合意を形成することが不可欠です。

安全メカニズム:さまざまなブロックチェーンが、ビザンチン障害に対処するために、PBFT (Practical Byzantine Fault Tolerance)、Tendermint、DPoS (Delegated Proof of Stake) などのさまざまな BFT ベースのコンセンサス メカニズムを使用しています。これらのプロトコルにより、大多数の正直なノードがチェーン内の次のブロックに同意できるようになり、ネットワークを攻撃から保護し、二重支払いやその他の種類の詐欺を防止できます。ネットワークの実際の例としては、Hyperledger Fabric、Cosmos、Klever などが挙げられます。

51% 攻撃の緩和:ビットコインなどの従来のブロックチェーンは、 51% 攻撃の影響を受けやすいプルーフ オブ ワーク (PoW) を使用していますが、BFT ベースのシステムは、ネットワークの整合性を損なうことなく、最大 3 分の 1 の障害のあるノードや悪意のあるノードを許容するように設計されています。

分散型信頼:ビザンチン フォールト トレランスは、分散型ネットワークの信頼モデルの基盤となります。ネットワークのセキュリティは、中央機関に頼るのではなく、誠実なノードが悪意のあるノードの数を上回り、それを打ち負かす能力に依存します。

プライベートおよび許可型ブロックチェーン: BFT は、限られた数の既知の参加者が迅速かつ安全に合意に達する必要があるプライベートまたは許可型ブロックチェーンで特に重要です。これらのネットワークでは、パフォーマンスとセキュリティを強化するために BFT プロトコルがよく使用されます。

ボーイング777航空機情報管理システム（ ARINC 659 SAFEbusネットワーク経由）、ボーイング777飛行制御システム、ボーイング787飛行制御システムなどの一部の航空機システムは、ビザンチンフォールトトレランスを使用しています。これらはリアルタイムシステムであるため、ビザンチンフォールトトレランスソリューションは非常に低いレイテンシでなければなりません。たとえば、SAFEbusは、1マイクロ秒のオーダーの追加レイテンシ内でビザンチンフォールトトレランスを実現できます。^{[34] [35] [36]} SpaceX Dragonは、設計においてビザンチンフォールトトレランスを考慮しています。^[37]

• アトミックコミット – 一連の個別の変更を単一の操作として適用する操作
• ブルックス・アイアンガーアルゴリズム – センサーネットワーク向け分散アルゴリズム
• アルゴリズムとデータ構造に関連する用語の一覧
• Paxos (コンピュータサイエンス)  – 合意形成を解決できるプロトコル群
• 量子ビザンチン合意 – ビザンチン合意プロトコルの量子バージョン
• 二人の将軍の問題 – 思考実験
• 競合のない複製データ型 – データ構造の種類

• Deirmentzoglou, Evangelos; Papakyriakopoulos, Georgios; Patsakis, Constantinos (2019). 「Proof of Stake プロトコルに対する長距離攻撃に関する調査」. IEEE Access . 7 : 28712–28725 . Bibcode :2019IEEEA...728712D. doi : 10.1109/ACCESS.2019.2901858 . eISSN  2169-3536. S2CID  84185792.
• バシール、イムラン。「ブロックチェーンコンセンサス」。ブロックチェーンコンセンサス - 古典、ブロックチェーン、量子コンセンサスプロトコル入門。ISBN 978-1-4842-8178-9 Apress、カリフォルニア州バークレー、2022年。doi : 10.1007 /978-1-4842-8179-6 

• RKBExplorer におけるビザンチンフォールトトレランス