Casper FFG コンセンサス アルゴリズムについて詳しく説明する
原作者：ソウルマシン; この記事のサポートビデオ:https://v.qq.com/x/page/f07704nx4iq.html
最初のレベルのタイトル
Casper FFG アルゴリズム フロー
画像の説明
PoWプロセス
上の写真の黄色のマイナーは、突然計算量を増やして悪さをし始めました。古いブロックから開始して、新しいチェーンが分岐し、その上で採掘を続けました。長さが左を超えると、新しいチェーンは壊れます。」古いチェーンを正常に置き換えることができた場合、以前の古いブロックは取り消され、内部のすべてのトランザクションが上書きされて書き換えられます。
現在の PoW に基づいて、Casper FFG は PoS 投票プロセスのレイヤーを追加し、ファイナリティをさらに強化し、古いブロックを取り消すことは理論的に不可能です。 Casper FFG は非侵襲的なアルゴリズムです。現在のイーサリアム PoW アルゴリズムは変更しませんが、PoW のこの層に BFT スタイルの PoS を追加します。つまり、すべてのブロックは PoW マイナーによって掘り出されます。このコアのプロセスは保存されています。これに基づいて、100 ブロックがマイニングされるたびに、PoS 検証ノードは最後のブロックに投票し、2/3 が経過した後の最後のブロックはチェックポイント (チェックポイント) と呼ばれます。確定されたチェックポイントは元に戻すことができません。要約すると、PoW ブロック生成のメカニズムは維持され、同時に PoS は 100 ブロックごとに投票するため、イーサリアムのセキュリティ (安全性、またはファイナリティ) がさらに強化されます。
投票メッセージのフィールドは次のとおりです。
上の表に示すように、各投票メッセージには 5 つのフィールドが含まれており、s はソース チェックポイントのブロック ハッシュを表し、t はターゲット チェックポイントのブロック ハッシュを表し、h(s) は s のブロックの高さを表し、h( t) はt のブロック高さ、S は署名を表します。これら 5 つのフィールドのうち、実際にコアとなるのは 3 つだけ、つまり h(s)、t、h(t) です。
Casper FFG の投票メッセージは、2 つのステップを 1 つのステップに巧みに組み合わせており、本質的には、pBFT と Tendermint の 2 段階の投票 (事前準備 -> 準備、事前投票 -> 事前コミット) と同等です。
以下の図は、投票に 2 つの段階が必要な理由を説明しています。
同時に、Casper FFG の投票メッセージは、Tendermint のロック メカニズムと同様の効果をもたらします。
以下は、Casper FFG アルゴリズムでよく見られるいくつかの用語の定義です。
ワンピースsupermajority linka→b と書かれている場合、投票メッセージの 2/3 以上がチェックポイント a から始まりチェックポイント b を指している場合、a と b の間に超過半数のリンクがあることを意味します。超多数リンクは複数のチェックポイントにまたがることができます。つまり、h(b)>h(a)+1 は正当です。
2つのチェックポイントaとbが相互に対立これは、a と b が異なるブランチ上にある、つまり、a と b が同じパス上にないことを意味します。
チェックポイント c は、justifiedチェックポイントは、(1) ジェネシス ブロックである、(2) チェックポイントを指す超多数のリンクがある、のいずれかの条件を満たす必要があります。
チェックポイント c は、finalizedチェックポイント、正当化する必要があり、そこから発生する超多数リンクがあります。c→c'、c' はそのチェックポイントです。直系の子つまり、c' の高さは c の高さに 1 を加えたものになります。
たとえば、次の図に示すように:
最初のレベルのタイトル
ペナルティ条件 (SlashCondition)
バリデーターが以下の 2 つの条件のいずれかに違反した場合、罰せられ、すべてのデポジットは没収されます。
1. No double vote: t1==t2。同じ高さにある 2 つの異なるブロックに投票することはできません。これは比較的理解しやすいですが、同じ高さで 2 つの異なるブロックに投票することは、Nothingat ステークの典型的な投機的行動であり、罰せられます。
2. No surround vote.t2 < t1 < s1 < s2 。たとえば、バリデーターは最初に s1 -> t1 と投票し、数ブロック後に s2 -> t2 と投票を続けます。ブロックの高さは時間の経過とともに増加するため、s2> e1 であることは明らかであり、2 番目の場合はt2< t1,これは前回の投票のターゲット ブロックよりも低く、問題があります。なぜなら、以前に s1 -> t1 に投票したからです。つまり、s1 と t1 の間のすべてのブロックが正しいと認識されたことになりますが、2 番目の投票 s2 -> t2、間隔が s1->t1 より小さく、s1->t1 で完全にカバーされている場合、この投票は、前の投票を忘れたかのように、s2 と t2 の間のブロックに繰り返し同意します。このような忘れ行為も罰せられます。
以下の図は、Nodouble 投票違反の例を示しています。
PoW マイニング中、フォークが同じ高さで発生するのは通常のことです。現時点では、4 つの検証ノードのうち、両方のフォークに同時に投票した悪意のあるノードが 2 つあり、これにより 2 つの新しいブロックが正当化されます。この場合、2 つの悪意のあるノードは罰せられ、デポジットが課されます。は破壊され、通報者には報奨金（発見料）が与えられます。
以下の図は、サラウンド投票禁止の違反の例を示しています。
ある時点で、A->B および A->C という 2 つの超多数リンクが存在するため、A が確定され、B と C は両方とも正当化されたブロックになります。この場合、検証ノードの 1/3 以上が B と C に同時に投票したことを意味します。これは合法であり、二重投票禁止ルールやサラウンド投票禁止ルールに違反しません。
最初のレベルのタイトル
安全性と妥当な生存性の証明
このセクションでは、Casper FFG の安全性 (ファイナリティ) と生存性を証明します。
まず第一に、Casper FFG は安全性と妥当な生存性を説明責任があると主張しています。説明責任があるとは、バリデーター ノードが相当額のデポジットを支払う必要があることを意味します。デポジットにより、初期の信頼があり、信頼できる (説明責任がある) ことができます。
もっともらしい生存性は実際には新しいものではなく、ビットコインの生存性とまったく同じです。ネットワークが分割 (分割) されても、システム全体が引き続き新しいトランザクションを書き込み、ブロックを生成できることを意味します。
詳細な証明は以下から始まります。
責任ある安全性: 2 つの矛盾するチェックポイント (チェックポイント)、am と bn をファイナライズできません (ファイナライズ済み)
証明する：反証の方法を使用して、am と bn が互いに競合し (つまり、同じブランチ上ではなく 2 つのブランチ上で)、ファイナライズが完了し、それぞれが正当化されたサブブロック am+1 を持っていると仮定します。そしてbn+1。
高さ m と n が等しい場合、両方のチェックポイントに同時に投票する検証ノードの 1/3 が存在する必要があります。これらのノードは二重投票禁止のルールに違反し、すべてのデポジットは破棄され、1/3 が失われます。検証ノード、am および bn をファイナライズできません。
高さ m と n が等しくない場合は、n > m(n< m は同じプロセスを証明します)、genesis ブロックから bn へのパスは、genesis→b1→b2→...→bi→bj→...→bn、bi は高さ以下の最初のブロックです。 am、つまり i≤m、bj は高さが am+1 以上である最初のブロック、つまり j≥m+1 です。以下は次のことを証明します。
i==m の場合、検証ノードの 1/3 が二重投票禁止ルールに違反して罰せられ、am と bn を確定することができなくなります。
j==m+1 の場合は上記と同じ。
もし私が
結論から言えば、amとbnはどんな状況でも確定することは不可能であり、証明は完了です。
妥当な生存性: バリデーター ノードの 2/3 以上が開始点として正当化されたブロックを使用して投票する限り、常に新しい最終化されたブロックを生成できます。
簡単に言うと、位置揃えされたブロックを開始点として取り、それより上の任意のノードに投票できます。たとえば、2 つの新しいブロックがあり、1 つは高さ m にあり、1 つは高さ n にあります (開始点を含む) 、3 つのブロックが一直線上にある必要があります)、ダブル投票禁止およびサラウンド投票禁止ルールに違反することなく、2 つのブロックのいずれか、あるいは両方に投票できます。つまり、複数のブロックをスキップして、より高いブロックを直接キャストできます。次に位置合わせされたブロックは、am または bn、あるいはその両方である可能性があります (両方とも 2/3 以上の票を獲得します。この時点で、ノードの 1/3 以上が両方に投票している必要があります)。これが、この理由がもっともらしいと呼ばれる理由です。
ネットワークが分割された場合でも、PoW は両側でブロックを生成し続けることができますが、現時点では片側の半分が通信できないため、Validators ノードはどのチェックポイントでも 2/3 の投票に達することができません。最終的には成長し続けます。ネットワークが 2 つの半分に分割されても、まだ動作することができます (ネットワークが分割されている場合、Tendermint は無期限に待機することしかできません)。この種の堅牢な稼働性も、もっともらしいの別の意味かもしれません。
Casper FFG は、Plasible liveness から推定できます。ForkChoice ルール: 最も高い位置にある正当なチェックポイントの上にある最長のチェーンを常に選択します。つまり、最初に最も高い位置にあるブロックを見つけ、次にこのブロックから開始して最も長いチェーンを選択します。 PoW アルゴリズムでの最長チェーンの単純な選択と比較して、前提条件が 1 つあります。
たとえば、次のようになります。
上図では、確定した上位から順に、2つの正当なチェックポイントを指す超多数のリンクが2つありますが、このとき、海底光ケーブルが断線するなど、ある瞬間にネットワークが分断され、グローバルネットワークが2つに分断されました。二。現時点では、両側の PoW は通常どおりブロックを生成し続けますが、各チェックポイントが投票すると、新しいチェックポイントに 100% 同意したとしても、バリデーター ノードには半分しか投票がないため、最大でも半分の投票しか受け取ることができません。 、2/3を超えることはできません。したがって、ネットワークが分割された後も、PoW はチェーンを拡大し続けますが、すべての新しいブロックを確定して正当化することはできません。
最初のレベルのタイトル
バリデーターの動的セット
最初のレベルのタイトル
スタック攻撃では何もありません
純粋な PoS ブロックと投票にはコンピューティング能力は必要なく、コストもかかりません (PoW では、短いチェーンでマイニングすると、掘っても報酬が得られず、コンピューティング能力が無駄になり、コストがかかります) ) なので、ブロックチェーンがフォークするとき、バリデーターノードはどのブランチが正しいのかわかりません。報酬を得るために、最善の戦略は各ブランチに投票することです。この種の行為を罰するために、PoS では通常、投票前に検証ノードにデポジットの支払いを要求しており、各支店で誰かが投機していることが判明するとデポジットは没収されます。
最初のレベルのタイトル
遠距離攻撃
遠距離攻撃とは、次の 3 つの状況を指します。
純粋なPoSの場合、純粋なPoSではブロックを生成するコストがかからないため、実際のチェーンよりも長いフォークチェーンを作成することが簡単です。
PoW の場合、悪意のあるノードが 51% 以上の計算能力を持っていると仮定すると、実際のチェーンよりも長いフォークされたチェーンを作成することもできます。 PoW ブロックの生成にはコストがかかるため、このような状況は比較的まれですが、このような大きな計算能力がある場合は、正直にマイニングしてより多くの報酬を得る方が良いでしょう。ただし、悪意のあるノードが利益を求めてずっと前に巨額のトランザクションを行っていた場合、悪意のあるノードは再フォークしてお金を二重に使う動機も持ちます。遠距離攻撃。
3 番目のケースは、PoS と PoW に当てはまります。新しいフル ノードがオンラインになったばかりの場合、ブロックの同期を開始するためにたまたま複数の悪意のあるノードに接続されます。チェーンはまだ長いです。この時点では、たとえ正規のフル ノードがオンラインであったとしても、後で接続すると、完全なノードによって送信されたチェーンは短くなり、新しいノードによって拒否されます。それは恥ずかしいですね。
1番目と3番目の場合も問題は本質的に同じですが、より長いチェーンを受信した場合、それが真であるか偽であるかをどのように判断するのでしょうか。この投稿のヴィタリックProof of Stake: How I Learned toLove Weak Subjectivity 解決策を説明すると、やはり外の世界からの知識と信頼、いわゆる弱い主観を少し導入する必要がありますが、この種の弱い信頼は簡単に達成できると神は信じているので、安全性が弱まるわけではありません。ブロックチェーン。新しいノードがオンラインになると、外部から次の情報を取得して信頼する必要があります。
1. プロトコルの定義 これは扱いが簡単で、ブロックチェーンのプロトコルはコード内に存在します。新しいノードがどのバージョンのコードを実行するかは、そのコードがデフォルトで信頼されることを意味します。
2. 最新の有効なブロック。このブロックは古すぎることはできません。最後の N 以内にある必要があります。 N は、十分に新しいものである限り、事前に定義できます。たとえば、ビットコインの場合、最後の 6 ブロック内のすべてのブロックが十分に新しいとみなされます。イーサリアムの場合、最後の 12 ブロックは比較的新しいと考えられます。
2 については問題が大きく、新しいフルノードがオンラインになった場合、最新の有効なブロックはどこで入手できるのでしょうか?ここでは追加の信頼に関する知識を導入する必要があります。たとえば、CasperFFG の場合、新しいノードがオンラインになるときは、デポジットを支払った完全なノードのみを信頼する必要があり、最新の最終ブロックを取得するには複数のノードに接続するのが最善です。最新の確定ブロックを取得できれば、安心して同期を開始できますが、悪意のあるノードからより長いチェーンを受信した場合でも、悪意のあるノードのブロックのハッシュ値は同じ高さで異なるはずなので、同期を開始することができます。偽物のチェーンに違いないと判断した場合は、このチェーンを捨ててください。
要約すると、長距離攻撃に対処するには、そのような攻撃を防ぐために外部の世界からの少しの知識に頼る必要があります。
最初のレベルのタイトル
大規模墜落事故（壊滅的墜落事故）の事例
検証ノードの 1/3 以上が同時にクラッシュした場合、ネットワークに問題が発生してオフラインになった場合、またはネットワークが分断された場合、この投票で 2/3 以上の票を集めることができません。つまり、これからは、新しいスーパーマジョリティリンクを作成できなくなります。つまり、新しいブロックを確定できなくなります。
この論文では、と呼ばれる方法が紹介されています。 Inactivity leak 秘訣は、2 つのサブネットワークを独立して動作させ、独立して投票を続け、新しいブロックを完成させることです。
要約する
要約する
Casper FFG アルゴリズムは、2 つのペナルティ条件 (スラッシュ条件)、フォーク選択ルール (フォーク選択ルール)、および検証ノードの動的セットの 3 つの部分で構成されます。 Casper FFG はあらゆる PoW アルゴリズムに適用でき、PoW アルゴリズムのセキュリティを向上させます。
Casper FFGのブロック生成メカニズムはPoW（PoWベースのブロック提案メカニズム）ですが、将来的にはブロック生成メカニズムは純粋なPoSであるPoSに置き換えられる予定です。
ネットワーク通信の複雑さについては、PoW 段階では O(n)、BFT 投票段階では O(n2) です。一般に資本閾値の関係で検証ノードの数はネットワーク全体のノードに比べて少ないため、O(n2)であってもnが小さいため通信量は比較的少なくなります。
最大耐障害性に関しては、PoW 段階では悪意のあるノードの計算能力が 50% 未満まで許容され、BFT 投票段階では悪意のあるノードが必要とする資金量は 1/3 未満です。簡単かつ大まかにまとめると、最大耐障害性は 1/3 と考えられます。
ネットワーク仮定に関しては、PoW 段階では同期、BFT 投票段階では非同期ですが、一般にネットワーク仮定は同期です。
Finality に関しては、PoW 段階では Probabilistic ですが、BFT 投票後に Deterministic となり、一般的に Deterministic となります。
参考文献
参考文献
Casper the Friendly Finality Gadget
EthereumPoS: Casper FFG In Depth - YouTube
Ethereum PoS Overview: Casper FFG
Casper FFG with one message type,and simpler fork choice rule
Ethereum Casper 101
A Simplified Look at Ethereum’sCasper
Consensus Compare: Casper vs.Tendermint - Medium
Proof of Stake: How I Learned toLove Weak Subjectivity
