zk-STARKs | succinct proofs of computation
ZKPsとは
関数とそのoutputがpublicで、inputがprivateな状況下において、inputを明らかにすることなく確かにそのoutputがその関数のoutputであることを証明できること。
ブロックチェーンにおいて最新のブロックだけをダウンロードした時、そのブロックが確かに「そのブロックチェーンの最新ブロックであること」を証明する。フルノードが全ブロックチェーンをinputとし、正当性を検証する関数に通し、outputが最新ブロックのハッシュ値となる。
laptopだと計算に2週間かかる関数でもデータセンターなら2時間でできる場合、その関数をデータセンターに渡し、そのoutputがユーザーに返され、ユーザーはlaptopでそのoutputが正しいか（その関数のoutputかどうか）msオーダーで検証できる。
暗号化されたトランザクションの検証。この場合、xが暗号鍵ペアとなり関数を通すことで、正しく両者のbalanceが変化した場合outputが1を返す。
多項式の準備
データを100万次多項式にエンコードし、その多項式上の200万個の点を選ぶ。それらのうち100万＋1個の点があればデータは復元できる。（ラグランジュの補間公式）
逆に、100個までの点の選定で多項式は大きく変わる。このアルゴリズムはエラー増幅器に用いられる。
1<= x <= 1Mの整数xに対して、0<= P(x) <= 9となる多項式Pを考えると、シンプルなrange chekingによる検証ができる。つまり、1M個のxをinputにして0<= P(x) <= 9が成り立つか検証する。しかしこれでは1M回のステップが必要である。
0<= x <=9であればC(x)=0で、それ以外のxであればnonzeroとなる多項式C(x)=x(x-1)...(x-9)を考えると、上記の問題は1<= x <= 1Mの全てのxに対してC(P(x))=0となるPを知っていることを証明することに置き換わる。（Pは1M次）
さらに、Z(x)=(x-1)(x-2)...(x-1000000)とすると、1<= x <= 1Mの全てのxに対してC(P(x)) = Z(x)*D(x)となるようなPとDを知っていることを証明することに置き換わる。
例えば、1B個の1~10^9ドメインの$ x_0をランダムにピックアップし多項式を評価する。
C(P(x))を知っていれば、Z(x)は1M次式なので、long polynominal divisionやFFTs（高速フーリエ変換）によりC(P(x))/Z(x)からD(x)を計算することは難しくない。
3 step model
まずは、prover→verifier→proverの3ステップコミュニケーションが必要なモデルを考える。
Proverは、1<= x <= 1Bのxで評価したP(x)とD(x)をマークルリーフとしたルートをverifierに送る（0<= P(x) <= 9となる1M個のxとそれ以外の999M個のxを含むことになる）
https://gyazo.com/5aef823724f6f64fcb1cdb4a1603113d
Verifierは1B個のxで評価されたZ(x)を想定。つまり、Z(x)がvertification keyとして働く。（もし全てのZ(x)を保持しておくデータストレージがクライアントにない場合は、Z(x)のマークルルートのみを保持しておき、proverが全てのZ(x)に対するマークルブランチを送信する方法も可能）
verifierがコミットメント（マークルルート）を受け取った後、1~1Bの中から16個のxをランダムに選び、proverにそれらの値で評価されたP(x)とD(x)のマークルブランチをリクエストする。
proverはそのリクエストに応え、verifierは以下を検証する。
それらが以前渡されたマークルルートに対してマッチするかチェック
16個のxに対して 、C(P(x)) = Z(X) * D(x)であるかチェック
完全性(completeness)：もしProverがP(x)を知っていて、D(x)を算出していれば正しいproofを生成でき、以上の16チェックは全て通ることになる。
completeness：Proverの持っている命題が真であるならば、Verifierが真であることが必ず分かること。
健全性(soundness)：もしProverに悪意があり不当なP(x)を送った場合は$ 1-10^{-32}の確率で検知できる。これはハッシュ値が衝突するくらいの確率。
soundness：Proverの持っている命題が偽であるならば、Verifierは高い確率でそれが偽であることを見抜けること。
C(x)は10次多項式、P(x)は1M次多項式なのでC(P(x))は10M次多項式。
一般的に２つの異なるN次多項式はN個の点で一致する。
直線は1点で交わるし、2次曲線は2点で交わる。
この性質により異なる２つの多項式上の点は99％以上の確率で一致しないことが分かる。
xにおいてC(P(x))はZ(x)*D(x)と少なくとも990M個の点で異なる。
これを16個の点で評価するので1-10^(-32)になる。
つまり、以上のプロセスにより、ミリオンチェックが必要であった問題に対し、多項式を利用することで1回の検証で99％の精度まで高めることができた。計算量は多くなり、精度も1％下がり、3回のコミュニケーションが必要になったが「1回の検証」に集約することができた。
Fiat-Shamir heuiristicを用いたnon-interactiveなproof
まずProverはP(x)とD(x)をマークルリーフとして、マークルルートを生成する。
マークルルートは、どのブランチをproofとして提供するかのランダム値として利用する。
proofはそのマークルルートとそのエントロピーを利用したマークルブランチ。
データからマークルルートを計算するプロセスとそれからauditされるブランチの選定はProverサイドで計算されている。
Proverが不正な証明（不正なinputで正当な証明）をするためにはマークルルートのエントロピーにマッチするマークルブランチを繰り返しトライするしかない。正当なproofの確率は1-10^(-32)。
フィボナッチ数列の1M番目のZKPを考える
C(x1, x2, x3)=x3 - x2 - x1、P(x)をフィボナッチ項、C(P(x), P(x+1), P(x+2))=0となるPを知っていることを証明すること。
からの、C(P(x), P(x+1), P(x+2)) = Z(x) * D(x)となるPとDを知っていることを証明すること、に置き換えられる。
ZKPするためには、マークルルートとそれに対応するP(x)、P(x+1)、P(x+2)、D(x)のマークルブランチ、さらにP(0)=P(1)=1となるマークルブランチをproofとして提示する。
計算効率化のために有限体上で計算すべき。
soundnessに関する問題
もし不正なProverが1M次式のP(x)と9M次式のD(x)の代わりに、P,Dの低次元多項式上にない値をコミットした場合は、不正なC(P(x))は正当なC(P(x))と少なくても990M点で一致しない必要があり、これはより効率的な攻撃を促す。
例えば、攻撃者が全てのxからランダムな値pを生成し、d=C(p)/Z(x)を計算し、P(x)とD(x)の代わりにこれらの値をコミットすると低次元な多項式上にはない値であるが、検証を通ってしまう。