HyperNova
ざっくりまとめると
Novaの回路をR1CSからCCS(customizable constraint system)に拡張したもの 特徴
R1CSからCCSへの拡張
Novaは制約を(Extended) R1CSで記述する必要があったが、HyperNovaではPlonkish / AIR arithmetizationも扱えるCCS(customizable constraint system)を使う。CCSのstructureは次の式で与えられる。
$ \sum_{i=1}^{q} c_{i} \cdot \bigcirc_{j \in S_{i}} M_{j} \cdot z=\mathbf{0}
ここで$ c_iは定数、$ S_i \in \{1,...,t\}はindexのmultiset、$ M_jは$ m\times nの行列で、$ z = (x, 1, w)はpublic input $ x (長さ$ lのベクトル)とwitness $ w (長さ$ n - l - 1のベクトル)を並べたもの。$ \bigcircはベクトルの要素ごとの積を表す。
R1CS$ (Az)\circ (Bz) - Cz = 0 と比較すると、2次以上の項を作ることができ、それらの項の比例定数を自由に決めることができるのが違い。
Multi-folding schemes
structureを共有した複数のインスタンスを一つのインスタンスにまとめることができる。
2つのインスタンスをまとめることしかできなかったNovaよりも複雑な構造の再帰証明が可能に(例えばDAG構造を持った再帰証明)。multi-foldingにはsum-check protocolが使われる。これが"Hyper"の由来だと思われる(sum check protocolはhyper cube上の関数の和に関するIOPで、sum-check protocolを使ったPlonkはHyperPlonkと命名されている)
CCSとそれに対応するMulti-folding schemeを使う以外はNovaと全く同じ。
一様な回路しか扱えないので、非一様な回路を扱うにはSuperNovaと組み合わせてSuper-HyperNovaにする必要がある 多重線形関数
ベクトルや行列は多重線形関数として表すことができる。
例えば、ベクトル$ \vec{v} = (v_0, v_2, ..., v_{n-1}) は、$ s = \log nとして$ \tilde{v}(x_1, x_2, ..., x_s)という多重線形関数で表すことができる。$ \tilde{v}は自然数$ 0 \le i < nの2進数表示を$ (b_0, ..., b_s)としたとき、
$ \tilde{v}(b_0,...,b_s) = v_i
となるように構成されており、
Commited CCS
CCSのwitnessをadditively-homomorphic polynomial commitment schemeでコミットしたもの。
まず行列$ M_jとベクトル$ zを多線形関数にしたものを$ \tilde{M}_j