本稿について
The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。
今回の範囲は「4. The HoneyBadgerBFT Protocol」の「4.5 Analysis」です。原文はこちらになります。
スポンサードサーチ
4. HoneyBadgerBFTプロトコル（続き）
4.5 分析
まず、合意と全順序の特性は、ACSの定義とTPKEスキームのロバスト性からすぐに導かれることを確認する。
定理1（合意と全順序）
無視できるほど小さな確率を除き、HoneyBadgerBFTプロトコルは合意と全順序の特性を満たす。
証明
これら2つの特性は、ハイレベルのプロトコル、すなわちACSとTPKEの特性からすぐに導かれる。各ACSインスタンスは、それぞれのエポックにおいてノードが暗号文のベクトルに合意することを保証する（Step2）。TPKEのロバスト性は、全ての正しいノードが暗号文を特定の値に復号することを保証する（Step3）。これは合意と全順序が保証されるのに十分である。□
定理2（複雑性）
バッチサイズB ＝ Ω(λN2logN)を仮定すると、HoneyBadgerBFTの各エポックの実行時間は期待値でO(logN)で、期待値の合計の通信複雑性はO(B)である。
証明
ACSのコストと実行時間は第4章の4で説明した。N個のインスタンスの閾値復号は1回のラウンドとO(λN2)のコストを余計に発生させるが、全体の漸近的なコストに影響するものではない。□
HoneyBadgerBFTプロトコルでは1エポックで最大Bのトランザクションまでコミットできる可能性がある。しかし実際の数はこれよりも小さい。というのも正しいノードが重複するトランザクションセットを提案したり、そうでないノードがあまりに遅いレスポンスを返したり、壊れたノードが空のセットを提案したりする可能性があるからだ。幸いにも、正しいノード全てのキューがいっぱいであると仮定すると、1エポックでコミットされるトランザクションの期待値の下限はB/4であることを（Appenndixで）証明する5。
定理3（効率性）
正しいノード全てのキューに少なくともBの異なるトランザクションが含まれているとすると、1エポックでコミットされるトランザクションの期待値は少なくともB/4で、一定の効率性がある。
最後に、攻撃者はどんなトランザクションのコミットもあまりに遅延させることはできないことを（Appenndixで）証明する。
定理4（検閲耐性）
攻撃者がトランザクションtxをN - fの正しいノードにインプットとして渡すと仮定する。Tを"バックログ"のサイズ、つまり過去に任意の正しいノードに入力されたトランザクションの総数とコミットされたトランザクション数との差とする。すると、無視できるほど小さな確率を除いてtxはO(T/B + λ)以内にコミットされる。
脚注5：実際の下限は(1 - e-1/3)B > B/4であるが、可読性のためより緩い下限のB/4を用いる。
（HoneyBadgerBFTプロトコルを見てみる9 ←← 前）｜（次 →→ HoneyBadgerBFTプロトコルを見てみる11）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。