FRI
FRIは点の集合が指定値以下の次数を持つ多項式上にあるかどうかを判定するために用いられ、線形証明複雑度(linear proof complexity)と対数検証複雑度(logarithmic verification complexity)を達成することが目標となる。
具体的にはO(D)以下を目指している
Trusted setupで作成していたαでsecretをマスクしていたように、ハッシュ関数で同じことしてる
基本的な考え方
D以下のクエリで次数＜Dの多項式の近接性を証明する基本的なプロトコルを説明する
そのアイデアは次のようなもの。
N個の点(ここではN=10億とする)があり、それらすべて次数<1Mの多項式f(x)上にあるとする
そこで、$ g(x, x^{1000}) = f(x) となる2変数多項式$ g(x, y)を求める
$ 1 + x + xy + x^5 ・ y^3 + x^{12} + x ・ y^{11} のような式
これは、f(x)のk次の項(例えば、$ 1744・x^{185423})に対して、x^{k%1000}・y^{floor(k/ 1000)}に分解すると、次のようになる
$ 1744 ・ x^{423} ・ y^{185}
例えば$ y = x^{1000} であれば、$ 1744 ・ x^{423} ・ y^{185}= 1744 ・ x^{185423} が得られる
検証者は、数十の行と列をランダムに選択し、その行と列上の点(例えば1010個の)のサンプルを証明者に要求する
証明者は、要求された点と、それらが検証者によってコミットされた元のデータの一部であることを証明するために、x座標が1B(0<=x<=1B-1)、y座標が$ x^{1000}で評価された$ g(x,y)のMerkleツリーをコミットメントとして検証者に返信する。
列のx座標10億個に対応する行のy座標1000乗個すべて
これらの(x,y)座標で表される正方形の対角線は，$ g(x, x^{1000})の形をした$ g(x, y)の値を表しており，したがって，f(x)の値に対応している
Fiat-Shamirヒューリスティックを用いる場合、マークルルートをランダムエントロピーに用いてピックアップした時のマークルブランチもコミットする
これにより、検証者は、以下の統計的なproofを証明者から受け取る
1. 行(row, y座標)はほとんどdegree < 1000次多項式上の点により成り立っている。
2. 列(columun, x座標）はほとんどdegree < 1000次多項式上の点により成り立っている。
3. 対角線(g(x, x^1000)=f(x))はほとんどdegree < 1000次多項式上にある。
検証者はMerkle分岐が一致しているか、検証者が提供した点が実際にdegree-1000の多項式に対応しているかを検証する
つまり、かなり高い確率で対角線上の点がdegree < 1M次多項式と一致していることを検証することができる。
https://scrapbox.io/files/61dbaaf07d8bd700205d90d0.png
それぞれのrow、colmunは1000次多項式なのでそこから1010個のクエリは安全に取得できる。それぞれ30個ずつ計60個のrow、colmunをピックアップすれば60*1010個の点で多項式の存在を証明できる
これにより、例えばVerifierの検証ポイントが60600ポイントになる。（オリジナルは1Mポイント）
ただし、ProverはN*Nのレクタングル全体を計算してコミットしなければならないのでProverの計算複雑性はより増す。（10^18）
結果的に Dよりも小さいクエリで検証可能になったが、計算複雑性を改良する必要がある。
Proverの計算複雑性の最適化
このプロトコルの少し複雑なバージョンに移ってみましょう。
これは証明者の複雑さを$ 10^{18}から$ 10^{15}に減らし、さらに$ 10^{9}にすることができる
方針はモジュラー演算を使った効率化
具体的には、p = 1,000,005,001を対象とする。このモジュラスを選んだ理由は、
1. 最低でも1Bポイントは検証できるようにする必要があるため1Bより大きい位数。
2. 素数である
3. p-1が1000の偶数倍である。x^1000において、フェルマーの小定理より演算結果は1,000,006個になる
もし$ p-1が$ kの倍数であれば、$ x -> x^kの写像の値は$ \frac{p-1}k+1個に集約される
つまり、FRIプロトコルの「対角線」(x, x^1000)は折り返しのある対角線になり、y座標が1,000,006個であればOKということ
このようにして、$ g(x, x^{1000})の完全な評価要素は、~ 10^{15} 個になる
さらに、証明者はあるy座標をコミットするだけでOKにできる。
なぜなら、特定のrowはすでに1000ポイントを含んでいる(元のデータ自体に、任意の行にある1000個の点がすでに含まれている)からdegree < 1000次多項式を抽出できる
rowだけのピックアップに。colmunは1個。
https://scrapbox.io/files/61dbccdfca117d001d6a293e.png
検証者の計算複雑性は依然としてsublinearだが、証明者の計算複雑性は10^9まで減少し、クエリの数に対してlinearになった
ただし、多項式評価のオーバーヘッドがあるため、実際にはまだsublinear
Verfierの計算複雑性の最適化
再帰的アルゴリズムによるさらなる効率化を図る
これにより検証者の複雑さを2次関数から対数関数へとさらに下げる
多項式をxとyの次数が等しい2次元多項式に埋め込むのではなく、xの次数が2とか4とか小さな固定値にして分割する
つまり，f(x) = g(x, x^2) などと表現し，行のチェックでは，常にサンプリングした各行の3点（対角線から2点，列から1点）をチェックするだけでよいようする
これを再帰的に証明していくことで、次元数を半分にしていき、直接点をピックアップしても証明できるほどに小さな次元数になるまで繰り返す。
元の多項式が次数＜nであれば、行は次数＜2
つまり、行は直線）、列は次数＜ n/2 )
したがって，これは，次数 < n の多項式への近接性を証明する問題を，次数 < n/2 の多項式への近接性を証明する問題に変換する線形時間プロセス
さらに、コミットしなければならないポイントの数、つまり証明者の計算量は、毎回2分の1になる。
https://scrapbox.io/files/61dbd90b7a031b001dd94ed1.png
実際のFRIプロトコルは、他にもいくつかの改善点がある
2進ガロア体を使用している
行に使われる指数も2ではなく4が一般的
これらの変更により、システムの効率が上がり、その上にSTARKを構築しやすくなる
Soundness
健全性を計算すること、つまり、最適に生成された偽の証明が、与えられた数のチェックに対してテストをパスする確率がどれだけ低いかを決定すること
1,000,000 + k点を取るという単純なテストについては、簡単な下限があります。あるデータセットが、任意の多項式について、データセットの少なくとも一部pがその多項式上にないという性質を持っている場合、そのデータセットに対するテストは、最大で(1-p)^kの確率で合格します。
しかし，これは非常に悲観的な下限です．
例えば，同時に2つの低次多項式に50%以上近づくことは不可能ですし，最初に選択した点が最も多くの点を持つ点である確率は非常に低いものです．本格的なFRIの場合、様々な種類の攻撃が絡む複雑さもあります。
ここでは、Ben-Sassonらが最近発表した論文を紹介します。この論文では、STARKスキーム全体のコンテキストにおけるFRIの健全性特性について説明しています。
一般的には、STARKのD(x) ・ Z(x) = C(P(x)) チェックをパスするためには、無効な解のD(x)の値は、ある意味で「最悪のケース」である必要があり、有効な多項式から最大限に離れている必要があると考えられます。これは、そこまでの近接性をチェックする必要がないことを意味しています。
下限が証明されていますが、この下限は、実際のSTARKのサイズが1～3メガバイト程度であることを意味します。より強い下限が推測されていますが、証明されていませんので、必要なチェックの数は4分の1に減少します。
参考文献