本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「4. The HoneyBadgerBFT Protocol」の「4.2 Overview and Intuition」です。原文はこちらになります。
スポンサードサーチ
4. HoneyBadgerBFTプロトコル（続き）
4.2 概略と洞察
HoneyBadgerBFTではノードはインプットとしてトランザクションを受け取り、自らの（無制限の）バッファに保存する。プロトコルはエポックで進み、それぞれのエポックの後には新しいトランザクションのバッチがコミットログに追加される。各エポックの開始時にノードはトランザクションのサブセットを選んでバッファに取り込み（近いうちに定義するポリシーによる）、それをランダム化合意プロトコルのインスタンスにインプットとして与える。ランダム化合意プロトコルの終わりにこのエポックの最終的なトランザクションセットが選ばれる。
高いレベルでは私たちのアプローチは既存の非同期アトミックブロードキャストプロトコルと似ている。特にCachinら[15]の大規模なトランザクション処理システム（SINTRA）の礎となるプロトコルと似ている。私たちのプロトコルと同様に、Cachinらのプロトコルは非同期コモンサブセット（ACS）プリミティブのインスタンスを中心に展開される。ざっくり言うと、ACSプリミティブは各ノードが値を提案できるようにし、各ノードが少なくともN - 2f個の正しいノードによるインプット値を含む共通ベクトルをアウトプットすることを保証するものである。このプリミティブからアトミックブロードキャストを構築するのは普通のことである。各ノードは単純にキューの先頭からトランザクションのサブセットを提案し、合意されたベクトル内で元の和集合をアウトプットする。しかし重要なチャレンジが2つある。
チャレンジ1：検閲耐性の実現
ACSのコストは各ノードが提案するトランザクションセットのサイズに直接依存する。アウトプットのベクトルにはこのようなトランザクションセットが少なくともN - f個含まれるので、各ノードが確実に「ほぼ重ならない（mostly disjoint）」トランザクションセットを提案するようにすることで全体の効率性を高めることができ、こうして同じコストながら1バッチでよりたくさんの異なるトランザクションをコミットすることができる。従って（CKPS01[15]のように）単純にバッファから最初の元を選ぶのではなく、その代わりにHoneyBadgerBFTプロトコルのノードはランダムに選んだサンプルを提案するので、各トランザクションは平均してただ一つのノードにより提案される。
しかしナイーブに実装してしまうと、この最適化は検閲耐性を弱めてしまう。というのもACSプリミティブにより攻撃者がどのノードの提案を最終的に取り込むか選ぶことができるからだ。攻撃者はどんなノードが提案したトランザクションでも排除して選択的にトランザクションの検閲ができてしまう。私たちは閾値暗号を使ってこの欠陥を回避する。これにより合意が形成されるまで、どのノードがどのトランザクションを提案したのかを攻撃者に分かってしまうのを防ぐ。プロトコル全体は第4章の3で説明する。
チャレンジ2：実用性のあるスループット
非同期ACSとアトミックブロードキャストの理論的な実現可能性は知られている[9, 15, 17]が、実用上のパフォーマンスについては知られていない。私たちの知る限り、ACSを実装した他の研究はただ一つCachinとPortiz[17]によるものだけで、広域ネットワーク上で0.4tx/秒のスループットを出すことができると明らかにした。ゆえに興味深い疑問は、このようなプロトコルが実際的に高いスループットを出すことができるかである。
本論文では、慎重に選択した一連のサブコンポーネントをつなぎ合わせることで、効率的にACSをインスタンス化し漸近的かつ実際的にはるかに高いスループットを得られることを示す。特に（ノードあたりの）ACSの漸近的なコストをO(N2)（Cachinら[15, 17]のように）からO(1)に改善する。私たちが選りすぐったコンポーネントは（知る限りでは）かつて紹介された事例がないので、構成全体の自己完結的な説明を第4章の4で与える。
モジュラープロトコルの構成
これで構成を形式的に紹介する準備が整った。そうする前にプレゼンテーションのスタイルについて意見を述べる。私たちはプロトコルをモジュラー形式で定義しており、各プロトコルが他の（サブ）プロトコルのインスタンスをいくつか動かす可能性がある。ノードは（サブ）プロトコルにインプットを渡す前であっても（サブ）プロトコルを実行開始する可能性がある（例えばノードが他ノードからのメッセージを受信した場合など）。
一つのインスタンスに関するメッセージを確実によそでは再生できないようにするために、このような（サブ）プロトコルを隔離することが必要不可欠だ。これは実際には各（サブ）プロトコルのインスタンスをユニークな文字列（セッション識別子）を関連付けることで実現され、この（サブ）プロトコル内で送受信される全てのメッセージをこの識別子とともにタグ付けし、それに応じてメッセージをルーティングする。読み易さを考慮してプロトコルにおけるメッセージタグについては説明を省略する。タグ付けされたサブプロトコルのインスタンスの区別に大括弧を使う。例えばRBC[i]はRBCサブプロトコルのi番目のインスタンスを表す。
パーティ間の非同期通信は認証済みの非同期チャネルで行われるものと暗黙的に仮定する。実際には、このようなチャネルはTLSソケットを使って例えば第5章で論じるようにインスタンス化される。
プロトコル内でパーティ間で送信されるメッセージ型を見分けるため、typewriterフォントのラベルを用いる（例えばVAL(m)はVAL型のメッセージmを意味する）。
（HoneyBadgerBFTプロトコルを見てみる6 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる8）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。