本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「2. Background and Related Works」です。原文はこちらになります。
スポンサードサーチ
2. 背景と関連研究
全体的な目標はレプリケートステートマシンを構築することで、レプリケートステートマシンではクライアントはトランザクションを生成・送信し、ノードのネットワークが受け取って処理する。アプリケーションの仕様詳細（例えばステートの表現方法やトランザクションの処理方法）を抽象化すると、完全にグローバルに一貫していて、完全に順序通りで、アペンドオンリーなトランザクションログを作ることと言えば十分だろう。従来からこれらのプリミティブは「全順序（total order）」とか「アトミックブロードキャスト（atomic broadcast）」と呼ばれてきた[23]。Bitcoinの用語で言えば、「ブロックチェーン（blockchain）」と呼ぶことになるだろう。
フォールトトレラントなステートマシンレプリケーションプロトコルはセーフティとライブネスの強い保証を与え、分散システムがネットワークのレイテンシやノードの故障に関わらず正しいサービスを提供できるようにする。膨大な研究がこれらのプロトコルに取り組んでおり、これまでと異なるパフォーマンスのトレードオフを示したり、別の故障や攻撃の形態に対する耐性を持つようにしたり、基盤ネットワークについての仮定変更をしたりしてきた。以下に私たちに最も密接に関係する取り組みを説明する。
2.1 ロバストなBFTプロトコル
Paxos[36]やRafe[45]ほか多くのよく知られているプロトコルはクラッシュ障害に耐性がある一方、PBFT[20]を始めとするBFTプロトコルは任意の（例えば悪意があって）壊れたノードにも耐性がある。後続のプロトコルの多くが、故障がなかったりクライアントがあまり競争しなかったりネットワークがうまく動いている場合には素晴らしいパフォーマンスをもたらす「楽観的実行（optimistic execution）」を通じてパフォーマンス向上を提示しているし、パフォーマンス向上ではなくとも最低限何らかの進歩がある[2, 5, 33, 39, 51]。
一般にBFTシステムはレイテンシとCPUがボトルネット区であるデプロイシナリオの中で評価されてきた[49]ので、最も効果的なプロトコルはラウンド数を減らし高価な暗号操作を最小化するものである。
Clementら[22]は「最悪の場合（worst-case）」のパフォーマンスの改善を提唱して最近の一連の研究[4, 6, 10, 21, 22, 50]を始め、システムが攻撃されている状況下でも、楽観的な場合に想定されるパフォーマンスを犠牲にする結果となってもサービスの品質保証を提供した。しかし、"ロバストなBFT"はこのような調子で侵害されたノードに対しても優れた耐性を持つものの、基盤ネットワークについてのタイミングアサンプションに依然として頼っている。私たちの研究はこのアプローチをさらに広げ、完全に非同期のネットワークであっても良好なスループットを保証する。
2.2 ランダム化合意
決定論的非同期プロトコルはほとんどのタスクで実現不可能だ[27]。大多数の実用的なBFTプロトコルがタイミングアサンプションを置くことでこの不可能性のクリアを進めてきたが、ランダム性（特に暗号理論）は別の道筋を示してくれる。実際、バイナリ合意（ABA）やリライアブルブロードキャスト（RBC）、その他[13. 15. 16]など様々なタスクに関して非同期BFTプロトコルを知っている。
私たちの研究はSINTRA[17]と最も密接に関連していて、SINTRAはCachinら（CKPS01）[15]の非同期アトミックブロードキャストプロトコルをベースとするシステム実装である。このプロトコルはアトミックブロードキャスト（ABC）からコモンサブセット合意（ACS）までの削減とともに、ACSから多値バリデート型合意（MVBA）までの削減からなる。
私たちが貢献する重要な発明はABCからACSまでの最新の削減手法で、検閲耐性を保証するために閾値暗号を使いながら、バッチ化を通じてより高い効率性を提供する（O(N)のファクターによる）（第4章の4を参照）。またサブコンポーネントのインスタンス化を改善する文献からいいとこ取りをすることで、より高い効率性が得られる。特に、別のACS[9]と効率的なRBC[18]を共に用いることで、第4章の4で説明するように高価なMVBAプリミティブを回避する。
表1はHoneyBadgerBFTといくつかのアトミックブロードキャストプロトコルの漸近的なパフォーマンスを要約したものである。"Comm. compl."はコミットされたトランザクションごとの予想される通信複雑性（つまり転送されるバイト数の合計）を表す。PBFTは弱同期性の仮定に基づいているので、非同期ネットワークにおいては全く進捗しない可能性がある。プロトコルKS02[34]とRC05[46]は楽観的で、MVBAに基づく高価なリカバリモードに逆戻りする。既に述べたように、Cachinらのプロトコル（CKPS01）[15]はもっと効率的なACS構成[9, 18]を使って改善できる。また、私たちの最新の削減手法を介してもう一つO(N)の改善が得られる。
最後に、KingとSaia[30, 31]はスパースグラフ上で通信をルーティングすることで二次数未満のメッセージで合意するプロトコルを最近開発した。しかし、この成果を非同期設定に拡張することは未解決の問題として残っている。
（HoneyBadgerBFTプロトコルを見てみる2 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる4）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。