最近、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 が互いに素である場合、a に関するモジュロ f の乗法逆元は存在します。互いに素でない場合は存在しません。f が素数の場合、1 から f-1 までの任意の数は f と互いに素であるため、1 から f-1 の範囲でモジュロ f の乗法逆元がちょうど 1 つ存在します。
モジュロ演算#
モジュロ演算は、有限空間での演算を行うことで、数学者たちは新しい演算システムを構築しました。モジュロ演算を使用することで、数学者たちは新しい演算システムで伝統的な数学演算システムで議論されるさまざまな構造、多項式などを議論することができます。特に、暗号学者はこの新しい演算システムが好きです。
モジュロ演算システムでは、四則演算と指数演算も行うことができますが、除算演算は実装が複雑です。通常、除数の逆元を求め、除算を乗算に変換して計算します。
実際の計算では、一般的に素数 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であり、各値に対してk個の要素が対応します。したがって、実際には、プルーバーは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)を使用して、低次検証を行います。