本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「3. The Gap between Asynchronous and Weakly Synchronous Network Models」の序文と「3.1 Many Forms of Timing Assumptions」です。原文はこちらになります。
スポンサードサーチ
3. 非同期ネットワークモデルと弱同期ネットワークモデルの差
現代のほとんどのBFTプロトコルはライブネスの保証をタイミングアサンプションに頼っている（「部分的同期性（partial synchrony）」、「弱同期（weak synchrony）」など）。本当に非同期のBFTプロトコルには近年ではほとんど関心が向けられなかった。次の論を考えてみよう。これが成り立つとしたら非同期BFT無視の一点集中を正当化するものだ。
[X]弱同期性の仮定は不可避である。というのも、この仮定に反するあらゆるネットワークでは、非同期プロトコルであっても許容できるパフォーマンスを提供できないからだ。
本章で私たちは上記の前提に反駁する論を二つ展開する。第一に、非同期ネットワークモデルと弱同期ネットワークモデルの理論的な違いを説明する。具体的には、PBFTの「弱同期性」の仮定には反する（そして実際に失敗を引き起こす）が本当に非同期のプロトコル（HoneyBadgerBFTなど）ではうまく進行する敵対的なネットワークスケジューラを構築する。第二に、実際的な考察を行う。すなわち、弱同期性の仮定が適する場合であっても、弱同期プロトコルはネットワーク分裂が発生するとそのリカバリに時間がかかるのに対し、非同期プロトコルではメッセージが配信されるとすぐに進行することを示す。
3.1 多様なタイミングアサンプションの形
話を進める前にタイミングアサンプションの様々な標準様式についてレビューする。非同期ネットワークでは攻撃者はメッセージをいつでも任意の順序で送信できるが、それでも「最終的に（eventually）」正しいノード間で送られた全てのメッセージを配信せねばならない。非同期ネットワークのノードには"リアルタイム"の時計は不要で、受け取ったメッセージの「整序（ordering）」に基づいてアクションをとることしかできない。
ご存知のFLP不可能性[27]はアトミックブロードキャストとその他多くのタスクについての決定論的非同期プロトコルの可能性を除外している。ゆえに決定論的プロトコルにはより強いいくつかのタイミングアサンプションを立てる必要がある。便利な（しかし非常に強い）ネットワーク仮定は「同期性（synchrony）」である。Δ-synchronousなネットワークは送られた全てのメッセージが最大でもΔ（Δはリアルタイムの指標）のディレイの後には配信されることを保証する。
より弱いタイミングアサンプションはいくつかの形がある。「Δがよくわからない（unknown-Δ）」モデルでは、ディレイの上限をパラメータとして使えない。あるいは「最終的同期（eventually synchronous）」モデルでは、メッセージディレイの上限Δは（未知の）ある時間の経過後に保持されることが保証されるのみである。これは"グローバルスタビリゼ―ションタイム（Global Stabilization Time）"と呼ばれる。これら二つのモデルはまとめて「部分的同期性」[26]と呼ばれる。もう一つのタイミングアサンプションの形は「弱同期性」で、これはディレイの上限は時間変化するが、結局のところ多項式時間を超える速さで大きくなることはないというものだ[20]。
実現可能性の観点からすれば上述のものは等価である。すなわち、ある設定で成功したプロトコルはシステマティックにもう片方に適合させることができる。しかしながら具体的なパフォーマンスの観点からすると、「弱同期性」向けに調整を行うということは時間が経つにつれて（例えば"エクスポネンシャルバックオフ"のポリシーにより）徐々にタイムアウト変数を増やすことを意味する。後に示すが、これは一時的なネットワーク分裂からのリカバリが遅れることにつながる。
典型的にはプロトコルはこれらのタイミングアサンプションをタイムアウトイベントという形で明確に定めている。例えば一定期間内に何ら進捗が検知されない場合には、新たなリーダーを選ぶなどの修正策を講じる。非同期プロトコルはタイマーには頼らず、メッセージが配信されるといつでも実時間とは無関係に進行する。
非同期ネットワークにおけるラウンドカウンティング
最終的なメッセージ配信の保証は"リアルタイム"の概念からは離れているものの、非同期プロトコルの実行時間を特徴づけられる方が好ましい。スタンダードなアプローチは（例えばCanettiとRabin[19]が解説しているように）攻撃者が各メッセージに架空のラウンドナンバーを割り当てるというもので、r+1番目のメッセージが一つでも送られてしまう前に正しいノード間でr-1番目のメッセージが全て配信されなければならないという条件を要する。
（HoneyBadgerBFTプロトコルを見てみる3 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる5）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。