ビザンチン耐故障性

ビザンチン耐故障性とは、一部のプロセスが任意に故障し、矛盾したメッセージや悪意のあるメッセージを送信する可能性があっても、合意に達する方法を研究する分野です。

Definition

ビザンチン故障とは、悪意のある動作を含む、コンポーネントの仕様からの任意の逸脱を指します。ビザンチン耐故障性とは、分散プロトコルが、限定された数の故障した参加者が存在しても、その正確性条件を満たす能力を指します。

Scope

このトピックでは、ビザンチン将軍問題とその確立する厳密な耐障害性限界（f個の任意の故障を許容するには、少なくとも3f+1個のプロセス、または署名付きメッセージが必要）、同期的な口頭および署名付きメッセージ合意アルゴリズム、ならびにPBFTとその派生プロトコルなどの実用的な非同期ビザンチン耐故障性プロトコルについて扱います。これは、許可型ブロックチェーンや高信頼性複製サービスの信頼モデルの基礎となります。

Core questions

• 与えられた数の任意の故障を許容するために、いくつの正しいプロセスが必要ですか？
• デジタル署名はビザンチン合意の耐障害性限界をどのように変化させますか？
• 実用的な非同期システムのために、ビザンチン合意をどのように効率化できますか？

Key theories

ビザンチン将軍の限界

認証されていない（口頭の）メッセージの場合、ビザンチン合意は、プロセスの3分の2以上が正しい場合にのみ解決可能です（n > 3f）。偽造不可能な署名を持つ認証済みメッセージは、この要件を緩和します。

実用的なBFT複製

PBFTは、ビザンチン合意が、プライマリと3段階プロトコルを使用するステートマシン複製を備えた部分同期システムで実行可能であることを示し、最大3分の1の故障したレプリカを許容しながら実用的なパフォーマンスを達成します。

同期合意アルゴリズム

同期モデルでは、再帰的な口頭メッセージおよび署名付きメッセージアルゴリズムがf+1ラウンドで合意を達成し、任意の故障を許容するためのラウンド複雑度のコストを示しています。

Clinical relevance

ビザンチン耐故障性は、クラッシュだけでなく、侵害や悪意のある動作にも耐えなければならないシステムの基盤となります。これには、許可型ブロックチェーン、高信頼性複製サービス、および任意のコンポーネント故障が排除できない航空電子工学や航空宇宙制御などが含まれます。

History

Pease、Shostak、Lamportは1980年に合意限界を確立し、1982年にビザンチン将軍問題として劇的に表現しました。約20年間、ビザンチン合意は実用にはコストがかかりすぎると考えられていましたが、1999年のCastroとLiskovによるPBFTが効率的な非同期ビザンチン複製を実証し、この分野を再活性化させ、後にブロックチェーンのコンセンサスに影響を与えました。

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

f個のビザンチン故障を許容するために3f+1個のプロセスが必要なのはなぜですか？

正しいプロセスは、f個の故障したプロセスが嘘をつき、さらにf個のプロセスが遅延または到達不能である場合でも、多数決の決定に達する必要があります。故障した参加者と遅延している参加者の組み合わせを常に上回るには、故障したプロセスの数の3倍を超えるプロセスが必要となります。