STARK：多項式証明
TechFlow厳選深潮セレクト
STARK：多項式証明
この新しいゼロ知識証明は、一体どのように機能するのでしょうか？
Web3業界の深掘り報道に専念し潮流を洞察ZK-SNARKSという、検証可能な計算からプライバシー保護を必要とする暗号通貨まで、さまざまなシナリオに応用できる汎用的で簡潔なゼロ知識証明技術を聞いたことがある人は多いでしょう。しかし、おそらくまだ知らないかもしれませんが、今やZK-SNARKsには新しい兄弟が登場しています：それがZK-STARKsです。「T」は「transparent（透明な）」を意味し、ZK-STARKsはZK-SNARKsの主要な欠点である「信頼できるセットアップ（trusted setup）」への依存を解決します。またZK-STARKsは、より単純な暗号学的仮定に基づき、楕円曲線やペアリング、指数知識仮定（knowledge-of-exponent assumption）を使わず、完全にハッシュと情報理論のみに依拠しています。つまり、量子コンピュータを持つ攻撃者に対しても安全であることを意味します。
もちろん、これには代償があります。証明サイズが288バイト（b）から数百キロバイト（kb）へと増加するのです。ある用途ではこのコストが見合わない場合もありますが、特に高い信頼最小化を求めるブロックチェーンアプリケーションでは価値があるかもしれません。そして、楕円曲線が破られたり、量子コンピュータが実現した場合には、必然的にその価値は非常に高くなるでしょう。
では、この新しいゼロ知識証明は一体どのように機能するのでしょうか？その前にまず、簡潔かつ汎用的なゼロ知識証明が何を行うのかを振り返ってみましょう。ここに（公開の）関数f、（秘密の）入力x、および（公開の）入力yがあるとします。xの内容を明かさずに、f(x) = y となるようなxが存在することを証明したいのです（訳注：たとえば金庫があり、そのパスワード自体を明かさずに、あなたが正しいパスワードを知っていることを証明するようなものです）。さらに、この証明はある程度簡潔であってほしい。つまり、f自体を計算するよりも、はるかに高速に検証できる方法で確認できなければなりません。
いくつかの具体例を見てみましょう：
-
fは通常のコンピュータで2週間かかる一方、データセンターなら2時間で完了する計算です。あなたは計算タスク（つまりfのコード）をデータセンターに送り、データセンターが計算を実行して結果yを返します。数ミリ秒で検証でき、yが真の答えであると確信できます。
-
「X1は私の古い残高、X2はあなたの古い残高、X3は私の新しい残高、X4はあなたの新しい残高」という形式の暗号化された取引があるとします。この取引が有効であることを証明したい（具体的には、古い残高と新しい残高が非負であり、私の残高の減少分がちょうどあなたの残高の増加分と一致することを証明）。xは鍵のペア、fは取引の公開入力を組み込み、鍵を受け取り取引を復号・チェックを行い、成功すれば1を、失敗すれば0を返す関数とします。yは当然1になります。
-
イーサリアムのようなブロックチェーンがあり、最新のブロックをダウンロードしたとします。このブロックが有効であり、チェーンの最新ブロックであること、かつチェーン内のすべてのブロックが有効であることを証明したい。既知のフルノードにそのような証明を提供するよう依頼します。xは全（あるいは一部の）ブロックチェーン、fは各ブロックを処理して有効性を検証し、前のブロックのハッシュを出力する関数、yはあなたがダウンロードしたブロックのハッシュです。
さて、これらのすべてのケースにおいて、困難なのはどこでしょうか？実は、
ゼロ知識（つまりプライバシー）の保証は（比較的！）与えやすいのです。任意の計算を三色グラフ問題に変換する方法は複数あり、そのグラフの彩色が元の問題の解に対応します。その後、伝統的なゼロ知識プロトコルを使って、実際に解を明かすことなく、有効な彩色を持っていることを証明できます。Matthew Greenによる2014年の素晴らしい記事がその詳細を説明しています。
より難しいのは簡潔性です。直感的には、計算に関する事柄を簡潔に証明するのは極めて困難です。なぜなら、計算は非常に壊れやすいからです。非常に長く複雑な計算があり、途中で任意の1ビットを0から1に変更できると仮定しましょう。多くの場合、たった1ビットを変えるだけで、計算結果がまったく異なるものになってしまいます。そのため、計算の軌跡をランダムにサンプリングして正しさを判定しようとしても、「悪意のある1ビット（one evil bit）」を見逃してしまう可能性が非常に高いのです。しかし、巧妙な数学的手法により、これは実は可能であることが示されています。
一般的な高次元の直感としては、エラスリャ編集で使われる数学に似ており、これはデータに耐障害性を持たせるためによく使われます。あるデータがあり、それを直線として符号化し、その線上から4点を選択するとします。この4点のうち任意の2点があれば、直線を再構築でき、他の2点も得られます。さらに、データにごく微小な変更を加えても、少なくとも3つの点は保証されます。これを応用して、データを1,000,000次多項式として符号化し、その上に2,000,000個の点を選ぶことができます。任意の1,000,001点があれば元のデータを復元でき、他の点も得られます。元のデータのわずかな逸脱でも、少なくとも1,000,000点が変化します。ここで紹介するアルゴリズムは、この種の多項式を活用して誤差を拡大することに大きく依存しています。
簡単な例
Pという多項式があり、xが1から100万の範囲にあるすべての整数に対して、P(x)が整数かつ0 <= P(x) <= 9であることを証明したいとします。これは「範囲チェック」の非常に基本的な例です。このようなチェックは、たとえば取引実行後の口座残高が依然として正であることを検証するのに使えます。もし1 <= P(x) <= 9であれば、それは正しい数独の解答の一部を検証していると考えることもできます。
この問題を「従来の」方法で証明するには、1,000,000個の点すべてを1つずつ検証する必要があります。しかし、1,000,000ステップ未満で検証できる証明を構築できるかを知りたいと思います。Pをランダムに評価して検証するだけでは不十分です。悪意ある証明者が、999,999箇所では条件を満たすが最後の1箇所で満たさないようなPを作ることが常に可能であり、少数の値しかサンプリングしない限り、その不正な値を見逃すでしょう。では、どうすればよいでしょうか？
まず、この問題を数学的に変換してみましょう。
C(x) を制約チェック多項式（constraint checking polynomial）とし、0 <= x <= 9 のとき C(x) = 0、そうでなければ非ゼロとします。C(x) を作る簡単な方法は次の通りです：x * (x-1) * (x-2) * ... * (x-9)。
今や問題はこうなります：1から1,000,000までのすべてのxについて、C(P(x)) = 0 となるようなPを知っていることを証明せよ。Z(x) = (x-1) * (x-2) * ... (x-1000000) と定義します。数学的に知られている事実として、1から1,000,000までのすべてのxでゼロになる多項式は、必ずZ(x)の倍数です。したがって、問題は再び次のように変換できます：すべてのxについて、C(P(x)) = Z(x) * D(x) を満たすPとDを知っていることを証明せよ（注意：適切なC(P(x))がわかれば、Z(x)で割ってD(x)を計算するのはそれほど難しくありません。多項式の筆算除法、あるいは高速フーリエ変換に基づくより実用的で高速なアルゴリズムを使います）。これで、元の命題を数学的により明確で証明しやすい問題に変換できました。
では、どうやって証明するのでしょうか？証明プロセスを、証明者と検証者の3段階のやり取りとして想像できます：
- 証明者が情報を送信する
- 検証者がクエリを送信する
- 証明者が追加情報を送信する
まず、証明者はxが1から10億（そう、10億）までの範囲におけるP(x)とD(x)の値を提出します（Merkle木を生成し、そのルートハッシュを検証者に送信します）。これは100万の正当な点（0 <= P(x) <= 9）と、9.99億の（おそらく）異常な点を含みます。
検証者はすべての点でのZ(x)の値をすでに知っていると仮定します。このスキームでは、Z(x)は公開検証鍵のようなものであり、誰もが事前に知っていなければなりません（クライアントはZ(x)全体を保存するスペースがないため、代わりにMerkleルートだけを保存し、検証者が照会する各Z(x)の値については証明者が同時に枝を提供する必要があります。または、特定のxに対してZ(x)を簡単に計算できるようにしておくことも可能です）。提出（Merkleルート）を受け取った後、検証者は1から10億の間でランダムに16個のxの値を選択し、その点でのP(x)とD(x)のMerkle枝を要求します。証明者はそれらを提供し、検証者は以下の点を確認します：
-
枝が以前に提供されたMerkleルートと一致していること
-
16回すべての場合においてC(P(x)) = Z(x) * D(x)が成り立つこと
この証明が完全性を満たしていることはわかります。つまり、本当に適切なP(x)を知っており、D(x)を正しく計算して証明を構築すれば、16回のチェックはすべて成功します。しかし健全性はどうでしょうか？
つまり、悪意ある証明者が不正なP(x)を提出した場合、それが発見される最低確率はどれくらいでしょうか？次のように分析できます。C(P(x))は1,000,000次多項式なので、その次数は最大で10,000,000です。
一般に、異なるN次多項式は高々N個の点でしか交わらないことが知られています。したがって、1,000,000次多項式と、常にZ(x) * D(x)に等しい任意の多項式が異なる場合、それらは少なくとも990,000,000点で異なります。したがって、1回のチェックでも不正なp(x)が発見される確率は99%であり、16回のチェックでは1 - 10^-32まで上昇します。つまり、このスキームはハッシュ衝突を見つけるのと同じくらい騙しがたいのです。
ここまで我々が分析してきたのは何でしょうか？多項式を使って「悪い」解に含まれる誤差を「増幅」したのです。つまり、百万回の直接チェックを必要とする元の問題を、たった1回のチェックで99%の確率で誤りを検出できる検証プロトコルに変換したということです。
この3段階の仕組みを、Fiat-Shamirヒューリスティックを利用して、非対話型の証明に変換できます。証明者がそれを放送し、誰もが検証できるようになります。証明者はまずP(x)とD(x)の値のMerkle木を構築し、ルートハッシュを計算します。ルート自体がエントロピー源となり、証明者がどの枝を提供するかを決定します。証明者はその後、Merkle木のルートと枝を証明として一斉に放送します。すべての計算は証明者側で行われます。データからMerkleルートを計算し、それを用いて監査する枝を選択することで、対話型検証者の必要性を効果的に排除しています。
有効なP(x)を持たない悪意ある証明者ができることは、最終的に幸運にも選ばれたMerkleルートの枝が通るまで、ひたすら有効な証明を構築し続けることです。しかし、健全性が1 - 10^-32（つまり、与えられた偽の証明が検査を通過できない確率が少なくとも1-10^-32）であるため、悪意ある証明者は数十億年かけても通る証明を見つけられない可能性があります。
さらに深く
この技術の強力さを示すために、少し変わったことをしてみましょう：あなたが第100万フィボナッチ数を知っていることを証明します。そのためには、計算帯を表す多項式P(x)を知っていることを証明します。ここでP(x)はx番目のフィボナッチ数を表します。制約チェック多項式は今度は3つのx座標にまたがります：C(x1, x2, x3) = x3 - x2 - x1（注意：すべてのxについて、P(x)がフィボナッチ列を表すならば、C(P(x), P(x+1), P(x+2)) = 0 となります）。
-フィボナッチ-
変換後の問題は次のようになります：C(P(x), P(x+1), P(x+2)) = Z(x) * D(x) となるPとDを知っていることを検証する。16回の証明検査のそれぞれについて、証明者はP(x)、P(x+1)、P(x+2)、D(x)のMerkle枝を提供する必要があります。さらに、P(0) = P(1) = 1であることを示すためのMerkle枝も提供しなければなりません。それ以外は同じプロセスです。
ただし、これを実際に実装するには2つの問題を解決する必要があります。第一に、普通の数字でこのスキームを実際に行うと、非常に非効率になります。なぜなら数字自体が極めて大きくなりやすいからです。例えば、第100万フィボナッチ数は208,988桁あります。実際の簡潔性を達成するには、普通の数字ではなく、有限体（finite field）上で多項式を計算する必要があります。有限体とは、a * (b+c) = (a*b) + (a*c) や (a^2 - b^2) = (a-b) * (a+b) といった通常の数学的規則に従いながら、各数字が一定サイズの空間しか使わない数体系です。第100万フィボナッチ数を証明するには、この有限体の数学の上で巨大数の算術を実装する、より複雑な設計が必要になります。
最も単純で可能性が高い有限体はモジュラー数学です。つまり、ある素数Nに対して、すべてのa + bを a + b mod N で置き換えます。減算と乗算にも同様の操作を適用し、除算にはモジュラー逆数を使います（例えばn = 7の場合、3 + 4 = 0、2 + 6 = 1、3 * 4 = 5、4 / 2 = 2、5 / 2 = 6）。このような数体系について詳しくは、私が素数体について紹介している「ここ」（ページ内で「prime field」を検索）をご覧ください。あるいは、「有限体（finite fields）」と「素数体（prime fields）」をウィキペディアで調べてみてください（抽象代数に関連して非常に複雑に見えるかもしれませんが、そこは気にしないでください）。
第二に、上記の健全性証明の概要で、私はある攻撃を無視していたことに気づいたかもしれません。つまり、100万次のP(x)と900万次のD(x)ではなく、低次の多項式に由来しない他の値を提出する攻撃です。このような不正なC(P(x))は、有効なC(P(x))と少なくとも990万点で異なるため、さらなる攻撃が可能かもしれません。たとえば、攻撃者は各xに対してランダムな値pを生成し、d = C(p) / Z(x) を計算し、P(x)とD(x)の代わりにこれらを提出できます。これらはいかなる低次多項式にも基づいていませんが、テストを通過する可能性があります。
実際には、使うツールはかなり複雑ですが、このような可能性は効果的に防げます。そして、これこそがSTARKの数学的革新の空白を埋めていると言えます。ただし、この解決策には制限があります：100万次多項式から大きく離れたデータ（例えば、すべての値の20%を変更しないと100万次多項式にならないようなもの）は除外できますが、ほんの一、二の座標しか異なるない多項式データまでは除外できません。したがって、これらのツールは近接性の証明（proof of proximity）— PとDの大部分の点がそのような多項式に関連していること — を提供します。
したがって、2つの「落とし穴（catches）」があるものの、証明を構築することは依然として十分可能です。まず、検証者はその制限によって導入される誤差の余地を見越して、さらに多くのチェックを行う必要があります。第二に、もし「境界制約チェック（boundary constraint checking）」（例えば上記のフィボナッチ例でのP(0) = P(1) = 1の証明）を行っている場合、近接性の証明を拡張して、単に大部分の点が同じ多項式上にあるだけでなく、特定の2点（またはチェックしたい任意の点）がその多項式上にあることも証明する必要があります。
このシリーズの次回では、近接性チェック問題の解決策についてさらに詳しく解説します。
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
@VitalikButerin
