CycleFold

楕円曲線サイクル上でのNovaのエレガントな実装。HyperNovaにおけるverifierのscalar multiplicationのみを第2楕円曲線上の回路にoutsourceする。

https://eprint.iacr.org/2023/1192

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://lagrangelabs.notion.site/Nova-from-IVC-to-general-PCD-for-zkMapReduce-d04afec2d70c47db9dfb67e84d0d796e

しかしながら、これには次の問題点があった。

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