Folding Schemes

\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\set#1{\mathcal{#1}} \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\R{\mathrm{R}} \gdef\P{\mathsf{cm}} \gdef\H{\mathsf{H}} \gdef\Z{\mathrm{Z}} \gdef\bigop#1#2{\mathop{\Large #1}\limits_{#2}} \gdef\zkp#1#2#3{\p{ \begin{array}{c}#1\\\hline#2\end{array} \middle\vert \begin{aligned}#3\end{aligned}}}

Nova

Given a cycle of curves \G_1, \G_2 with scalar fields \F_1, \F_2 (and thus base fields \F_2, \F_1). Construct the pairs (with element-wise operations) \G = \G_1 × \G_2, \R = \F_1 × \F_2. Note that \R degrades to a ring, \G_i is a vector space over \F_i and \G is and \R-module.

Construct family of cryptographic hashes \H_X: Y → X. Where elements of the inputs set (defined implicitly) map to pseudo-random elements in the target set X. We will use the shorthand \H_1 and \H_1 for \H_{\F_1} and \H_{\F_2} respectively.

Construct a Pedersen commitment \P: \R^n → \G by fixing a random vector in \vec g ∈ \p{\G_{\setminus \{0\}}}^n and taking the linear combination: \P(\vec x) = \sum_i x_i ⋅ g_i. Factor \P into two commitments \P_1: \F_1 → \G_1 and \P_1: \F_2 → \G_2.

Relaxed R1CS

Given a computable partial function f: \R^u × \R^v → \R^v on a ring \R.

\vec v = f(\vec u_n, … f(\vec u_1, f(\vec u_0, \vec v_0)))…)

Given a computable function f: \R^u → \R^v on a ring \R. We arithmatize the function to \mat A, \mat B, \mat C ∈ \R^{m×n} such that

f(\vec u) = \vec v \quad ⇔ \quad \bigop{∃}{\begin{subarray}{l} \vec w ∈ \R^t \\ \end{subarray}} \left\{\begin{aligned} \vec z &= \begin{bmatrix}1 & \vec u & \vec v & \vec w\end{bmatrix}\\ \mat C ⋅ \vec z &= \p{\mat A ⋅ \vec z} ⊙ \p{\mat B ⋅ \vec z}\\ \end{aligned}\right.

For convenience we will write \vec x = [\vec u\ \vec v]. An instance is a tuple (e, w, s, \vec x)∈\G×\G×\R×\R^{u+v} such that there exists a \vec w ∈ \R^n, \vec e ∈ \R^m that satisfy

\begin{aligned} e &= \P(\vec e) & \vec z &= \begin{bmatrix}s & \vec x & \vec w \end{bmatrix}\\ w &= \P(\vec w) & \p{\mat A ⋅ \vec z} ⊙ \p{\mat B ⋅ \vec z} &= s ⋅ \mat C ⋅ \vec z + \vec e\\ \end{aligned}

Relaxed R1CS instances form an \R-module. The zero instance is (0, 0, 0, \vec 0). The scalar product of (e, w, s, \vec x) and r ∈ \R is (r²⋅e, r⋅w, r⋅s, r⋅\vec x). The sum of (e_1, w_1, s_1, \vec x_1) and (e_2, w_2, s_2, \vec x_2) is (e_1 + e_2 + \P(\vec d), w_1 + w_2, s_1 + s_2, \vec x_1 + \vec x_2) where

\vec d = \p{\mat A ⋅ \vec z_1} ⊙ \p{\mat B ⋅ \vec z_2} + \p{\mat A ⋅ \vec z_2} ⊙ \p{\mat B ⋅ \vec z_1} - \mat C ⋅ \p{s_1 ⋅ \vec z_2 + s_2 ⋅\vec z_1}

Instances of the form (0, w, 1, \vec x) correspond directly to regular R1CS instances.

To update prover state:

\p{\mat A ⋅ \vec z, \mat B ⋅ \vec z, \mat C ⋅ \vec z, s, s⋅\mat C ⋅ \vec z - \p{\mat A ⋅ \vec z} ⊙ \p{\mat B ⋅ \vec z}}

\p{r⋅\vec a, r⋅\vec b, r⋅\vec c, r⋅s, r²⋅\vec e}

\p{\vec a_1 + \vec a_2, \vec b_1 + \vec b_2, \vec c_1 + \vec c_2, \vec e_1 + \vec e_2 + \vec d}

\vec d = \vec a_1 ⊙ \vec b_2 + \vec a_2 ⊙ \vec b_1 - s_1 ⋅ \vec c_2 - s_2 ⋅\vec c_1

The important thing is that linear combinations can be computed element-wise.

We can also compute \vec e by recovering it from the added instance as \vec e = \vec a ⊙ \vec b - s ⋅ \vec c. This may be more efficient?

Note. An instance can be generated for any \vec x by solving for \vec e. Only when s ≠ 0 and \vec e = \vec 0 does the instance proof a f(\vec u) = \vec v claim. So we are interested in the subspace spanned by those instances.

Note. For every R1CS (A, B, C) we can construct an R1CS (A', A', C') with at most twice the constraints. The verification relation then becomes \p{\mat A ⋅ \vec z}^{⊙2} = s⋅\mat C ⋅ \vec z + \vec e. If we add two instances we get

$$ \vec d = 2⋅\p{\mat A ⋅ \vec z_1}⊙\p{\mat A ⋅ \vec z_2}

the main advantage is one fewer state vector to carry around. \vec e = \vec a^{⊙2} - s ⋅ \vec c.

Customizable Constraint System (HyperNova)

\sum_{\set T ∈ \set S}\ \bigodot_{M ∈ \set T}\ \mat M ⋅ \vec w = \vec 0

ProtoStar

Generic constraints, test for f(\vec w) = \vec 0 for polynomial f. R1CS translates as

f_i(\vec w) = (\mat A ⋅ \vec w)_i ⋅ (\mat B ⋅ \vec w)_i - (\mat C ⋅ \vec w)_i

Instance (w; \vec w) satisfies iff w = \P(\vec w) and f(\vec w) = \vec 0.

Given two instances interpolate

ω(X) = X⋅\vec w_1 + (1 - X)⋅ \vec w_2

from the initial instances we have f(ω(0)) = ω_0 and f(ω(1)) = ω_1.

f(ω(X)) = X⋅ ω_1 + (1 - X) ⋅ ω_2 + \mathrm{Z}_{{0,1}}(X)⋅ q(X)

where \mathrm{Z}_{{0,1}}(X) = X^2-X is the polynomial that is zero on \{0,1\}.

Evaluate in random r and have a error term \vec e = f(ω(r)) = q(r).

New instance (w; \vec e, \vec w) st. w = \P(\vec w) and f(\vec w) = \vec e. Interpolate

\begin{aligned} ε(X) &= X⋅\vec e_1 + (1 - X) ⋅ \vec e_2 \\ ω(X) &= X⋅\vec w_1 + (1 - X) ⋅ \vec w_2 \end{aligned}

New equation is

f(ω(X)) = X ⋅ \vec e_1 + (1 - X) ⋅ \vec e_2 + \mathrm{Z}_{{0,1}}(X)⋅ \vec q(X)

new instance is (\vec q(r), ω(r))

Generalizing this, we can pick a set of basis points \mathcal A ⊆ \R and interpolate.

\begin{aligned} ε(X) &= \sum_{i∈[0,n)} \Z_{\mathcal A\setminus\{a_i\}}(X) ⋅\vec e_i \\ ω(X) &= \sum_{i∈[0,n)} \Z_{\mathcal A\setminus\{a_i\}}(X) ⋅\vec w_i \end{aligned}

\begin{aligned} f(ω(X)) = ε(X) + \Z_{\mathcal A}(X) ⋅ \vec q(X) \end{aligned}

Nova

At each step the circuit produces commitments to the witness and the cross term.

\begin{aligned} w &= \P(\vec w) & d &= \P(\vec d) \end{aligned}

R1

\zkp{x_0,x_1}{i}{ asd \\ asd \\ asdas }

SuperNova generalizes this to allow multiple functions f_i where the previous function selects the applicable next step.

References

Maybe

Remco Bloemen
Math & Engineering
https://2π.com