Incrementally Verifiable Computation：効率的に証明をつなげる

Table of Contents

はじめに

本稿では[1]で提案されたIVC (Incrementally Verifiable Computation)と呼ばれる証明システムについて解説します。この証明システムは証明の長さを変えずに合成することが特徴です。途中までの証明を長さを変えずにつなげることができ、この概念がPCD[3]他の証明システムに応用されています。

この論文はIVCという証明をつなげるという概念を提唱し、「知識証明」の仮定によって効率の良い証明システムが構成できることを示しました。
しかし証明システムの具体的な構成はこの論文中では行われておらず、後のPCD[3]等によって初めて与えられたことに注意してください。

概要

この証明システムの主な動機は

長い計算のうち途中までの計算が正しいことを伝えたい

ということです。愚直な方法としては

計算過程を全て覚えておいてそれを相手に送る

という方法が考えられます。しかしこの方法は証明者が送る証明に必要な空間が時間に比例してしまうので長い計算の場合に検証者が必要とする空間や時間が大きくなってしまうため非効率的です。この問題を解決するため、この論文ではPCPシステム (probabilistically checkable proof system)を応用したCS 証明(Computationally sound proof, CS proof) という方法を用いています。 PCPシステムとは確率的なアルゴリズムを用いることで指数的な長さの証明の検証を多項式時間で行うことが可能となる証明システムのことです。詳しくは[2]の記事を参照してください。そしてCS証明とはPCPシステムを更に拡張して証明の長さを指数的な長さから多項式で抑えられるようにした証明システムです[4]。

計算過程の証明をそのままCS証明に変換すると証明したい計算過程にかかる時間以上の記憶領域と時間がかかってしまいます。またCS証明の証明をつなげることに伴って

計算量的に健全な証明システムでは、間違った証明と正しい証明を正確に区別できない
ランダムオラクルを用いることができない

という課題が挙げられます。

1つ目の課題について、「計算量的に健全な証明システム」では健全性に関して

証明者の計算能力が多項式時間以下であるという仮定のもとでは十分な健全性が成り立つ

ということのみが保証されています。
したがってそのまま証明を繋げようとしても検証者はそれまでの証明が本当に正しい証明なのかどうか正確に判断することができません。
そこでこの論文ではCS証明が「知識証明」(proof of knowledge)という良い性質を満たす証明を仮定することで、証明の正当性を保証しています。

2つ目の課題について、ランダムオラクルを用いたCS証明を繋げようとすると前の証明からは「あるランダムオラクルを使うとそれまでの証明が正しいらしい」ということが分かるだけで、同じランダムオラクルへのアクセスを使うことができない次の証明者は前の証明が本当に正しいのかどうか判断することができません。そのためこの論文ではランダムオラクルを用いた非対話CS証明の代わりにランダムな文字列を用いる(CRSモデルでの)非対話CS証明の存在を仮定しています。非対話CS証明のシステムではランダムオラクルを用いているものしか存在しません。しかしランダムオラクルのアクセスをハッシュ関数の存在とランダムな文字列へのアクセスに置き換える変換[5]が存在することがこの仮定の動機になっています。

まとめるとこの論文では

ランダムオラクルを用いない非対話CS知識証明の存在

を仮定した上で長さを変えずに証明をつなげるIVCという証明システムを構成しています。そしてその結果

「知識証明」の仮定によって証明の時間的、空間的効率性を実現できること

を示しています。

記号の定義

$M$ ：チューリングマシンを表す。計算の途中でその時点での状態表示を出力できるとする。
$\alpha$ -増加のタイムライン：タイムラインを表す整数列 $\{t_j\}$ であって $t_j - t_{j-1}\leq \alpha$ が全ての $\alpha$ について成り立つもの。
$\alpha$ -増加出力のチューリングマシン： $\alpha$ -増加のタイムラインの各時点で計算の時点表示を出力するチューリングマシン。
実現可能なコンパイラ：二入力の多項式時間の確率的アルゴリズム $C$ であって入力 $(M, k)$ ( $|M| < k$ )に対して出力 $C(M, k)$ が $k^{c}$ -増加出力のチューリングマシンを用いる空間が $k^{c}$ 未満であるもの( $c$ は定数)。

つまりこのコンパイラはチューリングマシンを受け取ると、効率的な空間を用いてそれと同程度の時間間隔で計算過程を出力するチューリングマシンに変換します。

IVCの定義

IVCとは実現可能なコンパイラ $C$ と多項式時間のチューリングマシンである検証者 $V$ の組であって、入力であるどんなチューリングマシン $M$ とセキュリティパラメータ $k$ に対しても以下の三つの性質を満たすものです。

コンパイラは $C$ チューリングマシン $M$ とセキュリティパラメータ $k$ を入力としてのチューリングマシン $M$ の計算過程と証明の組を順に出力します。このときの $j$ 番目の出力を $M$ の $j$ 番目の計算過程の出力 $m_j$ とその計算過程の正当性を示す証明 $\pi ^r_j$ の組 $(m_j, \pi ^r_j)$ として

正当性： $m_j$ が本当に $M$ の $j$ 番目の計算過程の出力である。
完全性：出力された証明 $\pi ^{r}_j$ を検証者 $V$ が必ず受理する、つまり $V(M, j, m_{j}^r, \pi ^{r}_{j}, r) = 1$ が成り立つ。
計算量的健全性：計算能力の限られた証明者は、偽りの計算過程に対して検証者を高い確率で納得させる証明を求めることができない。
つまり入力 $r$ に対して限られた時間内ではどんな機械を使って得た出力 $(j, m^{'r}_{j}, \pi _{'j}^{r})$ に対してもチューリングマシンの長さ $k$ が十分大きい場合に $\text{Prob}[m_j \neq m^{'r}_j \land V(M, j, m_{j}^{'r}, \pi ^{'r}_{j}, r)=1]< k^{-c}$ を満たす。

知識抽出の性質によって健全性が保証されます。上で述べたようにCS証明ではランダムオラクルを用いたものが多く、CRSモデルでのこのようなCS知識証明は実際には存在しませんが、この存在を仮定してIVCを構成します。

非対話CS知識証明の定義

CRSモデルにおける非対話CS知識証明とは証明者 $P$ と検証者 $U$ の組 $(P,U)$ であって入力である全てのチューリングマシン $M$ に対して以下の性質を満たすものです。 $c, c_1, c_2, K'$ を定数として $K'$ は $k$ に依存するとします。

効率的な証明者: $\text{time}_P (M,x,w,r) = k^{O(1)}$
証明の長さが一定: $|P(M, x, w, r)| = k$
効率的な検証: $\text{time}_U (P (M,x,w,r),M,x,r) = k^{c-1}$
完全性: $U (P (M,x,w,r),M,x,r) = 1$
知識抽出性: 証明にかかる時間が $K'$ 以下で成功確率が $\text{Prob}[U(P'(M, x, w, r),M, x, r)=1] =\alpha > 1/K'$ を満たす証明者 $P'$ に対して、 $P'$ とやりとりを行う知識抽出機(エクストラクター) $E_{P'}$ が存在して、その成功確率が $\text{Prob}[w\leftarrow E_{P'}(M, x)| M(x, w)=1]>1/2$ を満たし、エクストラクター $E_{P'}$ の動作時間は証明者の計算時間の $k^{c_2}/\alpha$ 倍以下となる。

最後の知識抽出性を満たす証明を「知識証明」(proof of knowledge)と呼び、証明システムの健全性が保証されます[5]。

IVCの構成

ここでは非対話CS知識証明 $(P,U)$ を用いてIVCを構成します。

言語とチューリングマシンの定義

まず証明システムの言語 $\mathcal{L}_c$ を以下のように帰納的に構成します。ここで $|M|=k$ で $s$ は計算状況を表し、長さは全て $|s|=k$ です。

言語 $\mathcal{L}_c$ はチューリングマシン $T_i$ とメッセージ $x = (M, s_1, s_2)$ の組で $T_i$ が $(x, w)$ を $k^{c}$ 以内に受理する様な長さ $3|M| = 3k$ の証明 $w$ が存在するとき $(T_i, x) \in \mathcal{L}_c$ とします。
チューリングマシン $T_i$ は以下のように帰納的に定義します。
$T_0$ ： $x = (M, s_1, s_2)$ として $((M, s_1, s_2),w)$ を入力として受け取り、チューリングマシン $M$ を計算状態 $s_1$ から $1$ 秒間動作させて計算状態 $s_2$ になるかどうかを検証します( $w$ は無視する)。
$T_{i+1}$ ： $x = (M, s_1, s_3), w = (p_1, p_2, s_2)$ として $(x,w)$ を入力として受け取ります。そして $p_1, p_2$ がそれぞれ $(T_i, (M, s_1, s_2)) \in \mathcal{L}_c, (T_i, (M, s_2, s_3)) \in \mathcal{L}_c$ の証明であるかどうかを検証します。ここで $p_1, p_2$ は非対話CS知識証明の証明者 $P$ による証明です。

この定義から言語 $\mathcal{L} _c$ はその要素 $(T_i, (M, s_1, s_2)) \in \mathcal{L}_c$ が状態 $s_1$ から $2^i$ 秒間チューリングマシン $M$ を動作させると $s_2$ になるような言語となります。

定義がwell-definedであること

言語 $\mathcal{L} _c$ とチューリングマシン $T_i$ の定義がwell-definedであることを確認します。

非対話CS知識証明 $(P,U)$ が存在することを仮定すると
$(T_{i+1}, (M, s_1, s_3)) \in \mathcal{L}$ であるとき
この $P$ を用いて $k^{O(1)}$ の時間で効率的な証明を構成できます。

また非対話CS知識証明の証明者 $P$ が出力する証明 $p$ の長さは $|M| = k$ なので
$\mathcal{L}_c$ の全ての証拠 $w = (p_1, p_2, s_2)$ の長さは全て $k+k+k = 3k$ です。

以上で言語 $\mathcal{L} _c$ とチューリングマシン $T_i$ の定義に矛盾がないことを確認できました。

IVCの構成

非対話CS知識証明 $(P,U)$ とそれを用いて構成した言語 $\mathcal{L} _c$ によって以下のように実現可能なコンパイラ $C$ 、検証者 $V$ の組 $(C,V)$ であるIVCを構成することができます。入力されたチューリングマシンを $M$ セキュリティパラメータを $k=|M|$ とします。ここで入力されるチューリングマシンの出力までにかかる時間 $t$ について $2^k \geq t$ を仮定します。

コンパイラC
チューリングマシンMに対して上で定義した言語\mathcal{L} _cの構成の通りに初期状態から順に計算過程とその非対話CS知識証明の証明者による証明を構成していきます。
ノードが(非対話CS知識証明の証明者による)証明、葉が計算過程となるような木グラフを考えると、この計算は葉から帰りがけの順に深さ優先探索を行なって順に計算を行うことに相当します。
ここで各ノードを計算するためにはそのノードの子を全て計算し終えている必要がありますが、
1. 一つのノードが二つの親によって共有されているため、二つの子ノードのうち一方の計算はすでに終わっていて、もう一方の子ノードの証明を計算すれば良いので各ノードの計算のために新たに必要となる子ノードの証明の計算回数は木グラフの深さとなること
2. $2^k \geq t$ であること及び言語 $\mathcal{L} _c$ はその要素 $(T_i, (M, s_1, s_2)) \in \mathcal{L}_c$ が状態 $s_1$ から $2^i$ 秒間チューリングマシン $M$ を動作させると $s_2$ になるような言語であることから木グラフの深さは $k$ 未満であること
3. 各ノードの計算にかかる時間は非対話CS知識証明の証明者による計算時間なので $k$ の多項式となること

を合わせると $k^{O(1)}$ 時間ごとに木グラフの葉の計算が終わり、計算過程が出力されることが分かります。
従ってコンパイラ $C$ は実現可能なコンパイラです。

検証者 $V$
メッセージ $(T_{i+1}, (M, s_1, s_2))\in \mathcal{L}$ と $(T_{i+1}, (M, s_2, s_3)) \in \mathcal{L}$ であることを示す証拠 $w = (p_1, p_2, s_2)$ を受け取って本当に $(T_{i+1}, (M, s_1, s_3)) \in \mathcal{L}$ であるかどうかを検証します。
非対話CS知識証明の定義より検証者 $U$ はそれぞれ $k^{c-1}$ 時間以内に証明 $p_1, p_2$ を用いてそれぞれ $(T_{i+1}, (M, s_1, s_2))\in \mathcal{L}$ , $(T_{i+1}, (M, s_2, s_3)) \in \mathcal{L}$ であるかどうかを検証を行うことが可能なので $w = (p_1, p_2, s_2)$ の検証にかかる時間は $k^{c-1} + k^{c-1} < k^c$ 以下となり、検証者の計算時間は多項式で抑えることができます。

さらにセキュリティパラメータと入力 $k$ の間に制約を加え、非対話知識証明の知識性を用いることでIVCの計算量的健全性を示すことができます。

ランダムオラクルモデルでの知識証明の性質を持つ非対話CS証明

IVCの構成ではランダムオラクルを使わずに知識証明の性質を持つ非対話CS証明の存在を仮定してきましたが実際にはこのような証明システムは存在しません。一方で非対話CS証明のエクストラクターは証明の安全性を保するためにしか用いられず、実際の証明システムの中には現れません。したがって非対話CS証明のエクストラクターがランダムオラクルを用いていてもIVCを構成することが可能です。
そこで論文ではランダムオラクルモデルでの知識証明の性質を持つ非対話CS証明を構成し、これを用いることで（安全性の保証は不完全であるけれども）実際にIVCを構成できることを示しています。
詳しくは元論文[1]の4章を参照してください。

　まとめと感想

この論文は具体的な証明システムの構成は与えていませんが計算をつなげることによって知識証明の性質を仮定することで時間的、空間的に効率の良い証明システムをIVCを構成できることを示しました。
これがどのように応用されるかはPCD[2]などを参照してください。

ところで私はこの論文を読んで勝手にこの論文中の二分木の構成がサヴィッチの定理[7]の証明にとてもよく似ていると思いました。

サヴィッチの定理 : NSPACE $(f(n))\subseteq$ DSPACE $(f^2(n))$

この定理は「 $f(n)$ の領域で動作する非決定性チューリングマシンの動作を高々 $f^2(n)$ の領域で動作する決定性チューリングマシンでシミュレートできること」を主張しています。
愚直に非決定性チューリングマシンの動作をシミュレートしようとすると遷移先の数は指数爆発してしまい、動作に必要な領域も大きくなってしまいます。
しかしこの問題を遷移可能性問題とみなし、半分の時間で中間の状態を介して遷移し得るかどうかを再帰的に調べることで $f^2(n)$ 空間の決定性チューリングマシンによってシミュレートすることができます。
この再帰的な計算はIVCの木グラフの構成と似ており、計算状況を考えている点も同じです。

この論文はブロックチェーン技術が発展するより前に書かれているので、サヴィッチの定理の証明を元にして書かれてたのではないかと勝手に想像しました。
私が勝手に想像しているだけなので実際には全く関係がないかもしれません。

理解が曖昧な箇所も多いためこの記事に誤りを見つけたら教えて下さい。

参考文献

[1] Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency [https://iacr.org/archive/tcc2008/49480001/49480001.pdf]
[2] PCP定理〜計算理論とゼロ知識証明をつなぐ〜 [https://tech.hashport.io/1810/]
[3] Proof-Carrying Data and Hearsay Arguments
from Signature Cards [https://www.cs.tau.ac.il/~tromer/papers/pcd.pdf]
[4] Computationally Sound Proofs [https://epubs.siam.org/doi/abs/10.1137/S0097539795284959?journalCode=smjcat]
[5] How To Prove Yourself: Practical Solutions to Identification and Signature Problems [https://link.springer.com/chapter/10.1007/3-540-47721-7_12]
[6] 知識抽出機(Knowledge Extractor)とは？知識抽出可能性と健全性の関係 [https://tech.hashport.io/3478/]
[7] Savitch, W. J. (1970). Relationships between nondeterministic and deterministic tape complexities. Journal of computer and system sciences, 4(2), 177-192.