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:小さなフィールドでの効率的なゼロ知識証明
サークルスタークを探索する
近年、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ビットのフィールドでは簡単です：ランダムな256ビットの数字を選べばいいのです。しかし、小さなフィールドでは、選択できるrの値は約20億種類しかありません。攻撃者は膨大な作業量を要しますが、それでもすべての可能性を試みることができるかもしれません。
解決策は二つあります:
何度もチェックするのは簡単で効果的ですが、効率の問題があります。拡張フィールドは複数に似ていますが、有限体に基づいています。特定の関係を満たす新しい値αを導入し、例えばα^2=ある値となります。これにより、新しい数学的構造が作成され、有限体上でより複雑な演算を行うことができます。拡張体はランダムな線形結合が必要な場合にのみ使用され、大部分の演算は依然として基礎フィールドで行われます。
! ヴィタリックの新作:サークルスタークの探索
一般的なFRI
SNARKまたはSTARKを構築する第一歩は、計算問題を多項式方程式P(X,Y,Z)=0に変換することです。解決策は、提案された値が合理的な多項式であり、かつ次数が有限であることを証明する必要があります。これは、ランダムな線形結合を段階的に適用することで実現されます。
BはAの偶数係数を隔離し、Cは奇数係数を隔離します。BとCが与えられた場合、Aを復元できます:A)x( = B)x^2( + xC)x^2(。もしAの次数が<2^20であれば、BとCの次数はそれぞれAの次数とAの次数-1になります。Dはランダムな組み合わせとして、次数はAの次数である必要があります。
FRIは、dの多項式の度数をd/2の度数の証明に簡略化することで検証を簡素化します。このプロセスは何度も繰り返すことができ、毎回問題は半分に簡略化されます。ある段階で出力が期待される度数と一致しない場合、そのラウンドのチェックは失敗します。
FRIは各ステップで多項式の次数と点集合の規模を半分にします。前者はFRIの動作の鍵であり、後者はアルゴリズムを非常に高速に実行します：総計算コストはO)N(であり、O)N*log(N()ではありません。
ドメインを段階的に削減するために、二対一マッピングを使用します。このマッピングはデータセットのサイズを半分にすることを可能にし、繰り返し可能です。乗法部分群から始めて、各要素xの倍数2xも集合に含まれます。集合Sを二乗すると、新しい集合S^2は同じ属性を保持します。これにより、データセットのサイズを継続的に削減して、最終的に一つの値だけが残ります。
BabyBearのモジュラスは、その最大乗法部分群がすべての非ゼロ値を含むようになっており、サイズは2^k-1です。これは上記の技術に非常に適しており、繰り返しマッピングによって多項式の次数を効果的に減少させることができます。Mersenne31の乗法部分群のサイズは2^31-1で、2で一度だけ割ることができ、その後はこの技術を使用することができません。
Mersenne31域は32ビットCPU/GPU計算に非常に適しています。そのモジュラス特性)は2^31-1(のように、多くの計算が効率的なビット操作を利用できることを意味します: モジュラスを超える結果はシフトによって減少させることができます。乗算は特定のCPU命令を使用して効率的に処理できます。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は二つの点を表します: )x,y(と)x,-y(。)x → 2x^2 - 1(は点倍増法則です。私たちは円上の二つの対称点のx座標を、倍増後の点のx座標に変換します。
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-cb343bb0791734002ef1a3b813eea1e2.webp(
サークルFFT
CircleグループもFFTをサポートしており、構造方法はFRIに似ています。主な違いは、Circle FFTが厳密な多項式ではなく、Riemann-Roch空間を処理することです：多項式mod円)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を証明するには、次のステップが必要です:
1.電卓:Q = )P-y(/)X-x( 2. Qが多項式であり分数でないことを証明する
circle group STARKにおいて、単点の線形関数を通さないため、異なる技術が必要です。接線関数を構築することはできますが、それは点において重数2を持っています。したがって、証明するために2点で評価する必要があります。
もしPがx1でy1に等しく、x2でy2に等しい場合、私たちはこの2点で等しい補間関数Lを選択します。そして、P-Lがこの2点でゼロであることを証明し、LでLを割ることで商Qが多項式であることを証明します。
消える多項式
STARKが証明しようとする多項式方程式は通常、C)P(x(の形をしており、P)next(x()) = Z)x( · H)x(であり、Z)x(は元の評価域上で常にゼロに等しい。
円形STARKにおいて、対応する関数は: Z1)x,y( = y Z2)x,y( = x Zn+1)x,y( = )2 * Zn(x,y(^2) - 1
! 【ヴィタリックの新作:サークルスタークの探索】)https://img-cdn.gateio.im/webp-social/moments-0277731a7327da529c85417a01718c59.webp(
逆順
STARKsにおける多項式評価は通常、逆ビット順で配置されます。circle STARKsでは、折りたたみ構造が若干異なります:
逆順を調整するには、最後の1桁を除くすべての桁を反転させ、最後の桁で他の桁を反転させるかどうかを決定する必要があります。
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-13da9460855ee8c504c44696efc2164c.webp(
効率性
Circle STARKsは非常に効率的です。計算は通常、次のようなものを含みます:
効率の鍵は計算トラッキングスペースを十分に活用することです。ここでのフィールドサイズは2^31で、無駄なスペースはあまりありません。Poseidonなどのハッシュは、どのフィールドにおいても各数字のすべてのビットを十分に活用しています。
Biniusは異なるサイズのフィールドを混合することによってより効率的なビットパッキングを実現しますが、その代償として概念はより複雑になります。Circle STARKsは概念的に比較的シンプルです。
まとめ
Circle STARKsは開発者にとってSTARKsと比べて複雑ではありません。実装において通常のFRIとの主な違いは、上述の3つの問題にあります。背後にある数学は複雑ですが、その複雑さはうまく隠されています。
サークルの FRI と FFT を理解することで、バイナリ ドメイン FFT や楕円曲線 FFT など、他の特殊な FFT を理解することができます。
Mersenne31、BabyBear、Biniusなどの技術を組み合わせることで、私たちはSTARKs基盤の効率限界に近づいています。今後の最適化は次の点に集中する可能性があります:
! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-972d4e51e7d92462c519ef900358a6af.webp(