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

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

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

この記事では、これらの技術の動作原理を探り、特にMersenne31フィールドと互換性のあるCircle STARKsというソリューションに焦点を当てます。

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

小さなフィールドの一般的な問題

ハッシュベースの証明を作成する際の重要なテクニックは、ランダムな点での多項式の評価を通じて間接的に多項式の性質を検証することです。これにより、証明プロセスが大幅に簡素化されます。

しかし、小さなフィールドでこのようなランダムサンプリングを行うことにはセキュリティ上の問題があります。例えば、Mersenne31フィールドには約20億の可能なサンプリングポイントがあり、決意した攻撃者にとっては実行可能です。

解決策は二つあります：

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

何度もチェックするのは簡単で効果的ですが、効率の問題があります。拡張フィールドは、より多くのサンプリングポイントの選択肢を提供し、安全性を向上させることができます。

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

一般的なFRI

FRIプロトコルの第一歩は、計算問題を多項式方程式に変換することです。そして、提案された多項式解が実際に合理的な多項式であり、一定の最大次数を持つことを証明します。

FRIは、証明多項式の次数がdである問題を、次数がd/2である問題に段階的に簡略化することによってこれを実現します。このプロセスは何度も繰り返すことができ、毎回問題の規模が半分に減ります。

FRIの各ステップは、多項式の次数と点の集合の規模を半分にします。前者はFRIの動作の鍵であり、後者はアルゴリズムの実行速度を非常に速くします。

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

サークルFRI

Circle STARKsの巧妙さは、pの大きさを持つ群を見つけたことで、類似の二対一特性を持っています。この群は特定の条件を満たす点で構成されています。

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

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

このマッピングは、毎回点の集合のサイズを半分に減らします。

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

サークルFFT

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

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

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

商演算

Circle STARKsでは、単点の線形関数が存在しないため、従来の商演算方法に代わる異なる技術を採用する必要があります。

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

消える多項式

Circle STARKsでは、消失する多項式の形式は次のとおりです。

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の逆位序は、その特殊な折りたたみ構造を反映するように調整する必要があります。具体的には、最後の1ビットを除くすべてのビットを反転させ、最後のビットで他のビットを反転させるかどうかを決定する必要があります。

効率性

Circle STARKsは非常に効率的です。大規模なフィールドSNARKsと比較して、計算トレース内のスペースをより十分に活用できます。

Biniusはある点でCircle STARKsより優れていますが、その代償として概念がより複雑です。それに対して、Circle STARKsは概念的に比較的シンプルです。

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

まとめ

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

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

1. ハッシュ関数と署名の効率を最大化する
2. 並列性を向上させるための再帰的構築
3. 仮想マシンを最適化して開発体験を向上させる

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