This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Circle STARKs:効率的なZKプルーフへの新しいアプローチを探る
サークルスタークを探索する
近年、STARKsプロトコルの設計はより小さなフィールドの使用に向かっています。最初期のSTARKs実装は256ビットフィールドを使用しており、楕円曲線に基づく署名と互換性があります。しかし、この設計は効率が低く、大きな数を処理する際に計算力を浪費します。この問題を解決するために、STARKsはより小さなフィールドの使用に向かい始めました: まずGoldilocks、次にMersenne31とBabyBearです。
この変化は、証明速度を向上させました。例えば、StarkwareはM3ノートパソコンで毎秒620,000のPoseidon2ハッシュ値を証明できます。私たちがPoseidon2をハッシュ関数として信頼する限り、高効率のZK-EVMの開発の課題を解決することができます。それでは、これらの技術はどのように機能するのでしょうか？これらの証明はどのように小さなフィールド上に構築されるのでしょうか？この記事では、これらの詳細、特にCircle STARKsソリューションに焦点を当てて探ります。
! 【ヴィタリック新作:サークルスタークの探索】(https://img-cdn.gateio.im/webp-social/moments-7aa9220380d346efa2a3619b0f4e3372.webp)
小さい数学フィールドを使用する際の一般的な問題
ハッシュベースの証明を作成する際の重要なテクニックは、多項式のランダムな点での評価結果を証明することによって、多項式の性質を間接的に検証することです。これにより、証明プロセスが大幅に簡素化されます。
例えば、ポリノミアルAのコミットメントを生成する必要があると仮定すると、A^3(x) + x - A(ωx) = x^Nを満たさなければなりません。プロトコルはランダムな座標rを選択し、A(r) + r - A(ωr) = r^Nを証明することを要求することができます。その後、A(r) = cを逆推し、Q = (A - c)/(X - r)が多項式であることを証明します。
攻撃を防ぐためには、攻撃者がAを提供した後にrを選択する必要があります。楕円曲線に基づくプロトコルでは、ランダムな256ビット数を選択できます。しかし、小さなフィールドのSTARKsでは、約20億のr値しか選択できず、攻撃者は総当たりで解読する可能性があります。
解決策は2つあります:
何度もランダムチェックが簡単で効果的ですが、効率の問題があります。拡張体は複素数に似ていますが、有限体に基づいています。新しい値αを導入し、α^2=ある値と宣言します。これにより、有限体上でより複雑な計算が可能になります。拡張体はFRIプロトコルなどのシーンでのみ使用されており、ほとんどの数学的演算は依然として基本フィールドで行われます。
! ヴィタリックの新作:サークルスタークの探索
一般的なFRI
SNARKまたはSTARKを構築する際、最初のステップは算術化であり、計算問題を多項式方程式に変換します。解があることを証明するためには、提案された値が合理的な多項式であり、最大次数を持つことを証明する必要があります。そのために、段階的に適用されるランダム線形結合のテクニックを使用します:
本質的に、Bは偶数次数を隔離し、Cは奇数次数を隔離します。BとCが与えられれば、Aを復元できます。もしAの次数が<2^20であれば、BとCの次数はそれぞれAの次数とAの次数-1です。Dはランダムな線形結合として、次数はAの次数であるべきです。
FRIは、dの次数の多項式を証明する問題をd/2の次数の問題に簡略化することで、検証プロセスを簡素化します。このプロセスは何度も繰り返すことができ、毎回問題が半分に簡略化されます。
ドメインの段階的な削減を実現するために、二対一のマッピングを使用します。このマッピングにより、データセットのサイズを半分に削減でき、再現可能です。乗法部分群から始めて、集合Sに平方操作を施すと、新しい集合S^2は同じ属性を保持します。これにより、データセットのサイズを継続的に減少させ、最終的に1つの値だけが残ることを可能にします。
BabyBearモジュラスは、その最大乗法部分群がすべての非ゼロ値を含むようにし、部分群のサイズは2k-1です。2^kサイズの部分群を選択し、次にFRIメソッドを適用して多項式の次数を15まで段階的に減少させます。Mersenne31モジュラスは乗法部分群のサイズを2^31-1にし、2で1回のみ割り切れ、その後は上記の技術を使用できません。
Mersenne31域は32ビットCPU/GPUの計算に適しています。そのモジュラス特性により、多くの計算が効率的なビット操作で完了できます。Mersenne31域では、算術演算がBabyBear域より約1.3倍速くなります。Mersenne31域でFRIを実現できれば、計算効率が大幅に向上します。
! [ヴィタリックの新作:サークルスタークを探索する])https://img-cdn.gateio.im/webp-social/moments-b32679a50fc463cfc1c831d30ab2d7e2.webp(
サークルFRI
Circle STARKsの巧妙さは、素数pが与えられたときに、二対一の特性を持つ大きさpの群を見つけることができる点です。この群は、x^2 mod pが特定の値に等しい点の集合など、特定の条件を満たす点で構成されています。
これらの点は加法の法則に従います: )x1,y1( + )x2,y2( = )x1x2 - y1y2, x1y2 + x2y1(
倍の形式は: 2 * )x,y( = )2x^2 - 1, 2xy(
私たちは円の奇数位置にある点に焦点を当てています。まず、すべての点を1本の直線に収束させます: f0)x( = )F(x,y( + F)x,- y()月2日
その後、ランダムな線形結合を行い、一次元多項式P)x(を得る。
第二ラウンドから、マッピングは次のように変わります: f0)2x^2-1( = )F(x( + F)-x()/2
このマッピングは、毎回集合のサイズを半分に減らします。各xは2つの点を表します: )x,y(と)x,-y(。)x → 2x^2 - 1(は点倍増法則です。
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-cb343bb0791734002ef1a3b813eea1e2.webp(
サークルFFT
Circle グループは、FRI と同様の方法で構築される FFT もサポートしています。 円FFTの対象はリーマン・ロッホ空間である:多項式モジュラー円)x^2 + y^2 - 1 = 0(。
サークル FFT 出力の係数は特定の基数です: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
開発者はこの点をほとんど無視できます。STARKsは多項式を評価値セットとして保存するだけです。FFTは低次元拡張に使用されます：N個の値が与えられた場合、k*N個の同じ多項式上の値を生成します。
! 【ヴィタリック新作:サークルスタークの探索】)https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(
商演算
STARKプロトコルでは、特定の点に対して商演算を行うことが一般的な操作です。例えば、証明P)x(=y:
circle group STARKでは、単一の線形関数が存在しないため、従来の商算方法の代わりに異なる技術を使用する必要があります。2点で評価することによって、注目する必要のない虚擬点を追加することを証明します。
もし多項式Pがx1でy1に等しく、x2でy2に等しいなら、補間関数Lを選択してx1でy1に等しく、x2でy2に等しくします: L = )(y2 - y1(/)x2 - x1() * )x - x1(+Y1
そして、P - Lがこの2点でゼロであることを証明し、LをLで割ることによって商Qが多項式であることを証明します。
! 【ヴィタリックの新作:サークルスタークの探索】)https://img-cdn.gateio.im/webp-social/moments-0277731a7327da529c85417a01718c59.webp(
消える多項式
STARKでは、多項式方程式は通常C)P(x(のような形をしています。 P)next(x()) = Z)x( · H)x(、評価領域全体で Z)x( は 0 です。
円形STARKにおいて、対応する関数は: Z1)x,y( = y Z2)x,y( = x Zn+1)x,y( = )2 * Zn(x,y(^2) - 1
消失多項式は折りたたみ関数から導出できます: 通常のSTARKはx → x^2を繰り返し使用し、円形STARKはx → 2x^2 - 1を繰り返し使用します。
逆順
STARKsでは、多項式評価が通常逆ビット順で配置されます。例えばn=16の場合: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
この並べ替えにより、FRI評価プロセスの初期グループの値が隣接して並び、スペースを節約します。
circle STARKsでは、折り畳み構造がわずかに異なります。この構造を反映するために逆順を調整するには、最後のビットを除くすべてのビットを反転させ、最後のビットによって他のビットを反転させるかどうかを決定します。
サイズ16の折りたたみ逆順序: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-13da9460855ee8c504c44696efc2164c.webp(
効率性
Circle STARKsは非常に効率的です。計算には通常次のものが含まれます:
効率の鍵は計算トラッキングスペースを十分に活用することにあります。Circle STARKsフィールドのサイズは2^31で、無駄なスペースが少ないです。
BiniusはCircle STARKsよりも優れており、異なるサイズのフィールドを混合することを可能にし、より効率的なビットパッキングを実現します。しかし、その代償として概念はより複雑であり、Circle STARKsの概念は相対的に単純です。
まとめ
Circle STARKsは開発者にとってSTARKsよりも複雑ではありません。Circle FRIとCircle FFTsを理解することは、他の特殊FFTsを理解するための道筋となります。
Mersenne31、BabyBear、Biniusなどの技術を組み合わせることで、私たちはSTARKsの基盤層の効率限界に近づいています。今後のSTARKの最適化方向には、以下が含まれる可能性があります:
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-972d4e51e7d92462c519ef900358a6af.webp(