本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「3. The Gap between Asynchronous and Weakly Synchronous Network Models」の「3.2 When Weak Synchrony Fails」です。原文はこちらになります。
スポンサードサーチ
3. 非同期ネットワークモデルと弱同期ネットワークモデルの差（続き）
3.2 弱同期が失敗する場合
さて、ネットワーク状態が敵対的（あるいは予測不能）である場合になぜ弱同期BFTプロトコルが失敗する（あるいはパフォーマンス悪化に悩まされる）かを説明する。これはなぜこれらのプロトコルが第1章で述べた暗号通貨指向のアプリケーションのシナリオに不適であるかという理由を与えるものである。
PBFTを阻むネットワークスケジューラ
PBFT（Practical Byzantine Fault Tolerance）[20]を用いる。これは古くからあるリーダーベースのBFTプロトコルで、いかにして敵対的ネットワークスケジューラがリーダーベースBFTプロトコルにあたるもの[4, 6, 10, 22, 33, 50]が急停止する原因となるかを説明する代表例である。
任意の時点で、指名されたリーダーは次のトランザクションバッチを提案する責任がある。リーダーが故障しているかネットワークが停止しているかで進捗がない場合、ノードは新しいリーダーの選出を試みる。PBFTはライブネスに関して弱同期ネットワークに極めて強く依存している。私たちはこの仮定に反する敵対的なスケジューラを作り、実際にPBFTが全く進まないようにしたが、HoneyBadgerBFTについてはうまく動く。タイミングアサンプションに基づくプロトコルがその仮定が成立しない場合に失敗するのは驚くことではない。だが、明らかな攻撃を実際にやってみせることは私たちが非同期プロトコルを作る理由を与えてくれる。
スケジューラの裏にある洞察はシンプルだ。まず、一つのノードがクラッシュしていると仮定する。そしてネットワークは正しいノードがリーダーである場合はいつもメッセージを遅延させることとし、進行を妨害してラウンドロビン方式で次のノードが新たなリーダーになるようにした。次にリーダーになるのがクラッシュしているノードの場合、このスケジューラは速やかにネットワーク分裂を修復し誠実なノード間で極めて速やかにメッセージを配信する。しかしリーダーはクラッシュしているので、どちらにせよ進行しない。
この攻撃は弱同期性の仮定を成り立たなくさせる。というのもサイクルごとにだんだんとメッセージのディレイを長くせねばならないからである。これはPBFTがリーダー選出の失敗のたびにタイムアウト間隔を長くするためだ。一方で、同期期間もだんだんと長くなる。しかし同期期間が都合の悪いときに発生するので、PBFTはこれを活用することができない。翻ってHoneyBadgerBFTやその他の非同期プロトコルはこの日和見的な同期期間でも進行する。
分析確認のため、新しいリーダーへのビューチェンジメッセージを全て捉えて遅延させるプロキシとしてこの悪意のあるスケジューラを実装し、1200行のPBFTのpython実装についてテストした。私たちが観測した結果とメッセージログは上記分析と一致した。私たちのレプリカ（筆者注：PBFTのpython実装のこと）はビューチェンジをリクエストするループでスタック状態に陥り、決して正常終了することはなかった。Appendix AにてPBFTの詳細を示し、この攻撃下でどのように動くのかを説明する。
ネットワーク分裂からの回復の遅さ
たとえ弱同期性の仮定が最終的に満たされるとしても、この仮定に頼るプロトコルはまた一時的なネットワーク分裂からの回復が遅い可能性がある。次のシナリオを考えてみよう。単純に先に述べた攻撃の有限個のプレフィックスであるとする。ある一つのノードがクラッシュし、ネットワークが一時的に時間にして2DΔの間、分裂している。私たちの作ったスケジューラはクラッシュしたノードがリーダーになる場合には即座にネットワーク分裂を修復する。タイムアウト間隔はこの時点で2D+1Δであるので、プロトコルは新しいリーダーの選出を始める前に2D+1Δ待たねばならない。この間にネットワークが同期しているとしても、である。
ロバスト性と応答性のトレードオフ
上記で確認されるようなふるまいはPBFTに特有のものではなく、むしろクラッシュの対応をタイムアウトに頼るプロトコルに根本的に備わっているものだ。プロトコルの形に関わらず、実行者は何らかのトレードオフに従ってタイムアウトポリシーを調整せねばならない。一方（最終的同期性）では、実行者はネットワークディレイΔの具体的な見積もりを作る。この見積もりが小さすぎるとシステムは全く進まなくなるかもしれないし、大きすぎると帯域幅を有効活用できない。もう一方（弱同期性）では、実行者は絶対的なディレイを具体的に定めないが、とはいえシステムがどれだけ速く条件変動に追随するかに影響する"何か得るもの（筆者注：何らかの変数）"を選ばねばならない。非同期プロトコルではこのようなパラメータを調整の必要性を避けることができる。
（HoneyBadgerBFTプロトコルを見てみる4 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる6）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。