Circle STARKsを深く掘り下げる

近年、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) = cを逆算し、Q = (A - c)/(X - r)が多項式であることを証明します。

攻撃を防ぐために、攻撃者がAを提供した後にrを選択する必要があります。大規模フィールドプロトコルでは、rとしてランダムな256ビット数字を選択できます。しかし、小規模フィールドSTARKsでは、約20億種類のr値しか選択できず、攻撃者はすべての可能性を試すことができます。

この問題には二つの解決策があります:

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

複数回のランダムチェックはシンプルで効果的ですが、効率の問題があります。拡張フィールドは複数に似ていますが、有限体に基づいています。新しい値αを導入し、α^2=ある値を満たすことで、新しい数学的構造を作成します。これにより、より多くの値を選択でき、セキュリティが向上します。

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

レギュラーFRI

FRIプロトコルの第一歩は通常、算術化であり、計算問題を方程式P(X,Y,Z)=0に変換します。このとき、Pは多項式であり、X、Y、Zはパラメータです。方程式を解くことは、元の問題を解決することに対応します。

解の正当性を証明するには、提示された値が合理的な多項式であり、かつ最大次数を持つことを証明する必要があります。ランダム線形結合技術を使用します:

• 多項式Aの評価値があると仮定すると、その次数を<2^20であることを証明する。
• B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x)928374656574839201/x
• DはBとCのランダムな線形結合です: D = B + rC

本質的にBは偶数係数を隔離し、Cは奇数係数を隔離します。BとCはAを復元できます。Aの次数が<2^20の場合、BとCの次数はそれぞれAの次数とAの次数-1です。Dはランダムな組み合わせとして、その次数はAの次数であるべきです。

FRIはこの簡略化プロセスを繰り返し、毎回問題を半分に簡略化します。この設計は、要件を満たさない入力を効果的に検出します。

! [ヴィタリックの新作:サークルスタークを探索する])https://img-cdn.gateio.im/webp-social/moments-b32679a50fc463cfc1c831d30ab2d7e2.webp(

サークルFRI

これがCircle STARKsの巧妙な点です。素数pが与えられた場合、pの大きさの群を見つけることができ、類似の二対一特性を持っています。この群は、x^2 mod pが特定の値に等しい点の集合のような特定の条件を満たす点で構成されています。

これらの点は加法の法則に従います:)x1,y1( + )x2,y2( = )x1x2 - y1y2, x1y2 + x2y1( 二重形式は 2 * )x, y( = )2x^2 - 1, 2xy( です

私たちは円上の奇数位置の点に焦点を当て、すべての点を1本の直線に収束させます: f0)x( = )F(x,y( + F)x,- y()月2日

その後、ランダムな線形結合を行い、一次元多項式P)x(を得る。

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

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

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

サークルFFT

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

開発者としては、この点は基本的に無視できます。STARKsは多項式を評価値のセットとして保存するだけです。FFTは主に低次の拡張に使用されます：N個の値が与えられた場合、同じ多項式上のk*N個の値を生成します。

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

クオティエンティング

Circle STARKsでは、単一の線形関数がないため、従来の商算を代替する異なる技術を使用する必要があります。2つの評価ポイントで証明することにより、仮想点を追加します。

多項式Pがx1でy1に等しく、x2でy2に等しい場合、これらの2点で等しい補間関数Lを選択します。そして、P-Lが2点でゼロであることを証明し、Lで割った商Qが多項式であることを示します。

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

消失する多項式

Circle STARKsで消える多項式は次のとおりです。 Z1)x,y( = y Z2)x,y( = x
Zn+1)x,y( = )2 * Zn(x,y(^2) - 1

これは畳み込み関数から導出できます: x → 2x^2 - 1 を繰り返し使用します。

ビット順の逆転

Circle STARKsの逆位順を調整する必要があります: 最後の1ビットを除くすべてのビットを反転し、最後のビットで他のビットを反転させるかどうかを決定します。

16サイズの折りたたみ逆位相は: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-13da9460855ee8c504c44696efc2164c.webp(

効率性

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

1. ビジネスロジックのネイティブ算術
2. 暗号学のネイティブ算術
3. パラメータを探す

効率の鍵は計算追跡スペースを十分に活用することにあります。31ビット素数フィールドは無駄を減らします。Biniusは異なるサイズのフィールドを混合することで効率が向上しますが、概念はより複雑です。

まとめ

Circle STARKsは開発者にとって複雑ではありません。背後の数学を理解するには時間がかかりますが、複雑さはうまく隠されています。また、他の特別なFFTsを理解するための手段でもあります。

現在STARKsの基盤レイヤーの効率は限界に近づいています。今後の最適化の方向性には以下が含まれる可能性があります:

• ハッシュ関数など基本的な暗号原語の効率を最大化する
• 再帰的構造を使用して並列化を増やす
• 算術化仮想マシンで開発体験を改善する

! [ヴィタリックの新作:サークルスタークの探索])https://img-cdn.gateio.im/webp-social/moments-972d4e51e7d92462c519ef900358a6af.webp(