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

近年、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を生成することを要求すると仮定します。AはA^3(x) + x - A(ωx) = x^N(ZK-SNARKプロトコルにおける非常に一般的な証明タイプ)を満たさなければなりません。プロトコルは、あなたにランダムな座標rを選び、A(r) + r - A(ωr) = r^Nを証明するよう要求することがあります。次に、A(r) = cと逆算すると、あなたはQ = (A - c)/(X - r)が多項式であることを証明しました。

攻撃を防ぐために、攻撃者がAを提供した後にrを選択する必要があります。選択されたパラメータは、攻撃者がこれらのパラメータを予測または推測できないように、十分に大きな集合からのものである必要があり、システムの安全性を向上させます。

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

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

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

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

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

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

拡張領域を通じて、私たちは現在、安全要件を満たすために選択できる十分な値を持っています。次数がd未満の多項式を処理する場合、各ラウンドは104ビットのセキュリティを提供できます。これは、私たちが十分なセキュリティを持っていることを意味します。128ビットなどのより高いセキュリティレベルを達成する必要がある場合、プロトコルにいくつかの追加の計算作業を追加して、セキュリティを強化することができます。

拡張領域は、FRI(Fast Reed-Solomon Interactive)プロトコルおよびその他のランダム線形結合が必要なシナリオでのみ実際に使用されます。ほとんどの数学的演算は、基本フィールド上で行われ、これらの基本フィールドは通常、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-cb343bb0791734002ef1a3b813eea1e2.webp(

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

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

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

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

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

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

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

Mersenne31領域は、既存の32ビットCPU/GPUの操作で算術演算を行うのに非常に適しています。なぜなら、そのモジュラスの特性(、例えば2^31 - 1)により、多くの演算を効率的なビット操作を利用して完了させることができるからです: もし2つの数字を加算した結果がモジュラスを超えた場合、結果をモジュラスとビット演算することで対応できます。