アルゴリズム
Direct Edit

Practical Byzantine Fault Tolerance

Takami Torao #PBFT #BFT
  • このエントリーをはてなブックマークに追加

導入

PBFT (practical Byzantine Fault Tolerance) はビザンチン障害耐性をもつ分散合意アルゴリズムの 1 つ。それ以前に提案されていた研究レベルのいくつかの BFT アルゴリズムを改良し、実用的に利用できる水準となった最初の BFT アルゴリズムである。現在利用されているより効率的なビザンチン合意アルゴリズムの基本となっており、ブロックチェーン実装を含むいくつかの分散コンピューティングシステムで利用されている。

Table of Contents

  1. 導入
  2. シミュレーション
  3. PBFT アルゴリズム
  4. pros and cons
    1. 利点
    2. 欠点
  5. 参考リンク

シミュレーション

次の PBFT シミュレーションでは、全体のプロセス数 \(n\) とビザンチン故障プロセス数 \(f\) を設定して、プロセス 1 の提案 "TRUTH" に他の非故障プロセスすべてが同じ値で合意するか、拒否で合意するか、それともビザンチン合意となるかの様子を見ることができる。

Loading...
# pre-prepare prepare commit

PBFT アルゴリズム

PBFT は以下の仮定の下でビザンチン障害を許容する実用的な合意手段を提供することに焦点を当てている。

  1. 特定のノードで障害が発生する。
  2. 特定のノードによってメッセージが改ざんされうる。

このアルゴリズムは独立した非同期システム間で動作するように設計されており、わずかな実行時オーバーヘッドと遅延で性能を発揮するよう最適化されている。

基本的に PBFT に基づいたシステムでは 1 つのプライマリノード (リーダー) とそれ以外のバックアップノードに役割を分けている。PBFT はシステム内の全てのノードが互いに通信可能であり、ノードの多数が正しく機能しているならば、システム状態は合意を目標に動作する。ノード間は密に通信し、メッセージが特定のノードから来たことを検証するだけではなく、メッセージが途中で変更されたなかったことも検証する。

PBFT では同時障害許容ノード数を \(f\) とする場合、ネットワーク全体で \(3f + 1\) のノードが必要となる。つまり \(f\) 個のノードに障害や不正動作があったとしても、それ以外の \(2f+1\) ノードが正しく動作すれば正しいノード間でデータが共有できており、システム全体として動作と安全性の両方を提供することができる。

Practical Byzantine Fault Tolerance
Fig 2. PBFT sequence with \(f=1\).

PBFT は以下の手順で合意が行われる。

request
クライアントはトランザクションを作成し署名してリーダーノードに送信する。リーダーノードは全てのバックアップノードにマルチキャストする。
pre-prepare
全てのノードはトランザクションが正しいこと、内容が改ざんされていないことを検証し、トランザクション内容が検証されたことを他の全てのノードにマルチキャストする。
prepare
pre-prepare フェーズを完了し、他の \(2f\) 個のノードからトランザクション検証メッセージを受信したノードは、それらのトランザクションの内容が pre-prepare フェーズで自身が検証したものと一致していることを検証して他の全てのノードにマルチキャストする。
commit
prepare フェーズを完了し、他の \(2f\) 個のノードからのクロス検証メッセージを受信したノードは、それらのトランザクションの内容が prepare フェーズで自身が検証したものと一致していることを検証して自分が管理するデータベースを更新する。
reply
全てのノードはデータベースの更新結果をクライアントに送信する。クライアントは \(2f+1\) 個のノードから commit 完了メッセージを受信したら操作成功と見なす。

Fig 2. は障害許容ノード数 \(f=1\) とし 1 つのノードが故障しているケースである。このケースではシステム全体で少なくとも 3 ノードが機能していれば PBFT を実行することができる。

リーダーノードは一定回数のリクエストごと、または一定時間ごとにラウンドロビンで変更される。リーダーノードが要求をマルチキャストせずに特定の時間が経過した場合はビュー変更と呼ばれるプロトコルに移行する事もできる。正常なノードが多数派であればリーダーが故障しているかを判断し次のリーダーと入れ替えてそのノードを切り離すことができる。

pros and cons

利点

ブロックチェーンの Proof of Work, Proof of Stake と比較すると confirmation のような手順を必要とせずにトランザクションの finality を提供できる。トランザクションはリーダーノードによってブロック化されるためチェーンが分岐することがない。

また PoW で必須となるハッシュ計算 (いわゆるマイニング) のような計算集約が必要ないため commit までの時間が短く高いスループットを得ることができる。またそれによって電力エネルギーが節約できる。

欠点

ノード間の密な通信が必要であるためコンセンサスグループを大規模にするとスループットが大きく低下する。計算量と通信量は参加しているノード数 \(n\) に対して概ね \(O(n^2)\) で増加する。

ネットワークの大規模化が困難であることから、ある参加者が多数のノード (アイデンティティ) を操作することができた場合に Sybil Attack を受けやすい。PBFT をより最適化するか、他の合意アルゴリズムと組み合わせる必要がある。

ネットワーク上のノード数など特定の全体管理を行う必要があるため、プライベート型やコンソーシアム型のネットワークでしか利用することができない。

論文ではメッセージを承認するためにデジタル署名と MAC を使用する前提だが、暗号通貨ネットワークのような大規模なコンセンサスグループではノード間の大量の通信量に対して MAC を使用することは極めて非効率的である。また第三者へのメッセージの信憑性を証明することは MAC ではできない。

参考リンク

  1. Miguel Castro, Barbara Liskov (1999) Practical Byzantine Fault Tolerance (日本語訳)
  2. Leslie Lamport, Robert Shostak, Marshall Pease (1982) The Byzantine Generals Problem
↑ページの先頭