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

近年、STARKsプロトコルの設計トレンドは、より小さなフィールドの使用にシフトしています。最初期のSTARKsの実装では256ビットフィールドが使用されており、これは大きな数に対する剰余計算を行うもので、これによりこれらのプロトコルは楕円曲線ベースの署名と互換性があります。しかし、この設計の効率は比較的低く、一般的にはこれらの大きな数を計算することには実際の用途がなく、膨大な計算力を浪費することになります。この問題を解決するために、STARKsはより小さなフィールドの使用にシフトし始めました：最初はGoldilocks、次にMersenne31とBabyBearです。

この変化は証明速度を向上させ、例えばStarkwareはM3ノートパソコンで毎秒620,000のPoseidon2ハッシュ値を証明できるようになりました。これは、Poseidon2をハッシュ関数として信頼する限り、高効率のZK-EVMの開発における課題を解決できることを意味します。それでは、これらの技術はどのように機能するのでしょうか？これらの証明はどのように小さなフィールド上に構築されるのでしょうか？これらのプロトコルはBiniusなどのソリューションと比較してどのように異なるのでしょうか？この記事では、特にMersenne31フィールドと互換性のある独特の特性を持つCircle STARKsと呼ばれるソリューションに焦点を当てて、これらの詳細を探ります。

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

小さい数学フィールドを使用する際によくある問題

ハッシュベースの証明を作成する際に非常に重要なテクニックは、多項式をランダムな点で評価した結果を通じて証明することで、多項式の特性を間接的に検証できることです。この方法は証明プロセスを大幅に簡素化することができ、ランダムな点での評価は通常、全体の多項式を扱うよりもはるかに容易です。

攻撃を防ぐためには、攻撃者がAを提供した後にrを選択する必要があります。Fiat-Shamirは、特定のパラメータを特定のハッシュ値に設定することによって攻撃を回避するためのプロトコルの安全性を向上させる技術です。選択されたパラメータは十分に大きな集合から得られる必要があり、これにより攻撃者がこれらのパラメータを予測または推測できないようにし、システムの安全性を高めます。

楕円曲線に基づくプロトコルと2019年のSTARKsでは、この問題は非常に簡単です。私たちのすべての数学的演算は256ビットの数字で行われるため、rをランダムな256ビットの数字として選択すればよいのです。しかし、より小さなフィールドのSTARKsでは、問題が発生します。選択できるr値は約20億通りしかないため、証明を偽造しようとする攻撃者は20億回試すだけで済みます。作業量は膨大ですが、決意した攻撃者にとっては全く不可能ではありません！

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

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

複数回のランダムチェックを実施する方法は最も簡単で効果的です：1つの座標でチェックするよりも、4つのランダムな座標で繰り返しチェックする方が良いです。理論的には可能ですが、効率の問題があります。もしあなたがある値よりも小さい次数の多項式を扱っていて、あるサイズの体で操作しているのであれば、攻撃者は実際にこれらの位置で正常に見える悪意のある多項式を構築することができます。したがって、彼らがプロトコルを成功裏に破壊できるかどうかは確率的な問題であり、全体の安全性を強化するためにチェックのラウンド数を増やす必要があります。これにより攻撃者の攻撃に効果的に防御できることを保証します。

これは別の解決策を導入します：拡張体で、拡張体は複素数に似ていますが、有限体に基づいています。新しい値αを導入し、α²=ある値を満たすと宣言します。この方法で、有限体上でより複雑な演算を行う新しい数学的構造を作成します。この拡張体では、乗算の計算は新しい値αを使用した乗算に変わります。私たちは今、単一の数字だけでなく、拡張された体の中で値のペアを操作できます。例えば、MersenneやBabyBearのような体で作業している場合、このような拡張はより多くの値の選択を可能にし、安全性を向上させます。体のサイズをさらに大きくするために、同じ技術を繰り返し適用できます。すでにαを使用しているので、新しい値を定義する必要があります。これはMersenne31では、αを選択してα²=ある値を満たすようにすることを示します。

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

ドメインを拡張することによって、私たちは今、私たちのセキュリティ要件を満たすのに十分な値を持っています。次数がd未満の多項式を処理している場合、各ラウンドは104ビットのセキュリティを提供します。これは、私たちに十分なセキュリティ保障があることを意味します。もし128ビットのようなより高いセキュリティレベルに達する必要がある場合、プロトコルに追加の計算作業を加えてセキュリティを強化することができます。

拡張領域は、FRIプロトコルや他のランダム線形組み合わせが必要なシナリオでのみ実際に使用されます。ほとんどの数学演算は基礎フィールドで行われ、この基礎フィールドは通常、pまたはqの剰余によるフィールドです。同時に、ほぼすべてのハッシュデータは基礎フィールド上で行われるため、各値は4バイトのみハッシュ化されます。このようにすることで、小さなフィールドの効率性を活用しつつ、安全性を強化する必要がある場合には、より大きなフィールドを使用できます。

レギュラーFRI

SNARKやSTARKを構築する際、最初のステップは通常、算術化です。これは任意の計算問題を方程式に変換することであり、その中のいくつかの変数と係数は多項式です。具体的には、この方程式は通常、P(X,Y,Z)=0のように見え、ここでPは多項式で、X、Y、Zは与えられたパラメータであり、ソルバーはXとYの値を提供する必要があります。このような方程式があれば、その方程式の解は基盤となる計算問題の解に対応します。

解を証明するには、提案された値が確かに合理的な多項式であること（分数でないこと、あるいはある場所では多項式に見えるが他の場所では異なる多項式であることなど）を証明する必要があります。また、これらの多項式は一定の最大次数を持っている必要があります。そのために、段階的に適用されるランダム線形組み合わせの技術を使用しました：

• 多項式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と表され、rはランダム係数です。

本質的に、起こっていることはBが偶数係数Aを隔離し、Cが奇数係数を隔離することです。BとCが与えられた場合、元の多項式Aを復元できます：A)x( = B)x^2( + xC)x^2(。もしAの次数が実際に2^20未満であれば、BとCの次数はそれぞれAの次数とAの次数から1を引いたものになります。偶次項と奇次項の組み合わせは次数を増加させません。DはBとCのランダムな線形結合であるため、Dの次数もAの次数であるべきであり、これによりDの次数を通じてAの次数が要件を満たしているかどうかを検証できます。

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

まず、FRIは多項式の次数がdであることの証明を次数がd/2であることの証明に簡略化することによって検証プロセスを簡素化しました。このプロセスは何度も繰り返すことができ、毎回問題を半分に簡略化します。

FRIの動作原理は、この簡略化プロセスを繰り返すことです。たとえば、もしあなたが多項式の次数がdであることを証明することから始めた場合、一連のステップを経て、最終的に多項式の次数がd/2であることを証明することになります。各回の簡略化後に生成される多項式の次数は徐々に減少します。もしある段階の出力が予想される多項式の次数でない場合、そのラウンドのチェックは失敗します。誰かがこの技術を使って次数がdでない多項式を押し込もうとすると、2回目の出力でその次数が期待通りでない確率が一定の割合であり、3回目ではさらにその確率が高くなり、最終的なチェックは失敗します。このような設計は、要求に合わない入力を効果的に検出し、拒否することができます。データセットがほとんどの位置で次数がdの多項式に等しい場合、そのデータセットはFRI検証を通過する可能性があります。しかし、そのようなデータセットを構築するためには、攻撃者が実際の多項式を知っている必要があるため、わずかな欠陥のある証明であっても、証明者が「真の」証明を生成できることを示しています。

ここで起こっていることをもっと詳しく理解し、これを正常に機能させるために必要な属性について見ていきましょう。各ステップで、多項式の次数を半分に減らし、同時に点集合（私たちが注目している点の集合）も半分に減らします。前者はFRIプロトコルが正常に機能するための鍵です。後者はアルゴリズムの実行速度を非常に速くします：各ラウンドの規模が前のラウンドの半分になるため、総計算コストはO)N(となり、O)N*log(N()ではありません。

ドメインの段階的な削減を実現するために、各点が2つの点のうちの1つにマッピングされる1対2のマッピングが使用されました。このマッピングにより、データセットのサイズを半分に削減することができます。この1対2のマッピングの重要な利点の1つは、それが再現可能であることです。つまり、このマッピングを適用すると、得られた結果セットは同じ属性を保持します。乗法部分群から始めると仮定しましょう。この部分群は集合Sであり、各要素xにはその倍数2xも集合に含まれています。集合Sに平方操作（すなわち、集合内の各要素xをx^2にマッピングする）を行うと、新しい集合S^2も同じ属性を保持します。この操作により、最終的に1つの値だけが残るまでデータセットのサイズを引き続き削減できます。理論的には、データセットを1つの値だけに縮小することができますが、実際の操作では通常、より小さな集合に到達する前に停止します。

この操作を、円周上の線（例えば、線分や弧）を円周に沿って伸ばし、円周を2回回転させるプロセスとして考えることができます。例えば、円周上のある点がx度の位置にある場合、この操作を経ることで、それは2x度の位置に移動します。円周上の各点は0から179度の位置にあり、180から359度の位置に対応する点が存在し、これらの2つの点は重なります。つまり、x度の点を2x度にマッピングすると、x+180度の位置にある点と重なります。このプロセスは繰り返し可能です。言い換えれば、このマッピング操作を何度も適用することができ、毎回円周上の点を新しい位置に移動させます。

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

マッピング技術を有効にするためには、元の乗法部分群のサイズが大きな2の冪を因子として持つ必要があります。BabyBearは特定の法のシステムであり、その法はある値で、最大乗法部分群がすべての非ゼロ値を含むため、部分群のサイズは2k−1（ここでkは法のビット数）になります。このサイズの部分群は前述の技術に非常に適しており、マッピング操作を繰り返し適用することで多項式の次数を効率的に削減することができます。BabyBearでは、サイズが2^kの部分群を選択することができ（または全体集合を直接使用することもでき）、その後FRIメソッドを適用して多項式の次数を15まで段階的に削減し、最後に多項式の次数を確認します。この方法は法の性質と乗法部分群のサイズを利用して計算プロセスを非常に効率的にします。Mersenne31は別のシステムで、法はある値で、乗法部分群のサイズは2^31 - 1になります。この場合、乗法部分群のサイズは1つの2の冪を因子として持つため、2で1回しか割り切れません。その後の処理は前述の技術には適用できず、つまりBabyBearのようにFFTを使用して効率的に多項式の次数を削減することができません。

Mersenne31領域は、既存の32ビットCPU/GPU操作での算術演算に非常に適しています。その素数の特性（例えば2^31 - 1）により、多くの演算が効率的なビット操作を利用して実行できます。もし2つの数字の合計が素数を超えた場合、結果を素数でシフト操作を行うことで適切な範囲に縮小できます。シフト操作は非常に効率的な演算です。乗算演算では、特定のCPU命令（通常は高位シフト命令と呼ばれる）を使用して結果を処理できます。これらの命令は、乗算の高位部分を効率的に計算し、演算の効率を向上させます。Mersenne31領域では、上記の特性により、算術演算はBabyBear領域よりも約1.3倍速くなります。Mersenne31はより高い計算効率を提供します。もしMersenne31領域でFRIを実現できれば、計算効率が大幅に向上し、FRIの応