Scaling Bitcoin 2018 復習シリーズ。今回はヘブライ大学のYonatan Sompolinskyによる「The GHOSTDAG Protocol」の発表↓（30分あたりから）
書き起こしは↓
ホワイトペーパーは↓
https://eprint.iacr.org/2018/104.pdf
Bitcoinのオンチェーンスケーラビリティを向上させるプロトコル、GHOSTDAGの提案。
Bitcoinのコンセンサスプロトコル
基本的にBitcoinのプロトコルでは、10分間隔でブロックが生成され、そのブロックサイズの上限は1MBと決められている。各ブロックは前のブロックを参照するハッシュチェーンを形成し、同じタイミングでブロックが作られチェーンが分岐すると、後ろにより多くのブロックが続いた方が正当なチェーンとなる最長チェーンのルールが適用され、チェーンが１つに収束するようになっている。
Bitcoinでは正直なマイナーが取る行動は、
- 最も長いチェーンの先頭のブロックをマイニングする。
- ブロックがマイニングできたらすぐに公開する。
安全性の仮定は、
- 51%以上が正直なマイナーであること。
- ブロックを作成する時間より、ブロックを伝播する時間の方が短いこと。
この仮定の下、ネットワークに参加している各ノードは最長のチェーンをピックアップし、最長チェーンのトランザクションが別のブロックに置き換わる確率は、後続にブロックが続くほど指数関数的に低くなる。
オンチェーンスケーラビリティを上げるのに問題となるのが、↑のブロック作成時間と伝播時間の関係。スケーリングさせる方法は大きく2つあって、１つはブロックサイズを大きくすることで、この場合ブロックの伝播時間は長くなる。もう１つはブロックの生成間隔を短くするというものだが、いずれも均衡を破ることになる。GHOSTDAGで実現しようとすることは、ブロック伝播の仮定を取り除く、もしくは何らかの方法でそれを弱めること。
プロトコル加える変更は最長チェーンの先頭を見るのではなく、有向非巡回グラフ（DAG）を使用するようにし、その構造でProof of Workでマイニングをする。Proof of Workをすることは変わらず、できるだけ早くブロックを公開するというのも変わらない。ただ最長チェーンを選択するのではなく、最も長いk-クラスター（後述）を選択するようになる。また、確率の高い取引セットを持つというのも変わらず、多くの承認を経ることで二重使用の確率は指数関数的に減少する。
プロトコルの変更によって得られるもの
正しく適用されれば安全性を損なうことなくハイスループットが得られるが、フリーライドではない。レイテンシーはもちろん増加する。コンセンサスプロトコルにおいてスループットとレイテンシーは避けられないトレードオフであるため、それを回避するのは難しい。承認のため長時間待たないといけないが、安全性が損なわれるよりは良い。
ブロックチェーン全体を保存する方法や、検証時間の改善方法、起動してデータ全体を同期する方法など、他のコンセンサスの問題は解決しない。ここでターゲットにしているのはコンセンサスレイヤーのみ。
PHANTOMプロトコル
最長チェーンを正とする１つのチェーンを維持するデータ構造を、有向非巡回グラフ（DAG）をベースにしたデータ構造に変えたのがPHANTOMプロトコルになる。Bitcoinの場合、ブロックは１つのチェーンとしてリンクするのに対し、PHANTOMプロトコルではブロックはツリー構造でリンクされ、blockDAGと呼ばれる有向非巡回グラフを形成する。
各ブロックは前の単一のブロックのハッシュを参照するのではなく、前の複数のブロックのハッシュを参照するようになる。
表記
blockDAGの要素を指す際に使用する表記：
- ブロックDAG：G = (C, E)
Cはブロックを表し、Eは前のブロックのハッシュを指す。
Bから到達可能なブロックのサブセット＝Bの前に作られたブロックのセットを表す。
Figure 1では、past(H) = {Genesis, C, D, E}となる。これはHが直接もしくは間接的に参照するブロックでHより先に作られたことが保証される。
Bへ到達可能なブロックのサブセット＝Bの後で作られたブロックのセットを表す。
Figure 1では、future (H) = {J, K, M}となる。これはHを直接もしくは間接的に参照するブロックで、Hより後に作られたことが保証される。- anticone (B, G)
と
に含まれないブロック＝直接または間接的にBを参照せず、Bからも直接または間接的に参照されないDAG内のブロックのセット。
Figure 1では、anticone (H) = {B, F, I, L}となる。これはHとの順序が曖昧なブロックで、この順序を決めるのがコンセンサスの課題（後述）。 - tips(G)
入次数が０のブロック＝誰からも参照されていないブロック＝最新のブロックのセット
Figure 1では、tips(G) = {J, L, M}となる。リーフブロックで、次のブロックで参照されるようになる。
DAGのマイニングプロトコル
DAGの場合単一のチェーンを伸ばすのではなく、マイナーが作る新しいブロックはtips(G)のすべてのブロックを参照する（Gはブロック作成時にマイナーがローカルで観測しているDAG）。
新しいブロックを発見したら、マイナーはすぐにそのブロックを公開する（ここはBitcoinの場合と変わらない）。
DAGの順序付けプロトコル
DAGのマイニングプロトコルでは、チェーンのTIPを参照する複数のブロックが作られることになる。Bitcoinの場合、最長チェーンルールによりやがて１つになるが、DAGの場合複数のブロックのまま残る。残った際に問題となるのは順序の問題だ。例えば競合する２つのトランザクションがあった場合（二重使用）、どちらのトランザクションを正とするか？Bitcoinの場合最長チェーンルールにより順序が決まり、これを解決する。DAGの場合、２つのブロックができ、そのブロック内に競合するトランザクションがあった場合、どちらのトランザクションが正しいのか決定する必要がある。
PHANTOMプロトコルでは以下の2段階で順序付けを行う。
- 最初にブロックをブルーとレッドに分ける。ブルーのセットは協調ノードによってマイニングされたように見えるブロックを表し、レッドのセットは悪意あるノードもしくは戦略的なノードによってマイニングされた可能性が高い異常値のセット。
- 次に、ブルーブロックを優先し、レッドブロックにペナルティを与えるようDAGの順序付けをする。
重要なのは1のカラーリングで、これをどのように行うか？
PHANTOMプロトコルもBitcoinと同様Proof of Workによりマイニングが行われ、正直なノードはタイムリーに周りのノードと最近のブロックについて連携する能力を持ち、そんな正直なノードがハッシュパワーの50%以上を保持しているという前提を元にしている。Bitcoinと異なるのは、Bitcoinがブロックの作成が通信（伝播）にかかる時間より遅く設計されているが、PHANTOMプロトコルではそのようなことはなく、フォークが自然的に発生する環境下でも正しいブロックのセットが認識されるよう設計される必要がある。
こういった前提の下、ネットワークの伝播遅延時間の上限をDとし、ブロックBが正直なマイナーによって時刻tでマイニングされた場合、t - Dより前に公開されたブロックは必ず時刻tより前にマイナーに届いており、それはpast(B)に含まれる。同様に正直なマイナーはすぐにBを公開するので、時刻 t + D 後にマイニングされたブロックにはBが過去のブロックとして含まれる。結果として、Bのanticoneになる正直なブロックのセットは、一般的に小さく、期間[t - D, t + D]の間に生成されたブロックのみで構成される。proof-of-workの仕組みは、長さ２・Dの間隔で作成されたブロックの数は通常あるk > 0未満であることを保証する。要するに、正直なノードによって作成されたブロックのセットは、well-connected = anticoneが少ないセットとなる。
つまり正直なノードが発見したブロックをすぐに公開し、かつ周りから受け取ったブロックを組み込んでマイニングしているのであれば、そうやって作られたブロックは多くのTIPへの参照を持ち、多くの後続ブロックから参照が行われるブロック＝well-connectedなブロックになる。そのため、そうでないブロックは攻撃者によって作られたブロックであると。この時のセキュリティパラメータがkで、Figure 2はk=3とした場合、DAGのカラーリング結果になる。
kはPHANTOMプロトコルの相互接続パラメータで、k = 3の場合、anticoneのサイズは3を超えてはならない。Figure 2を見てみると、このルールに違反しているのがレッドカラーのブロックで、ブロックEのanticoreは（B, C, D, F, G, I）で3を超えている。これらのブロックがEを参照しないのは、おそらくEを作成したマイナーによってEが保留されていたため。同様にブロックKのanticoreは(B, C, G, F, I, J)で、悪意あるマイナーは既に(B, C, D, G)を受け取っているにもかかわらず、その一部を参照していないという点でマイニングプロトコルに違反している。
ということで、blockDAGの順序付けは以下のように行う。
- DAGが与えられた場合に、上記k-クラスタールールを適用してブルーセットを決め、その補足セットとしてレッドセットを使う。
- いくつかのトポロジカルなソートに基づいてブルーブロック間の順序を決定する。次に任意のブルーブロックBについて、Bの直前の順序にまだ順序付けされていないpast(B)のレッドブロックを追加する。レッドブロックもトポロジー的に追加する必要がある。
そのため、Figure 2の小さなDAGの順序はA, D, C, G, B, F, I, E, J, H, Kとなる。
こうやってDAG構造の各ブロックの順序が決められるが、1つ大きな問題がある。成長し続けるDAGにおいて、DAG内の最大k-クラスターを見つけるのはNP困難な問題だということ（最良のセットを見つけるのに指数関数的な計算量がかかる）。このためPHANTOMプロトコルを適用するのは実用的ではなく、代わりにgreedyアルゴリズムを導入したPHANTOMプロトコルの変形であるGHOSTDAGプロトコルが提案されている。
k = 0 == Bitcoin
ちなみにk-クラスターの値を0に設定した場合、そのブロックはanticoneを持たないブロックとなり、この設定の下ではPHANTOMプロトコルやGHOSTDAGプロトコルはツリーではなくBitcoinのようにチェーンを形成するようになる。
そういう意味では、SatoshiのBitcoinはPHANTOMプロトコルにおけるk＝0のクラスターであるとも言える。
GHOSTDAGプロトコル
PHANTOMと同様、GHOSTDAGプロトコルは（選択されたクラスタ内のブロックである）ブルーと（クラスタ外のブロックである）レッドのブロックのカラーリングを誘発するk-クラスターを選択する。ただし、GHOSTDAGプロトコルでは最大のk-クラスターを見つけるのではなく、greedyアルゴリズム＝貪欲法を使って大きなk-クラスターを見つける。このアルゴリズムによって見つけたクラスターは最大のk-クラスターではないものの、十分に大きなものになる。基本的にk-クラスターは正直なノードであると考えられるグループで、最大のk-クラスターを探す場合、正直なマイナーがネットワークの過半数でブロックの大きなセットを生成しそれぞれのブロックのanticoneは小さいと仮定しているため、貪欲法はそれを検出するのにうまく作用する。
ブロックを追加する際にその時点の最良のTIP＝これまで最大のブルーセットを持つ を継承し、
の過去に無いブルーセットのブロックに追加することで、DAGのブルーセットを構築する。これでk-クラスター特性は保持される。
GHOSTDAGの基本的な考え方は重いk-クラスターをブロック単位で継承しながら徐々にDAG構築していくことで、最大k-クラスターを発見するというNP困難な問題を回避している。この辺りは同じくGHOSTプロトコルを採用しているEthereumと似ている。
GHOSTDAGの順序付け
GHOSTDAGの各ブロックの最終的な順序付けは、カラーリングの手順と同様の経路に従う。最初にpast()のブロックに対して
の順序を継承し、次に
自体をその順序に追加し、最後にpast(
)にないブロックをトポロジカルな順序付けに従って追加することで、blockDAGを順序付けする。
マイニング報酬
マイニングの報酬については、k-クラスター内のすべてのブロックに報酬を与えるようになる。それがSelfish-Miningへの耐性となる。Selfish-Miningはブロックの１つをチェーンから外し、正直な参加者へ報酬を渡すのを拒否しようとする試みになるが、ブロックを隠し持つことで、そのブロックのanticoneは増えていくことになり、後からそのブロックをk-クラスター内に入れるためには、より多くの計算量が必要になる。
