本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「4. The HoneyBadgerBFT Protocol」の「4.3 Constructing HoneyBadgerBFT from Asynchronous Common Subset」です。原文はこちらになります。
スポンサードサーチ
4. HoneyBadgerBFTプロトコル（続き）
4.3 HoneyBadgerBFTを非同期コモンサブセット（ACS）から構築する
ブロック生成：ACS
主な生成ブロックは非同期コモンサブセット（ACS）と呼ばれるプリミティブだ。ACS構築に関する理論的な実現可能性はいくつかの研究で取り組みがなされてきた[9, 15]。本章ではACSの形式的な定義を紹介し、ブラックボックスとして用いてHoneyBadgerBFTを構築する。後ほど第4章の4にて、過去に見落とされてきたいくつかの構成を組み合わせることでACSを効率的にインスタンス化できることを示す。
より形式的には、ACSプロトコルは以下の特性を満たすものである。
- （バリディティ（Validity））：正しいノードが集合vをアウトプットするならば、|v| ≥ N - fかつvには少なくともN - 2f個の正しいノードのインプットが含まれている。
- （合意（Agreement））：正しいノードが集合vをアウトプットするならば、全てのノードがvをアウトプットする。
- （トータリティ（Totality））：N - f個の正しいノードがインプットを受け取るならば、全ての正しいノードがアウトプットを生成する。
ブロック生成：閾値暗号
「閾値暗号（threshold encryption）」スキームTPKEは暗号プリミティブで、誰でも公開鍵の持ち主にメッセージを暗号化できるようにするので、ネットワークのノードはこれを復号するために協力しなければならない。f + 1個の正しいノードが暗号文に関する「復号シェア（decryption shares）」を計算して明らかにすると、平文が復元される。少なくとも一つの正しいノードが復号シェアを明らかにするまでは攻撃者は平文について何も分からない。閾値スキームは以下のインタフェースを提供している。
- TPKE.Setup(1λ) → PK, {SKi} は、各者の秘密鍵SKiと公開鍵PKを生成する。
- TPKE.Enc(PK, m) → C は、メッセージmを暗号化する。
- TPKE.DecShare(SKi, C) → σi は、i番目の復号シェアを生成する（Cが不正な形式であれば⊥（偽）を生成する）。
- TPKE.Dec(PK, C, {i, σi}) → m は、少なくともf + 1個のノードから復号シェアの集合{i, σi}を結合して、平文mを得る（Cに無効なシェアが含まれる場合、そのシェアを特定する）。
インスタンス化においては、具体的にはBaekとZheng[7]の閾値暗号スキームを利用する。このスキームもロバスト（私たちのプロトコルに必須）で、敵対的に生成された暗号文Cに関しても最大1つの平文（⊥を含む）を復元できるということを意味する。TPKE.Decは効果的にインプットの中の「無効な（invalid）」シェアを特定すると仮定している点に注意されたい。最後に、個のスキームは明らかに正当性の特性を満たすとともに、IND-CPAゲーム3の閾値版を満たす。
脚注3：BaekとZhengの閾値スキームは（閾値が同じで）より強いIND-CCAゲームも満たすが、こちらは私たちのプロトコルには必要ない。
ACSからのアトミックブロードキャスト
さて、私たちのアトミックブロードキャストプロトコルをもっと詳しく説明する。図1に定義する。
既述の通り、このプロトコルはACSを中心に展開される。スケーラブルな効率性を得るためにバッチ化のポリシーを採用している。Bをバッチサイズとし、各エポックでΩ(B)のトランザクションをコミットするとする。各ノードは自身のキューからB/Nのトランザクションを提案する。ノードがほぼ別のトランザクションを提案していることを確実にするため、それぞれのキューで最初のBからランダムにトランザクションを選ぶ。
第4章の4で確認するが、私たちのACSインスタンス化手法の通信コストの合計はO(N2|v| + λN3logN)である。|v|はあらゆるノードのインプットサイズを限定する。従って各ノードからの貢献（B/N）がこの付加的なオーバヘッド（筆者注：λN3logNの部分）を吸収できるようにするためにバッチサイズB = Ω(λN2logN)とする。
以下に説明するように、攻撃者が結果に影響するのを阻止するために閾値暗号スキームを利用する。簡潔に言えば、各ノードはトランザクションセットを選んで暗号化する。次に各ノードはACSサブルーチンにインプットとしてこの暗号を渡す。従ってACSのアウトプットは暗号文のベクトルである。ACSが完了すると暗号文は復号される。これにより、各ノードが行った提案の具体的な内容を攻撃者が知る前にトランザクションセットが完全に決定されるということが保証される。これは十分な数の正しいノードのキューの先頭にトランザクションがあれば、攻撃者はそのトランザクションのコミットを選択的に妨害することはできないということを保証している。
（HoneyBadgerBFTプロトコルを見てみる7 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる9）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。