「合意アルゴリズム」の簡潔な説明

分散システムで一貫した結果を生むアルゴリズムはすべて「コンセンサス（合意）アルゴリズム」と呼ばれる。ビットコイン等の暗号通貨、ブロックチェーンで頻出する話題である。

悪意のある攻撃者を想定する分散合意の問題が、ビザンチン将軍問題である。中央の管理システムが存在せず、参加者の中に故障したコンピュータや悪意を持った個人が紛れ込んでいる状態で、全体で正しい合意を形成できるかどうか...。この問題に耐性をもち合意を成し遂げられる性質のことを「ビザンチン障害耐性（Byzantine Fault Tolerance: BFT）」と呼ぶ。

よく知られているPaxosアルゴリズムでもビザンチン問題に対処できるし、Paxosの改善されたバージョンが公開されている。ただし、多くのBFTプロトコルはヘビーな通信が必要であるため、多数の参加者に対応できない。確定的な合意形成アルゴリズム（Paxos、PBFT系）を使う場合は、現実的にはノード数は十数ノード程度の規模にとどまると考えられる。

PoW、PoSのようなブロックチェーンの合意アルゴリズムでは、より多数の参加者を想定している。最も有名なブロックチェーンであるビットコインのノード数は一万に近い。この中に半数〜3分の1以下の悪意の攻撃者を含んだ状態で正しい合意を取るのがPoW、PoSのプロトコルであり、最も難易度が高い。

これらの分散合意はトランザクションごとの対話を制限しているが、トランザクションの一貫性が確定的に保証されるのではなく、より制限の少ない確率的なモデルを採用しているのだ。ビットコインのPoWは6つのブロックが生成された段階でその取引が確定したと見なすのが通例である。それは確率的にトランザクションが遡及的に覆されることが考えられないことに依拠するのだ。

合意アルゴリズムには以下の4つの分類がある。下の項目に進むほど難易度が上がる。「悪意の攻撃者」を想定した下の2項目を「ビザンチン合意」と呼ぶのである。

• 既知の参加者、非ビザンチン障害耐性：Paxos、Raft
• 未知の参加者、限定的な攻撃モード：Chordおよび他の分散ハッシュテーブル
• 既知の参加者、ビザンチン障害耐性：PBFT(Practical Byzantine Fault Tolerance)、UpRight、Byzantine Paxos
• 未知の参加者、ビザンチン障害耐性：プルーフ・オブ・ワーク(PoW)、プルーフ・オブ・ステークス(PoS)

多くのBFTアルゴリズムはノードの母集団を事前に”知っている”ことを想定している。通常、ブロックチェーンアルゴリズムはこの仮定をせず、参加者はいつでも参加できる。つまり、区分の一番下、PoWとPoSは多数で未知の参加者、しかも悪意の参加者を含むなかでの分散合意を成し遂げたのが画期的だった。

ビットコインとはビザンチン合意を金融取引に応用したものであり、金融機関という信用を提供する「Trusted third party」（信頼される第三者）を必要とせずに価値移転を可能にしたのだ。ビットコインはサードパーティに依存せずプロトコルに従い、ステークホルダーのふるまいによりそのネットワークは継続し続けている。採掘者にとっては、P2Pネットワークを攻撃するよりも採掘（コンピュテーション資源を投入し新しいブロックを生成するための競争をすること）することの方が儲かるのだ。2009年にビットコインが登場しやがて中国山間部に信頼の置けない採掘者の集団が生まれた後もPoWはBFTを実証し続けたのだ。

Photo by Evangeline Shaw on Unsplash