BFTプロトコル：PBFTとTendermint

Lamport、Shostak、Peaseが1982年に定式化したビザンチン将軍問題は、一部の参加者が矛盾するメッセージを送る場合でも、分散システムはコンセンサスに到達できるのかを問います。この問題は、攻撃を調整しなければならない一方で、相反する命令を送る裏切り者が含まれている可能性のあるビザンチン帝国の将軍にちなんで名付けられました。合計3f+1個のノードのうち最大f個が悪意を持っていても正しいコンセンサスに到達できるシステムを、ビザンチンフォールトトレラント（BFT）と呼びます。BFTは、敵対的な条件下でも安全性が必要なブロックチェーンコンセンサスにおける標準的な基準です。

PBFT（CastroとLiskov、1999年）は、初めて実用化されたBFTプロトコルであり、BFTが実システム上で効率的に動作できることを示しました。PBFTはビュー（ターム）単位で動作し、各ビューには指定されたプライマリ（リーダー）が存在します。通常の処理は、pre-prepare（プライマリがクライアントリクエストとシーケンス番号をブロードキャスト）、prepare（レプリカがシーケンス番号付きの合意をブロードキャスト）、commit（レプリカがコミット確認をブロードキャスト）の3フェーズで実行されます。レプリカが一致するcommitメッセージを2f+1個集めると、リクエストが実行されます。PBFTは、レプリカの3分の1未満がビザンチンであることを前提に、安全性とライブネスを提供します。

PBFTの主な制限は、リクエストごとのメッセージ計算量がO(n^2)になることです。n個のレプリカそれぞれが、prepareフェーズとcommitフェーズで他のすべてのレプリカにメッセージを送信するためです。レプリカがn=100個の場合、1つのリクエストでおよそ10,000件のメッセージが生成されます。そのため、PBFTは大規模なバリデータ集合には現実的ではありません。BFT研究コミュニティは20年にわたってこの問題を改善してきました。BFT-SMARTは定数倍のコストを削減し、HotStuffはリーダー・リレー方式によってメッセージ計算量を線形にし、TendermintはPBFTの考え方をパブリックブロックチェーン向けに適応しました。

PBFTのプライマリに障害があると疑われる場合（タイムアウト時）、レプリカはビュー変更を開始します。各レプリカは、自身の状態（古いビューでprepareされた値）を含むview-changeメッセージをブロードキャストします。新しいプライマリは2f+1個のview-changeメッセージを集め、以前にコミットされた値と状態遷移が整合していることを証明するnew-viewメッセージを構築してブロードキャストします。ビュー変更はO(n^3)件のメッセージを必要とする高コストな処理であり、実用上のボトルネックでした。PBFTのview-change certificateやHotStuffのパイプライン化設計などの最適化が、この問題に対処しています。

Tendermint（2014年、Kwon。Cosmosでの本番運用は2019年）は、PBFTをパブリックブロックチェーン環境向けに適応したものです。Tendermintでは、各ブロックについてpropose（リーダーが提案ブロックをブロードキャスト）、prevote（バリデータが提案に投票）、precommit（3分の2のprevoteを確認した後、バリデータがコミットに投票）の3フェーズを実行します。バリデータが3分の2のprecommit投票（クォーラム証明）を集めると、ブロックがコミットされます。バリデータは、ステークに応じた重み付きラウンドロビン順でプロポーザーを務めます。コミットされないままラウンドがタイムアウトすると、バリデータはnil投票とともに次のラウンドへ進みます。

Tendermintは強い安全性を提供します。ステークの3分の1未満がビザンチンである限り、コミットされたブロックはファイナルであり、覆すことはできません。これは同期的ファイナリティであり、コミット後にフォークは発生しません。ライブネスには部分同期ネットワークが必要です。つまり、メッセージ遅延が上限内に収まればプロトコルは進行しますが、継続的な同期性は必要ありません。ライブネスと安全性のトレードオフは本質的なものです。Tendermintは、安全性を保証する代わりにライブネスを犠牲にし、ネットワークが分断されると停止する可能性があります。一方、Bitcoinのようなチェーンは、安全性を犠牲にして一時的なフォークを許容し、ライブネスを優先します。

Tendermintの重要なメカニズムの1つが投票ロックです。バリデータがラウンドrであるブロックに対するprecommitを送信すると、そのブロックにロックされます。その後のラウンドでは、ロックされたバリデータは、ロック対象のブロックに対してのみprevoteできます（または、そのブロックがコミットされなかったことを示す証明を受け取った場合はnil投票を行えます）。これにより、ラウンドをまたいだ矛盾するコミットを防ぎます。バリデータがロックを解除できるのは、後のラウンドで別のブロックに対するpolka（3分の2のprevote）を受け取り、元のブロックがコミットされなかったことが証明された場合だけです。

Cosmos Inter-Blockchain Communication（IBC）は、チェーン間転送のためにTendermintの即時ファイナリティに依存しています。Tendermintライトクライアントは、バリデータ集合と最新のコミット（ブロックヘッダーと3分の2のprecommit署名）を追跡します。チェーンAからのパケットを検証するため、チェーンBのIBCモジュールはクォーラム証明を検証します。これは、チェーンAのバリデータの3分の2が該当するブロックヘッダーに署名したことを確認するものです。そのため、IBCの安全性はTendermintのBFT保証に依存します。送信元ブロックがコミットされると、チェーン間転送は直ちにファイナルになります。

HotStuff（Yinら、2018年。FacebookのLibraBFT/DiemBFTの基盤であり、現在はAptosとSuiで使用）は、スター型トポロジーを用いてコンセンサスラウンドあたりのメッセージ計算量O(n)を実現します。すべてのバリデータがリーダーに投票を送り、リーダーがそれらをthreshold署名（QC、クォーラム証明）に集約して、QCをブロードキャストします。HotStuffは3フェーズのチェイニング設計を採用しており、安全性の証明が連続する3つのQCにまたがることで、パイプライン化を可能にしています。線形の計算量により、HotStuffはAptosやSuiで採用されているような、100～300個のバリデータを扱う実用的なプロトコルになっています。

エンタープライズブロックチェーン（Hyperledger Fabric、Besu、Quorum）は、バリデータの身元が既知であるパーミッション型ネットワークでBFTコンセンサスを使用します。Hyperledger FabricのRaftベースのオーダリングサービスは、信頼されたコンソーシアム向けにクラッシュフォールトトレランス（ビザンチンフォールトには非対応）を提供します。Fabricで計画されているBFTのマイルストーンは、ライブラリベースの実装であるSmartBFTを対象としています。R3 Cordaは、二重支払いの防止にBFT-SMARTを使用するノータリークラスターを採用しています。CFTとBFTの選択は、信頼に関する前提を反映します。バリデータが敵対的に振る舞う可能性がある場合はBFTが必要ですが、単に信頼性が低いだけならCFTで十分です。

BFTを理解するには、どのような攻撃に耐えられ、どのような攻撃には耐えられないのかを理解する必要があります。BFTは、異なるピアに矛盾するメッセージを送るエクイボケーションを行うバリデータや、クラッシュまたは無応答になるバリデータに対処できます。一方、Sybil攻撃には対処できません。攻撃者が偽のIDを作成してバリデータの3分の1を支配すると、安全性を破ることができます。これが、パブリックBFTチェーンがPoSのステークウェイトを使用する理由です。ステークの3分の1を取得するには実際の資金が必要となるため、Sybil耐性が得られます。またBFTは、最終的にメッセージが配信されること（部分同期性）を前提とします。ネットワーク分断がライブネスのタイムアウトより長く続くと、チェーンは停止する可能性があります。

安全性を維持できる標準的なBFTプロトコルにおいて、ビザンチンになり得るバリデータの最大割合はどれだけですか？

BFTプロトコルは、最大3分の1の悪意あるバリデータが存在してもコンセンサスを保証します。PBFT（1999年）はBFTが実用的であることを示しましたが、メッセージ計算量はO(n^2)です。TendermintはPBFTをブロックチェーン向けに適応し、即時ファイナリティと投票ロックを実現しています。HotStuffはthreshold署名によるQCを通じて計算量O(n)を達成し、AptosとSuiで使用されています。Cosmos IBCは、検証済みのチェーン間転送にTendermintの即時ファイナリティを利用します。エンタープライズブロックチェーンでは、ビザンチン障害が想定されるか、単なるクラッシュ障害が想定されるかに応じて、BFT-SMARTまたはRaftを使用します。