Circle STARKsを深く掘り下げる

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

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

しかし、小さなフィールドを使用することは、限られたフィールドサイズでの安全性をどのように保証するかといういくつかの課題も引き起こします。Circle STARKsソリューションは、円群の特性を利用して効率的で安全な証明システムを構築する革新的な解決策を提供します。

この記事では、Circle STARKsの原理と実装の詳細について深く探ります。

• 小さなフィールドSTARKsが直面する主な課題
• サークルFRIの基礎知識
• サークルFFTの実装
• Circle STARKsにおける商演算と消失多項式
• 逆順の調整
• Circle STARKsの効率解析

これらの技術的詳細の議論を通じて、私たちはCircle STARKsの革新性と、それがSTARKsの効率を向上させる上での重要な貢献をよりよく理解することができます。

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

小フィールドの使用に関する課題

楕円曲線に基づくプロトコルでは、ランダムな256ビット数を検証パラメータとして選択できます。しかし、小さなフィールドのSTARKsでは、選択可能なパラメータの範囲が大幅に狭まり、攻撃者による総当たり攻撃を受けやすくなります。

2つの解決策があります:

1. 複数のランダムチェックを実施する: 複数のランダム座標で繰り返し検証します。この方法は簡単で効果的ですが、効率は低下します。

2. 拡張フィールド: 新しい数学構造を導入して選択可能な値の範囲を拡大します。例えば、Mersenne31フィールド上で、特定の値になるようにαを定義することで、より大きなフィールドを構築できます。

拡張フィールドは主にFRIプロトコルなどのランダム線形結合を必要とするシーンで使用されます。ほとんどの演算は基礎フィールド上で行われ、小さなフィールドの効率性が保持されています。

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

Circle FRIの仕組み

Circle STARKsのコアイノベーションはCircle FRIにあります。素数pが与えられた場合、pのサイズを持つ群を構成することができ、その群は二対一対応の特性を持っています。

この群は、x^2 mod pが特定の値に等しい点の集合で構成されています。これらの点は特別な加法ルールに従います:

(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

ダブルポイントの公式は:

2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRIは最初にすべての点を1本の直線に収束させます:

f0(x) = (F(x,y) + F(x,- y))月2日

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

第二ラウンドから、マッピングは次のようになります:

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

このマッピングは、ポイントセットのサイズを毎回半分に減らし、従来のFRIに似た効果を実現します。

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

サークルFFT

Circle群もFFT操作をサポートしており、構築方法はCircle FRIに似ています。重要な違いは、Circle FFTが厳密な意味での多項式ではなく、いわゆるRiemann-Roch空間を処理することです。

これは、Circle FFTの出力係数が通常のFFTのように単項式ではなく、Circle FFTに特有の基底関数であることを意味します。

開発者として、これらの数学的詳細を無視することができます。多項式を評価値のセットとして保存し、FFTを使用して低次の拡張を行うだけで済みます。

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

商演算と消失多項式

Circle STARKsでは、単一の線形関数が存在しないため、異なる商演算の技術を採用する必要があります。私たちは、2つの点で評価を行うことによって、仮想点を追加することを証明します。

消失多項式も適切に調整する必要があります。Circle STARKsでは、消失多項式の形式は次のようになります:

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-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp)

逆順の調整

Circle FRIの折りたたみ構造に適応するために、逆位順を調整する必要があります。基本的な考え方は、最後の位を除くすべての位を反転し、最後の位が他の位を反転させるかどうかを決定します。

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

効率分析

Circle STARKsは31ビット素数フィールド上で非常に効率的です。それはフィールドスペースを最大限に活用し、無駄を減らします。大きなフィールドSNARKsと比較して、Circle STARKsはビジネスロジックとルックアップテーブルの面でより優れています。

Biniusなどのソリューションは、異なるサイズのフィールドを混合することで高い効率を実現しましたが、複雑さも増しました。Circle STARKsは、概念的にはよりシンプルです。

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

まとめ

Circle STARKsは開発者に効率的で比較的簡単なSTARKsの実装ソリューションを提供します。それは円群の特性を巧妙に利用し、安全性を維持しながら効率を大幅に向上させています。

未来STARKsの最適化の方向性には、次のようなものが含まれる可能性があります:

• ハッシュ関数などの基本的な暗号原語の効率を最大化する
• 再帰的な構造を通じて、より多くの並列処理を実現する
• 開発体験を向上させるために、仮想マシンの算術化を改善する

総じて、Circle STARKsはSTARKs技術の発展における重要なマイルストーンであり、より効率的なゼロ知識証明システムを構築するための新たなアプローチを提供します。

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