STARKs Part II
This article is the Japanese translation of
[STARKs, Part II: Thank Goodness It's FRI-day](https://vitalik.ca/general/2017/11/22/starks_part_2.html) originally written on 2017 Nov 22.
Eli Ben-Sasson さんに引き続き、手助け、説明いただき、多大なる感謝をもうしあげます。ならびに、Justin Drake さんの査読にも感謝いたします。
このシリーズの[前回の投稿](/ethereum/411-STARK1.md/)で、計算の端的かつ明確な証明においてとても興味深いものを見ました。
100万番目のフィボナッチ数を知っていることの証明に、多項式の合成や分割を含んだ技術を用いました。
しかし、重要な事項の説明の途中で筆をおいていたことともいます。
それは、『低次数テスト』の問題と呼ばれており、STARKs プロトコルの一番複雑な部分です。
問題をもう一度始めから考えてみましょう。
点の集合が与えられ、それらはすべて $ \lt D $ 多項式（ $D$ 次未満多項式）上にあるかどうかという命題を考えましょう。
（つまりは、 $deg \lt 2$ ならば、直線上にあることを意味し、 $deg \lt 3$ ならば放物線上にある、といった次第です。）
あなたは実際にこの命題が正しいことを証明する、端的かつ明確な確率的証明をひとつ作りたいのです。
もし、全ての点が同じ $D$ 次未満多項式上にあることを検証したい場合、
あなたは、もしひとつの点でも検査が失敗した場合、他のすべての点が多項式上にあるにもかかわらず、その一点が多項式上にないことが常にわかるように、
あらゆる検査を行いたいと思うことでしょう。
しかし、あなたが選択可能な検査は、確率的な検査であり、例えば「少なくとも90%の割合で保証される」ような検査なのです。
もし多項式上のすべての点を処理する能力があるならば、問題は簡単です。
しかし、たくさんある点のうち、限られた少しの点しか見ることができない、という状況であればどうでしょう。
つまりは、検証者であるあなたが検証したい点を依頼することができ、
証明者がプロトコルとしてそれを提供し、探索の総数には制限がつくような状況だとしたらどうでしょうか。
問題は、『ある確定した次数が与えられたとして、その下で検査を行うには、いくつの点が必要になるか』となります。
明らかに、 $D$ 点では足りません。
$D$ 点は、まさに $D$次未満の多項式を一意なものとして定義するのに必要な点の数であり、
上の図にもみられるように $D+1$ 以上の点が手がかりとなるでしょう。
与えられた値の集合が、ある同じ $D$ 次未満多項式上にあるかどうかを探索し検査するようなアルゴリズムはそれほど複雑なものではありません。
まず無作為に $D$ 個の点からなる部分集合を選び、ラグランジュ補間等を使い、それらすべての点を乗せた一意な、 $D$ 次未満の多項式を復元します。
次に、無作為にもう一点選び、それらが同じ多項式上にあるか見れば良いのです。
今行っているのは『近接のテスト』だということには注意してください。
というのは、大部分の点が、同じ低次元の多項式上にあり、少しの点が多項式上にないような状況で、かつ $D+1$ 個の点のサンプルが、この多項式上にない少しの点を悉く外しているという可能性が常にあるのです。
特に、もし $D+k$ 回の探索を行い、少なくともある割合 $p$ 以上の点の集まりが、他の点とは異なり、同じ多項式上にないような場合、
テストは $(1-p)^k$ の確率でのみ成功するでしょう。
しかし、前回の記事でみた例のように、 $D$ の値が非常に大きく、 $D$ 未満の探索で、多項式の次数を検証したい場合どうすればよいのでしょうか。
もちろん、これは、上に述べた簡素な議論から（つまり、 $k \le D$ 個の点が、すべて少なくともある一つ以上の無数のD次未満多項式上に乗っており、正しい多項式がなんであるのか決定すらできないため）、直接的に検証を行うのは不可能です。
しかし補助的なデータを用いることで、間接的な方法を用いた検証が、実は可能であり効率の観点で莫大な恩恵を受けることができます。
その方法とは、まさに新しいプロトコルとして知られた、[FRI](https://eccc.weizmann.ac.il/report/2017/134/) ("Fast RS IOPP", RS = "[Reed-Solomon](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Constructions)", IOPP = "Interactive Oracle Proofs of Proximity") や、
probabilistically checkable proofs of proximity (PCPPs) と呼ばれる初期の設計などのことです。
それでは、この新しいプロトコルを見ていきましょう。
# A First Look at Sublinearity
これが結局のところ可能だということを証明するために、
比較的単純なプロトコルからはじめましょう。
大変貧相となるトレードオフがありますが、部分線形な検証の複雑度の目的を達成することができます。
つまりは、 $D$ 未満の探索で、 $D$ 次未満の多項式への近接を証明することができます。
（そして、つまりは $O(D)$ の計算量で証明を計算することができるのです。）
アイデアは次の通りです。
$N$ 個の点があるとしてください。（例えば $N$ を10億とでもしましょうか。）
そしては、それらの点はすべて、ある1,000,000次未満の多項式 $f(x)$ 上にあるものとします。
我々は、その多項式を、『二変数に拡張 bivariate』し、
$$g(x,x^{1000}) = f(x)$$
を満たすような $g(x,y)$ を作ることができます。
つまり $f(x)$ の $k$ 番目の項に対し $x^{k\%1000}y^{floor(\frac{k}{1000})}$ を与えることで構築します。
（例として $1744x^{185423}$ に対して $1744x^{423}y^{185}$ を与えます)。
$y=x^{1000}$ とおけば、 $1744x^{185423}$ と $1744x^{423}y^{185}$ は一致することがわかります。
証明の最初のステージにおいて、証明者は、正方領域 $\{1,2 .. N\} \times \{x^{1000} : 1 \le x \le N\}$ 上の $g(x,y)$ の評価をマークル木へコミットします。
つまり、10億個のx座標を列として取り、 $y=x^{1000}$ によって対応する 10億個のy座標を行としてとったものです。
対角線上の $g(x,y)$ の値は、 $g(x,x^{1000})$ となります。
次に検証者は、無作為に数十個の行と列を選びます。
（証明者と検証者のやりとり無しの non-interactive な証明をしたい場合は、正方領域のマークル木のルートハッシュを、疑似乱数のソースとして使うことができるでしょう）
そして、各行と各列にたいして、今検証者がそれぞれ 1010 個の点のサンプルを求め、要求をみたすような点というのは、必ず対角線上にあるということを検証したいとします。
証明者は、これらの点について、証明者がもともとコミットしたデータの一部であることを証明するマークル枝でもって、その情報を返信しなければなりません。
検証者は、それがマークル枝がマークル木の一部であることち、
証明者が提供した点が、実装ひとつの1000次多項式上に一致するかを検査します。
これは、検証者に対して、次の三つの性質を満たす統計学的な証明を与えます。
1. ほとんどの行が、1000次未満の多項式上の点によって構成されたものである。
2. ほとんどの列が、1000次未満の多項式上の点によって構成されたものである。
3. 対角線上の点のほとんどが、これらの多項式上にある。
これによって、検証者は、1,000,000次未満の多項式 $f(x)$ での検証に相応することをしていることがわかるのです。
もし、各行と列を30ずつ選んだとしたら、検証者は各ケースについて、1010個、つまりは、 $(30+30) \times 1010 = 60600$ 個の点にアクセスする必要があり、
元の 1,000,000個の点より少なくなります。
計算が続く限りは、1000次未満多項式を補間するには、そのオーバーヘッドがありますが、
多項式への補間は、部分的に二次形式にできるので、アルゴリズム全体としては、検証するのに必要な計算量の空間は、それでも部分線形となります。
証明者の計算複雑度はより高くなります。というのは、証明者は $N\times N$ の正方領域全ての計算を行わなくてはなりません。
これは、$10^{18}$ の計算労力が必要となります。（実際は、多項式の評価のため、これ以上となります）
これらすべてのアルゴリズムにおいて、計算を証明するということは、
潜在的にただ計算することより複雑なものと言えます。
しかしながら、これからみていくように、ここまでオーバーヘッドが高くなる必要はありません。
# A Modular Math Interlude
我々の欲するところのより複雑なプロトコルの話に入る前に、
少しだけ合同算術の世界へと話を脇道にそれる必要があるでしょう。
たいていの場合、多項式を考えるときは、学校で習ったような、通常の数の加減乗除を考えます。
しかし、数学者が発見したこととして、これらの加算や乗算、減算や除算を定義する方法というのは、
これら演算子の自己一貫性をもつ唯一の方法ではない、ということです。
最も単純な別の方法としては、合同算術を用いた次のような定義です。
ここで、 $\%$ は割った余りを返す演算子です。
$$ x + y \Rightarrow x + y \% p $$
$$ x - y \Rightarrow x - y \% p $$
$$ x ^ y \Rightarrow x ^ y \% p $$
$$ x \times y \Rightarrow x \times y \% p $$
$$ \frac{x}{y} \Rightarrow xy^{p-2} \% p $$
例えば $p=7$ とすると、
- $5+3=1$
- $1-3=5$
- $2\times 5 = 3$
- $\frac{3}{5} = 2$
となり、自己一貫性をもちます。
少し複雑な等式、例えば『分配則』なども成り立ちます。
$(2+4)\times 3$ と $2\times3 + 4\times3$ のどちらを評価しても $4$ となります。
$(a^2-b^2) = (a+b)(a-b)$ のような公式もこの新種の算術の中で成立します。
除算は一番大変な部分です。というのは、我々は通常の割り算を適用できません。なぜならば、通常の割り算では、商は分数をとりえますが、
この新しい算術では、$\frac{3}{5}$ の場合のように必ず商が整数となることを期待しているからです。
上で与えた除算の公式は[フェルマーの小定理]()の結果としてえられるものです。
この定理は、任意の非零数 $x$ に対して、 $x^{p-1} \% p = 1$ が成り立つというものです。
これが意味することは、 $x^{p-2}$ という数に $x$ をかけると、 $1$ となるということです。
つまり、 $x^{p-2}$ と $\frac{1}{x}$ は同じ数だと言えるわけです。
少しより複雑なものとなりますが、この合同算術の割り算を高速に実装した python コードは[こちら](https://github.com/ethereum/py_ecc/blob/b036cf5cb37e9b89622788ec714a7da9cdb2e635/py_ecc/secp256k1/secp256k1.py#L34)にあります。
これは、[extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) を使用しています。
今われわれが構築したこの新しい算術のシステム上の合同数学では、
通常の算術が自己一貫性ともつのと全く同じように自己一貫性をもつため、
この『体』（数学用語：加減乗除を含んだ数体系）上で、通常の数学で行うことのできる同じような構造について、多項式を含め、同様に議論することができます。
暗号家は、合同算術上の（より一般的に『有限体』上での）数学を仕事で用いることをこよなく愛しています。
というのは、どんな計算をしても、かならず、結果はある上限内に収まり、
与えられた集合 $\{0,1,2, .. ,p-1\}$ の枠からはみ出すようなことは、決しておこりえません。
フェルマーの小定理は、もうひとつ興味深い結果をもたらしてくれます。
もし、$p-1$ がある数 $k$ の倍数だとしたら、関数 $x \mapsto x^k$ は、より小さい『像（値域）image』を持ちます。
つまりは、関数を評価した値は、必ず、 $\frac{p-1}{k}+1$ 個の異なる値のどれかにしかなりません。
（これは次の簡単な計算による。 $x^{p-1} \% p = 1$ は、 $\frac{x^{p-1}}{p} \equiv 1\ mod\ p$ であり、
$(x^k)^{\frac{p-1}{k}+1-1} \equiv p \equiv 0\ mod\ p$ となる。
そのため、 $x^k$ は位数 $\frac{p-1}{k}+1$ の巡回群となる。）
例えば、関数を $x \mapsto x^2$ 、 $p=17$ とすると、9個の異なる値しか取ることができない。
乗数を少し大きくなると、より著しい結果となる。
例えば、
$x \mapsto x^8$ とすれば、たったの $3$ 個の値しか取らず、
$x \mapsto x^{16}$ とすれば、たったの $2$ 個の値しか取らず、 $0$ に対しては、 $0$ を返し、その他はすべて $1$ を返す関数となってしまいます。
# Now A Bit More Efficiency
さて、少しより複雑なバージョンのプロトコルへみるところへ入っていきましょう。
ここでは、証明計算の複雑度を $10^{18}$ から $10^{15}$ へと、さらに $10^{9}$ まで減らします。
最初に、通常算術ではなく、合同算術上で、多項式への近接を検査します。
前回の記事でみたように、この算術を用いるのは、200,000桁の数へと膨れ上がるような計算を STARKs 上では排除する必要があります。
ここでは、我々のプロトコルをとても非効率にするような副作用として、合同算術上の乗数関数が『小さな像』を持つという性質を使います。
特に今は、 $p=1,000,005,001$ と仮定します。
この除数を選んだ理由としては、
1. 10億よりおおきく、少なくとも10億個の点の検査を行うことができる
2. 素数である
3. $p-1$ が 1000 の倍数である
の三つです。乗数 $x^{1000}$ の像のサイズは $1,000,006$ です。
つまり、関数 $x \mapsto x^{1000}$ は $1,000,006$ 個の異なる値しか取れません。
この事実から、次のことがわかります。
『対角線』 $(x,x^{1000})$ は、今、巡回する対角線となるのです。
つまり、行数はたったの 1000,006 しか必要ありません。
つまり、全てを評価するのに必要な計算量は約 $10^{15}$ まで減るということになります。
今から見るように、さらに減らすことができます。
われわれは、証明計算をただひとつの列上の g の評価だけをコミットするだけで良いという風にすることができます。
ここで使われている鍵となるトリックとは、
行を計算した時点で、データにはすでに 1000 個の点の評価した値が含まれています。
そのため、それらをサンプルし、必要な1000次未満の多項式を導き、その多項式上で、今評価したい列の点に相応する点を代入して検査してやればよいわけです。
そして、その列自体が、1000次未満多項式であることを検査します。
検証の計算複雑度は、部分的線形のままですが、探索数を線形にすることで、証明の計算量を $10^9$ まで減らすことができました。
（しかし、評価のオーバーヘッドがあり、実際はまだ、線形より大きな計算量を必要とします）
# And Even More Efficiency
証明者の計算量は基本的な下限まで落としましたが、
検証者の計算量はまださらに、二乗オーダーから対数オーダーへと落とすことができます。
これはアルゴリズムを再帰的に変更することで行います。
上で示した最後のプロトコルから始めましょう。
x と y の次数が等しいような 2引数多項式へ落とすのでなく、
x の次数の上限が小さい定数であるような 2引数多項式へ落とし込んでみましょう。
例えば、ここでは、定数を 2 とし、 $f(x) = g(x,x^2)$ と置いて考えてみましょう。
このことにより、行の検査が、たった（２つは対角線上から、一つは列からサンプルした）3点を検査するだけでよくなります。
もし元の多項式が、n次未満多項式だとすれば、行は2次多項式となり、列は n/2 次となります。
さてこのようにして、n次未満の多項式への近接を証明する問題を、n/2次未満の多項式への近接を証明する問題へと変換することができました。
さらに、コミットする必要のある点の数は、つまりは証明者の計算量は、さらに 2 で割ることができます。
（Eli Ben-Sasson はこの性質をもつ FRI と 高速フーリエ変換 FFT を好んで比較しています。違いとして鍵となるのは、FFT と異なり、
再帰の過程で、二つに部分問題に分岐するのでなく、一つの部分問題をもたらすだけだということです）
このようにして、列を再帰計算により、十分に小さくなるまで、どんどん小さくすることが可能であり、
計算複雑度はトータルで、 $n + \frac{n}{2} + \frac{n}{4} + ... \approx 2n$ となります。
実際はプロトコルを何回か繰り返す必要があります。
というのは、攻撃者が、プロトコルのラウンド一回をチートする重要な可能性がまだあるからです。
しかしながら、これをしたところで、証明はさほど大きくなりません。
検証の計算量は対数オーダーとなりますが、
マークル木の証明のサーズを数えたならば、 $log n^2$ まで上昇します。
実際の FRI では、さらに修正を加えています。
例えば、2値[ガロア体](https://en.wikipedia.org/wiki/Finite_field#Explicit_construction_of_finite_fields) を使用しています。（これは有限体の変種で、[ここ](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)で話をした12次拡大体と同じものですが、今は 除素数は 2 となります。）
また、行の多項式の次数は 2 でなく 4 です。
これらの修正により効率性が上昇し、STARKs を作りやすい環境を提供してくれます。
しかしながらこれらの修正というのは、アルゴリズムの仕組みを理解する上で、必要なものではありません。
実際ここで示したようなシンプルな FRI でもって、 STARKs を実装することは可能です。
# Soundness
ここで、計算の健全性をみるというのは、この場においては、龍の棲家のようなものだと警告しておきます。
健全性とはつまり、ある与えられた数の検査に対して、贋作の証明が通る確率がどれほど低いかを決定することです。
$1,000,000 + k$ 個の点を取ってくるようなシンプルなテストで、
ある下限値があります。
もし与えられたデータセットが『データセットの少なくとも $p$ の比率の部分がその多項式上にない』という性質を持てば、
そのデータセット上のテストは、高々 $(1-p)^k$ の確率で通ることでしょう。
しかしながら、もしとても悲観的な下限値であったとしても、
つまり、例えば、二つの多項式に対して、同時に50%以上近接するということは不可能であり、
最初にあたなが選んだ点がほとんどの点でその値をとるというようのものとなるような確率はとても低いのです。
FRI の全実装には、さまざまな攻撃に対する複雑度もまた考慮されています。
[ここ](https://eccc.weizmann.ac.il/report/2016/149/)に Ben-Sasson らによる STARK scheme 全体にわたる FRI の健全性を記述した最近の記事があります。
一般論として、良い知らせは、 $D(x)Z(x) = C(P(x))$ の検査を STARK 上パスするためには、無効な解に対する $D(x)$ の値であれば、それは「最悪の状況」である必要があるということです。最悪の状況であるとは、つまるところ、どのような有効な多項式からも、最大限離れている必要があるということです。
このことより、近接の検査をさほどたくさんする必要がない、ということがわかります。
証明された下限値というものがありますが、
これらの値が意味するところは、実際の STARK は、~1-3 メガバイトのサイズを持つ必要があるということです。
4 の数によって、検査に必要な数が、より強い制限によって減らされるということは、予想されていますが、まだ証明されていません。
このシリーズの[第3回目](/ethereum/413-STARK3.md/)となる次回の記事では、
STARKs を実際に作りが得るための大部分をみていくこととなります。
どのようにして、フィボナッチ数の例だけでなく、任意の計算に関する命題を証明するために、多項式検査による制約条件を構築するのかというのをみていきます。