検証者のジレンマ：ビットコインフォーク6周年記念とブロックチェーンの信頼できる計算

作者: Truebit

编译: ChainCatcher

このシリーズ「検証済み」では、著者のRaghav Kulkarniと会い、彼はLoi Luu、Prateek Saxena、Jason Teutschと共同で執筆した「検証者のジレンマ」に関する論文の共著者です。この論文は、著者がシンガポール国立大学に在籍していた期間に書かれました。このインタビューは、2015年7月4日に発生したビットコインのフォークから6周年を記念するもので、その際にこの論文はCCSセキュリティ会議で審査を受けていました。この出来事では、約半数のビットコインマイナーがSPVマイニングを行っていました。マイナーはブロックを検証できませんでしたが、彼らは検証者のジレンマを十分に検証し、その結果、論文は科学会議に受け入れられました。このチームの発見により、TruebitはNakamotoコンセンサスの計算制限を解決する実用的なソリューションとして注目を集めました。

私はコンピュータサイエンティストであり、コンピュータサイエンスのさまざまな分野の問題を探求し、理解し、解決することが好きです。私はシカゴ大学を卒業し、博士号を取得しました。その後、LIAFA（パリ第七大学）というラボでポスドク研究を続けました。その後、パリで一緒に働いていた教授が引っ越し、彼がシンガポール国立大学のラボに私を招待したため、私はシンガポールの量子技術センターに移りました。この期間中、私は量子計算、機械学習、ブロックチェーン技術など、コンピュータサイエンスの新興分野の研究成果を学び、発表する機会がありました。ポスドクの仕事を終えた後、私はLinkedInの生産において私のいくつかのアルゴリズムと機械学習スキルを大規模に応用することができました。それ以来、私は最先端技術を使用して現実世界のソリューションを構築することに情熱を注いでいます。

私はシカゴ大学でジェイソンと出会いました。彼は論理と再帰理論の分野で最も賢く、知識が豊富な人の一人です。私たちはアルゴリズム、複雑性、組合せ論などのテーマについて何度も刺激的な議論を交わし、これが私たちの協力の基盤を築きました。その後、私が量子技術センターで働いているとき、ジェイソンはシンガポールを訪れており、そこでPrateek Saxenaと一緒に働いていました。彼は私にエキサイティングなブロックチェーン技術の分野を紹介し、私が研究しているブール関数の属性テストが彼のブロックチェーン研究における検証可能な計算と関連している可能性があることを考えました。その後、私たちはいくつかの興味深い例を導き出し、これがさらに興味深い問題やアイデアにつながりました。たとえば、この記事の第6節で見られる最初の問題やアイデアです。ジェイソンはこれらのアイデアを新しいレベルに引き上げ、私たちはPrateek SaxenaとLoi Luuとともに2つの刺激的な発見をしました。まず、ブロックチェーンは特定のタイプの攻撃に対して脆弱であること、次に、適切なインセンティブと構造によって、ブロックチェーンが強力な信頼できる計算源として使用される可能性があることです。興味深いことに、2015年7月にビットコインで発生した出来事は、私たちの理論を支持する証拠を提供しました------合理的なマイナーは不誠実に誘導され、ブロックの有効性を無視しました。この理論は現在「検証者のジレンマ」として知られています。

私はこのプロセスが好きです。なぜなら、その協力的な性質がコンピュータサイエンスの分野の異なる研究者の洞察を集めるからです。ジェイソンは、彼の分野での厳密さと誠実さに加えて、異なる分野からのアイデアを理解し、それらを結びつける努力に情熱を注いでいます。私は彼が仕事以外の生活を楽しむ方法を知っていると推測しており、必要なときに笑いで沈黙を打破する方法を最もよく理解していると思います。

前述のように、この記事のいくつかのアイデア（すべてではありません）は、非常に古典的な属性テストの設定といくつかの類似点があるようです。これは集中計算においても非常に意味があります。しかし、検証者のジレンマは「イーサリアム類似」のブロックチェーンのいくつかの独自の特性を解決します。これらのブロックチェーンの「スマートコントラクト」スクリプトは「チューリング完全」と呼ばれ、より強力な表現能力を持っています。したがって、検証者のジレンマは、複雑な計算を許可するイーサリアムブロックチェーンや、大規模なトランザクションセットを許可するビットコインブロックチェーンなど、これらのタイプのシステムに具体的な観察を行います。人々は、これらのアイデアがその抽象的な形式で、他の計算モデルの限界を理解するために適用できると主張することができます（たとえば、古典的および分散設定、さらには量子環境におけるランダムおよび近似アルゴリズムの背景における証明者検証者ゲーム計算モデル）。

大まかなアイデアは次のとおりです。「イーサリアム類似」のブロックチェーンは表現力のある「スマートコントラクト」を許可するため、特定の状況では合理的なマイナーが計算を検証せず、ブロックの検証をスキップすることで不誠実になるインセンティブを受けることがあります。この記事では、2つの可能な攻撃を特定しています：1）問題提供者のリソース枯渇攻撃と2）証明者の不正取引攻撃です。これらの攻撃はブロックチェーンのコンセンサスの完全性に影響を与え、私たちの焦点は、インセンティブメカニズムがこのような攻撃を許可する上でどのように機能するかを強調することです。私の興味は、ブロックチェーン上の属性テストと検証可能な計算との間の可能な関連を探求することから始まりました。特に、共通の計算モデルの力と限界を理解し、属性テスト文献からインスピレーションを得たアルゴリズムを提供することです。探求を始めたとき、私は、限られた信頼の下でロバストな計算を実現する方法、多者間ゲームにおけるインセンティブの互換性を理解すること、ブロックチェーン上のゼロ知識証明など、さらに多くの刺激的な分野と応用があることに気づきました。

イーサリアムスクリプトは非常に強力な表現力を持っているため、正当なマイナーのリソースを枯渇させる「サービス拒否（DoS）攻撃」と呼ばれる特定のタイプの攻撃に対して脆弱です。さらに、このような攻撃では、重い取引が最終的にブロックチェーンが追加の取引をサポートできなくなる原因となり、停止状態に陥る可能性があります。「ガス制限」の導入は、このリスクを軽減することを目的としています。一般的に言えば、これはブロックの作成者が高価な検証に対して代償を支払うことを意味します。目的は、DoS攻撃が攻撃者にとって高コストになるようにすることです。しかし、私たちが論文で議論したように、このメカニズムはDoS攻撃の問題を完全には解決していません。

潜在的な攻撃者は、他のマイナーのリソースを無料で枯渇させることができます。主な理由は、取引手数料------ガス------がブロック作成者によってのみ徴収されるからです。潜在的な攻撃者は、彼自身がその有効性をすでに知っている取引を自由に自分のブロックに追加できます。攻撃者は自分の取引を検証するために計算力を費やす必要はありませんが、正直なマイナーはそうする必要があります。イーサリアムは、次のブロックを最も早く検証した者に報酬を与えます。攻撃者は、未使用の計算リソースを利用して競争上の優位性を得ることができ、正直なマイナーとの競争に勝つことができます。検証者のジレンマにより、合理的なマイナーは重複ブロックを検証するかどうかを判断できません。未検証のブロックで満たされている場合、これはブロックチェーン全体の健康に影響を与える可能性があります。

2015年のビットコインの出来事の文脈において、約半数のネットワークが無効なブロック（BIP66に対して）上で検証なしにマイニングを行っていることがわかりました。無効なブロックを検証するための計算/時間コストのために、検証をスキップする可能性があります。以前から存在するインセンティブ構造のために、ステップをスキップし、不誠実な行動が無意識のうちに報われ、ブロックチェーンの健康が依然として危険にさらされています。

一般的に、私たちは、ブロック内の取引を検証するために必要な作業量を制限することによって、合理的なマイナーに正しく検証するようインセンティブを与えるモデルを提案します。これは、誠実な行動から逸脱してもあまり競争上の優位性をもたらさないことを意味します。この新しいフレームワークは、さまざまな方法で実現されます。私たちはこの記事の中でそのいくつかを説明しています：限られたカテゴリの問題に対する正確なコンセンサス、より広範な問題カテゴリに対する近似コンセンサスをサポートするものです。

コンセンサスコンピュータはフレームワークです。その実装には課題があり、これらの課題を克服するための技術があります。古典的なコンピュータとは異なり、コンセンサスコンピュータは分散処理を行います。これにより、信頼のない計算などの独自の能力（たとえば、私たちの2015年モデルにおける明らかな制限、すなわち簡単に検証できる問題しか正しく解決できない）と限界が与えられます。まだ発展途上のブロックチェーン技術は、何らかの形でコンセンサスコンピュータを実現する可能性があるように見えます。たとえば、Truebitはコンセンサスコンピュータに似ていますが、ホワイトペーパーで紹介された新しいかつスケーラブルな検証ゲームメカニズムの助けを借りて、ある程度それを超え、置き換えています。

2015年に私たちが使用し始めたコンセンサスコンピュータは、問題が「簡単に検証できる」解決策を持つことを要求しているようです。これは、いくつかの巧妙な数学的証明を必要とします。簡単な例として、2つの整数mとnのGCDを計算する問題を考えてみましょう。典型的な解決策の複雑性は、整数を表すのに必要なビット数の三乗です。しかし、解決策は、検証の複雑性がはるかに低い方法でエンコードできます。たとえば、私たちが証明者に5つの整数a、b、x、y、zを提供するよう要求し、(i) ay + bz = 1、(ii) xがaとbの両方で割り切れる、(iii) |y| < bおよび|z| < aを満たす場合、ベズーの定理を使用してxが実際にmとnの正しいGCDであることを検証できます。これは、わずか10回の算術演算を使用し、その複雑性はビット数の二乗に過ぎません。2015年のコンセンサスコンピュータは、これらの特別な数学的構造を利用して検証可能な問題を提起しました。

一方、Truebitはこれらの概念を新しいレベルに引き上げ、問題提供者は彼が提起する問題の数学的構造を明示的に心配する必要がありません。ほぼすべてのコードをTruebitタスクにコンパイルできます。したがって、このコンセンサスコンピュータの概念は進化し、Truebitはそれを取って代わる可能性があります。

検証可能な計算の考え方は、問題を外部に委託し、彼らの作業を検証した後に問題解決者に公正に報酬を与えることができることです。このような検証可能な計算をブロックチェーンなどの分散システムで実現するための1つの可能な方向は、正しいインセンティブ構造と計算制約を設計して、正しく実行されることを保証することです。たとえば、Truebitはこの方向に向けた有望な一歩であり、論文のアイデアを新しいレベルに引き上げ、その一部を具体的な方法で具体化しました。ブロックチェーン技術が現実世界で応用されることで、全く新しい可能性が開かれるかもしれません。

Truebitは確かにリーダーです。ある意味で、Truebitはシンプルな二分探索アルゴリズムに基づくスケーラブルな検証メカニズムを導入することで、検証者のジレンマを回避しようとしています。Truebitのインタラクティブな検証ゲームは、Solver（計算タスクの解決策を提供する者）とChallenger（その解決策に同意しない者）間の争いを効果的に解決します。Truebitのホワイトペーパーで説明されているように、この追加のメカニズムは、検証者のジレンマによって引き起こされるボトルネックを克服します。検証者のジレンマを成功裏に緩和することで、Truebitはブロックチェーン技術に対してより信頼性が高く、スケーラブルな機会を創出しました。