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

近年、STARKsプロトコルの設計トレンドは、より小さなフィールドの使用に移行しています。初期のSTARKs実装では256ビットフィールドを使用しており、楕円曲線署名と互換性がありますが、効率が低いです。効率を向上させるために、STARKsはGoldilocks、Mersenne31、BabyBearなどのより小さなフィールドを使用し始めました。

この変化は、証明速度を大幅に向上させました。例えば、StarkwareはM3ノートパソコン上で毎秒62万のPoseidon2ハッシュを証明できます。これは、Poseidon2をハッシュ関数として信頼する限り、高効率のZK-EVMの課題を解決できることを意味します。本稿では、これらの技術の仕組みを探り、特にCircle STARKsソリューションに焦点を当てます。

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

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

ハッシュに基づく証明において、重要な技術は、ランダムな点での多項式の評価を通じて多項式の特性を間接的に検証することです。これにより、証明プロセスが大幅に簡素化されます。

例えば、証明システムは多項式Aのコミットメントを生成することを要求するかもしれません。これにより、A^3(x) + x - A(ωx) = x^Nが満たされます。プロトコルでは、ランダムな座標rを選択し、A(r) + r - A(ωr) = r^Nを証明することが要求される場合があります。

攻撃を防ぐために、攻撃者が A を提供した後に r を選択する必要があります。256 ビットフィールドではこれは簡単ですが、小さなフィールドでは約 20 億種類の r が選択可能であり、攻撃者がそれを解読する可能性があります。

解決策は2つあります:

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

複数回のチェックは簡単で効果的ですが、安全性を向上させるためにはラウンド数を増やす必要があるかもしれません。拡張領域は類似の複素数ですが、有限体に基づいています。新しい値αを導入することにより、より複雑な数学構造が作成され、より多くの選択肢が提供されます。

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

レギュラーFRI

FRIプロトコルの第一歩は、計算問題を多項式方程式P(X,Y,Z)=0に変換することです。その後、提案された値が妥当な多項式であり、次数が有限であることを証明します。

FRIは、次数がdの多項式の証明問題を次数がd/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のマッピングは第2ラウンドから次のようになります: f0(2x^2-1) = (F(x) + F(-x))/2

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

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

サークルFFT

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

円FFTの係数は、{1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, ...}

開発者はこの点をほとんど無視でき、単に多項式を評価値の集合として保存すればよい。FFTは主に低次の拡張に使用される。

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

クォティング

circle groupのSTARKでは、単一の線形関数がないため、従来の商演算を代替する異なる技術を採用する必要があります。通常、証明のために2点で評価する必要があり、仮想点を追加します。

消失する多項式

Circle 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. 暗号学のネイティブ算術(はPoseidonハッシュ)のようです。
3. パラメータを探す

2^31のサイズのフィールドはスペースの無駄を減らしました。Biniusは混合フィールドサイズにおいて優れていますが、概念はより複雑です。

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

まとめ

Circle STARKsは開発者にとってSTARKsよりも複雑ではありません。その数学を理解するには時間が必要ですが、複雑さはうまく隠されています。

Mersenne31、BabyBear、バイナリーフィールド技術を組み合わせることで、STARKの基盤層の効率は限界に近づいています。将来の最適化の方向性には、以下が含まれる可能性があります:

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

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