Nova
IVC (incremental verifiable computation)を実装するための1手法。2つのR1CSを一つにまとめるfolding schemeによる。 再帰証明では、前ステップのvalidityを検証するのではなく、foldingの正しさのみを検証するためオーバーヘッドが小さい。
Folding scheme
2つのR1CSをfoldingすると生じるcross termをキャンセルするために、次のようなR1CSの拡張版を考える(Relaxed R1CS)
$ Az \circ Bz = u (Cz) + E
ここで$ uはスカラーで、$ Eはベクトル。また$ z = (x, u, w)はpublic input vector $ xと$ u, witness vecotr $ wを並べた構造になっている。Relaxed R1CSのインスタンス(公開入力)は$ (E, u, x)で与えられる。$ E, uが公開入力に入っていなければ任意の$ zに対して解が存在してしまうことに注意。
いま、あるRelaxed R1CS$ A z_1 \circ B z_1 = u_1 (Cz_1) + E_1と別のRelaxed R1CS$ A z_2 \circ B z_2 = u_2 (Cz_2) + E_2をfolding したいとする。
このとき、2つの乱数結合$ z =z_1 + r z_2 , $ u = u_1 + ru_2を取ってrelaxed R1CSの関係に代入すると
$ (A z_1 + r A z_2 ) \circ (Bz_1 + rB z_2) = (u_1 + ru_2)(Cz_1 + r Cz_2) + E
$ (Az_1 \circ B z_2 - u_1 C z_1) + r^2 (Az_1 \circ B z_2 - u_2 C z_2) + r (Az_1 \circ B z_2 + A z_2 \circ Bz_1 - u_1 Cz_2 - u_2 Cz_1) = E
ここで第一項が$ E_1、第二項が$ E_2のことに注意すると、
$ E = E_1 + r T + r^2 E_2
$ T := Az_1 \circ B z_2 + A z_2 \circ Bz_1 - u_1 Cz_2 - u_2 Cz_1
と$ Eを選べば良いことが分かる。
以上を再帰証明の中で実行するのは大変なので、proverを用意して、verifierはproverが提出した証明を検証するだけでfoldingの正しさを検証できるようにする。
そのために、まずwitness ($ w)と大きいインスタンス($ E)をコミットして
$ (\bar{E}, u, \bar{W}, x)
をRelaxed R1CSのインスタンスとする。目的はverifierが持っている2つのインスタンス$ (\bar{E_1}, u_1, \bar{W_1}, x_1) , $ (\bar{E_2}, u_2, \bar{W_2}, x_2) をfoldingしたものが$ (\bar{E}, u, \bar{W}, x) になることを検証すること。
次の手順でproverはverifierに証明する。
1. $ T = Az_1 \circ B z_2 + A z_2 \circ Bz_1 - u_1 Cz_2 - u_2 Cz_1のcommitment $ \bar{T}をverifierに渡す。
2. verifierは乱数$ rをサンプルする。
3. verifierは$ \bar{E} = \bar{E_1} + r \bar{T} + r^2 \bar{E_2}, $ u = u_1 + ru_2, $ \bar{W} = \bar{W_1} + r \bar{W_2}, $ x = x_1 + rx_2を計算する。
$ \bar{T}の正しさを検証しなくても、folding後のインスタンス$ (\bar{E}, u, \bar{W}, x)がrelaxed R1CSの関係を満たせば、元の2つのインスタンスがrelaxed R1CSの関係を満たすことが保証されるのがポイント(folding schemeの健全性で、別途証明が必要)
IVCの構成
ある関数$ F(z_i, w_i) = z_{i+1}を$ n回適応すると、$ z_0が$ z_nになることの証明をしたいとする。このとき、$ Fのaugmented(増量版) 関数 $ F'を次のように構成する。
$ F^{\prime}\left(\mathrm{vk}, \mathrm{U}_i, \mathrm{u}_i,\left(i, z_0, z_i\right), \omega_i, \bar{T}\right) \rightarrow \mathrm{x}
引数:
$ \mathrm{vk}: commitment schemeの検証鍵
$ U_i, $ u_i: relaxed R1CSインスタンス
$ i: 現在のステップ数
$ z_0: 初期値
$ z_i: 現在の値
$ w_i: 現在のwitness
$ \bar{T}: foldingで使うcommitment
関数の内容:
$ i=0のとき、$ \operatorname{hash}\left(\mathrm{vk}, 1, z_0, F\left(z_0, \omega_i\right), \mathrm{u}_{\perp}\right)を出力する
$ i \neq 0のとき、
$ \mathrm{u}_i . \mathrm{x}=\operatorname{hash}\left(\mathrm{vk}, i, z_0, z_i, \mathrm{U}_i\right)を検証する
$ \mathrm{u}_i . \bar{E} = \mathrm{u}_{\perp}. \bar{E}と$ \mathrm{u}_i .u = 1を確認する
$ \mathrm{U}_{i+1} \leftarrow \text { NIFS.V }(\mathrm{vk}, \mathrm{U}, \mathrm{u}, T)を計算する
$ \operatorname{hash}\left(\mathrm{vk}, i+1, z_0, F\left(z_i, \omega_i\right), \mathrm{U}_{i+1}\right)を出力する
ここで、$ \mathrm{u}_{\perp}はrelaxed R1CSを$ u=1で自明に満たす定数インスタンス、NIFS.Vはfoldingの計算結果のインスタンスのみを取り出す関数。
https://scrapbox.io/files/64641833e6fbd7001b2f5904.png
この$ F^{\prime}\left(\mathrm{vk}, \mathrm{U}_i, \mathrm{u}_i,\left(i, z_0, z_i\right), \omega_i, \bar{T}\right) \rightarrow \mathrm{x}を(relaxed) R1CSで表現したものを$ \mathrm{u}_{i+1}, そのwitnessを$ w_{i+1}とする。
このように再帰的に$ \mathrm{u}_{i}, $ U_iを定義することでIVCの構成ができる。
IVCの最後尾のverifierのみ、$ F'の検証内容に加え、$ U_i, $ u_iがrelaxed R1CSの関係式を満たすことを検証する。
この処理は一般的には重いので、任意のSNARKを使ってwrapする。即ち、SNARKの回路の中で$ U_i, $ u_iがrelaxed R1CSの関係式を満たすことを検証し、そのproofを作る。これによってサイズの小さいproofをつくることができる。
コスト
Commitment schemeにPedersen Hashを使う場合、IVCの主要なコストは、folding時の楕円曲線のscalar multiplication $ \bar{E} = \bar{E_1} + r \bar{T} + r^2 \bar{E_2}, $ \bar{W} = \bar{W_1} + r \bar{W_2}の計算になる。 楕円曲線のscalar multiplicationは、有限体が256bitのとき、512回の楕円曲線の足し算が必要になる(2倍していく処理が256回、scalarのbitが立っているところの楕円曲線の足し算で256回)
このコストはPasta/Vestaなどの楕円曲線のサイクルを使うことで回避できる。つまり、現在のステップの楕円曲線上のscalar fieldを、次のステップのbase fieldに採用する。これにより、scalar multiplicationは次ステップのbase fieldのべき乗の計算になる。