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

2.概要と定義

まず、Libra BFTの特に重要な点と、我々が、どのように、我々のステートマシンのレプリケーション・プロトコルをLibraブロックチェーンにインテグレーションしているかについてお話する。

2.1. ステートマシン・レプリケーション

ステートマシン・レプリケーション(SMR)プロトコルは、ネットワークに分散化された抽象的なステートマシンを提供することを意味し、実際にノード間にそのステートを複製することを意味している。

特に、SMR プロトコルは、いくつかの初期の実行フェーズから開始する。全てのプロセスは、指令を送り、一連のコミットを確認する。各コミットは、直前のコミットの上に実行された特定コマンドの実行結果のステートを含む。コマンドは、実行時に拒否されることもある。この場合は、そのコマンドが不正と判断される。

コマンドの実行が決定論的であることを想定した場合、我々は、以下の結果を保証したいと考える。

安全性 – つまり、全ての善意的なノードは、同じ順序で並ぶコミットを確認する。

生存性 – 新しいコミットは、正当な命令が実行された場合に限り、実行される。

注意点は、各ノードは、コミットを同じ順序で確認すべきだが、必ずしも同時ではなくていい。善意的なノードの定義については、2.3で説明している。

2.2. Epochについて

実践的な応用面で、ネットワークに参加するノードは、時間と共に進化していくことができる。LibraBFTにおいては、この進化をEpochという形で表記している。

• 各Epochは、手前のEpochの最新の実行ステートを使うところからスタートする、もしくは第1のEpochに使用されたパラメーターを使う

• 我々は、全てのステートの実行は、現在の Epochを特定可能なEpoch IDを含むことを想定している。

• Epoch-IDをインクリメントしたコマンドが実行されるとき、現在のEpochは、このコミットの後にストップし、次のEpochが開始する。

2.3.BFTについて

歴史的に、BFTコンセンサスのプロトコルは、システムのクラッシュという共通の問題に対する耐性を意味していた。ブロックチェーンの文脈においては、 SMTコンセンサスプロトコルでは、システム内の個々のノードのパワーを制限するために使われる。それを実現するために、特定のノードが、ネットワークから外れるような状態が起きたとしても、その安全性と生存性を保証しなければならない。

このレポートのの残りでは、あらかじめ、全てのEpochには、一定の規模の悪意的なノードがいることを想定し、これをビザンチンノードと呼ぶ。他のノードは、プロトコルのルールにきちんと従う善意的なノードと呼ぶ。ある一つのEpochの更新の間に、全てのSMRのノードαは、一定の投票権を持ち、それを? (?) ≥ 0で表現する。そして、Nを全てのノード数を合計投票権と定義し、プロトコルのセキュリティを保つスレッシュホールドをNのファンクションとしてのfと定義し、? > 3?と表現する。例えば、? = [(?−1)/3]と定義できる。

このレポートにおける定義の単純化のため、我々は、Xを ノード数Xの投票権として定義している。そして、BFTの前提条件に従う、全てのコンセンサスのプロパティを以下のように分析する

(BFTの前提条件)全てのEpochにおけるビザンチンノードの投票権は、セキュリティスレッシュホールドの値Fを超えてはならない。

一連の投票権Mを持ったノード群が、? ≥ ? − ?を満たす場合、これを、コンセンサスに必要な最低数を満たす状態、つまり、クオラムと呼ぶ。クオラムは、以下の伝統的なモデルによって正当化されている。

Lemma B1: BFTの前提では、同じEpockにおける全ての二つのクオラムのノードにつき、その両者のクオラムには、善意的なノードが紐づいている状態と言える。これを我々は、Proof of Lemma B1と読んでおり、セクション6.1で触れている。

2.4.暗号学上の前提条件

まず、ハッシュ計算とデジタル著名の方式は、コンピューターを使った攻撃者に対してセキュアであり、全ての善意的なノードが、その著名に使ったプライベートキーを秘密裏に保管することを必要とする。

LibraBFTプロトコルでは、ハッシュ値と著名を公開データとして保持するだけなので、確率的な意味合いを完全に排除する形で、全てのデジタル著名が偽造できないようにしなければならない。つまり。全てのデジタル著名は、プライベートキーのオーナーから生成されなければならない。同様に、ハッシュ値同士の不一致は発生しないと想定しているため、hash(?1) = hash(?2) は、すなわち ?1 = ?2 であると想定する。

2.5.ネットワークの前提条件と正直なクラッシュについて

LibraBFTの安全性は、BFTの前提条件下であれば保証される一方で、ネットワークの生存性は、これに加えて、ネットワーク上の環境やプロセスも前提条件に加えなければならない。特に、接続環境の良し悪しにブレがあることを想定しなければならないため、同期性と非同期性をそれぞれ考慮しなければばならない。

生存性は、同期性が長期に渡って維持できている場合のみ保証される。では、非同期の期間中はどうなるか?というと、メッセージの紛失を許容するか、裁定処理を行うことになる。同時に、善意的なノードが、時にクラッシュし、再起動することも許容する必要がある。同期性の期間においては、我々は、アッパーバウンドの??が、善意的なノード間のメッセージのやりとりの間で、転送遅延の発生を想定する必要がある。この条件下では、善意的なプロセスは、反応性をきちんともち、クラッシュすることは許されない。

我々は、ネットワークの敵対者が、悪意的なノードをコントロールし、同期をしている間でさえネットワーク間のメッセージのやりとりのスケジュールしなければならないのであり、これが、?? という遅延を引き起こす。

例えば、?? のようなこのモデルの変数は、そのネットワークがその時点で同期が取れているかどうかに関わらず、そのシステム内の参加者が利用することはできない。

この分析を単純化するために、一般的には、現時点でのGST(Global Stabilization Time)とそのGSTの後の時間の二つの期間を考慮する。我々のProof of Liveness(生存性の証明)は、GSTの後に、システムがコミットを行うことに必要な、具体的なアッパーバウンドの値を与える。

より正確に表現すると、そのネットワーク環境の前提とクラッシュは、以下のように表現できる:

(結果的に同期性を維持するネットワーク)GSTのあと、ネットワークは、?? > 0という未知の遅延下で、善意的なノード間に全てのメッセージを配布する。

(結果的にクラッシュしないネットワーク)- GSTの後、善意的なノードは完全に反応性を維持し、決してクラッシュしない。

ここで再度、注目すべきは、GSTモデルは、メッセージを処理するに関わるCPUの処理時間は考慮に入れていないことだ。更に、LibraBFTのメッセージサイズは、上限が設定されていないため、??の値をあらかじめ固定で想定するのは、モデルを単純化しすぎている。将来的には、我々も、メッセージサイズの上限を設定し、各メッセージの送信時におけるネットワークの遅延について、メッセージサイズに応じた転送遅延が発生するかや、固定した遅延を前提にした送信モデルの場合の振る舞いなどについてみて行きたいと考えている。

2.6. リーダー、投票、そしてクオラム・コンセンサスを得る条件について

Libra BFTは、リーダーベースのコンセンサスプロトコルのカテゴリに該当している。リーダーベースのプロトコルでは、バリデーターは、ラウンドごとに投票を行い、その際、特定のバリデーターの中からそのリーダーを選ぶ。リーダーは、新しいブロックの提案について責任を追い、他のバリデーターからそのブロックを承認するための著名入りの投票を得る。

LibraBFTでは、HotStuffのコンセンサスプロトコルを応用しており、そこでは、選ばれたリーダーが、新しいブロックを提案するためのラウンドを実施し、リーダーのその更新提案は、暗号的ハッシュ値を使ってブロックチェーンの中で運用される。そのラウンドの間は、リーダーは、ネットワーク全体の中では、最長のチェーンを拡張するための新たなブロックを提案する。

その提案が正当なものでかつ時間通りであるならば、各善意的なノードは、デジタル著名し、その投票をリーダーに戻す。そして、リーダーは、クオラム・コンセンサスに達するだけの十分な投票をえた場合、その投票をQuorum Certificate (QC) にアグリゲーションし、元の同じチェーンを拡張する。

その後、QCは、すべての参加ノードにブロードキャストされる。もし、そのリーダーが、QCを作るのに失敗した場合、ネットワーク参加者は、タイムアウトし、別の新しいラウンドへと移行する。この一連の作業を通じて、結果的に、十分なブロックとQCが、時間通りにそのブロックチェーンを更新し、そして、新たなブロックは、そのコンセンサスプロトコルのコミットルールに従う形で更新される。これが起きるときは、コミットされていないブロックをもつチェーンは、最長のブロックに統合される形でコミットされる。

つづく。

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

関連記事