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

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

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)を得ます。

第二ラウンドから、マッピングは次のようになります: f0(2x^2-1) = (F(x) + F(-x)) / 2

このマッピングは、集合のサイズを毎回半分に減らし、円上の2つの対称点のx座標を倍増した後の点のx座標に変換します。

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

サークルFFT

CircleグループはFFTもサポートしており、構造方法はFRIに似ています。重要な違いは、Circle FFTが厳密な意味での多項式ではなく、リーマン・ロッホ空間を処理することです。

開発者として、これはほとんど無視できます。STARKsは多項式を評価値の集合として保存するだけです。FFTが必要なのは、低次元の拡張を行うところだけです。

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

商演算

STARKでは、一般的な操作は特定の点に対する商演算です。circle groupでは、単一の点の線形関数が存在しないため、異なる技術を採用する必要があります。

私たちは、注目する必要のない仮想ポイントを追加するために、2つのポイントで評価を行わなければなりません。

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

消える多項式

円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)

逆順

Circle STARKsはその折りたたみ構造を反映するために逆位序を調整する必要があります。私たちは最後のビットを除くすべてのビットを反転させ、最後のビットで他のビットを反転させるかどうかを決定する必要があります。

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

効率性

Circle STARKsは非常に高効率です。証明された計算には通常、次のものが含まれます:

1. ビジネスロジックに使用されるネイティブ算術
2. 暗号化に使用されるネイティブ算術
3. パラメータを探す

効率の鍵は、計算トラッキングにおけるスペースを十分に活用することです。Circle STARKsは2^31サイズのフィールドで無駄にするスペースが少ないです。

まとめ

Circle STARKsは開発者にとって従来のSTARKsと比べて複雑ではありません。背後にある数学は非常に複雑ですが、その複雑さはうまく隠されています。

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

• ハッシュ関数などの原始操作の効率を最大化する
• 並列処理を改善するための再帰的構築
• 算術化仮想マシンによる開発体験の改善

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