Libra BFTコンセンサス・アルゴリズムの解説 #2

主な技術的アプローチについて

LibraBFTは、ラウンド毎に、参加しているバリデーターの中からコンセンサスを取るためのリーダーを選ぶ。先に述べたように、このアプローチは、部分的なデータ同期に対して必要になるものです。

選ばれたリーダーが、トランザクションのデータからなる新しいブロックを提案し、そして、それを残りのバリーデーターに送る。そして、そのバリーデーターが、そのトランザクションデータに問題ないと判断した場合、新しいブロックの承認になる。リーダーが、過半数の投票を集めた時点で、そのブロックを残りのバリーデーターに送る。もしリーダーが、正しいブロックの提案に失敗した場合や、過半数の投票を得られない場合、タイムアウトのルールが働き、新しいラウンドが始まる。そして、先ほどとは別のリーダーが、既存のバリーデーターから選ばれる。

この方法によって、新しいブロックがブロックチェーンに追加される。結果的に、その新たなブロックが、LibraBFTのコミットルールに適っている場合、これの更新が発生すると、このブロックとその手前のブロックは、コミットされる。

関連情報

ここで、LibraBFTに影響を与えた重要なコンセプトやメカニズムについて紹介しましょう。

伝統的な環境におけるコンセンサスアルゴリズム。ビンザンチン故障問題は、Lamportによって指摘され、彼が、悪意的な行為の総称としてビザンチンというネーミングもしました。Lamportが提唱したこの問題への解決策のセキュリティ面は、共時性に依存しているのだが、この依存性は、実践的なシステムは複雑性を避けようとしつつも、結果的に、DoS攻撃に自分たちのシステムを晒してしまう。

共時性の前提の代わりに、Ben Orが提唱したランダム化するアルゴリズムは、高い確率でこの安全性を保証しました。このアルゴリズムの拡張性は、長年の研究により徐々に改良されていきました。しかし、多くの実践的システムは、このランダム化を取り入れてきませんでした。

将来、LibraBFTは、一定のランダム化を適用するかもしれない。また別のアプローチでは、Dworkが提唱した非同期環境でのアプローチがあり、このやり方では、システムの生存性(データの同期を取っている間)を安全性からは切り離します。実現方法としては、Dworkは、ラウンド毎にコンセンサスを取るやり方を提要、各ラウンドでは、選出されたリーダーがコンセンサスを取りにいきます。

善意的な振る舞いをするリーダーが現れ次第、データの同期が保証され、かつ、一定時間内にコンセンサスを得られない場合はタイムアウトでリーダーが別の人に変わります。Dworkのアプローチ(DLS)は、現時点ではもっとも実践的なBFTコンセンサスアルゴリズムと評価されており、そのパフォーマンスについて継続的に改良が続けられています。特に、一番初めに実践的な解決策として登場したのは、CastroとLiskovによる通称PBFTと呼ばれるアルゴリズムです。

PBFTにおいては、善意的なリーダーは、2対2のコミュニケーションで行うラウンドでコンセンサスを得ていく。オリジナルのPBFTに加えて、このプロトコルは、BFT-SMaRtと、最近では、FaBやZyzzyvaなどに組み込まれていき、全く失敗がない場合、1回のラウンドで合意が取れる。

スレッシュホールドの暗号学を使った反応性のアグリゲーションは、Cachinとレイターによって実用化されたコンセンサスプロトコルであり、この実用化に取って、全員対全員のコミュニケーションアプローチは、全体対収集役か、収集役対全員のパターンに切り替えられた。これによって、コミュニケーションコストは直線的なパターンに限定することができるようになった。

スレッシュホールドの著名によるアグリゲーションは、いくつかのPBFTベースのシステムに組み込まれている。たとえば、Byzcoin、SBFTや同様に、LibraBFTも、メッセージコレクションと高速な著名アグリゲーションを組み入れている。スレッシュホールド著名と比較して、LibraBFTにおける著名アグリゲーションは、分散型のセットアップは必要なく、一つのノードにつき一つの著名を割り当てる形でそのときの価格で追加の入札を一度行い、投票者は、経済的なインセンティブを得ることができる。

新たなに登場したTendermintとCasperというブロックチェーンシステムでは、PBFTのアルゴリズムは、リーダーのリプレイスメントモデル(ラウンド毎にリーダーを入れ替える)を採用することで、直線的なコミュニケーションコストだけをかければよいモデル(直線性)を実現した。この改良点は、実践的な解決策の一つである反応性という優れた特徴で他を先んじている。

非公式には、(楽天的な)反応性は、一定の遅延を待つのとは異なり、リーダーがあらかじめ決められた数のメッセージを受信次第、新しいブロックを提案することができる。故に、TendermintとCasperでは、PBFTのモデルとしては、直線性と反応性の両者の特質は抑えておらず、どちらかになっている。つまり、この両者の特質にはトレードオフが発生している。しかし、Libra BFTが採用しているHotStuffのソリューション(ThunderCoreなども採用している)では、このトレードオフの問題を解消しており、両者の特質を兼ね備えたBFTコンセンサスプロトコルとなっている。

パーミッションレス環境でのコンセンサスについて – 以上の話は、パーミッション環境におけるコンセンサスの話、つまり、ネットワーク環境への参加者があらかじめ把握できている場合である。これとは異なり、パーミッションレスの環境では、だれでもネットワークに参加可能であるため(いわゆるナカモト・コンセンサス)、そのプロトコル構造は、完全に異なるものになる。

ナカモト・コンセンサスにおいては、一定のトランザクションを格納したブロックがチェーンによってつながれ、単純にネットワーク全体に拡散され、Proof of Workのコンセンサスによって維持される。それが故、ファイナリティは、確率的にしか保証されない。その過去のトランザクションの履歴が改ざんされない確率性とは、ブロックチェーンが正しく更新される上で、コンピューターリソースにかけたコストが比例する。現時点で最長のチェーンを拡張し続ける報酬のメカニズムは、マイナー達を、現在のチェーンがデファクトであることを受け入れさせ、急速に、一つかつ最大のチェーンに収束させていくモデルによっている。

いくつかのブロックチェーンは、DAG構造と呼ばれるグラフ形態でブロックを保持するやり方に基づいているため、複数のブロックを並行してつないでいくことができる。代表例は、GHOST、Conflux、Blockmania、そして、Hashgraphなどである。我々が色々と検証した結果を踏まえると、これらのアプローチのいくつかは、ネットワーク参加者が一時的にネットワークから何かしらの理由で離脱した後に、それが原因で抜け落ちたグラフ情報を修復し、そして、それを認証する作業への取り組みが大きな課題になると考えている。

LibraBFTでは、リーダーだけがチェーンを更新できる。故に、分散的であり、リカバリがしやすく、かつ、グラフ情報を認証できる。このアプローチは、シンプルであり、かつ本質的に直線的なのです。

再度、Libra BFTを総括すると、HotStuffを活用しつつ、上記に述べたような過去40年の成果を超えて、新たなBFTコンセンサスプロトコルの実現を目指している。特に、LibraBFTは、DLTとPBFTが採用しているラウンドベースのコンセンサスモデルを採用し、ネットワーク参加者からの著名収集モデルを採用し、そして、直線性と反応性の両者を備える。また、CasperとHotStuffのチェーン構造を踏まえると、強力な実行環境と的確なセキュリティ環境を構築できると考えている。

HotStuff自体と比較して、LibraBFTは、いくつかの強化を実現している。例えば、LibraBFTでは、ペースメーカーメカニズムを取り入れており、これによって、ネットワーク参加者がラウンドの同期を取れるようにしている。これは、トランザクションのコミットを構成するネットワーク参加者の生存確認とセットで機能する。

LibraBFTは、バリーデーターの投票権を再構成するアルゴリズムを持っている。これは同様に、ブロックの提案者と投票者へのリワードメカニズムも含んでいる。当然、セキュリティ面を配慮し、悪意的なバリーデーターを検知し、ペナルティを課すルールも将来的に組み込んでいく。また、バリデーター同士がデータを同期するために、バリデーターにデータを分散させるための改良も加える予定である。

このペーパーの各章の構成について

まず、次のセクション2で、LibraBFTの重要なコンセプトと定義について紹介し、セクション3で、LibraBFTが、Libra Blockchainで活用されるかについて話をし、セクション4で、LibraBFTのコアのデータタイプと、ネットワークコミュニケーションレイヤーについて説明し、セクション5で、BFTのプロトコルそのものについて説明し、セクション6で、我々の考えるProof of Safetyについての詳細を話す。

そして、セクション7では、先に述べたペースメーカーモジュールについて話をし、次のセクション8で、そのモジュールを使ったネットワーク参加者の生存確認の方法について説明し、セクション9で、LibraBFTの経済的インセンティブについて説明し、セクション10で結論づける。

この初期のレポートでは、LibraBFTプロトコルの説明に、Rustのプログラミン言語を選択した。このコードを元に、シュミレーションを行い、その実験結果については、このレポートの続編で、共有していく。

つづく。

Libra BFTコンセンサス・アルゴリズムの解説 #3

関連記事