はじめに
SNARKs, STARKs, Bulletproofs, Auroraなどが
privacy(Zcash) と scalability (Ignis, StarkDEX, scaling Ethereum)に貢献しています。今回はそれらの根底を支える証明PCPについて紹介します。
PCPとは
計算複雑性理論における PCP とは、確率的検査可能証明系を持つ決定問題の複雑性クラスである。確率的検査証明とは対話型証明の一種で証明者は無限の計算資源を持つ全能の計算能力を持つ一方、検証者の方は限定的な計算能力を持ちまっす。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられます。このPCPは次のことが言います。
- 証明の中のたった数ビットの部分を知るだけ(検査)で証明が正しいことが言えてしまう
それぞれの検査は少なくとも確率\frac{1}{2}で拒否するが何度も検査が通れば、その証明は確率的に正しい
PCP(q(n),r(n))の定義
言語:L,検証者(oracle):V,任意入力:x \in {0,1}
-
完全性:
x \in Lならばあるオラクル\piでV(\pi,x)が確率１で受理 -
健全性:
x \notin Lならば任意のオラクル\piに対して$$V(\pi,x)$が$\frac{1}{2}$で拒否 -
サイズnの入力に対して検証者は高々、
q(n)回のコイン投げ、r(n)回のオラクルアクセスq:N→N ,r:N→N
PCP(Q,R) = \bigcup_{q \in Q,r \in R} PCP(q(n),r(n))
かんたんにすると,
- コインをr(n)回トスする
- proof
\piのq(n)bit分の部分に質問をする - これらの質問に対する結果をつかい多項式時間で検証をする。その後、0または１を返す。
PCP定理
NP=PCP[O(\log n),O(1)]
O(\log n)の乱数列とO(1)ビットの検索でNP問題がとける。これは入力サイズの対数程度の回数のコイントスを行い、定数のページ数を見るだけでNPが解けるいう意味で.多項式で解ける問題は何も証明はいらないのでP = PCP(1,1)右辺を拡張してPCP(1,log_n) = Pが成立
PCP(1,log_n) = PよりP \subsetneq NPから
PCP(1,log_n) \subsetneq PCP[O(\log n),O(1)]
乱数列長を増やすほうが盗み見する部分をふやすより強力ということが上の式からわかります。つまりコインのトスを増やすほうが証明の部分にあたりを付ける場所を増やすより強力ということが言えます。
