古代東ローマ帝国の首都であるビザンツはかつて世界でも有数の強力で豊かな都市の1つでした。しかしながら、その広大な領土のため、ビザンツは外部からの侵略や内部からの反乱にしばしば直面しました。国境を守るために、ビザンツは異なる将軍に指揮される複数の軍を送り出しました。これらの将軍の間で合意を形成することは大きな課題となりました。
ビザンチン将軍問題はブロックチェーンと密接な関係があります。ブロックチェーンネットワークは、ビザンチンの将軍のようなノードが信頼性の低いネットワーク環境で取引やデータについて合意を形成しなければならない分散ネットワークです。

2つの将軍問題

Two Generals ProblemはByzantine Generals Problemの特殊なケースです。この問題とその解決不能性の証明は、E.A. Akkoyunlu、K.Ekanadham、R.V. Huberによって最初に提案され、1975年の論文「Some Constraints and Trade-offs In The Design of Network Communications」で発表されました。1978年、Jim Grayはこの問題を正式に彼の著書「Notes on Data Base Operating Systems」で「Two Generals Problem」と名付けました。もともとは、信頼性の低い通信リンクを介してコミュニケーションを通じて合意に達する問題を分析するために使用されました。現在では、分散システムにおける整合性と合意の問題を示すために一般的に使用されています。

問題の定義：
国Aの2つの軍隊はそれぞれ将軍に率いられ、国Bの軍隊を攻撃する準備をしています。国Bの軍隊は谷で包囲されており、Aの2つの軍隊は谷の両側の丘に配置されています。ただし、Aの2つの軍隊の間をつなぐ唯一の道は谷を通るものです。Bの軍隊はAのどちらの軍隊よりも強力ですが、Aの両軍が一緒に攻撃すればBの軍隊を打ち負かすことができます。
問題: A軍の2人の将軍が同時攻撃に合意するアルゴリズムを考案することは可能ですか？ そのアルゴリズムにはメッセージの送受信が含まれる場合があります。
解決策:古典的な2人の将軍の問題は解決できません。Aの両軍が攻撃をうまく連携させることを保証するプロトコルはありません。しかし、実際のシステムでは、TCPプロトコルの「3ウェイハンドシェイク」メカニズムなど、比較的確実に問題に対処できます。

ビザンチン将軍問題

ビザンチン将軍問題は、2013年のチューリング賞受賞者であるレスリー・ランポートによって最初に提案され、彼の1982年の論文「ビザンチン将軍問題」で述べられています。この問題は、メッセージの改ざんなどの悪意のある行動が存在する中で、分散システムにおいて一貫性を実現する方法を説明しています。
ビザンチン帝国の複数の軍隊が敵の都市を包囲し、各軍は将軍に率いられていた。ビザンチン軍は使者を通じてのみ通信できた。敵の軍勢を観察した後、ビザンチンの将軍たちは同じ結論に達しなければならない：ビザンチン軍の半数以上が一緒に攻撃すれば、都市を攻略し勝利を収めることができる。

解決策：ビザンチンシステム内の将軍（ノード）の数がZであり、信頼できない（反逆者の）将軍の数がXである場合、Z ≥ 3X + 1のときのみ、ビザンチンフォルトトレランス（BFT）プロトコルはシステムの一貫性を保証できます。
実用システムでは、ノードが応答しなくなる障害は「クラッシュ障害」として分類され、メッセージを偽造または改ざんするノードは「ビザンチン障害」として分類されます。

コンセンサスアルゴリズムの分類

ブロックチェーンシステムは、特にビットコインやイーサリアムなどの公開チェーンのような、非常に分散化され、お互いに信頼しあっていない多数のネットワークノードで構成される分散システムの一種です。ブロックチェーンの合意メカニズムにより、フォークなしでデータの整合性を一貫して達成します。
故障耐性タイプに基づいて、合意アルゴリズムは非ビザンチン・フォルト・トレランス（CFT）アルゴリズムとビザンチン・フォルト・トレランス（BFT）アルゴリズムに分類されることができます。

非ビザンチン故障許容アルゴリズム

分散システムでは、ノードがシステムの障害や予期しない停止（非ビザンチン障害）を経験した場合、非ビザンチン障害耐性アルゴリズムは、分散システム全体の信頼性を確保します。ただし、悪意のあるノードがデータを偽造または改ざんした場合、非ビザンチン障害耐性アルゴリズムではシステムの信頼性を確保できません。これらのアルゴリズムは、閉じられた制御された企業向け分散システムで主に使用されます。最も代表的な非ビザンチン障害耐性アルゴリズムには、PaxosアルゴリズムとRaftアルゴリズムが含まれます。

ビザンチン障害耐性アルゴリズム

ビザンチン障害耐性アルゴリズムは、ノードがどの種類の障害を経験しても、故障しているノードの数が一定の割合を超えない限り、分散システムの信頼性を確保することができます。簡単に言えば、故障しているノードの数（ビザンチン障害または非ビザンチン障害による）が、総ノード数の一定割合を下回っている限り、ビザンチン障害耐性アルゴリズムはシステムの信頼性を確保できます。ビットコインやイーサリアムのようなブロックチェーンシステムには多くの信頼できないネットワークノードが存在するため、ビザンチン障害耐性アルゴリズムは主にブロックチェーンのコンセンサスメカニズムで使用されています。最も代表的なビザンチン障害耐性アルゴリズムには、PBFT（実用的ビザンチン障害耐性）、PoW（プルーフ・オブ・ワーク）、PoS（プルーフ・オブ・ステーク）が含まれます。