本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「4. The HoneyBadgerBFT Protocol」の「4.4 Instantiating ACS Efficiently」です。原文はこちらになります。
スポンサードサーチ
4. HoneyBadgerBFTプロトコル（続き）
4.4 ACSを効率的にインスタンス化する
Cachinらは私たちがCKPS01と呼ぶプロトコルを発表しており、これは（暗黙的に）ACSを多値バリデート型ビザンチン合意（MVBA）に削減する[15]。MVBAによりノードはプレディケートを満たす値を提案でき、そのうちの一つが最終的に選ばれる。削減手法はシンプルだ。バリデーションプレディケートは、アウトプットが少なくともN - fのパーティからの署名付きインプットのベクトルでなければならないとする。残念ながらMVBAプリミティブの合意はボトルネックとなる。なぜなら、唯一私たちが知る構成法ではO(N3|v|)のオーバヘッドを生じるからだ。
私たちはACSの別のインスタンス化手法を用いてこのボトルネックを回避し、MVBAは全く使わない。用いるインスタンス化手法はBen-Orら[9]によるもので、恐らく幾分か見落とされていたものだ。実際にこの手法はCKPS01[15]の前に発表されており、当初はほぼ関係のない目的向けに（効率的な非同期マルチパーティ計算を行うためのツールとして[9]）開発されたものだ。このプロトコルはACSから「リライアブルブロードキャスト（reliable broadcast, RBC）」と「非同期バイナリビザンチン合意（asynchronous binary Byzantine agreement, ABS）」まで削減する。ごく最近、これらのサブコンポーネントの効率的な構築法が分かった。それを手短に説明する。
ハイレベルではACSプロトコルは2つの主要フェーズを進める。最初のフェーズでは、各ノードPiはRBCを使って他ノードに提案値を伝え、その後に続いてどのRBCが正常に完了したのかを示すビットベクトルを決定するためにABAが行われる。
Ben-Orのプロトコルを詳細に説明する前に、RBCとABAの構成を大まかに説明させてもらった。
通信最適なリライアブルブロードキャスト
非同期のリライアブルブロードキャストチャネルは次の特性を満たすものである。
- （合意（Agreement））：任意の2つの正しいノードがvとv'を配信するならば、v = v'である。
- （トータリティ（Totality））：一つでも正しいノードがvを配信するならば、全ての正しいノードがvを配信する。
- （バリディティ（Validity））：送信者が正しく、インプットがvであるならば、全ての正しいノードがvを配信する。
Bracha[13]の旧来のリライアブルブロードキャストプロトコルがサイズ|v|のメッセージをブロードキャストするために合計で通信量O(N2|v|)が必要だったのに対し、CachinとTessaro[18]は抹消コーディングにより最悪の場合でも単にO(N|v| + λN2logN)までコストを削減できると考察した。これは巨大なメッセージ（つまり、|v| >> λNlogNの場合）に関しては非常に大きな改善であり、（第4章の3を振り返ってみれば分かるように）私たちがバッチサイズを選んだ理由でもある。抹消コーディングの利用は、最大でもN/N-2f < 3に等しい小さなオーバヘッドの定数ファクターを誘発することになる。
送信者が正しい場合、合計実行時間は（非同期の）3ラウンドであり、またどんな場合でも、最初の正しいノードが値をアウトプットしたときと最後の正しいノードが値をアウトプットしたときの間で最大2ラウンドが経過する。リライアブルブロードキャストのアルゴリズムを図2に示す。
バイナリ合意
バイナリ合意は標準的なプリミティブでノードがシングルビットの値について合意できるようにするものだ。より形式的に表現すれば、バイナリ合意は下記3つの特性を保証する。
- （合意（Agreement））：一つでも正しいノードがビットbをアウトプットするならば、正しいノードそれぞれがビットをアウトプットする。
- （ターミネーション（Termination））：全ての正しいノードがインプットを受け取るならば、正しいノードそれぞれがビットをアウトプットする。
- （バリディティ（Validity））：一つでも正しいノードがbをアウトプットするならば、少なくとも一つの正しいノードがインプットとしてbを受け取っている。
このバリディティの特性は「満場一致（unanimity）」であることを意味する。もし全ての正しいノードが同じインプット値bを受け取るならば、bは決定された値でなければならない。一方で、任意の時点で2つのノードが異なるインプットを受け取るならば、攻撃者は残りのノードがインプットを受け取る前であってもどちらかの値に意思決定を強制できる可能性がある。
私たちは暗号共通通貨に基づくMoustefaouiら[42]のプロトコルでこのプリミティブをインスタンス化する。このインスタンス化の説明はAppendixにて行う。この実行時間の期待値はO(1)で、実際には1 - 2-kの確率でO(k)ラウンド以内に完了する。ノードあたりの通信複雑性はO(Nλ)で、これは主に共通通貨で用いられる閾値暗号のおかげである。
提案値の部分集合についての合意
上述のものをまとめることで、少なくともN - f個のノードの全提案を含む値の集合についての合意にBen-Orら[9]のプロトコルを用いることができる。
ハイレベルではこのプロトコルは2つの主要フェーズを進める。最初のフェーズでは、各ノードPiはRBCを使って他ノードに提案値を伝える。次のフェーズでは、N個のバイナリビザンチン合意の並行インスタンスをビットベクトル{bj}j∈[1...N]についての合意に用いる。ここでbj = 1はノードPiの提案値が最終的な集合に含まれていることを示す。
実際には上記の説明にはさりげない困難が隠れているが、Ben-Orは賢いソリューションを提供している。
上記をナイーブに実装しようとする試みでは各ノードに最初の（N - fの）ブロードキャストが完了するまで待ってもらい、そのあとでこれに一致するバイナリ合意インスタンスについては1を、それ以外については0を提案してもらうことになるだろう。しかし、正しいノードが異なる順序でブロードキャストの完了を観測してしまう可能性がある。バイナリ合意が保証するのは全ての正しいノードが満場一致で1を提案するならばアウトプットは1であるということだけなので、結果として得られるビットベクトルが空になってしまう可能性がある。
この問題を避けるため、ノードは最終的なベクトルが少なくともN - f個のビットの集合を有することが確定するまでは0の提案を控える。このプロトコルのフローにいくつか直感的な洞察を与えるため、いくつかありえそうなシナリオを図3に示す。
Ben-Orら[9]のアルゴリズムについては図4に示す。実行時間は期待値でO(logN)である。バイナリ合意インスタンスが全て終わるまで待たねばならないからだ4。上述のようにリライアブルブロードキャストとバイナリ合意の構成でインスタンス化を行うと、合計の通信複雑性は|v|が全ノードで最大のインプットであるとしてO(N2|v| + λN3logN)である。
脚注4：実行時間の期待値はいくつかのインスタンスを並列実行することでO(1)まで減らせるが(cf.[8])、これはスループットを犠牲にすることになる。
（HoneyBadgerBFTプロトコルを見てみる8 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる10）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。