Casper FFGはプロトコル内で機能するバリデーターをどのように扱うか? ~Dynamic Validator Setsの仕組み~

Ethereumは現行のPoWからPoW/PoSハイブリッド型、もしくはPoSへの以降を計画しています。EthereumのPoSシステムはCasperと呼ばれており、Casperは二種類あり、それぞれの開発者の名前を取ってVitalik’s Casper(Casper FFG= Friendly Finality Gadget), Vlad’s Casper(Casper CBC=Correct-by-Construction)と呼ばれています。Casper FFGがハイブリッド型で、Casper CBCがPoS型です。

バリデーターにはマイナーのように、ブロックを生成したり、ファイナリティを与える役割があります。Casper FFGではマイナーがPoWでブロックを生成し、バリデーターがPoSで特定のブロック高ごとに検証を行い、チェーンにファイナリティをもたらします。PoWによって生成されたブロックチェーンは確率的ファイナリティをもたらすに留まりますが、Casper FFGではPoSによってファイナリティがもたらされます。

この記事では、Casper FFGのペーパーを参考に「Casper FFGがバリデーターをどのように扱うのか」についてまとめたいと思います。

Casper FFGにおけるバリデーターの扱い

PoWにおけるマイナー同様に誰でもバリデーターになることができます(「Validator setに参加する」と表現します)。故にEthereumはPoSにおいてもPermissionless(ネットワークに参加するために誰かの許可を必要としない)です。しかし、ロングレンジアタックなどPoSにはPoW以上に影響を受けやすい攻撃が存在するため、Permissionless性を保ち、ネットワークの分散性を保つためには、PoWにはない仕組みをPoSに導入する必要があります。

その一つがDynastyと呼ばれるものです。

Dynastyは「王朝」や「支配的グループ」を意味する単語ですが、ここでの意味合いは全く異なります。私の理解力が充分でないからかもしれませんが、Ethereumの「響きはカッコイイけど分かりにくい用語」の多さが、ただでさえ難しいEthereumの理解を余計に難しくしている気がします(慣れたら分かりやすいケースもありますが)。

ペーパーでは、Dynastyは以下のように定義されています。

  • ブロックbのDynastyは、ルートからブロックbの親ブロックへと連なるチェーンにおけるファイナライズされたチェックポイントの数である
  • バリデーター志願者のメッセージがDynasty dを持つブロックに含まれたとき、バリデーターvはDynasty d+2においてバリデーターに加入する
  • このd+2のことをStart dynastyと呼び、DS(ν)と表記する

チェックポイントとは何でしょうか?PoWのマイナーによってブロックが生成されるわけですが、100ブロック毎に「チェックポイント」と呼ばれる”区切り”のようなもの設置され、それをチェックポイントと呼びます。チェックポイントはPoSのバリデーターによって検証されます。Casper FFGでは「バリデーターによってFinalizeされたチェックポイントは後に覆されることはない」という性質を持っており、これによりロングレンジアタックと呼ばれる過去のブロックを書き換えるような攻撃を防ぎます。またチェックポイントの設置と、そのFinalizationによって、ブロックチェーンにファイナリティをもたらすことができます。

Casper the Friendly Finality Gadget

上図は、チェックポイントツリーを表しています。ブロックチェーンの図に似ていますが少し違います。上の点線がチェックポイント間の100ブロックを表しており、長方形がチェックポイントを表しています。rはルートです。

Validator setから抜けるためには、バリデーターは”withdraw”メッセージを送る必要があります。

  • バリデータvのメッセージがDynasty dに含まれた場合、バリデーターはDynasty d+2においてValidator setから離脱することができる
  • このd+2をEnd dynastyと呼び、DE(ν)と表記する
  • もしWithdraw messageがまたブロックに含まれていない場合、DE(ν) = ∞となる
  • 一旦バリデーターvがValidator setから離脱した場合、そのバリデーターのパブリックキーは永遠にValidator setに再加入することができなくなる
  • これによって複数のStart/End dynastiesを一つの識別子で管理する必要がなくなる

End dynastyを開始するにあたって、バリデーターのポジットは一定期間ロックされます。これをWithdrawal delayと呼びます(期間は不明、ペーパーには”例えば4ヶ月に相当するブロック数”と書いてあります)。この期間中にバリデーターが何らかのルールを破った場合、デポジットに対するSlashが行われます。

Slashについては以下の記事をご覧下さい。

EthereumのPoS「Casper」の概要をまとめてみる

上述のDynastyを用いてバリデーターは以下のようにThe forward validatorとThe rear validatorの2つのグループに分けられます。

  • Vf(d) ≡ {ν : DS(ν) ≤ d < DE(ν)}
  • Vr(d) ≡ {ν : DS(ν) < d ≤ DE(ν)} .

Dynasty dを基点に、参加と離脱のタイミングによってバリデーターが2つに分けられていることが分かります。これら2つの式が表すValidator setsを実際に図示してみれば分かりますが、Vf(d)とVr(d+1)が一致することに注目して下さい。それぞれ1チェックポイント違いのValidator setを表しているというわけです。

チェーンが自身のDynastyを正確に把握するために、”Finalization”は以下のように再定義されます。ちなみにFinalizationの以前の定義は、「チェックポイントcがJustifyされ、チェックポイントツリーにおけるcからcの子へのバリーデーターの過半数の承認を伴う直接のリンクが存在する場合、チェックポイントはcはFinalizedされる」というものでした。

以下の図では、チェーンがr→b1→b2→b3という流れでJustifyされていく様子が示されています。

「Justify」は以下を意味します。

チェックポイントcは(1)それがルートであるとき、(2)c’→cのSupermajority link(※後述)が存在し、c’がJustifyされているとき、Justifyされているという。

Casper the Friendly Finality Gadget

rはルートなので、Justifyされており、r→b1のSupermajority linkがあるので、b1もJustifyされていることが見て取れます。b2, b3も同様です。

Finalizationの定義の話に戻ります。上述の定義に加えて以下の条件が付加されます。

  • 以前の条件に加え、cを再帰的にJustifyする全ての過半数を伴うリンクと共に、cからc’への過半数を伴うリンクに対する投票がc’の子の前にブロックチェーンに含まれている場合にのみ、cはFinalizeされる。c’の子の前とはつまり、ブロックナンバーh(c’)∗100のことである(100の倍数のブロック高がチェックポイントとして定義されている)。

Dynamic validator setsをサポートするために、Supermajority linkとFinalizationは以下のように再定義されます。

  • あるチェックポイントのペア(s, t)があり(sはtよりも古いチェックポイント)、tがDynasty dに含まれるとき、Dynasty dのThe forward validator setの2/3以上がsからtへのリンクに投票し、同様にDynasty dの2/3以上のThe rear validatorもsからtへのリンクに投票場合に、チェックポイントのペア(s, t)はSupermajority linkを持つ
  • 現状、チェックポイントcがJustifyされ、c→c’(c’はcの子)へのSupermajority linkがあるとき、cはFinalizeされたと言われる。今後以下の条件を加える。c→c’のSupermajority linkへの投票が、cをJustifyするSupermajority linkと共に、c’のブロックチェーンに含まれ、c’の子(つまりブロックナンバーh(c’)∗100)以前のブロックに含まれる場合のみ、cがFinalizeされたという

※デポジット合計の2/3であり、バリデーターの数の2/3ではありません。PoSの世界では1人1票ではなく1ETH1票です。

The forward validatorとThe rear validatorは通常大部分が同じバリデーターによって構成されますが、これら2つのValidator setsが大きく異なる場合、上述のメカニズムが機能します。例えばFinalizeされたチェックポイントの2つの孫が異なるDynastyを持っている場合、証拠が片方のチェーン上には記録されており、もう片方のチェーンには記録されていないため、「Safety failureが防がれる」わけです。

Casper the Friendly Finality Gadget

Safetyとは何でしょうか?ペーパーには以下の説明が載っています。

Accountable safetyは「1/3以上のバリデーターがSlashing conditionを侵さない限り、2つの矛盾するチェックポイントの両方はFinalizeされ得ないこと」を意味する。

Slashing conditionは(1)対立するチェックポイントが存在しない、(2)後で生成されたチェックポイントが、それ以前に生成されたチェックポイントの子よりも前に存在する子にリンクすることはできない(下図参照)というものです。

Casper the Friendly Finality Gadget

堅い説明になってしまったので、後で鳥瞰したあとに部分的に書き直すかもしれません。怪しい部分は、是非以下の原文でご確認下さい。


Casper the Friendly Finality Gadget

Ethereum Casper 101 – jon choi – Medium

Safety Under Dynamic Validator Sets – Vitalik Buterin – Medium