サークルスタークを探索する

近年、STARKsプロトコル設計のトレンドは、より小さなフィールドの使用に移行しています。初期のSTARKsの実装では256ビットフィールド、つまり大きな数に対する剰余演算を使用していました。しかし、この設計は効率が低く、大きな数を処理する際に多くの計算力を浪費してしまいます。この問題を解決するために、STARKsはより小さなフィールドの使用を開始しました。最初はGoldilocks、次にMersenne31とBabyBearです。

この変化は、証明速度を大幅に向上させました。例えば、Starkwareは現在、M3ノートパソコンで毎秒620,000個のPoseidon2ハッシュを証明できます。これは、Poseidon2をハッシュ関数として信頼すれば、高効率のZK-EVM開発の課題を解決できることを意味します。では、これらの技術はどのように機能するのでしょうか？小さなフィールドでの証明はどのように構築されるのでしょうか？この記事では、特にMersenne31フィールドと互換性のあるCircle STARKsというソリューションに焦点を当てて、これらの詳細を探ります。

! 【ヴィタリック新作:サークルスタークの探索】(https://img-cdn.gateio.im/webp-social/moments-7aa9220380d346efa2a3619b0f4e3372.webp)

小フィールド使用時の一般的な問題

ハッシュベースの証明を作成する際の重要なテクニックは、多項式の性質を間接的に検証するために、多項式をランダムな点で評価することです。これにより、証明プロセスが大幅に簡素化される可能性があります。

例えば、プロトコルが多項式Aのコミットメントを生成することを要求する場合、A^3(x) + x - A(ωx) = x^Nを満たす必要があります。プロトコルはランダムな座標rを選択し、A(r)^3 + r - A(ωr) = r^Nを証明することを要求することができます。次に、A(r) = cを逆算し、Q = (A - c)/(X - r)が多項式であることを証明します。

攻撃を防ぐために、攻撃者がAを提供した後にrを選択する必要があります。楕円曲線に基づくプロトコルでは、これは簡単です：rとしてランダムな256ビットの数字を選ぶことができます。しかし、小さなフィールドのSTARKsでは、約20億のrしか選択できず、攻撃者は総当たりで解読する可能性があります。

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

1. 複数回のランダムチェックを実施する
2. 拡張フィールド

複数回のランダムチェックは簡単で効果的ですが、効率の問題が存在する可能性があります。拡張体は複素数に似ていますが、有限体に基づいています。新しい値αを導入し、α^2=ある値と宣言します。これにより、新しい数学的構造が作成され、有限体上でより複雑な計算を行うことが可能になります。

拡張領域を通じて、安全要件を満たすために選択できる十分な値が得られました。ほとんどの数学演算は基本フィールドで行われ、セキュリティを強化する必要がある場合にのみ、より大きなフィールドが使用されます。

! ヴィタリックの新作:サークルスタークの探索

レギュラー FRI

FRI (ファストリード・ソロモンインタラクティブ)プロトコルは、SNARKまたはSTARKを構築するための重要なステップです。それは、証明多項式の次数がdである問題を、証明の次数がd/2である問題に簡素化することによって、検証プロセスを簡素化します。このプロセスは何度も繰り返すことができ、毎回問題を半分に簡素化します。

FRIの動作原理は、繰り返し簡略化プロセスです。多項式の次数がdであることを証明することから始まり、一連のステップを経て、最終的に次数がd/2であることを証明します。各簡略化の後、生成された多項式の次数は徐々に減少します。ある段階での出力が期待通りでない場合、そのラウンドの検証は失敗します。

ドメインの段階的な削減を実現するために、二対一のマッピングが使用されました。このマッピングは、データセットのサイズを半分に減らすことを可能にし、同時に同じ属性を保持します。この操作は、円周上の線分を円周に沿って二周伸ばすプロセスとして想像できます。

マッピング技術を効果的にするためには、元の乗法部分群のサイズが大きな2の冪を因子として持つ必要があります。BabyBearのモジュラスは、その最大乗法部分群がすべての非ゼロ値を含んでおり、この技術に非常に適しています。Mersenne31の乗法部分群のサイズは、2の冪因子が1つだけであり、その応用範囲を制限しています。

Mersenne31フィールドは、32ビットCPU/GPU上での算術演算に非常に適しており、BabyBearフィールドより約1.3倍速いです。Mersenne31フィールドでFRIを実現できれば、計算効率が大幅に向上します。

! ヴィタリックの新作:サークルスタークを探索する

サークルFRI

Circle STARKsの巧妙さは、質数pが与えられると、pのサイズを持つグループを見つけることができ、類似の二対一特性を持つことです。このグループは、x^2 mod pが特定の値に等しい点の集合など、特定の条件を満たす点で構成されています。

これらの点は加法の法則に従います:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) 二重形式は 2 * (x, y) = (2x^2 - 1, 2xy) です

Circle FRIはまずすべての点を1本の直線に収束させ、その後ランダムな線形結合を行って1次元多項式P(x)を得ます。第2ラウンドから、マッピングは次のようになります:f0(2x^2-1) = (F(x) + F(-x))/2

このマッピングは、毎回集合のサイズを半分にし、円上の2つの対称点のx座標を倍増後の点のx座標に変換します。これは2次元空間で行うこともできますが、1次元操作の方が効率的です。

! ヴィタリックの新作:サークルスタークの探索

サークルFFT

CircleグループはFFTもサポートしており、構造方法はFRIに似ています。Circle FFTが処理する対象はRiemann-Roch空間であり、厳密な多項式ではありません。Circle FFTの出力係数はCircle FFTの基礎に特有のものです。

開発者として、あなたはほぼ完全にこれを無視することができます。STARKsは多項式を評価値の集合として保存するだけです。FFTが必要なのは、低次の拡張を行う場合だけです：N個の値が与えられたとき、同じ多項式上のk*N個の値を生成します。

! 【ヴィタリック新作:サークルスタークの探索】(https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp)

クォティエンティング

Circle STARKsでは、単一の線形関数を通じての処理ができないため、従来の商演算の代わりに異なる技術を使用する必要があります。私たちは、仮想点を追加することで、2つの点で評価を行って証明しなければなりません。

もし多項式Pがx1でy1に等しく、x2でy2に等しい場合、私たちはこの2点で等しい補間関数Lを選びます。次に、P-Lが2点でゼロであることを証明し、LでLを割って商Qが多項式であることを証明します。

! 【ヴィタリックの新作:サークルスタークの探索】(https://img-cdn.gateio.im/webp-social/moments-0277731a7327da529c85417a01718c59.webp)

消失する多項式

Circle STARKsでは、消える多項式は次のとおりです。 Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

これは折りたたみ関数から導き出すことができます: Circle STARKsではx → 2x^2 - 1を繰り返し使用します。最初のラウンドは特別な処理が必要です。

ビット順を反転する

Circle STARKsは修正された逆位順を使用し、最後のビットを除くすべてのビットを反転させ、最後のビットによって他のビットを反転させるかどうかを決定します。これはCircle STARKs特有の折りたたみ構造を反映しています。

! ヴィタリックの新作:サークルスタークの探索

効率性

サークルスタークは非常に効率的です。 通常、計算には次のものが含まれます。

1. ネイティブ算術:ビジネスロジックに使用される
2. ネイティブ算術: 暗号学(に使用されるPoseidonハッシュ)
3. パラメータを探す: テーブルを通じて値を検索し、さまざまな計算を実現する

Circle STARKsは計算空間を十分に活用し、無駄が少ない。Biniusにはやや劣るが、概念はよりシンプルである。

まとめ

Circle STARKsは開発者にとって従来のSTARKsよりも複雑ではありません。Circle FRIとFFTsを理解することは、他の特殊FFTsを理解するのに役立ちます。現在、STARKsの基盤層の効率は限界に近づいており、今後の最適化の方向性には以下が含まれる可能性があります:

1. ハッシュ関数と署名の算術的効率を最大化する
2. 並列化を改善するための再帰的構築
3. 算術化仮想マシンによる開発体験の向上

! ヴィタリックの新作:サークルスタークの探索