IVC - BitPickers

IVC

長いproofを高速に証明するinner snarkと短い証明と高速な検証を持つouter snark

https://scrapbox.io/files/64e631518f4794001b286f60.png

Incrementally Verifiable Computation (IVC)

例えば以下のような数式があったとして

https://scrapbox.io/files/64e635dbb9ba80001b332272.png

以下のようになる

https://scrapbox.io/files/64e636284fcb1e001c56fddb.png

この計算が正しく実行されることの証明を提供したいと思うかもしれない。

反復の回数が膨大になると計算が非常に長くなり、膨大な計算量に対する証明を作成するのは非常に高くつく。

さらに重要なことは、反復が永久に続く可能性があるということだ。

Fを証明するたびに全体の証明を１から行う必要があるし、n回の証明のために最後のnまで待つ必要がある

理想的には、各ステップの後に計算の正しさの証明を更新し（インクリメンタルに構築し）、検証者の証明/作業の長さが連続的に増加しない状態で、任意の時点でその正しさを検証できるようにしたい。

そこでIVC

計算の反復構造のため、Fのアプリケーションごとに別々の証明を作成することができるのは明らかだ。

i番目のproof作成だけでなく、i-1のproofの検証もFで行う

s_0からs_i-1までi-1ステップで辿り着いたこと

s_i-1にFを与えるとs_1が得られる

言い換えれば、各ステップの計算Fを、前のステップの証明に適用された検証回路で補強する。

つまり、最後の証明を検証することで、最後のステップが正しいことを確信でき、計算に組み込まれた検証回路を通して証明πᵢ -1を検証したことになる。つまり、与えられたステップとそこに入力された入力の両方が正しいということになる。

つまり、与えられたステップとそこに入力された入力の両方が正しいということである。

π-₁を検証したことで、ステップi -1が正しいことがわかり、証明πᵢ-₂がチェックアウトされ、その結果、前のステップとそれに投入された証明の正しさが保証される。

https://scrapbox.io/files/64e636f700bfa6001b2bab74.png

線形時間かかるproofをn回行えば指数関数的に時間がかかるので、線形時間より短い時間で証明できれば嬉し

コストのかかる部分を切り出し、1つのインスタンスに集積し、この集積インスタンスだけを検証することができる。

この検証ステップ全体を遅延させることで最大限

検証者が線形時間の多項式コミットメント開始チェックを延期し、最後の1回の操作でこれらを累積することで、再帰的合成を高速化するというこのアイデアは、Haloで導入された(recurcive snark)

Haloでは、多項式コミットメントのオープニング・クレームをチェックする作業は、2つのステップに分かれる：

多項式とそれに対するコミットメントからなるペアを出力する高速なステップ。

多項式とコミットメントのペアをチェックする高価なステップ。

つまり、オープンを検証するには、ペアを作り（高速）、それをチェックする（高価）必要がある。良い知らせは、コミットメントスキームが加法的同型であれば、高価なステップは簡単に蓄積できるということです。

ステップ2のインスタンスが複数あり、多項式f_iとそのコミットメントC_iのペア（f_i, C_i）が複数あるとします。

要約すると、各ステップでは簡単な部分のみを行う。高価な部分は、実行中の集約に蓄積され、その検証は後の時点に延期される - 高価な部分はすべて、そのようなチェックの1つのコストで、最後に一緒に検証される。

各ステップでは、前のステップから引き継がれた証明の検証をすべて行ったことを証明するのではなく、困難なステップが成立するという仮定の下で検証が成立することを証明する（つまり、「C_iは多項式f_iへのコミットメントである」という形の文の真偽を条件として証明が成立する）。

これらの難解な文は積み重ねられ、最後に一気に証明される。積み重ねが正しく行われたことの証明も含めれば問題ない！検証回路は計算量の多い部分を持っているが、潜在的に多くのステップを組み合わせて一度だけ行うので、コストは償却される。このようにして、高価な検証器を備えたSNARKを使用する余裕ができるのである。一方では、信頼できるセットアップやより単純なセキュリティの仮定がなくてもやっていけるのである。

Novaは、このアイデアを最大限に活用している。ある部分ではなく、検証ステップ全体を延期している。これは、新たに導入されたフォールディング・スキームと呼ばれるプリミティブ（2つのステップの検証を1つのステップの検証に減らすエレガントな方法）を使用することで実現される。

各ステップで、検証される新しいステートメントは、折りたたみスキームを使って実行中のステートメントに折りたたまれる。繰り返される折りたたみの結果得られる最終的なステートメントがチェックアウトされることと、各ステップでの折りたたみが正しく実行されることの2つを検証すれば十分である。

https://medium.com/veridise/intro-to-nova-zk-folding-schemes-halo-and-accumulation-fec7aeaa666f