調査

HoneyBadgerBFTプロトコルを見てみる2

更新日:

本稿について

The Honey Badger of BFT Protocolsを読みます。バージョンは20161024:215945です。

今回の範囲は「1. Introduction」の「1.1 Our Contribution」と「1.2 Suggested Deployment Scenarios」です。原文はこちらになります。

スポンサードサーチ

1. はじめに(続き)

1.1 貢献

タイミングアサンプションは有害

既存の最大のBFTシステムは、"ロバストである"と呼ぶとしても、何らかの「弱同期性(weak synchrony)」を仮定している。大まかに言えば弱同期性とは、メッセージがある上限Δが経過した後に配信されることを保証するものの、Δは時間変化するかもしれないしプロトコル設計者にも分からないかもしれないというものだ。ネットワークの接続が信頼できない可能性があり、ネットワーク速度が急速に変わり、ネットワークディレイが敵対的に誘発される可能性がある非中央集権型の暗号通貨の設定に対してタイミングアサンプションに基づくプロトコルは不適切であると考えている。

第一に、弱同期的プロトコルのライブネス特性は予想しているタイミングアサンプションが侵害される(例えば悪意あるネットワーク攻撃者による)と完全に失われる。これを説明するためにタイミングアサンプションを侵害する敵対的な"同期が途切れ途切れの"ネットワークを明示的に作ると、PBFTなどの既存の弱同期的プロトコルは急停止する(第3章)。

第二に、弱同期仮定が実際には満たされるとしても、基盤ネットワークが予測できないものである場合、弱同期的プロトコルはスループットが著しく悪化する。理想的には、ネットワークの状態が急速に変化する場合であってもスループットがネットワークのパフォーマンスと極めて近い動きをするプロトコルが好ましいだろう。残念ながら弱同期的プロトコルは、特に暗号通貨アプリケーションの設定においては調整に細心の注意が必要なタイムアウト変数が必須である。そして選んだタイムアウト変数が長すぎたり短すぎたりすると、スループットを妨げてしまう。具体例として、弱同期仮定が満たされる場合でもこのようなプロトコルは一時的なネットワーク分裂からの回復が遅いということを示す(第3章)。

実用的な非同期BFT

私たちはHoneyBadgerBFTを紹介する。これは初のBFTの「アトミックブロードキャスト(atomic broadcast)」プロトコルで、非同期設定で「最適な漸近的効率性(optimal asymptotic efficiency)」をもたらす。従ってこのようなプロトコルはどうしても非実用的であるという一般通念に直接反論する。

私たちはCachinら[15]による過去最高の非同期的アトミックブロードキャストプロトコルにたいして大幅な効率性向上を成し遂げた。Cachinらのプロトコルではコミットされるトランザクションそれぞれに対して各ノードがO(n2)ビットを送信することが必要で、最小のネットワークである場合を除き大きくスループットを制限してしまう。この非効率性には2つの根本的な原因がある。

一つ目の原因はパーティ間における冗長な仕事である。しかい、冗長性を真っ正面から排除しようとするとフェアネス特性を侵害してしまい、標的型検閲攻撃を許してしまう。私たちはこれらの攻撃を防ぐ閾値公開鍵暗号を用いてこの問題を克服する最新のソリューションを発明した。二つ目の原因は非同期コモンサブセット(Asynchronous Common Subset, ACS)サブコンポーネントの準最適なインスタンス化を用いていることである。私たちは既にあるものの見落とされていた手法を組み合わせてACSを効率的にインスタンス化する方法を示す。組み合わせる手法は、抹消コードを用いた効率的なリライアブルブロードキャスト[18]と、マルチパーティ計算の文献から分かったACSからリライアブルブロードキャストまでの削減[9]である。

HoneyBadgerBFTの設計は、ネットワーク帯域幅は乏しいリソースだが計算リソースは比較的余力がある暗号通貨ライクなデプロイシナリオ向けに最適化されている。これにより、コンテンション下でも応答時間を最小化することが主要目標となっていた従来のフォールトトレラントなデータベース設定では高価すぎると考えられていた暗号理論によるブロック生成(特に閾値公開鍵暗号)を活用できる。

非同期ネットワークでは最終的にメッセージが配信されるが、タイミングアサンプションはいらない。パラメータ調整に細心の注意を要する既存の弱同期的プロトコルとは異なり、HoneyBadgerBFTのスループットは常にネットワークの利用可能な帯域幅に近しい動きをする。こういうと正確性に欠けるが、メッセージが最終的に配信される限りHoneyBadgerBFTも最終的に進行する。さらに言うと、メッセージが配信されるとすぐに進行する。

私たちはHoneyBadgerBFTプロトコルのセキュリティとライブネスを形式的に証明し、楽観的な場合でも旧来のPBFTプロトコル[20]より高いスループットを出すことを実験的に示す。

実装と大規模実験

私たちは十分に開発の進んだHoneyBadgerBFTの実装を提供し、近い将来フリーのオープンソースソフトウェアとしてリリース予定である1。5大陸に散在する100超のノードを使ってAmazon AWSデプロイから得られた実験結果を示す。またロバスト性と多用途性を示すために、「パラメータを一切変更せずに」Torの匿名リレーネットワーク上にHoneyBadgerBFTを実装した。このスループットとレイテンシの結果を紹介する。

脚注1:https://github.com/amiller/HoneyBadgerBFT

1.2 デプロイシナリオの提案

幾通りも考えられるアプリケーションの中から、銀行や金融機関、完全な非中央集権型暗号通貨の支持者から重宝されそうなデプロイシナリオを2つ示す。

連合型暗号通貨

Bitcoinなどの非中央集権型暗号通貨の成功は、銀行や金融機関に新しい視点でトランザクション処理やセトルメントインフラを検査するきっかけを与えた。"連合型暗号通貨"はよく引き合いに出されるビジョン[24, 25, 47]で、金融機関のコングロマリットが連帯してビザンチン合意プロトコルに貢献し、高速かつロバストなトランザクションセトルメントをできるようにするというものだ。熱が上がってきているので、このアプローチは今日の銀行間セトルメント用の遅くて重いインフラの無駄をなくして改善するだろう。この結果、例えばIBMのOpen BlockchainやHyperledgerプロジェクト[40]のように、いくつかの新たなオープンソースプロジェクトがこの文脈で安定したBFTプロトコルを構築しようとしている。

連合型暗号通貨には、もしかすると数万のコンセンサスノードが関係するような広域ネットワーク上にBFTプロトコルをデプロイする必要があるかもしれない。この設定では、コンセンサスノードのセットは「アプリオリに」分かっているので、容易に登録を管理できる。こういったものはよく"パーミッション制の"ブロックチェーンと呼ばれる。HoneyBadgerBFTがこのような連合型暗号通貨で使われる候補となることはどう考えても不思議なことではない。

パーミッションレスなブロックチェーンへの応用

対照的にBitcoinやEthereumなどの非中央集権型の暗号通貨は、"パーミッションレス"なブロックチェーンを選ぶ。パーミッションレスブロックチェーンでは登録は誰でも行えるようになっており、ノードは動的かつ頻繁に参加したり退出したりする。この設定においてセキュリティを実現するために、シビルアタック対策で既知のコンセンサスプロトコルはプルーフオブワークに依拠しており、スループットとレイテンシの観点で大きな対価を支払っている。例えばBitcoinではトランザクションのコミットは~10分ごとで、スループットは現行のブロックサイズが最大化されても7tx/秒までに制限されてしまう。最近のいくつかの研究では、基盤となる通貨そのものに関連してはBitcoinなどのより低速な外部ブロックチェーンを利用するか経済的な"プルーフオブステーク"の仮定を活用し、それぞれのエポックごとにBFTを実行するランダムなコミティを選択することで高速なBFTプロトコルをブートするのという有望なアイデアが提唱されている[32, 32, 35, 37]。これらのアプローチは、登録が開かれている非中央集権型ネットワークのセキュリティと、旧来のBFTプロトコルとマッチするスループットや応答時間の両側面で、最良の結果を出すのではないかと期待させる。ランダム選択のコミティは地理的に不均一であることから、ここでもHoneyBadgerBFTが選ばれるのは自然なことである。

HoneyBadgerBFTプロトコルを見てみる1 ←← 前)|(次 →→ HoneyBadgerBFTプロトコルを見てみる3

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。

-調査
-, , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。