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

近年、STARKsプロトコルの設計は、より小さなフィールドの使用に向かっています。初期のSTARKs実装は256ビットフィールドを使用していましたが、この設計は効率が低いです。この問題を解決するために、STARKsはGoldilocks、Mersenne31、BabyBearなどのより小さなフィールドの使用に移行し始めました。

この変化は証明速度を大幅に向上させました。例えば、StarkwareはM3ノートパソコン上で毎秒620,000個のPoseidon2ハッシュ値を証明できます。これは、Poseidon2をハッシュ関数として信頼すれば、高効率ZK-EVMの問題を解決できることを意味します。

この記事では、これらの技術の動作原理について探求し、特にCircle STARKsソリューションに焦点を当てます。このソリューションは、Mersenne31フィールドと互換性があります。

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

小さなフィールドを使用する際の一般的な質問

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

攻撃を防ぐために、攻撃者が多項式を提供した後にランダムな点を選択する必要があります。小さなフィールドのSTARKsでは、選択可能なランダム値は約20億個しかなく、頑固な攻撃者にとっては実行可能です。

解決策は二つあります:

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

複数回のチェックは簡単かつ効果的ですが、効率の問題があります。拡張フィールドは複数に似ていますが、有限体に基づいています。これにより、有限体上でより複雑な計算を行い、安全性を高めることができます。

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

レギュラーFRI

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

FRIの動作原理はこの簡略化プロセスを繰り返すことです。ある段階の出力が期待される多項式の次数でない場合、そのラウンドのチェックは失敗します。

領域の段階的な削減を実現するために、二対一のマッピングが使用されました。このマッピングにより、データセットのサイズを半分に減らしながら、同じ属性を保持することができます。

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

サークル FRI

Circle STARKsの巧妙さは、素数pが与えられた場合、pの大きさを持つ群を見つけることができ、類似の二対一特性を持つことです。この群は特定の条件を満たす点で構成されています。

これらの点は加法の法則に従います。第二ラウンドから、マッピングが変化します。このマッピングは、毎回集合のサイズを半分にします。

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

サークルFFT

Circle groupもFFTをサポートしており、その構造方法はFRIに似ています。重要な違いは、Circle FFTが扱う対象は厳密には多項式ではなく、Riemann-Roch空間であるということです。

開発者として、ほとんど無視しても問題ありません。STARKsは、多項式を評価値として保存するだけです。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)

ビット順の逆転

Circle STARKsでは、折りたたみ構造が少し異なります。この折りたたみ構造を反映するために逆順序を調整するには、最後の1位を除くすべての位を反転させる必要があります。

効率性

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

1. ネイティブ算術:ビジネスロジックに使用される
2. ネイティブ算術:暗号学に使用される
3. パラメータを検索: テーブルから値を読み取ることによってさまざまな計算を実現します

効率の鍵は、計算空間全体を十分に活用して有用な作業を行うことです。

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

まとめ

Circle STARKsは開発者にとってSTARKsよりも複雑ではありません。主な違いは上記の3つの問題にあります。背後の数学は複雑ですが、その複雑さはうまく隠されています。

Mersenne31、BabyBear、Biniusなどの技術を組み合わせることで、私たちはSTARKsの基盤層の効率限界に近づいています。今後の最適化の方向性には、以下が含まれる可能性があります:

• ハッシュ関数と署名の算術的効率を最大化する
• 再帰構造を構築して、より多くの並列処理を有効にする
• 算術化仮想マシンによる開発者体験の改善

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