これらの日数、坊間では stark がコインを発行するという噂が広まっています！市況がまだ良好な時にコインを発行することは非常に賢明な選択です。
ここでは、stark の基本的な技術原理を振り返りたいと思います。以前から断続的に記録してきましたが、今回は整理してここに置いておきます（まだ少し乱雑ですが）。
計算の完全性#
計算の完全性（Computational Integrity）とは、ある計算の出力が正しいことを保証することです。
ステップ 1：算術化#
実行トレースの生成#
実行トレースは実際にはリストであり、リストの各行は計算ステップを表します。
実行トレースを多項式で表現する
多項式をより大きなフィールドに拡張する
多項式制約#
多項式制約は、実行トレースが有効な計算を表す場合にのみ、すべての多項式制約が満たされることを保証します。
多項式制約を使用して、それを別の多項式に変換し、新しい多項式の実行トレースが有効な場合にのみ、それが低次の多項式であることを保証します。
検証者の仕事は主に 2 つあります。
- ランダムな位置で合成多項式をクエリする
- これらのクエリに基づいて、多項式が低次であるかどうかをチェックする
簡潔性#
まだ完了していない作業があります。それは STARK の S、簡潔性です。簡潔性は次の 2 つの要素で構成されています。
- 少数のクエリのみを使用する
- 各クエリごとに非常に少量の計算を完了する
クエリ時に、多項式の計算に使用される計算量を減らすために、以下の図の方法を使用します。このグループの特性を利用して、実行トレースをドメイン上の部分群の多項式の評価として見なし、評価の多項式制約はその部分群に関するものであるため、検証者の検証時間が対数オーダーで減少します。この特性を利用して、より複雑な実行トレースを構築することができますが、制約はドメイン上の特定の部分群と一致する必要があります。
数学的背景知識：
整数モジュロ n 乗法群#
逆元の乗法#
群 G の任意の要素 a には、G 内で唯一の逆元 a' があり、aa'=a'a=e である。ここで、e は群の単位元です。
例：4 に関して 1 モジュロ 7 の逆元は何ですか？
4X≡1 mod 7
この方程式は、X と K を求めるための方程式です。
4X=7K+1
ここで、X と K は整数です。
ax≡1 mod f の場合、a に関する 1 モジュロ f の乗法逆元と呼ばれます。また、ax≡1 (mod f) とも表記できます。
a と f が互いに素である場合、モジュロ f の乗法逆元は解を持ちます。互いに素でない場合は解がありません。f が素数の場合、1 から f-1 までの任意の数はすべて f と互いに素であるため、1 から f-1 までの範囲でモジュロ f の乗法逆元が存在します。
モジュロ演算#
モジュロ演算は、有限空間での演算を行うことで、数学者たちは新しい演算システムを構築しました。モジュロ演算を使用することで、数学者たちは伝統的な数学演算システムである「通常の数学」についても議論することができます。特に、暗号学者はこの新しい演算システムが好きです。
モジュロ演算システムでは、四則演算と指数演算も行われますが、除算演算は実装がやや複雑です。一般的には、除数の逆元を求め、除算を乗算に変換して計算します。
実際の計算では、一般的に素数 pをモジュロとして使用します。
フェルマーの小定理#
整数 aがあり、pが素数である場合、a^p-aはpの倍数です。
フェルマーの小定理は逆元を求めるためにも使用され、これはモジュロ演算システムでの除算の基礎です。
フェルマーの小定理にはさらに推論があります。モジュロ演算空間では、p-1がkの倍数である場合、x => x^kの値空間のサイズは(p-1)/k+1です。
ユークリッドの拡張アルゴリズム#
ユークリッドのアルゴリズムは、2 つの数の最大公約数を求めるために使用されます。ユークリッドのアルゴリズムを拡張することで、モジュロ演算下の逆元を求めることもできます。
モンゴメリ算法#
モジュロ演算に除算が含まれる場合、すべての除算を乗算に変換するために逆元を使用します。ただし、逆元を求める操作も面倒ですし、大量の逆元を求める場合は時間がかかります。モンゴメリ算法は、複数の逆元の操作を複数の乗算と 1 回の逆元の操作に変換して計算を簡略化します。
高速フーリエ変換#
zk-stark の計算プロセスでは、多項式係数に基づいて値を求める必要があります。また、値から多項式係数を求める必要もあります。ラグランジュ補間法を使用することもできますが、その時間計算量は O (n^2) です。一方、高速フーリエ変換は O (n*log (n)) です。たとえば、100 万個の点に対して補間を行う場合、ラグランジュ法では 1 兆回の計算が必要ですが、高速フーリエ変換では 2000 万回の計算で済みます。ただし、高速フーリエ変換は点の取り方に要件があり、等比級数で取り、個数が 2^k を満たす必要があります。
低次テスト —FRI アルゴリズム#
多項式の次数は、最高次数を指します。既知の多項式の n個の点がある場合、その次数が m以下であることを証明するにはどうすればよいでしょうか（m<n-1、ラグランジュ補間法によれば、n個の点は次数が n-1以下の多項式を決定することができます）。比較的簡単な方法は、まず m+1個の点を使用して m次多項式を求め、その後、他の点がすべてこの多項式上にあることを検証することです。ただし、mが非常に大きい場合、この方法の計算量は線形的に増加します。FRI アルゴリズムを使用すると、この問題を m未満の計算量で検証できます。
アイデアは次のとおりです。N（たとえば 10 億）個の点が、次数が小さい（たとえば 100 万）多項式に存在するとします。f(x)=x^12012+x^11011+x^3005+x^1001+x+1とします。そして、y=x^1000とします。これを代入すると、g(x,y)=x^12*y^12+x^11*y^11+x^5*y^3+x*y+x+1が得られます。g(x,y)については、yを固定した場合、xに対しては次数が 1000 未満になります。同様に、xを固定した場合、yに対しても次数が 1000 未満になります。
証明手順：
- プルーバーは、
g(x,y)の各行と各列のすべての点の値を計算し、10^18回計算する必要があり、その Merkle Root を取得します。 - 検証者はいくつかの行と列をランダムに選び、各行または列について、
1010個の点をランダムに選択します。プルーバーは、使用されたすべての点の Merkle パスを提供する必要があります。検証者は、Merkle パスとその次数が 1000 未満であるかどうかを検証します。
このようなシナリオでは、プルーバーは10^18回計算する必要がありますが、次にプルーバーの計算をどのように減らすかを考えます。
前述のように、フェルマーの小定理には推論があります。モジュロ演算空間では、p-1がkの倍数である場合、x => x^kの値空間のサイズは(p-1)/k+1です。したがって、実際にはプルーバーは10^9回計算するだけで済みます。上記の図の特定の行に関連する点は、前回の計算で見つけることができます。また、特定の行は指定された列に補間できるため、低次計算のためのデータが準備されます。
新しい証明手順：
- プルーバーは、
f(x)のすべての点の値を計算し、10^9回計算する必要があり、その Merkle Root を取得します。 - 検証者はいくつかの列をランダムに選び、各列についていくつかの点をランダムに選択します。点の値は、対応する行の補間から取得され、対応する行の補間のデータソースはプルーバーがすでに計算した
f(x)の値です。同様に、プルーバーは使用されたすべての点の Merkle パスを提供する必要があります。
実際の計算では、通常はy=x^4を取ります。そして、yの低次証明についてもFRIメソッドを使用し、z=y^4とします。これを繰り返すことができます。
zk-stark の証明アイデア#
- プログラムの各ステップは値に対応し、すべてのステップを組み合わせて計算トレースを形成し、多項式
P(n)に対応します。 - 計算トレースの各ステップは制約
C(p)=0を生成します。 - トレース多項式と制約多項式を組み合わせて
D(x)=C(p(x),p(x-1)....)を得ます。 - 組み合わせ多項式
D(x)は計算トレースの各ステップでゼロであり、つまり根Z(x)=(x-x_1)(x-x_2)...(x-x_n)を持ちます。 - 多項式
T(x)=D(x)/Z(x)に対して低次検証を行うためにFRIアルゴリズムを使用します。