本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「4. The HoneyBadgerBFT Protocol」の序文と「4.1 Problem Definition: Atomic Broadcast」です。原文はこちらになります。
スポンサードサーチ
4. HoneyBadgerBFTプロトコル
本章ではHoneyBadgerBFTを紹介する。これは最適な漸近的効率性を実現する初の非同期アトミックブロードキャストプロトコルである。
4.1 問題定義：アトミックブロードキャスト
まずネットワークモデルとアトミックブロードキャストの問題を定義する。設定にはN個の指定ノードからなるネットワークと、そのノードの明確に区別する既知のアイデンティティ（P0からPN-1まで）が関係する。ノードはトランザクションをインプットとして受け取り、ゴールは受け取ったトランザクションの並び順について共通の合意に至ることである。私たちのモデルは、任意のクライアントがトランザクションを送信できるがプロトコルの実行責任のあるノードは固定されている"パーミッション制のブロックチェーン"のデプロイシナリオに特にマッチする。
アトミックブロードキャストプリミティブにより、アプリケーション特有のあらゆる情報、例えばトランザクションをどのように解釈するかといったことを抽象化できる（リプレイ攻撃防止のためで、例えばあるアプリケーションはトランザクションが署名とシーケンス番号を含むように定義している）。目的上、トランザクションは単純にユニークな文字列である。実際にはクライアントはトランザクションを生成して全ノードに送信し、ノードの過半数からの署名を集めるとそのトランザクションはコミットされたとみなす。内容簡略化のためクライアントを明示的にモデル化することはしないが、トランザクションは攻撃者により選択されてインプットとしてノードに与えられることは想定する。同様に、ノードがトランザクションをアウトプットするとそのトランザクションはコミットされたものとみなす。
私たちのシステムモデルでは以下の仮定を置く。
- （本当に非同期のネットワーク（purely asynchronous network））：各ノードペアは信頼できる認証済みのポイントトゥポイントチャネルで接続しているものとし、メッセージの欠落はない2ものとする。配信スケジュールは完全に攻撃者により決定されるが、正しいノード間で送信されるメッセージは全て最終的に配信されなければならない。（第2章で述べたように）私たちは非同期ラウンドの数に基づいてプロトコルの実行時間を明らかにすることに関心を抱くだろう。ネットワークは任意のディレイを伴ってメッセージをキューに入れるかもしれないので、ノードは無制限のバッファを持ち、受け取ったあらゆるメッセージを処理できるものとする。
- （静的なビザンチン故障（static Byzantine faults））：攻撃者には最大でf個まで故障ノードの完全な支配権が与えられる。ここでfはプロトコルのパラメータである。本設定では3f + 1 ≤ N（私たちのプロトコルは満たす）がブロードキャストプロトコルの下限である点を付け加えておく。
- （トラステッドセットアップ（trusted setup））：内容簡略化のため、ノードは最初のプロトコル特有のセットアップフェーズでは信頼できるディーラーとインタラクションすると仮定する。このインタラクションは公開鍵と秘密のシェアを作るのに用いる。実際の実装においては本当に信頼できるパーティがいない場合、代わりに分散型の鍵生成プロトコルが用いられる（cf. Boldyreva[11]）可能性があることを付け加えておく。私たちの知る全ての分散型鍵生成プロトコルはタイミングアサンプションに基づくが、幸いにもその必要性はセットアップだけに限られる。
定義1. アトミックブロードキャストプロトコルは次に示す特性を満たさなければならない。そしていずれの特性も非同期ネットワークにおいて攻撃者によらず高い確率で（セキュリティパラメータλの関数1 - negl(λ)として）成り立たなくてはならない。
- （合意（Agreement））：一つでも正しいノードがトランザクションtxをアウトプットすると、全ての正しいノードがtxをアウトプットする。
- （全順序（Total Order））：一つの正しいノードがトランザクションのシーケンス<tx0, tx1, ..., txj>をアウトプットし、もう一つの正しいノードが<tx'0, tx'1, ..., tx'j'>をアウトプットしたとすると、i ≤ min(j, j')に関してtxi = tx'iである。
- （検閲耐性（Censorship Resilience））：トランザクションtxがN - f個の正しいノードにインプットされると、最終的に正しいノードそれぞれからtxがアウトプットされる。
検閲耐性の特性はライブネスの特性で、攻撃者がトランザクションのコミットを1つでもブロックしてしまうのを防ぐ。この特性は別の名前、例えばCachinらによれば"公正性"などと呼ばれているが、私たちはライブネスの方がより説明のフレーズとして好ましいと考えている。
脚注2：ある程度の効率性を犠牲にするが、再送信することで信頼できないチャネル上で信頼できるチャネルをエミュレートできる。
パフォーマンス指標
私たちは主にアトミックブロードキャストプロトコルの「効率性（efficiency）」と「トランザクションディレイ（transaction delay）」を分析することに関心がある。
- （効率性）：誠実なノードそれぞれのインプットバッファは十分に大きなΩ(poly(N, λ))であると仮定する。このとき、効率性はコミットした全てのトランザクションの償却にかかる各ノードの期待通信コストである。
それぞれのノードが各トランザクションをアウトプットしなければならないので、O(1)の効率性（私たちのプロトコルは満たす）が漸近的に最適である。上記の効率性の定義はネットワークに負荷がかかっていることを仮定しており、これは利用可能な帯域幅を完全に使いながらも高いパフォーマンスを維持するという主要目標を反映している。バッチ化により高スループットを実現するので、トランザクションがまばらで需要が少ない期間はコミットされたトランザクションごとにシステムはより多くの帯域幅を利用する。仮にコストを最小化することが目標であるとしたら（例えば使用ごとの請求など）、この条件を省いたより強い定義の方が適切だろう。
実際には、ネットワークの接続がキャパシティを制限し、ネットワークの処理可能量を超えてトランザクションが送信される場合、一般にコンファメーション時間を保証できない。ゆえに、トランザクションディレイを以下のように当該のトランザクションより前にインプットされたトランザクション数との関係で定義している。トランザクションディレイが有限であることは検閲耐性があることを意味する。
- （トランザクションディレイ）：攻撃者はトランザクションtxをN - f個の正しいノードにインプットとして渡すものとする。Tを"バックログ"、すなわちこれまで全ての正しいノードにインプットされたトランザクションの総数とコミットされたトランザクション数の差であるとする。このときトランザクションディレイは、txが全ての正しいノードによりTの関数としてアウトプットされるまでにかかる非同期ラウンド数の期待値である。
（HoneyBadgerBFTプロトコルを見てみる5 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる7）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。