Recrusive SNARK
どうやらPCDベースなるものも存在する?
以下のMNTなるシステムによると、一方の回路で生成された証明は、他方の回路で再帰的に検証することができるらしい
https://scrapbox.io/files/6325d4e78e1e53001d790434.png
MNTは楕円曲線サイクルなるもの。この二つの回路を一つのProofとして出力することができる仕組みを用いると、以下のような木構造で多くのProofを格納することができる。
https://scrapbox.io/files/6325d4eda635c7001fab9f30.png
この時の葉は以下の要素を含む
A verification key
A proof
A primary inputs of the the proved assigneme
https://scrapbox.io/files/6325d52b7ac79b00237c7e0b.png
各親ノード(すなわち集約された証明)は、以前の証明のハッシュを一次入力とする。
したがって検証では、まず中間ノードを再帰的にハッシュ化し、その入力を再構築する必要がある。
最終的にエンドユーザーが証明したいことは、与えられた公開入力と与えられた回路に対して有効な割り当てがあることのみなので、証明をオンチェーンで公開する代わりに、単にそのハッシュを公開することで検証コストを削減できる。
しかし、証明はオフチェーンでアグリゲータープールに伝達されなければならない。
https://scrapbox.io/files/6325d53564ea9e001d60b2f4.png
再帰ZKでは、証明が他の証明の正当性を証明し、その証明がまた他の証明の正当性を証明する、ということを繰り返していく
このような複数のproofが他のproofに作用するよう仕向けることをAggregationと呼ぶ
あるロールアップにおいて、1,000件のトランザクションが有効であることを証明する場合を考える。
標準的なZKP
証明者は1,000件のトランザクションを順次検証するために1つの証明を生成する
これは非常に時間のかかる作業
再帰的ZKP
証明者は各トランザクションに1つずつ、計1,000個の証明を生成することができる。
すべての証明は独立しているため、並行して生成することができ、その結果、証明にかかる時間を大幅に短縮することができる。
これらの各トランザクションの証明は、上図のように再帰的に1つの証明に集約することができる。
つまり、zk-Rollupなどに応用すると検証コストだけでなく証明時間も削減できる
Incrementally verifiable computation (IVC)
以下のような計算の証明は、証明が漸進的に更新可能であれば、より効率的になる
長い計算
過度に長い計算の証明には、証明者側で膨大な量のメモリを消費する。
メモリに収まらない計算もあり、証明することが不可能になる。
進化する計算
例えば、ブロックチェーンの状態を証明したいが、ブロックチェーンは常に成長している。
新しいブロックを検証するだけでなく、既存の証明自体も検証する新しい証明を計算する必要がある。
IVCのアイデアは
これらの計算をより小さなステップに分割し、それを繰り返し証明する。
各ステップには、現在の計算の状態を証明する証明が含まれる。
再帰的ZKP(より具体的にはIVC)を用いると、現在のステップとその証明を再帰的に用いることで、次のステップのための新しい証明を生成することができる。
証明の更新は、標準的なZKPのように最初のステップから再計算する必要がなく、計算の総延長に依存しない。
例えば,iが0からnまでの関数Fに対して,次のような計算がある.
$ F(z_i,w_i)=z_{i+1}
zは公開入力、wは非公開入力(つまり、witness)である。
z₀から始めると最終出力がzₙになることを効率的に証明したい。
https://scrapbox.io/files/6325dd44cf2e8900233c9c25.png
IVCは、初期証明$ π_0(ΡF は証明アルゴリズム)を生成し、各ステップでそれを漸進的に更新することによってこれを実現する。例えば、$ π_2はF(z₁, w₁) = z₂を証明するだけでなく、$ π_1が有効であることも証明する。帰納法により、最後の$ π_nはすべての中間ステップが正しいことを証明する。
https://scrapbox.io/files/6325dda107a271001dd71409.png
実際には、検証はバイリニアペアリングのような重い暗号演算が必要であったり、効率的に動作させるために冒頭の楕円曲線の循環などの多くの新しい技術を採用する必要がある
参考文献
https://www.youtube.com/watch?v=_XwMgSUN8cE