ビザンチン将軍問題#
この名前を初めて見た場合、これは歴史上の人物が直面した戦闘の問題だと思うかもしれません。しかし、実際にはそうではなく、これは分散ネットワークの問題を解決するために提案されたものです。
ビザンチン将軍問題（Byzantine Generals Problem）は、レスリー・ランポートが同名の論文で提案した分散ピアツーピアネットワーク通信の容錯性問題です。
問題提起者について簡単に紹介します：
レスリー・ランポート（Leslie Lamport）は、アメリカのコンピュータ科学者です。また、組版システム LaTeX の開発者でもあります。2013 年にチューリング賞を受賞しました。
アイデアを出そう#
ビザンチン将軍問題を探求する前に、思考方法に慣れるために小さな問題を出してみましょう。
2 人の門番 A と B がいて、2 つの扉 a と b があります。私たちの目標は、正しい扉 a と b を見つけることです。以下の情報がわかっています：
- A と B にそれぞれ 1 つの質問をすることができます。
- A と B のうち 1 人は真実を言い、もう 1 人は嘘をつきます。
では、どのように質問すれば正しい扉を見つけることができるでしょうか？
考えてみてください。実は 1 つの質問だけで答えを得ることができます。
答え：A に尋ねる：B はどちらの扉が正しいと言うと思いますか？（正しい答えは、A が答えたもう一方の扉です）
共通意見を形成する#
ビザンチン将軍問題の例はやや複雑ですので、理解を助けるために簡単な例を使いましょう：
一群の親しい友人（将軍）が、明日の朝 10 時に一緒に公園に行くかどうかを話し合いたいと思っていますが、現在はグループチャットができず、個別にメッセージを送るしかありません。友人の中には、関係を悪化させたり妨害したりする意図を持つ人がいることがわかっています。では、どのようにしてみんなが統一行動の目標（一緒に行くか行かないか）に達することができるでしょうか？
例えば、合計 9 人のうち、多数決の原則を採用し、4 人が同意し、4 人が反対する場合、悪い人は同意する 4 人に同意すると言い、反対する 4 人に反対すると言います。両方の側が自分が勝利したと思い込むため、目標の失敗が起こります。
上記のストーリーをコンピュータシステムにマッピングすると、将軍はコンピュータになり、個別のメッセージ送信が通信システムになります。上記の問題は電子化された意思決定と情報セキュリティに関わるものですが、単純に暗号化とデジタル署名で解決することはできません。なぜなら、回路のエラーが暗号化プロセス全体に影響を与える可能性があるためです。これは、暗号化とデジタル署名アルゴリズムが解決する問題ではありません。したがって、コンピュータは誤った結果を提出する可能性があり、誤った意思決定を引き起こす可能性があります。
また、ブロックチェーンでは、合意が達成できない場合に分岐やダウンタイムの問題が発生します。一つのチェーンの合意が問題を抱えると、そのチェーンに対して信頼危機が生じ、致命的な打撃となります。そのため、ブロックチェーンにおいては、共通意見形成アルゴリズムは生態系の基盤となります。
口頭プロトコル#
実際には、共通意見形成アルゴリズムは進化し続けており、非常に賢明な人々が新しい解決策を提案しています。この問題が提起された論文では、レスリー・ランポートは既に 2 つの解決策を提案しており、今日は口頭プロトコルという解決策を共有します。
以下の内容はオリジナルの解決策ではなく、個人の理解に基づく表現です。誤りがあればご了承ください。
定義：
- 2 つのカテゴリに分けられる：善人（統一を望む）と悪人（統一を望まない）
- 提案者は自動的にリーダー（将軍）となる
目標：
- リーダーが善人である場合、すべての善人がリーダーの提案を実行することを保証する
- すべての善人が一致して実行することを保証する
失敗例#
先ほどの公園への例に基づいて、今回は a、b、c の 3 人が明日公園に行くかどうかを話し合っています。その中に 1 人の悪人がいます。
b が公園に行く提案を出し、リーダーとなります。
（下に図解があります）
可能性 1#
b はリーダーであり、c が悪人です。
a は b が公園に行く提案を受け取りますが、b が善人かどうかわからないため、c に尋ねます：b は公園に行くと言っていますか？c は行かないと答えるので、a は 1 人が行くと 1 人が行かないという情報を受け取ります。a は b と c のうち 1 人が悪人であることを知っていますが、どちらが悪人かはわかりません。
したがって、共通意見を形成することはできません：失敗
可能性 2#
b は悪人であり、a と c は善人です。
a は b が公園に行く提案を受け取り、c は b が公園に行かない提案を受け取ります。この時点で、a と c は情報を交換し、1 人が行くと 1 人が行かないという情報を得ます。
したがって、共通意見を形成することはできません。
成功例#
今度は a、b、c、d の 4 人が明日公園に行くかどうかを話し合っています。その中に 1 人の悪人がいます。
可能性 1：#
リーダーの c は善人であり、明日公園に行かない提案を出し、d は悪人です。
a は公園に行かない意見を受け取り、b と d のリーダーの意見を尋ねます。b は行かない（不同意）と言い、d は行く（同意しない）と言います。
a は（行かない、行かない、行く）という情報を得ますが、多数が行かない方を選ぶだけで十分です。b も同様の結論に至り、行かないことになります。
最終的に、a、b、c はすべて行かず、目標 2 を達成し、リーダーの命令に従って目標 1 を達成します。
可能性 2：#
リーダーの c は悪人であり、a と b には行くと言い、d には行かないと言います。
a は行く提案を受け取り、b と d のリーダーの意見を尋ねます。b は行く（同意）と言い、d は行かない（不同意）と言います。
a は（行く、行く、行かない）という情報を得ますが、多数が行く方を選ぶだけで十分です。b も同様の結論に至り、行くことになります。
d は行かない提案を受け取り、a と b のリーダーの意見を尋ねます。a は行く（同意）と言い、b も行く（同意）と言います。
d は（行かない、行く、行く）という情報を得ますが、多数が行く方を選ぶだけで十分です。
最終的に、a、b、d はすべて一緒に行きます。目標 2 を達成し、リーダーが悪人であるため、目標 1 を考慮する必要はありません。
実際には、レスリー・ランポートが口頭プロトコルを提案した当時、n 人が参加し、m 人が悪人である場合、n > 3m でのみ共通意見が形成されることを示しました。つまり、2 人が悪人である場合、共通意見を形成するには合計 7 人が必要です。具体的な推論プロセスは李永乐先生のビデオを参照してください。非常に興味深いです。
もちろん、ビットコインやイーサリアムなどのブロックチェーンでは、PoW（Proof of Work）が共通意見の問題を非常に優れた方法で解決しており、10 年以上の安定した運用を経て、この方法の実行可能性が証明されています。ただし、PoW には批判される要素も多くありますので、機会があれば PoW の基本的なロジックを詳しく研究してみてください。