イーサリアムのアップグレード：コンセンサスの基礎知識（下）
TechFlow厳選深潮セレクト
イーサリアムのアップグレード：コンセンサスの基礎知識（下）
これは、イーサリアムのプルーフ・オブ・ステーク（PoS）プロトコルに関する権威ある技術書籍です。本書は、イーサリアムに限定されないコンセンサスの基礎知識から始めます。
Web3業界の深掘り報道に専念し潮流を洞察執筆：Ben Edgington
翻訳：tiao
本稿は『コンセンサスの基礎知識』章の後半部分である。前編については『イーサリアムをアップグレードする：コンセンサスの基礎知識』を参照のこと。
フォーク選択ルール
前述の通り、ネットワーク遅延、ネットワーク障害、メッセージ受信順序の不整合、ピアノードの悪意ある行動などさまざまな理由により、ネットワーク上のノードは最終的にネットワーク状態に対する異なるビュー（view）を持つことになる。最終的には、すべての正当なノードが歴史に対して一貫した線形ビューを持ち、システム状態について共通の理解に達することを望んでいる。この合意を得るために用いられるのがプロトコルのフォーク選択ルール（fork choice rule）である。
ブロックツリーと、ノードがネットワークをどのようにローカルに認識しているかに基づく意思決定基準が与えられたとき、フォーク選択ルールは利用可能なすべての分岐の中から、最も最終的な線形的な正規チェーンになる可能性が高い分岐を選ぶことを目的として設計されている。つまり、ノードが正規ビューに近づこうとする際、ブロックツリーから切り捨てられにくい分岐を選択するのである。
フォーク選択ルールは、分岐の先端にあるブロック（ヘッドブロックと呼ばれる）を選択することで、暗黙的にその分岐を選択する。
任意の正当なノードにとって、どのフォーク選択ルールにも共通する最初の要件がある。それは、選ばれたブロックが有効であり、プロトコルのルールに従っており、かつそのすべての祖先ブロックもまた有効でなければならないということだ。無効なブロックはすべて無視され、無効なブロック上に構築されたブロック自体も無効となる。
これを踏まえると、フォーク選択ルールには多くの異なる例が存在する。
-
イーサリアムおよびビットコインのプルーフ・オブ・ワーク（PoW）プロトコルでは、「最重量チェーンルール」[4]（時折「最長チェーン」とも呼ばれるが、正確ではない）を使用している。ヘッドブロックとは、PoWのもとで累積的な「作業量」が最大のチェーンの先端にあるブロックである。
-
イーサリアムのプルーフ・オブ・ステーク（PoS）Casper FFGプロトコルにおけるフォーク選択ルールは、「最高の正当化済みチェックポイントを含むチェーンに従う」ことであり、一度確定したブロックを決して巻き戻さない。
-
イーサリアムのプルーフ・オブ・ステーク LMD GHOSTプロトコルにおけるフォーク選択ルールは、その名称に示されているように、「最も貪欲で最も重い観測済みサブツリー（the Most Greedy Heaviest Observed SubTree）」を採用するものである。これは、バリデータが各ブロックおよびその子孫ブロックに対して投じた投票の累計を計算することを含む。また、Casper FFGと同じルールも適用される。
後述の二つについては、それぞれの章で詳しく説明する。
気づいたかもしれないが、これらのフォーク選択ルールはいずれも、各ブロックに数値的なスコアを割り当てる方法である。勝利するブロック――すなわちヘッドブロック――は最も高いスコアを持つ。背後にある考え方は、すべての正当なノードが最終的に特定のブロックを目にしたときに、それがヘッドブロックであることに疑問なく同意し、自分のネットワークビューに関係なくその分岐に従うことによって、すべてのノードが創世ブロックまで遡る単一の正規チェーンという共通のビューに到達することである。
リオーグ（Reorgs）およびロールバック（reversions）
ノードが新しいブロック（およびPoSの場合にはそのブロックに対する新たな投票）を受信すると、新情報をもとにフォーク選択ルールを再評価する。最も一般的なケースでは、新しいブロックは現在のヘッドブロックの子ブロックであり、そのままヘッドブロックとなる。
しかし、場合によっては、新しいブロックがブロックツリー内の他のどこかのブロックの子孫であることもある（ノードが新しいブロックの親ブロックを持っていない場合は、対等ノードに問い合わせて親ブロックを取得する必要がある。欠けている他のブロックについても同様であることに注意）。
どのような場合でも、更新されたブロックツリー上でフォーク選択ルールを再実行した結果、以前のヘッドブロックとは異なる分岐上のブロックが新たなヘッドブロックとされることがある。このような場合、ノードはリオーグ（reorg、reorganisationの略）またはロールバックを行う必要がある。これにより、これまでのチェーンに含まれていたブロックを削除（ロールバック）し、新たなヘッドブロックの分岐上のブロックを取り込む。
以下の図において、ノードはブロックFをヘッドブロックと評価しており、そのためそのチェーンはブロックA、B、D、E、Fから構成されている。ノードはブロックCを知っているが、それはノードのチェーンビューには含まれていない。ブロックCはサイドブランチ上にある。
しばらくして、ノードはブロックGを受信する。これは現在のヘッドブロックFの上ではなく、ブロックCの分岐の上に構築されている。フォーク選択ルールの詳細により、ノードは依然としてFをGよりも優れたヘッドブロックと評価し、Gを無視する可能性もある。しかし、ここではフォーク選択ルールがGこそがより良いヘッドブロックであると示していると仮定する。
ブロックD、E、FはブロックGの祖先ではないため、これらはノードの正規チェーンから削除されなければならない。これらのブロックに含まれるすべての取引や情報はロールバックされ、まるで一度も受信されていなかったかのように扱われる。ノードはブロックB処理後の状態まで完全に巻き戻さなければならない。
ブロックBまで巻き戻した後、ノードはブロックCおよびGをチェーンに追加し、適切に処理することができる。これが完了すれば、ノードはチェーンのリオーグを完了したことになる。
その後、ブロックFの上に構築されたブロックHが登場するかもしれない。もしフォーク選択ルールが新たなヘッドブロックとしてHを示唆するなら、ノードは再びリオーグを行い、ブロックBまでロールバックし、Hの分岐を再構築する。
PoWおよびイーサリアムのPoSプロトコルでは、ブロック伝播におけるネットワーク遅延のため、短時間の一〜二ブロックのリオーグは珍しくない。ただし、チェーンが攻撃を受けたり、フォーク選択ルールの設計やクライアント実装にバグがない限り、非常に長いリオーグは極めて稀である。
安全性と活性
コンセンサスメカニズムの議論において、よく取り上げられる重要な二つの概念がある：安全性（safety）と活性（liveness）である。
安全性
非公式に言えば、「悪いことが起こらない」[5] ならば、あるアルゴリズムは安全であるとされる。
ブロックチェーン環境で起こり得る「悪いこと」とは、例えば暗号資産の二重支払い（double-spend）や、互いに矛盾する二つのチェックポイントが確定してしまうことなどが挙げられる。
分散システムにおける安全性の重要な側面の一つは「一貫性（consistency）」である。つまり、特定の進捗時点（例えば特定のブロック高におけるアカウント残高など）でのチェーンの状態について、異なる（正直な）ノードに尋ねたとしても、常に同じ答えが返ってくるべきである。安全なシステムでは、すべてのノードがチェーンの履歴について変更不能な同一のビューを持っている。
実際上、安全性とは「分散システムが、一度に一つの原子的操作しか実行しない集中型インスタンスのように振る舞うこと」（Castro と Liskov の引用）を意味する。Vitalikの分類によれば、安全なシステムは論理的には集中型である。
活性
再び非公式に言えば、「最終的に何か良いことが起こる」ならば、あるアルゴリズムは活性を持つとされる。
ブロックチェーンの文脈では、通常これは「チェーンに常に新しいブロックを追加できる」ことを意味する。つまり、取引を含む新しいブロックを作成できなくなるような行き詰まりに陥ることはない。
「可用性（Availability）」もまた、この問題を考える別の視点である。私はチェーンが利用可能であってほしい。つまり、正直なノードに有効な取引を送った場合、それが最終的にチェーンを伸ばすブロックに含まれると期待したい。
両立は不可能！
CAP定理は分散システム理論における有名な成果であり、「一貫性（consistency）」「可用性（availability）」「パーティション耐性（partition tolerance）」の三つを同時に満たす分散システムは存在しないと述べている。パーティション耐性とは、ノード間の通信が信頼できない状況下でも正常に動作し続ける能力を指す。例えば、ネットワーク障害によりノードが二つ以上の相互に通信できないグループに分断される場合がある。
ブロックチェーンの文脈ではCAP定理を容易に証明できる。例えば、Amazon Web Services（AWS）がダウンし、AWS上でホストされているすべてのノードは互いに通信できるが、外部との通信ができなくなる場合。あるいは、ある国が内外へのすべての接続を遮断し、gossipトラフィックが一切通過できなくなる場合。どちらのケースも、ノードをAとBのような互いに独立したグループに分断する。
Aグループのネットワークに接続されたアカウントが取引を送信したとしよう。Aグループ内のノードがその取引を処理すれば、その最終的な状態は取引を見ることができなかったBグループのノードとは異なってしまう。つまり全体として、すべてのノード間の一貫性を失い、安全性を損なうことになる。これを避ける唯一の方法は、Aグループのノードが取引の処理を拒否することだが、その場合可用性および活性を失うことになる。
結局のところ、CAP定理は、我々がインターネットという信頼できないネットワーク上で動作せざるを得ない以上、あらゆる状況で安全かつ活性を持つコンセンサスプロトコルを設計することは不可能であることを意味している[6]。
イーサリアムは活性を優先する
ネットワーク状態が良好なときは、イーサリアムのコンセンサスプロトコルは安全性と活性の両方を提供できるが、ネットワーク状態が不安定な場合には活性を優先する。ネットワークのパーティショニングが発生した場合、双方のノードは引き続きブロックを生成し続ける。しかし、確定性（finality、安全性の一種）は双方で同時に発生しなくなる。双方が管理するステークの比率に応じて、片方だけが確定性を持ち続けるか、あるいは双方とも確定性を持たなくなる。
最終的には、パーティショニングが解消されない限り、双方は独自の怠惰ペナルティ（inactivity leak）メカニズムにより再び確定性を回復する。しかし、これは最終的に安全性の喪失につながる。それぞれのチェーンが異なる履歴を確定させ、二つのチェーンは永遠に調和不能かつ独立したものとなる。
確定性（Finality）
以下では、チェーンの安全性に関連する「確定性」について詳しく触れる。
確定性とは、あるブロックが決してロールバックされないことを意味する。ブロックが確定すると、ネットワーク上のすべての正直なノードが、そのブロックはチェーンの履歴に永久に残ることに同意する。したがって、そのすべての祖先ブロックもまた履歴に残る。確定性があれば、ピザの支払いは現金と同じように取り消せなくなる。これは二重支払いに対する究極の保護である[7]。
クラシックなPBFTやTendermintなどの一部のコンセンサスプロトコルでは、ラウンドごと（＝各ブロックごと）に確定性が得られる。一度トランザクションがチェーンに含まれれば、すべてのノードがそれが永久に存在することに同意する。一方で、こうしたプロトコルは非常に「安全」である：取引がチェーンに含まれたら、決してロールバックされることはない。他方で、活性障害に弱い：ノードが合意に達できない場合（たとえば、3分の1以上のノードが停止または利用不可になった場合）、新たな取引をチェーンに追加できず、チェーンは停止してしまう。
ビットコインの中本コンセンサスのような他のコンセンサスプロトコルでは、確定性メカニズムがそもそも存在しない。より重い代替チェーンが提示される可能性は常に残っている。その場合、すべての正直なノードはそれに応じてチェーンをリオーグし、これまで処理した取引をすべてロールバックしなければならない。「あなたのブロックがいくつの確認を持っているか」といったヒューリスティックな手法は、確定性の近似値にすぎず、保証はできない[8]。
イーサリアムのコンセンサス層は活性を優先しつつも、好条件のもとで安全保証を提供すべく、確定性を目指している。これは「両方の良いとこ取り」を試みるものである。Vitalikは次のように弁護している[9]：
一般的な原則として、「可能な限り多くの合意を与える」ことを目指すべきである。つまり、合意に達したノードが > 2/3 であれば、通常の合意が成立する。しかし、< 2/3 であっても、何もせず立ち止まる必要はない。明らかに、新区塊の安全性は一時的に低下するが、チェーンは引き続き成長することが可能である。個々のアプリケーションが低いセキュリティレベルに満足しない場合、それらが確定するまでそのブロックを無視すればよい。
イーサリアムのコンセンサス層では、確定性はCasper FFGメカニズムによって提供される。これについては後ほど詳述する。その仕組みは、すべての正直なバリデータが定期的に最新のチェックポイントブロックについて合意し、それらのブロックを決して取り消さないというものである。これにより、そのブロックおよびそのすべての祖先ブロックは「確定済み」となる――決して変わらず、ネットワーク中のいかなる正直なノードに尋ねても、常に同じ答えが返ってくる。
イーサリアムの確定性は「経済的確定性（economic finality）」である。理論的には、プロトコルが互いに矛盾する二つのチェックポイントを確定させる可能性はある。しかし、それは巨大かつ定量可能なコストを伴う場合にのみ発生しうる。極端な攻撃や障害状況を除けば、「確定」はまさに「最終的なもの」なのである。
Casper FFGの項では、この確定性メカニズムの動作原理をさらに深く掘り下げる。
参考文献
Leslie Lamportの関与する資料は常に読む価値がある。1982年にShostakおよびPeaseと共著したオリジナル論文『ビザンチン将軍問題（The Byzantine Generals Problem）』には多くの洞察が含まれている。今日の条件下では彼らの提案したアルゴリズムは極めて非効率的だが、一般のコンセンサスプロトコルを考察する上での優れた導入となっている。同様に、CastroとLiskovによる1999年の画期的論文『実用的ビザンチンフォールトトレランス（Practical Byzantine Fault Tolerance）』も、イーサリアムのCasper FFGプロトコルの設計に大きな影響を与えた。しかし、こうした「古典的」な手法を、中本聪が2008年のビットコイン白書で記述したプルーフ・オブ・ワークの洗練された簡潔さと比較してみたくなるだろう。プルーフ・オブ・ワークに長所があるとすれば、その簡潔さにある。
前述したGilbertとLynchによる2012年の論文『CAP定理の視座（Perspectives on the CAP Theorem）』も参照されたい。この論文は一貫性と可用性（あるいは私たちの文脈では安全性と活性）の概念について深く探求しており、読みやすく理解しやすい。
フォーク選択ルールのクライアント実装間に差異があったため、イーサリアムのビーコンチェーンは2022年5月に7ブロックのリオーグを経験した。これらの差異は当時すでに周知されており、無害と考えられていた。しかし、実際にはそうではなかった。Barnabé Monnotによるこの出来事の分析は非常に示唆に富んでいる。
Vitalikのブログ記事『決済の確定性について（On Settlement Finality）』は、確定性の概念についてさらに深く、細部にわたる考察を提供している。
私たちが構築しようとしているシステムの理想像は、政治的に非中央集権的（許可不要かつ検閲耐性を実現するため）、構造的に非中央集権的（単一障害点のない堅牢性を実現するため）、しかし論理的には中央集権的（一貫した結果を実現するため）であることである。これらの基準は、コンセンサスプロトコルの設計方法に大きな影響を与える。Vitalikは『非中央集権の意味（The Meaning of Decentralization）』の中でこれらの問題を考察している。
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
@LXDAO_Official
