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

近年、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)

小さなフィールドの一般的な問題

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

攻撃を防ぐために、攻撃者が多項式を提供した後にランダムな点を選択する必要があります。256ビットのフィールドではこれは簡単ですが、小さなフィールドでは選べるランダム値が少なく、攻撃者によって総当たり攻撃されやすくなります。

解決策は2つあります:

1. 複数回のランダムチェックを行う
2. 拡張フィールド

複数回のランダムチェックはシンプルで効果的ですが、効率は低いです。拡張フィールドは複数に似ており、有限体上でより複雑な演算を行うことができます。

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

レギュラーFRI

FRIプロトコルの第一歩は、計算問題を多項式方程式に変換することです。そして、提案された多項式の解が実際に方程式を満たし、次数が要求を超えないことを証明します。

FRIは、多項式の次数がdであることを証明する問題を次数がd/2であることを証明する問題に簡略化することによって検証します。このプロセスは繰り返すことができ、毎回問題を半分に簡略化します。

FRIの鍵は、データセットのサイズを半分にするために1対2のマッピングを使用することです。このマッピングは、最終的に1つの値だけが残るまで繰り返し適用できる必要があります。

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

サークルFRI

Circle STARKsの巧妙さは、素数pに対して、サイズpの群を見つけることができ、類似の二対一特性を持つことにあります。この群は特定の条件を満たす点から構成されています。

これらの点は、三角関数や複素数の乗法に似た加法の法則に従います。

第2ラウンドから、マッピングが変更されます。各xは2つの点を表します: (x,y)と(x,-y)。(x → 2x^2 - 1)は点の倍増法則です。

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

サークルFFT

CircleグループはFFTもサポートしており、構造方法はFRIに似ています。しかし、Circle FFTが処理する対象は厳密な意味での多項式ではなく、Riemann-Roch空間です。

開発者として、これらの詳細はほとんど無視できます。多項式を評価値として保存し、低度の拡張が必要な場合にFFTを使用するだけです。

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

クオティング

circle groupのSTARKにおいて、単一の線形関数が存在しないため、従来の商演算の代わりに異なる技術を使用する必要があります。

私たちは2つの点を評価することで、仮想点を追加することを証明します。

消失する多項式

円の STARK では、消失する多項式は次のようになります。

Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

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

ビット順序を逆にする

STARKsでは、多項式評価は通常逆順に配置されます。Circle STARKsでは、その特有の折りたたみ構造を反映するために、この順序を調整する必要があります。

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

効率性

Circle STARKsは非常に効率的です。重要なのは、計算トレース内のスペースを最大限に活用して有用な作業を行い、大量の空きスペースを残さないことです。

Biniusと比べて、Circle STARKsは概念的によりシンプルですが、効率はやや低いです。

まとめ

Circle STARKsは開発者にとって通常のSTARKsと比べて複雑ではありません。Circle FRIとFFTsを理解することは、他の特別なFFTsを理解するのに役立ちます。

未来STARKの最適化は以下に集中する可能性があります:

1. ハッシュ関数などの基本的な暗号プリミティブの効率を最大化する
2. 再帰的な構造を用いて並列化を向上させる
3. 算術化仮想マシンで開発体験を改善する

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