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

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

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

この記事では、これらの技術の仕組みを探ります。特にCircle STARKsソリューションに焦点を当てます。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の大きさを持つ群を見つけることができる点にあります。この群は特定の条件を満たす点から構成されています。

第二ラウンドから、マッピングが変更されます:

f_0(2x^2-1) = (F(x) + F(-x))/2

このマッピングは、毎回集合のサイズを半分にします。各xは2つの点を表します: (x,y)と(x,-y)。(x→2x^2-1)は点倍増の法則です。

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

サークルFFT

Circle groupもFFTをサポートしており、その構造はFRIと似ています。しかし、Circle FFTが処理する対象は厳密な多項式ではなく、Riemann-Roch空間です。

開発者としては、ほとんど無視することができます。STARKは多項式を評価値として保存することだけを要求します。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は、その特有の折りたたみ構造を反映するために逆位置を調整する必要があります。最後のビットを除くすべてのビットを反転させ、最後のビットは他のビットを反転させるかどうかを決定するために使用されます。

効率性

Circle STARKsは非常に効率的です。計算には通常、次のようなものが含まれます:

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

重要なのは、計算トラッキングにおけるスペースを十分に活用することです。2^31のサイズのフィールドは、無駄なスペースを減らします。

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

まとめ

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

Circle FRIとFFTsを理解することは、他の特殊FFTsを理解する手段となり得る。

Mersenne31、BabyBear、バイナリーフィールド技術を組み合わせることで、私たちはSTARKsの基盤層の効率の限界に近づいています。今後の最適化の方向性には、次のようなものが含まれる可能性があります:

• ハッシュ関数などの最大効率化の算術化
• 再帰的に構築して、より多くの並列処理を有効にする
• 算術化仮想マシンで開発者体験を向上させる

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