CycleFold
楕円曲線サイクル上でのNovaのエレガントな実装。HyperNovaにおけるverifierのscalar multiplicationのみを第2楕円曲線上の回路にoutsourceする。 https://scrapbox.io/files/6626b53ade530000256ac208.png
CycleFoldは何を改善したか
Novaの問題点
Novaはfolding verifierが2回の楕円曲線のスカラー乗算を実行する必要があった。 $ E_2 = 0とすることで$ \bar{E} = \bar{E_1} + r \bar{T}, $ \bar{W} = \bar{W_1} + r \bar{W_2}の計算で2回必要になる
base fieldを$ F_q, scalar fieldを$ F_pとすると、楕円曲線の演算は回路のnative fieldである$ F_p上で$ F_qを扱う必要があり非効率である。そのため、github版のnovaでは、2つの楕円曲線 $ E_1 : base field$ F_q, scalar field $ F_p
$ E_2 : base field$ F_p, scalar field $ F_q
を使い、$ E_1上の回路のverifierを$ E_2上に、$ E_2上の回路のverifierを$ E_1上に実装して、non-native arithmeticを回避している。
https://scrapbox.io/files/6626bbaa637c070023975684.png
しかしながら、これには次の問題点があった。
Deciderは両方の曲線のインスタンスを検証する必要がある。片方の曲線にpairingが存在しない場合(bn254/grumpkinなど)はdeciderのsuccinct proofを作るのが大変になる。
PCD(直線構造を持ったIVCの一般化で、網目状の構造の再帰証明)の場合、もう片方のインスタンスも同時に扱う必要があって難しい(上の図の記事が詳しい)。
複雑な構造が脆弱性の温床になる。またセキュリティ証明が難しい。実際当初のnovaの実装には、もう一方のインスタンスをtranscriptに入れていないことによる脆弱性があった。 CycleFoldの改善点
$ E_2の回路をfolding verifierではなく、楕円曲線のスカラー乗算と和$ C' = C_1 + \rho C_2の計算のみを行うシンプルな回路に限定した。$ C' = C_1 + \rho C_2は$ E_1上のHyperNovaのverifierが唯一行わなければならないスカラー乗算で、この計算だけを$ E_2の回路に委託する。
これによって、deciderが検証すべきインスタンスは全て$ E_1上に載る。
2インスタンス以上のfoldingに容易に拡張可能なため、PCDが可能になる。
HyperNovaの復習
CCS