ヴィタリックの新作はサークルスタークを探る

原題："Exploring circle STARKs" Written by Vitalik Buterin, Co-Founder, Ethereum Compiled by Chris, Techub News

この記事を理解するための前提は、SNARKとSTARKの基本をすでに理解しているということです。

この記事を理解するための前提は、SNARKとSTARKの基本をすでに理解していることです。

近年、STARKsのプロトコル設計のトレンドは、より小さなフィールドに向かっています。STARKs の初期の製品実装では 256 ビットのフィールドを使用していました。.95617)を使用し、楕円曲線ベースの署名と互換性を持たせていた。しかし、この設計は比較的非効率であり、一般的に、このような大きな数の計算を処理する実用的な用途はなく、例えば、（ある数を表す）Xを処理するのと、Xを4倍にするのとでは、計算時間が9分の1にしかならないなど、多くの演算が無駄になります。

このシフトにより、次のような証明のスピードが向上した。Starkwareは、M3のラップトップで1秒間に620,000個のPoseidon2ハッシュを証明することができました。つまり、ハッシュ関数としてPoseidon2を信頼する気になれば、効率的な ZK-EVM の開発における課題を解決できるということだ。では、これらのテクニックはどのように機能するのだろうか？これらの証明はどのように小さなフィールドの上に構築されるのだろうか？これらのプロトコルはBiniusのようなソリューションと比較してどうなのか？この論文では、特に Circle STARKsと呼ばれるスキーム( Starkwareのstwo、Polygonの plonky3 、そしてPythonで実装された私自身のバージョン)に焦点を当てて、これらの詳細を探求する。これはMersenne31フィールドと互換性のあるユニークなプロパティを持ちます。

より小さな数学的場を使用する際によくある問題

ハッシュベースの証明（またはあらゆる種類の証明）を作成する際に非常に重要なトリックは、ランダムな点で多項式の結果を評価することによって多項式を証明することです。多項式の特性を間接的に検証することができる。ランダムな点での評価は通常、多項式全体を扱うよりもはるかに簡単であるため、このアプローチは証明プロセスを大幅に簡略化することができます。

例えば、ある証明システムが、A^3 (x) + x - A (\omega*x) = x^N (ZK-SNARKプロトコルで非常に一般的なタイプの証明)を満たさなければならない多項式Aへのコミットメントを生成するよう求めているとします。プロトコルはランダムな座標? そしてA (r) = cを反転することで、Q = Γ {A - c}{X - r}が多項式であることを証明する。

プロトコルの詳細や内部メカニズムを事前に知っていれば、それを迂回したり破ったりする方法を見つけられるかもしれません。そのための具体的な操作や方法は、次に挙げることができるだろう。例えば、A(Γ*r)の方程式を満たすには、A(r)を0とし、Aを両点を通る直線とすればよい。

このような攻撃を防ぐには、攻撃者がAを与えた後にrを選択する必要があります（Fiat-Shamir は、特定のパラメータを特定のハッシュ値に設定することで攻撃を回避するプロトコルのセキュリティを強化するために使用される技術です）。選択されるパラメータは、攻撃者が予測したり推測したりできないように、十分に大きなセットから選択する必要があります。

楕円曲線ベースのプロトコルや2019年代のSTARKでは、問題は単純です。数学的演算はすべて256ビット数で実行されるため、rを256ビット乱数として選択すれば問題ありません。つまり、証明を改ざんしようとする攻撃者は、20億回試行すればよいのです！

この問題には2つの解決策があります:

• 複数のランダムチェックを実行する

• フィールドを拡張する

複数のランダムチェックを実行する方法は、最も単純で効率的です：1つの座標でチェックする代わりに、4つのランダムな座標でチェックを繰り返します。これは理論的にはうまくいくが、効率性に問題がある。ある値より小さい次数の多項式を扱い、ある程度の大きさの領域で操作している場合、攻撃者は実際に、これらのすべての位置で正常に見える悪意のある多項式を構築することができます。その結果、攻撃者がプロトコルを破れるかどうかは確率的な問題であり、全体的な安全性を高め、攻撃者から効果的に防御できるようにするためには、チェックのラウンド数を増やす必要があります。

このことから、もう一つの解決策である拡張ドメインが導かれます。拡張ドメインは複素数に似ていますが、有限ドメインに基づいています。例えば、α2=some value αα^2 = \text {some value}α2=some valueである。このようにして、有限体上でより複雑な演算を実行できる新しい数学的構造を作り出す。この拡張領域では、乗算の計算は新しい値ααを使った乗算になる。拡張領域では、個々の数値だけでなく、値のペアを操作できるようになった。例えば、MersenneやBabyBearのようなフィールドを扱う場合、このような拡張を行うことで、より幅広い値を選択できるようになり、セキュリティが向上する。フィールドのサイズをさらに大きくするには、同じ技法を何度も繰り返し適用すればよい。すでにααを使ったので、新しい値を定義する必要がある。ααはMersenne31で α2=some value αα^2 = \text {some value}α2=some valueとなるように選択する。align:center">

コード（ Karatsuba で改良できます）

ドメインを拡張することで、セキュリティのニーズを満たすのに十分すぎるほどの値から選択できるようになりました。ddd未満の次数の多項式を扱う場合、1ラウンドあたり104ビットのセキュリティを提供できます。これは十分なセキュリティがあることを意味する。より高いレベル、例えば128ビットのセキュリティが必要な場合は、プロトコルに余分な計算を追加してセキュリティを強化することができる。

拡張ドメインは、FRI（Fast Reed-Solomon Interactive）プロトコルや、ランダムな線形結合を必要とする他のシナリオでのみ実用的に使用されます。数学的演算のほとんどは、通常pppまたはqqqのモジュラスのフィールドである基本フィールド上で実行されます。同時に、ハッシュのほとんどすべてがベースフィールド上で行われるため、各値の4バイトだけがハッシュされる必要がある。これは小さなフィールドの効率を利用する一方で、セキュリティの強化が必要な場合にはより大きなフィールドを利用できるようにするものである。

通常のFRI

SNARKやSTARKを構築する際の最初のステップは、通常算術化です。これは任意の計算問題を、ある変数と係数が多項式である方程式に変換することです。具体的には、この方程式は通常P (X,Y,Z) = 0P (X,Y,Z) = 0P (X,Y,Z) = 0のようになります。ここでPは多項式で、X,Y,Zは与えられたパラメータであり、ソルバーはXとYの値を提供する必要があります。このような方程式が利用可能になると、その方程式の解は基礎となる計算問題の解に対応する。

解があることを証明するには、提案している値が確かに妥当な多項式（分数や、ある場所では1つの多項式のように見えて別の場所では異なる多項式などとは異なる）であり、これらの多項式がある最大次数を持つことを示す必要があります。

• 多項式Aを評価し、その次数が 2^{20}

  未満であることを証明したいとします。

• 多項式B (x^2) = A (x) + A (-x)とC (x^2) = \frac {A (x) - A (-x)}{x}

• DはBとCのランダムな線形結合である。Cのランダムな線形結合、すなわち、D = B + rCD = B + rCD = B + rCであり、rはランダムな係数である。

基本的に、何が起こるかというと、Bが偶数係数Aを分離し、?は奇数の係数を分離します。BとCが与えられれば、元の多項式Aを復元できる：A (x) = B (x^2) + xC (x^2)。もしAの次数が本当に2^{20}より小さければ、BとCの次数はそれぞれAの次数とAの次数から1を引いたものになる。DはBとCのランダムな線形結合なので、Dの次数もAの次数になるはずです。これにより、Dの次数を通してAの次数が条件を満たしていることを検証できます。

まず、FRIは、多項式が次数dを持つことを証明する問題を、多項式が次数 d/2を持つことを証明する問題に還元することで、検証プロセスを単純化する。このプロセスは何度も繰り返すことができ、そのたびに問題は半分に単純化される。

FRI sはこの単純化プロセスを繰り返すことで動作します。例えば、多項式の次数がdであることを証明することから始めると、一連のステップを経て、多項式の次数がd/2であることを証明することになります。ある段階での出力が多項式の次数として期待されるものでない場合、チェックは失敗します。もし誰かが次数dでない多項式をこの手法で押し込もうとすれば、2ラウンド目の出力でその次数が予想と一致しない確率があり、3ラウンド目でも一致しない可能性が高くなり、最終チェックは失敗する。この設計は、不適合な入力を検出して拒否するのに有効である。データセットがほとんどの位置で次数dの多項式に等しい場合、このデータセットはFRI検証に合格する可能性が高い。しかし、そのようなデータセットを構築するためには、攻撃者は実際の多項式を知る必要があるので、少し欠陥のある証明であっても、証明者が「真の」証明を生成できることを示している。

ここで何が起こっているのか、そしてこれをすべて機能させるために必要な性質をより詳しく見てみよう。各ステップで、多項式の数を半分にし、点集合（見ている点の集合）も半分にする。前者はFRI（Fast Reed-Solomon Interactive）プロトコルを機能させるための鍵である。各ラウンドのサイズが前のものと比べて半分になるので、総計算コストはO (N*log (N))ではなくO (N)になります。

領域の段階的縮小を達成するために、2対1の写像が用いられ、各点は2点のうちの1点に写像される。このマッピングにより、データセットのサイズを半分にすることができる。この2対1のマッピングの重要な利点は、繰り返し可能であることである。つまり、このマッピングを適用しても、得られる結果集合は同じ性質を保っている。乗法的な部分群から始めるとしよう。この部分群は集合Sであり、すべての要素xはその倍数2xも集合内に持つ。集合Sを2乗する（つまり、集合の各要素xをx^2にマップする）と、新しい集合S^2は同じ性質を保持する。この操作によって，最終的に1つの値しか残らなくなるまで，データセットのサイズを縮小し続けることができる．理論的にはデータ集合を1つの値だけに減らすことができるが、実際にはより小さな集合に達する前に止めるのが一般的である。