ブロックチェーン
\( \def\vector#1{\boldsymbol{#1}} \newcommand{\argmax}{\mathop{\rm arg~max}\limits} \)

論文翻訳: Byzantine Finality Gadgets

Takami Torao 2019年の論文 #Blockchain #Polkadot #GRANDPA
  • このエントリーをはてなブックマークに追加

1 導入

我々はブロックチェーンプロトコルにおけるファイナリティの課題 - ブロックが過去の状態に戻らないようにすること - を検討する。オリジナルのブロックチェーンである Bitcoin のような多くのプロトコルは、チェーンのプレフィクスが増え続けると参加者全体が永久に合意するという結果的なコンセンサスの特性を持っている。しかしそれらは一般的に、ネットワークと参加者に関するいくつかの仮定のもとで、与えられたブロック上にいくつかのブロックが構築されるのであれば最終結果である確率を推定することのできるというだけで、特定のブロックについての確率的なファイナリティを与えているだけである。

しかし我々が望んでいるのは証明可能なファイナリティを持つことである - 例えば一連の権威者によって署名されたステートメントであり、一連の権威者は追跡可能であり、そのブロックは最終的なものである。これは、フルチェーンを持たなかったりネットワークを積極的にリッスンしていない軽量クライアントに何が起きたかを証明し、おそらくスケーラビリティを解決するための一環としてシステム内のすべてのデータを誰も受信ないしは保尊しない他のチェーンと通信するために役に立つ。

ブロックチェーンに対するコンセンサスメカニズムのもう一つの一般的なファミリーは、ブロックごとにビザンチン合意を得ることを含んでいる。これにより証明可能な最終性がすぐに得られる。しかしビザンチン合意に多数の参加者がいる場合は遅くなる。

我々が採用するアプローチは Ethereum が Casper の Friendly Finality Gadget (Casper FFG)[2] での採用を計画しているアプローチと似ている。ブロック生成メカニズムと結果的なコンセンサスを与えるチェーン選択ルールを使用し、そして証明可能なファイナリティを得るために参加者がすでに同意しているブロックをファイナライズするプロトコルであるファイナリティガジェットを追加する。

本論文では \(f\) つまり最大で 1/3 のビザンチン役が存在する下で動作する、部分同期ネットワークモデルで動作するファイナリティガジェットである GRANDPA と、1/5 のビザンチン役に対応できる非同期ファイナリティガジェットを紹介する。

コンセンサスに関する最近の研究は、ファイナリティ付きのコンセンサスを与える多くの異なるブロック生成メカニズムを示している。我々は多数の可能なブロック生成メカニズムに簡単に適用できるファイナリティガジェットの正式な保証を望んでいる。したがって我々はブロック生成メカニズムについては可能な限り最小限の仮定のみにしようと考えている。

この研究の重要な目標はファイナリティガジェットの問題を定式化することである。我々はファイナリティガジェットの safety と liveness を正式に保証したいと考えている。

Table of Contents

  1. 1 導入
    1. 1.1 問題の形式化
    2. 1.2 我々の結果
    3. 1.3 我々のアプローチ
    4. 1.4 関連する研究
      1. 1.4.1 Casper との比較
  2. 2 前置き [under construction]
  3. 3 GRANDPA プロトコル
    1. 3.1 ファイナリゼーション
  4. 4 分析
    1. 4.1 説明可能な安全性 [under construction]
    2. 4.2 継続性
      1. 4.2.1 Deadlock Freeness
      2. 4.2.2 Weakly synchronous liveness
  5. 5 Practicalities
    1. 5.1 Changing the voter set on-chain in an asynchronously safe way
      1. 5.1.1 Changing the voter set in an asynchronously safe way
      2. 5.1.2 Unsafe fallback for changing the voter set after stalling
    2. 5.2 Alternatives to the last block hash
    3. 5.3 Block production rule
  6. 6 Why?
    1. 6.1 ラウンドの終わりや時にはプレコミットの前に待つのはなぜか?
    2. 6.2 なぜプライマリがあるのか?
  7. 7 The asynchronous finality gadget problem
    1. 7.1 Impossibility of a deterministic protocol
    2. 7.2 1/5 BFT finality gadget using a common coin
  8. 8 Optimized version of GRANDPA
  9. References
  10. 翻訳抄

1.1 問題の形式化

我々は、確率的なファイナリティを持つ結果的コンセンサスのプロトコルから証明可能なファイナリティを持つものに修正するために使用できるファイナリティガジェットの概念を形式化したいと考えている。これ達成するためには、もし我々が影響を与えなければ結果的コンセンサスを達成するであろうプロトコルにアクセスできるということをビザンチン合意の定義に組み込む必要がある。多値ビザンチン合意の典型的な定義を考える: 大多数がプロトコルに従う参加者の集合 \(V\) が存在するが、一定の割合はビザンチンの可能性がある。それらは悪意的に行動することを意味する。つまり、誤った情報や一貫性のない情報を提供したり、オンラインにすべきときにランダムにオフラインにしたりする。

定義 1.1. 多値ビザンチン合意のプロトコルは、値の集合 \(S\) と投票者の集合 \(V\) を持ち、その一定の割合はビザンチンであり、各投票者 \(v \in V\) は初期値 \(s_v \in S\) で開始し、最後に、以下が成立するように最終値 \(f_v \in S\) を決定する:

  • 合意: 全ての正直な投票者は \(f_v\) に対して同一の値を決定する。
  • 終了性: 全ての正直な投票者は最終的に値を決定する。
  • 妥当性: 全ての正直な投票者が同じ初期値を持っている場合、それらは全てその値を決定する。

我々は、初期値を持つ代わりに全ての投票者が外部プロトコル (値に対するオラクル) にアクセスし、しばらくしてから呼び出されたときに全ての投票者に同じ値を返すという結果的コンセンサスを達成すると仮定するように定義を変更することができる。

定義 1.2 . プロトコルのオラクル \(A\) は、ある不特定の時間後に全ての参加者に同じ値を返す場合、結果的コンセンサスがあると言う。

定義 1.3. 多値ビザンチンファイナリティガジェット問題のプロトコルは値の集合 \(S\)、投票者の集合 \(V\) を持ち、その一定の割合はビザンチンであり、各投票者 \(v \in V\) は結果的コンセンサスオラクル \(A\) にアクセスでき、最終的に、各投票者は次のように最終値 \(f_v \in S\) を決定する:

  • 合意: 全ての正直な投票者は \(f_v\) に対して同一の値を決定する。
  • 終了性: 全ての正直な投票者は最終的に値を決定する。
  • 妥当性: 全ての正直な投票者は \(A\) がいつか投票者に返した値を決定する。

二値の場合、つまり \(|S|=2\) では、ビザンチンファイナリティガジェットの問題はビザンチン問題に誘導可能である。妥当性の定義がより強いため \(|S|\gt 2\) では当てはまらない。それぞれの初期値を報告する投票者は \(1/|S|\) の割合があり、ビザンチン投票者は検出されないように正直に行動できるため、正直な投票者の初期値を決定し、障害の \(1/|S|\) 以上の割合を許容する必要があるような、多値ビザンチン合意で妥当性の条件を満たせるようにすることは不可能であることに注意。ファイナリティガジェットでは、より強力な妥当性条件が可能であり、正直な投票者が値を持っている場合に定量化する、より強力なバージョンが必要である。

7.1 では一つの障害であっても非同期で決定性のある二値ファイナリティガジェットが不可能であることを示している。これは、合意からファイナリティガジェット問題の方向への必要な削減が分からないため、非同期で決定性のある二値ビザンチン合意プロトコルが不可能であることを示している [3] の有名な不可能性の結果から直ぐには導き出せない。\(A\) が結果的に全ての投票者に同意するという、投票者の追加情報ではこれを可能に為るのに十分ではない。

さて、これどのように拡張して一連のブロックに同意するのだろうか? 問題を形式化する際の難しさの一つは、ブロック生成メカニズムをファイナリティガジェットから完全に分離できないことである。新しいブロックをファイナライズするにはまず既にファイナライズされたチェーンを構築しなければならない。従って、少なくとも、ブロック生成メカニズムはファイナリティガジェットがファイナライズしたブロックを認識し、ブロック生成メカニズムが他の方法でファイナリティガジェットと対話できるようにする必要がある。

我々はファイナリティガジェットを可能な限り最も一般的なブロック生成メカニズムで動作するようにしようとしている。従って、結果的コンセンサスの特性と、最後にファイナライズされたブロックに基づいて構築するためのこの要件を組み合わせた条件が必要だが、それ以外の場合は限定的では無い。我々はある種の条件付きの結果的コンセンサスのようなものを想定している。ファイナライズされたブロック \(B\) に基づいて構築を続け、任意の新しいブロックをファイナライズしない場合、結果的には \(B\) だけではなくより長いチェーンでコンセンサスが得られる。我々はまた終了しないが、代わりにより多くのブロックを作り続けるプロトコルも必要としている。

ファイナリティガジェットプロトコル \(G\) と同時に実行されるブロック生成プロトコル \(P\) が存在すると仮定する。両方のプロトコルの参加者であるアクターは \(G\) で起きたことに応じて \(P\) では異なる振る舞いをする可能性がある。ただし逆方向となる \(G\) の正直な投票者 \(v\) の振る舞いが \(P\) に影響を受ける唯一の方法は、\(v\) とその状態 \(s_v\) に依存しブロック \(B\) を取り、\(B\) を含むチェーンの先頭となるブロック \(B'\) を返す投票ルール関数 \(A(v,s_v,B)\) を使用することである。

もし \(G\) がブロック \(B\) をファイナライズしており、結果的に \(G\) は \(B\) の子孫をファイナライズするか、将来の全ての状態 \(s_v\) の全ての投票者に対して先頭 \(A_{v,s_v}(B)\) を持つ全てのチェーンに \(B\) と同じ子孫 \(B'\) が含まれているなら、システム \(G\), \(P\) と \(A\) は条件付き結果的コンセンサスを達成するという。

定義 1.4. \(F\) を投票者 \(V\) の集合を持つプロトコルとし、その一定の割合はビザンチンの可能性があるとする。全てのブロック生成プロトコル \(P\) に対して投票ルール \(A\) があれば、\(F\) はブロックチェーンビザンチンファイナリティガジェット問題を解決すると言う。このとき以下のようになる:

  • Safety: 全ての正直な投票者は各ブロック番号で同じブロックをファイナライズする。
  • Liveness: もしシステム \(F\), \(G\), \(A\) が条件付き結果的コンセンサスを達成するならば、全ての正直な投票者はブロックのファイナライズを続ける。
  • Validity: もし正直な投票者がブロック B をファイナライズするなら、そのブロックは以前にファイナライズされているある \(B\) の先祖を含んでいるように観測される最良のチェーン上に見られる。

動機付けの例として、\(F\) を Proof of Work を使用した、\(G\) がファイナライズした最後のブロックを含む最長チェーン上に構築し、\(A(v,s_v,B)\) は状態 \(s_v\) の \(v\) から観測される \(B\) を含む最長チェーンとすることができる。

Proof of Work での最長チェーンが正しい仮定の下で結果的なコンセンサスを達成することはよく知られており、この場合の同様な議論は、条件付き結果的コンセンサスがあることを示している。我々が構築しているチェーン上で別のブロックをファイナライズしてチェーンを変更しない限り、市あごにファイナライズされたブロックより長いあるプレフィクス上で結果的に合意するだろう。従って定義 1.4 を満たすファイナリティガジェットは全てこのシステムで機能するため、正直な投票者は全て徐々に長くなる共通のチェーンを完成させる。上記の抽象化のおかげで \(F\) を多くの代替コンセンサスアルゴリズムの一つに置き換えることが可能となり、\(G\) は引き続き機能する。

ファイナリティガジェットのパフォーマンスを分析するには時間に適切に依存する最後の 2 つのプロパティのバージョンが必要だろう。

  • Fast termination: 最後にファイナライズされたブロック番号が \(n\) であり、別のブロックがファイナライズされるまで、全ての参加しゃん観測される最良のチェーンはブロック番号 \(n+1\) を持つあるブロックを含んでいるだろう。このとき番号 \(n+1\) のブロックは時間 \(T\) 内にファイナライズされる。
  • Recent validity: 正直な投票者がブロック \(B\) をファイナライズした場合、そのブロックは、以前にファイナライズされた \(B\) の祖先を含む、何人かの正直な投票者によって時刻 \(T\) 以前よりも最近に観測された最良のチェーンとして見られる。

直感的に Fast termination とは、ブロック生成メカニズムがコンセンサスを迅速に達成する限り、ブロックを高速にファイナライズすることを意味する。一方 Recent validity は、後で決定するブロック生成メカニズムのコンセンサスが最善でないもので合意し始めるコストを制限する。この場合、ファイナライズされることのないチェーンを公得するために時間を浪費する可能性があるため、その期間を制限することが重要である。

これらのプロパティは通常、高い確率でのみ保持される。非同期の場合、これらのプロパティを理解するために、秒ではなくプロトコルのラウンドで時間を測定する必要がある。またビザンチンの投票者を除外しペナルティを与えることにも関心がある。

  • Accountable Safety: 異なるチェーン上のブロックがファイナライズされた場合、少なくとも \(f+1\) ビザンチン投票者を特定することができる。

1.2 我々の結果

(原文に文章なし)

1.3 我々のアプローチ

ブロックチェーンのビザンチンファイナリティガジェット問題の解決策を見つけるために、典型的に我々は様々なビザンチン合意プロトコルを調べ、それらを使用して多値ビザンチンファイナリティガジェット問題のためのプロトコルを見つけるためにそれらを使用する。適切な特性を備えた合意プロトコルを使用して、ブロック番号ごとに並行して時効することを検討することにより、ブロックチェーンのビザンチンファイナリティガジェット問題に対するプロトコルを見つけることができる。一つのブロックプロトコルが適切な特性を持っていれば、それらは一貫してブロックに合意するだろう。従って、もしブロックをファイナライズすると、その祖先もファイナライズされ簡潔なプロトコルを作成することができる。

例えばあるブロックについて、参加者が定足数を観測することを必要とするブロックの投票を要求する 1 ブロックプロトコルがあるとする。例えば、あるブロックについては投票者からの 2/3 の票を観測する必要がある。次に、この投票を各ブロック番号に対して並行して実施し、特定のチェーンからのブロックに対して正直な投票者が投票することを考える。ビザンチン投票者は複数回投票することができるが、1 つのブロックに対する投票を、その番号を持つ 1 つのブロックプロトコルのインスタンスに対する投票でブロックの各祖先に対する投票と見なす場合、ビザンチン有権者は複数のチェーンにも投票できるがあるチェーンに投票しなければならない。これを行うと、あるブロックの投票が定足数を占めている場合、そのブロックの全ての祖先の投票も同様であることが分かる。従って、定足数をもつブロックはチェーンを形成する。さらに、投票者の 1/3 だけがごまかしている場合、参加者がチェーンに対する投票のサブセットを見れば、全ての投票が定足数を持つブロックのチェーンのプレフィクスを見る必要がある。直感的に、投票者の 2/3 がこれを使用することに合意するプレフィクスについて、プロトコルは合意することができる。

安全性を確保するために、各参加者はラウンド \(r\) でファイナライズされた可能性のある最後のブロックの推定 \(E_r\) を維持する。これは、将来のラウンドにおいてそれがファイナライズされた可能性のあるブロックが過大評価されるため、ラウンド \(r\) では先頭 \(E_{r-1}\) を有するチェーンがファイナライズされ得た全てのブロックを含むようにする特性を持つ。正直な投票者は推定 \(E_{r-1}\) を含むチェーンに対してラウンド \(r\) のみ投票し、これはラウンド \(r-1\) でファイナライズできたブロックがラウンド \(r\) でファイナライズされることが保証される。

1.4.1 Casper との比較

ファイナリティガジェットの概念は Casper the finality gadget で導入され、これは我々のものと最も類似したファイナリティガジェットである。従ってこれらを比較することは理にかなっている。ただし、最初に Casper とも呼ばれる他のプロトコルについて言及する必要がある。

最初の Casper は Casper TFG だった。Casper CBC [4] はこのプロトコルの最新で明確に特定されたバージョンを提供している。その分岐選択ルールは投票による GHOST 選択ルールを使用している。Casper TFG では投票はブロックだが、投票と同様に参加者 (提案者と検証者) によってカウントされる。これは GHOST を Proof of Work と共に使用する方法とは異なる。また、投票のグラフに基づいてブロックを主観的に確定する柔軟な方法もある。

Casper FFG [2] では検証者はチェックポイント間のリンクに投票する。これは、例えば 50 の倍数のブロック番号で発生する。連続したチェックポイントであるブロックに 2/3 票がある場合、最初のチェックポイントまでのブロックのチェーンをファイナライズできる。

Epochless Casper,

Casper...

Casper FFG と GRANDPA には 2 つの大きな違いがある。1 つは、GRANDPA では異なる投票者が高さの異なるブロックに同時に投票できると言うことである。これは、投票に関する GHOST の概念を Casper TFG から借用し、より伝統的なビザンチン合意プロトコルに適用することによって達成さえる。

もう 1 つの主な違いは、ファイナリティガジェットが、その基礎となるブロック生成メカニズムの分岐選択ルールにどのように影響するかである。GRANDPA では、デフォルトで、ファイナライズされたブロックを含めることによってのみ影響を受けると想定する。Casper FFT [2] は分岐選択ルールを指定していないが、liveness のために正当化されたブロック上に構築することを要求している。Casper の後の使用では分岐選択の投票に GHOST ルールを使用している。

ファイナライズされたブロックにのみ依存することで、ブロック生成メカニズムとファイナリティガジェットがより明確に分離される。それゆえ、結果的コンセンサスを達成する他のタイプのプロトコルに適用することも容易となる可能性がある - そしてこれを行う多くの多様なプロトコルが過去数年間に開発されてきた。また liveness 特性の証明が遙かに容易になる。ファイナリティガジェットが何もファイナライズしていないため、干渉しない場合、基盤となるメカニズムは結果的コンセンサスに到達する必要がある。これは、ファイナリティガジェットがコンセンサスを持つものをファイナライズするのに十分なはずである。

一方、ブロックの報酬を最大化するためのファイナリティガジェットがない場合、最長のチェーンを構築することは他の全員が同様に行うのであれば合理的であるかもしれないが、最後にファイナライズされたブロックを含む最長のチェーンを構築する場合は必ずしもそうでは無い。これは、別のチェーンが完成される可能性が高いためで、その場合、その上に構築することが合理的なことになるかも知れない。? および ? の分岐選択ルール投票の GHOST はより合理的であるかも知れない。しかしそれが層であることは明かではなく、そのような規則の liveness を証明する方法も明かではない。ファイナリティガジェットの liveness に繋がる分岐選択ルールがあることを示すために、さらなる調査が必要となるかもしれない。

2 前置き

ネットワークモデル: 殆どの場合 [1] のセクション II A に記述されているような部分的に同期したゴシップネットワークモデルを使用する。参加者はゴシップネットワークを介して通信し、そこで他の参加者のサブセットと接続し、受信した全てのメッセージを接続しているすべての接続相手に転送する。ネットワークグラフは、どのようなビザンチン参加者も正直な (honest) 参加者を遮断できないようなものであり、したがって正直な参加者が送受信したメッセージは全ての正直な参加者に到達すると想定する。ここで使用する部分同期モデルはメッセージが時刻 \(T\) 内に受信されるモデルである。ただし、場合によってはグローバル同期時間 (Global Synchronization Time) \(GTS\) の後にのみ受信される。具体的には、時刻 \(t\) の時点で一部の正直な参加者によって送受信されたメッセージは、遅くとも \(GTS+T\) までに全ての正直な参加者に受信される。

投票者: 我々は時々、合意に関する参加者の集合を能動的に変更したいと考えるだろう。此れをモデル化するために、メッセージをフォローする多数の参加者がいる。各投票ステップには \(n\) 人の投票者の集合がある。そのようなステップごとに多くても \(f\lt n/3\) の投票者がビザンチンであると想定する必要がある。ファイナリティに合意するためには \(n-f\) の投票者を必要とする。ブロック生成者が投票するかには関係なく、それらがプロトコルの状態を追跡する参加者である必要がある。

票: 票は、すべてが投票者の秘密鍵で署名されたラウンド番号や投票の種類 (プレ投票やプレコミットなど) などのメタデータとセットになったブロックハッシュである。

ラウンド: 各参加者は、現在のラウンド番号が何であるかについて独自に認識している。全てのプレ投票およびプレコミットにはラウンド番号が関連付けられている。正直な投票者は各ラウンドで (各種類に対して) 一度だけしか投票せず、その後のラウンド以降に前のラウンドで投票しない。

参加者は、現在どのブロックがファイナライズされたブロックとみなされているかを追跡し、最終ラウウンドでファイナライズされた可能性があるブロックの推定を行う必要がある。

ブロック \(B\) に対して、\(B\) を先頭に持つチェーンを \({\rm chain}(B)\) と記述する。ブロック \(B\) のブロック番号 \(n(B)\) は \({\rm chain}(B)\) の長さである。

ブロック \(B'\) と \(B\) について \(B\) のブロック番号が大きい場合に \(B\) は \(B'\) より後であると言う。我々は \(B\) と \(B'\) が同じブロックチェーン上で \(B\) が後ろに存在する、つまり \(n(B) \gt n(B')\) で \(B' \in {\rm chain}(B)\) であることに対して、\(B \gt B'\) または \(B\) は \(B'\) の子孫であると記述する。または、\(n(B') \gt n(B)\) の \(B \in {\rm chain}(B)\) に対して \(B \lt B'\) または \(B\) は \(B'\) の祖先であると記述する。\(B \ge B'\) または \(B \le B'\) は \(B=B'\) を許可することを除いて同様である。\(B \lt B'\), \(B=B'\) または \(B \lt B'\) の場合、\(B \sim B'\) または \(B\) と \(B'\) は同一のチェーンであると記述する; そのようなチェーンがないなら \(B \not\sim B'\) または \(B\) と \(B'\) は同一のチェーンにないとする。

ブロックはジェネシスブロックをルートとするツリーとして順序付けられている。したがって、2 つのブロックには共通の祖先が存在するが、同一のチェーン上にない 2 つのブロックには共通の子孫は存在しない。

投票者 \(V\) によるブロック \(B\) に対する票 \(v\) は、\(B\) のブロックハッシュとラウンド番号や票種別のようなメタ情報を含む \(V\) によって署名されたメッセージである。

ある投票者は票の集合 \(S\) に複数の票がある場合に \(S\) 内でごまかしを行う。我々は \(S\) でごまかそうとする投票者の数が多くても \(f\) である場合、票の集合 \(S\) は寛容 (tolerant) であると呼ぶ。つまり、ブロック \(B\) 以降の票を持っているか、\(S\) でごまかそうとしている投票者の数が少なくとも \((n+f+1)/2\) である場合、\(S\) はブロック \(B\) の定足数 (supermajority) を持っていると言う。このように、投票の観察を単調 (monotonic) にするために、ごまかしを全ての投票数としてカウントする。つまり、もし \(S \subset T\) のとき、\(S\) が \(B\) に対する定足数を持っているなら \(T\) もそうであるが、ごまかそうとしている投票者からさらに多くのごまかしの票を無視することができる。

2/3-GHOST 関数 \(g(S)\) は票の集合 \(S\) を取り \(S\) が \(B\) に対して定足数となる最も高いブロック番号を持つブロック \(B\) を返す。そのようなブロックが存在しない場合は 'nil' を返す (もし \(f \neq \lfloor (n-1)/3 \rfloor\) ならこれは誤った名称であり、それに伴って関数の名前を変更するだろう)。

\(S\) が寛容であれば \(g(S)\) を算出できることに注意。これはジェネシスブロックから開始して現在のブロックの子を定足数で繰り返し探索することで可能である。もし存在するのであればそれは一意でなければならない。したがって次のようになる:

補題 2.1. \(T\) を票の寛容な集合とする。このとき

  1. 前述の定義は \(g(T)\) を一意に定義する。
  2. もし \(S \subseteq T\) が \(g(S) \neq {\it nil}\) を持つなら \(g(S) \le g(T)\) である。
  3. もし \(1 \le i \le n\) に対してい \(S_i \subseteq T\) ならば、全ての非 \({\it nil}\) な \(g(S_i)\) は \(g(T)\) を先頭とする単一のチェーン上にある。

\(g(S)\) の任意の子が定足数を持つかを確認することで \(g(S)\) を \(s(S \cup \{v\})\) に簡単に更新できることに注意。

3 は、たとえ参加者が特定の投票ラウンドで投じられた票の異なる部分集合を見たとしても、この規則は異なるブロックを彼らに与えるかも知れないが、そのようなブロックは全てこの仮定の下で同じチェーンにあることを我々に示している。

次に、投票 \(T\) における全ての票の集合が寛容であり、一部の参加者がブロック \(B\) に対する定足数を持つサブセット \(S \subseteq T\) を観測するならば、他のサブセット \(S' \subseteq T\) を観測する全て参加者は \(S\) が \(B\) に対して定足数を持つことが可能であることもまた観測することになるという、定足数を持つ可能性の概念を定義する。我々は不寛容なセットにまで拡張する定義を必要とする。

少なくとも \((n+f+1)/2\) の投票者がブロック \(\not\ge B\) に投票するか、または \(S\) でごまかしを行った場合、集合 \(S\) が \(B\) に対して定足数を持つことは不可能であると言う。そうでなければ \(S\) が \(B\) の定足数を持つことが可能である。

\(S\) が寛容であれば、\(B\) の定足数を持つ寛容な \(T \supseteq S\) が存在する場合に限り、\(S\) が \(B\) の定足数を持つことが可能である点に注意。これは \(S\) に投票していない全ての投票者と、\(S\) にすでに投票している投票者の票数を \(f\) まで引き上げるのに十分な投票者に \(B\) からの票を追加することで構築できる。

\(S\) が少なくとも \(2f+1\) 人の投票者からの票を持っているなら、\(B\) のいかなる子も \(S\) で定足数を取ることは不可能であり、\(S\) が \(S\) のどの投票のチェーンに現れる \(B\) のそれぞれの子のために定足数を取ることは不可能であると言う。再び、もし \(S\) が寛容であれば、\(B\) のこの可能性があるものに対して、その子に対する定足数を持つ寛容な \(T \supseteq S\) が存在しない場合に限り、それが成立する。

不寛容な \(S\) が \(S\) に対して定足数を持つことは可能であり、いずれにせよ我々がそのような集合を不可能と考えるように、これらの定義の下では定足数を持つことは不可能であることに注意されたい。

補題 2.2 . (i) \(B' \ge B\) であり \(S\) が \(B\) の定足数を持つことが不可能である場合、\(S\) が \(B'\) の定足数を持つことは不可能である。
(ii) もし \(S \subseteq T\) であり \(S\) が \(B\) に対して定足数を持つことが不可能な場合、\(T\) が \(B\) に対して定足数を持つことは不可能である。
(iii) \(g(S)\) が存在し \(B \not\sim g(S)\) であるなら、\(S\) が \(B\) に対して定足数を持つことは不可能である。

3 GRANDPA プロトコル

このセクションでは部分同期設定のファイナリティガジェットである GRANDPA プロトコルを示す。

あるラウンドの 2 度の投票のそれぞれの投票者の集合に加えて、各ラウンドにはプライマリとして指定されている参加者が存在し、すべての参加者は投票者の集合とプライマリ役とに合意すると想定する。通常、我々は投票者の集合から擬似ランダムかローテーションでプライマリを選択する。

\(V_{r,v}\) と \(C_{r,v}\) をそれぞれ現時点のラウンド \(r\) から \(v\) が受信したプレ投票とプレコミットの集合とする。

\(C_{r,r}\) が定足数を獲得できる先頭 \(g(V_{r,v})\) を持つチェーンの最後のブロックによって与えられる、ラウンド \(r\) でファイナライズされた可能性のある \(v\) の推定を \(E_{r,v}\) と定義する。次に、ラウンド \(r\) でファイナライズされる可能性のある全ての \(B\) に対して \(E_{r,v} \ge B\) であると安全に結論付けられる条件を定義する: もし \(E_{r,v} \lt g(V_{r,v})\) であるか、\(g(V_{r,v})\) の任意の子に対して \(C_{r,v}\) が定足数を取ることが不可能であれば、\(v\) はラウンド \(r\) が完了していると見なすと表現する。\(E_{0,v}\) は \(r=1\) から始まると仮定したジェネシスブロックである。

言い換えると、推定チェーン \(E_{r,v}\) がラウンド \(r\) でファイナライズされた可能性のある全てを含んでいる場合にラウンド \(r\) は完了する。これにより次のラウンド \(r + 1\) を開始することができる。

メッセージを送信し全員にそれらをゴシッピングするのに十分な制限時間 \(T\) がある。ラウンド中では、\(E_{r,v} \lt g(V_{r,v})\) を意味する定足数を持つ \(E_{r,v}\) の特性と、ある所与のブロックで定足数を持つことが不可能な特性の両方が単調 (monotone) であり、完了可能である特性も単調である。したがって我々は、ラウンドが完了可能であると誰かが見えた場合、全員が時間 \(T\) 内にそう見えることを期待している。その後、ステップ間で \(2T\) のギャップを残しておくことで、続行する前に全ての正直な (honest) 票を確実に受け取ることができる。

ラウンド \(r\) では正直な参加者は以下を行う:

  1. 投票者 \(v\) は、ラウンド \(r-1\) が完了可能であり、\(v\) が投票者である以前の全てのラウンドにおいて投票を行ったとき、ラウンド \(r \gt 1\) を開始することができる。\(v\) がラウンド \(r\) を開始する時間を \(t_{r,v}\) とする。
  2. 時間 \(t_{r,v}\) で \(v\) がそのラウンドのプライマリであり、\(E_{r-1,v}\) がまだファイナライズされていない場合、\(E_{r-1,v}\) をブロードキャストする。ファイナライズが完了していればとにかく \(E_{r-1,v}\) をブロードキャストできる (ただし必要はない)。
  3. \(v\) がラウンド \(r\) のプレ投票の投票者である場合、\(v\) は少なくとも時間 \(t_{r,v}+2T\) またはラウンド \(r\) が完了するまで待機してからプレ投票をブロードキャストする。それらは \(E_{r-1,v}\) を含む最良のチェーンの先頭に対してプレ投票する。ただし、プライマリからブロック \(B\) を受信し \(g(v_{r-1,v}) \ge B \gt E_{r-1,v}\) である場合には、代わりに \(B\) を含む最良のチェーンを使用する。
  4. \(v\) がラウンド \(r\) のプレコミットステップの投票者である場合、\(g(V_{r,v}) \ge E_{r-1,v}\) かつ条件 (i) 少なくとも \(t_{r,v} + 4T\) である (ii) ラウンド \(r\) が完了可能である (iii) \(V_{r,v}\) が \(g(V_{r,v})\) の子に対して定足数を持つことが不可能である、のいずれかが成立するまで待機する。その後、\(g(V_{r,v}\) に対するプレコミットをブロードキャストする ((iii) はオプションで、(i) と (ii) だけで済ませることができる)。

\(C_{r,v}\) および \(V_{r,v}\) は時間とともに変化する可能性があり、\(V_{r-1,v}\) 及び \(C_{r-1,v}\) の関数である \(E_{r-1,v}\) もまた \(v\) が前のラウンドからより多くの票を検出する場合に時間とともに変換する可能性があることに注意。

3.1 ファイナリゼーション

あるラウンド \(r\) に対し、ラウンド \(r\) のプレコミットステップより後の任意の時点で、\(B=g(C_{r,v})\) が最後にファイナライズされたブロックより後であり \(V_{r,v}\) が定足数を獲得しているのであれば、\(B\) はファイナライズされる。また \(B\) と \(B\) 以上のブロックの一連のプレコミット (\(B\) 自体については可能であれば後述の "Alternatives to the last blockhash" を参照) で構成される、\(B\) に対するコミットメッセージを送信する場合がある。

スパムを避けるため、\(B\) とその子孫の有効なコミットメッセージを受信していない場合にのみ \(B\) に対するコミットメッセージを送信し、\([0,1]\) 秒範囲の一様な乱数で選択された時間を待機してブロードキャストする。

ラウンド \(r\) で \(B\) の有効なコミットメッセージを受け取った場合、それには \(B\) 自体をファイナライズするための十分なプレコミットが含まれているため、ラウンド \(r\) のプレコミットステップが終わっていてファイナライズが行われていないのであれば \(B\) をファイナライズする。

4 分析

4.1 説明可能な安全性

ビザンチン投票者が最大 \(f\) 人存在すると仮定した場合に、最初に示したいのは非同期の safety である。これは、\(v\) がラウンド \(r\) を完了可能と見なすのであれば、\(E_{r,v} \not\leq B\) をもついかなるブロック \(B\) も \(C_{r,v}\) または \(V_{r,v}\) のいずれかが \(B\) の定足数を持つことは不可能であり、従ってラウンド \(r\) で \(B\) がファイナライズされなかったという特性から導かれる。これにより、ラウンド \(r+1\) の全ての正直なプレ投票とプレコミットが、ラウンド \(r\) でファイナライズされた可能性のある全てのブロックを含むチェーン酔うとなる。帰納法では、これが異なるチェーンのブロックをファイナライズできないことを保証する。説明可能な安全性を示すためにはこの証明を逆にして対照的に、別のブロックをファイナライズするのであれば \(f+1\) ビザンチン投票者が存在しなければならないことを示す必要がある。もし我々がこの証明を建設的に行えば、そのような投票者に責任を割り当てることができる挑戦の手続きが得られる。

4.2 継続性

プロトコルがデッドロックフリーであり、弱い同期モデルで新しいブロックを迅速にファイナライズすることも示している。このセクションでは各投票ごとに最大で \(f \lt n/3\) ビザンチン投票者が存在し、各ラウンドのプレ投票とプレコミットのセットが許容さえると想定する。

\(V_{r,v,t}\) を時刻 \(t\) の集合 \(V_{r,v}\) とし \(C_{r,v,t}\) とブロック \(E_{r,v,t}\) も同様とする。

最初に、ラウンドの完了可能性と、完了可能なラウンドの見積もりが投票において単調であることを示す。後者のケースでは単調に減少する:

補題4.4. \(v\), \(v'\) を (おそらく同一の) 正直な参加者、\(t\), \(t'\) を時間、\(r\) をあるラウンドとする。このとき、\(V_{r,v,t} \subseteq V_{r,v',t'}\) と \(C_{r,v,t_ \subseteq C_{r,v',t'}\) と \(v\) は時刻 \(t\) で \(r\) が完了可能であると分かった場合、\(E_{r,v',t'} \le E_{r,v,t}\) と \(v'\) は時刻 \(t'\) で \(r\) が完了可能であると分かる。

Proof. \(v\) は \(r\) が時間 \(t\) で完了可能であることが分かるため、\((n+f+1)/2 \gt 2f+1\) 票を必要とする \(E_{r,v} \lt g(V_{r,v})\) または \(C_{r,v}\) が \(2f+1\) 票を必要とする \(g(V_{r,v})\) の任意の子に対して定足数を持つことは不可能である。いずれの場合も、\(V_{r,v,t}\) と \(C_{r,v,t}\) の両方に \(2f+1\) 人の投票者からの票が含まれるため \(V_{r,v',t'}\) と \(C_{r,v',t'}\) にも同じことが当てはまる。補題 2.1 (ii) より \(g(V_{r,v',t'}) \ge g(V_{r,v,t})\) である。\(C_{r,v,t}\) が \(g(V_{r,v,t})\) の任意の子に対する定足数を持つことは不可能であるため、補題 2.2 (i & ii) に従い \(C_{r,v',t'}\) も同様に不可能であることが分かる。そのため \(E_{r,v',t'} \le g(V_{r,v,t})\) と \(v'\) の両方で \(r\) は時刻 \(t'\) で完了可能であることが分かる。しかしここで \(E_{r,v,t}\) と \(E_{r,v',t'}\) は \({\rm chain}(g(V_{r,v,t}))\) 上の最後のブロックであり、\(C_{r,v,t}\) と \(C_{r,v',t'}\) はそれぞれ定足数を持つことができる。\(C_{r,v',t'}\) が \(E_{r,v',t'}\) に対して定足数を持つことができるため、\(C_{r,v,t}\) が \(E_{r,v',t'}\) の定足数を持つことも可能である。補題 2.2 (ii) および寛容の仮定により \(E_{r,v',t'} \le E_{r,v,t}\) である。∎

4.2.1 Deadlock Freeness

4.2.2 Weakly synchronous liveness

5 Practicalities

5.1 Changing the voter set on-chain in an asynchronously safe way

5.1.1 Changing the voter set in an asynchronously safe way

5.1.2 Unsafe fallback for changing the voter set after stalling

5.2 Alternatives to the last block hash

5.3 Block production rule

6 Why?

6.1 ラウンドの終わりや時にはプレコミットの前に待つのはなぜか?

ネットワークの動作に問題がある場合、それらのステップには任意の長時間に渡る待機が含まれる場合がある。ネットワークが正常に動作しているのであれば (我々のモデルの \(GST\) 後) 待機すべきではない。実際、投票者なしでは何もファイナライズできないため、投票者の 2/3 の投票を待つ必要はほとんどない。しかし、ゴシップネットワークが完全ではなく、一部のメッセージが届かない場合は、デッドロックを回避するために、前のラウンドと同様の方法で他の投票者に票を求める投票を実施する必要があるかも知れない。

これと引き換えに、現在は前回の投票の前の投票に注意を必要がない特性を手に入れることになる。待機がなければあるラウンド \(r\) でブロックをファイナライズしたかも知れないが、ネットワークは多くのラウンドで信用できなくなり、時間通りにわずかな票しか得られず、その場合、後でブロックをファイナライズするためにラウンド \(r\) の票を記憶する必要がある。

6.2 なぜプライマリがあるのか?

我々は liveness のためだけにプライマリを必要としている。繰り返し行われる vote splitting 攻撃に打ち勝つためには何らかの形の調整が筆代津亜。その攻撃の背後にある考え方は、投票者のほぼ 2/3 が何かに投票し、残りが別のものに投票するような状況であれば、ビザンチン投票者は何かに定足数を見るときにコントロールできるということである。彼らが慎重にそれに時間を合わせることができれば、彼らは次で vote splitting を行えるかも知れない。プライマリがいなければ彼らはプレ投票に対してこれを行うことができ、ブロック \(B\) の定足数を後で取得し、そしてプレコミットで split を仕掛けることで、\(B\) の定足数が後まで存在することが不可能であるとは思えない。もし \(B\) が最後にファイナライズされた最良のブロックではなく、同じブロック番号を持つ \(B'\) であるなら、ビザンチンプレーヤーの (未知の) 割合が少なくても、このようにファイナライズを停止することができる。

ネットワークが正常に動作していれば、正直なプライマリはどれだけを合意すべきかを決定することによってこの攻撃を打ち破ることができる。また同じことに共通のコインを使うこともできる。この場合、人々は共通のコインに応じて \(E_{r-1,v}\) または \(g(V_{r-1,v})\) を含む最良のチェーンのいずれかに投票するだろう。オンチェーン投票ではブロック生成メカニズムの確率的なファイナリティを利用することができる - もしブロックをファイナライズせず、常に最後にファイナライズされたブロックを含む最良のチェーン上に構築するならば、最良のチェーンは最終的に収束するだけではなく、もしブロックが最良のチェーンの先頭の後ろにあれば、肯定的な確率で結果的には誰もが知る最良のチェーンとなる。

我々の設定ではプライマリを持つことがこれに対する最も簡単なオプションである。

7 The asynchronous finality gadget problem

7.1 Impossibility of a deterministic protocol

7.2 1/5 BFT finality gadget using a common coin

8 Optimized version of GRANDPA

References

  1. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on bft consensus. arXiv preprint arXiv:1807.04938, 2018. URL https://arxiv.org/abs/1807.04938.
  2. Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437, 2017. URL https://arxiv.org/abs/1710.09437.
  3. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985. URL https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf.
  4. Vlad Zamfir. Casper the friendly ghost: A “correct-by-construction” blockchain consensus protocol. 2017. URL https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf.

翻訳抄

Polkadot で検討されている、重み付き PoW を使った分岐の発生するコンセンサスにファイナリティ特性を追加するための PoS に基づいたアルゴリズムに関する 2019 年の提示文書。原文は誤字、脱字、曖昧で難解な言い回しが多く非常に読みづらい。

  1. - (2019) GRANDPA
  2. - (2019) Byzantine Finality Gadgets