はじめに
SNARKs, STARKs, Bulletproofs, Auroraなどが
privacy(Zcash) と scalability (Ignis, StarkDEX, scaling Ethereum)に貢献しています。今回はそれらの根底を支える証明PCPとPCP定理について紹介します。
NP (Non-deterministic Polynomial time)
計算量クラスの一つであるNPは以下のような対話型証明系で定式化できます。
言語LがNPに属するとは、ある多項式時間のチューリングマシンV（検証者）が存在して
xがLに属していればある証明者Pの証明が存在してVがその証明を受け入れるxがLに属していなければ全ての証明者Pの証明をVは拒絶する
が成り立つことです。
PCP(Probabilistically Checkable Proof)
計算複雑性理論における PCP とは、確率的検査可能証明系を持つ決定問題の複雑性クラスのことです。確率的検査証明とは対話型証明の一種で証明者は無限の計算資源を持つ全能の計算能力を持つ一方、検証者の方は限定的な計算能力を持ちます。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられます。
クラスPCPに属する問題においては、次が成り立ちます。
- 証明の中のたった数ビットの部分を知るだけ(検査)で証明が(概ね)正しいことが言えてしまう
それぞれの検査は証明が間違っていても最大1/2の確率で受理してしまいますが、何度も検査が通ればその証明は確率的に正しいことが言えます。
PCPの定義
言語Lが\text{PCP}(r(n), q(n))に属するとは、入力x \in \{0,1\}^nに対して以下が成り立つような多項式時間の検証アルゴリズム（検証者）Vを持つことです。入力x \in \{0,1\}^nに対するオラクル\piへのランダムアクセスを持つVの出力をV^{\pi}(x)と表します。V^{\pi}(x)=1のとき受理、V^{\pi}(x)=0のとき拒絶とします。
-
完全性:
x \in Lならばあるオラクル\piが存在してPr[V^{\pi}(x)=1]=1 -
健全性:
x \notin Lならば任意のオラクル\piに対してPr[V^{\pi}(x)=1]\leq \frac{1}{2} -
Vのオラクル\piへのランダムアクセスは入力x \in \{0,1\}^nに対して高々r(n)ビットのランダムなビット列で位置が定まる高々q(n)回のアクセス
PCP定理
PCP定理の主張は\text{NP}=\text{PCP}(\log n, 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(\log n, 1)
すなわち乱数列長を増やすほうが盗み見する部分をふやすより強力ということが上の式からわかります。つまりコインのトスを増やすほうが証明の部分にあたりを付ける場所（覗き見る場所）を増やすより強力ということが言えます。
