PCD & IVC

Introduction

very introductory explanation on ivc is computation that can verify itself with constant overhead. In the paper, computation is defined as incremental steps that takes an input and a proof of previous step and can return proof of correct computation of the application and that the previous proof has been verified correctly.

IVC works on step based functions: $z_n=F^{(n)}(z_0)$ for some steps $n$, initial input $z_0$ and output $z_n$.

nova realises incremental verifiability using a relaxed R1CS instance. so each step is treated as an R1CS instance and that step proves that step was computed correctly and folds the R1CS instance of previous step and the current step to a new relaxed R1CS instance which is passed to next step.

how does nova map R1CS computation into a step computation function?

Preliminaries

Section 3 explains all the preliminary definitions used to construct a complete, knowledge sound and zero knowledge IVC scheme.

completeness:

knowledge soundness:

NIFS

In section 4, they propose a folding scheme for NP. they take R1CS as the NP-complete language for arithmetic circuit satisfiability. First attempt is the naive attempt where they just create random linear combination of $Z,w$ and witness matrix. But this doesn’t create correct folding instance, as there are cross terms from multiplying $AZ$ and $BZ$.

$$\begin{array}{rl}u& \leftarrow {\mathrm{u}}_1+r\cdot {\mathrm{u}}_2\\ E& \leftarrow E_1+r\cdot (A{Z}_1\cdot B{Z}_2+A{Z}_2\cdot B{Z}_1-u_1\cdot C{Z}_2-u_2\cdot C{Z}_1)+r^2\cdot E_2\end{array}$$

Then, they introduce two terms $u,e$ in the form of relaxed R1CS structure. $e$ amounts for the cross error terms in AZ and BZ, folds public instance and private witness into one.

$$\begin{array}{rl}\mathrm{x}& \leftarrow {\mathrm{x}}_1+r\cdot {\mathrm{x}}_2\\ W& \leftarrow W_1+r\cdot W_2\end{array}$$

Above folding scheme is not zero-knowledge as prover sends witness $W_1,W_2$ to the verifier. To circumvent this, commitments are used. Thus, committed relaxed R1CS is used to verify the folded instance. Let CRRI denotes committed relaxed R1CS instance: $(\overline{E},u,\overline{W},x)$, and $E,r_E,W,r_W$ denote relaxed R1CS witness satisfying CRRI. V takes $CRR{I}_1,CRR{I}_2$ outputs instance satisfying witness:

1. $\mathcal{P}$ sends commitment to $T=A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-u_1\cdot C{Z}_2-u_2\cdot C{Z}_1$, $\overline{T}$ to $\mathcal{V}$
2. $\mathcal{V}$ sends $r$ to P.
3. V calculates folded instance: $\overline{W},\overline{E},u,x$ from $\overline{W_1},\overline{W_2},\overline{E_1},\overline{T},\overline{E_2},x_1,x_2,u_1,u_2$
4. P outputs folded witness $(E,u,W,x)$ to V
5. V verifies that it satisfies.

Above folding scheme is rendered non-interactive in random-oracle model using Fiat-Shamir transformation. Constructing a non-interactive folding scheme: $\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}$

• $\mathcal{G}(1^{\lambda })\to pp$
• $\mathcal{K}(pp,(A,B,C))\to (\mathsf{pk},\mathsf{vk})$
• $\mathcal{P}(\mathsf{pk},(u_1,w_1),(u_2,w_2))\to \left(E,W,\overline{T}\right)$
• $\mathcal{V}(\mathsf{vk},(\overline{T},\overline{W}),(u_1,u_2))\to \left(\overline{E},\overline{W},u,x\right)$

Let’s understand efficiency of nova’s NIFS:

• verifier needs to do 2 scalar mults: $\overline{E},\overline{W}$, 3 EC add: 2 for $\overline{E}$, 1 for $\overline{W}$
• communication: relaxed R1CS witness: ${\mathbb{F}}^m,\mathbb{F},{\mathbb{F}}^{m-l-1},\mathbb{F}$

NOVA IVC

function $F$ is augmented to $F^{\prime }$ takes two arguments $u_i,U_i$: computes $F(z_i)$ and give $z_{i+1}$ and invokes verifier to fold $u_i$ and $U_i$ together to create $U_{i+1}$. IVC prover then creates a proof for $U_{i+1}$ that attests to $u_{i+1}$ being correct execution of steps $\mathrm{0..}i$ while $u_{i+1}$ attest to correct computation of step i+1 of $F^{\prime }$.

To construct an IVC from above folding scheme, let $\mathsf{NIFS}=(\mathsf{G},\mathsf{K},\mathsf{P},\mathsf{V})$ be non-interactive folding scheme for committed relaxed R1CS.

• $\mathcal{G}(1^{\lambda })\to pp$
• $\mathcal{K}(pp,F)\to (\mathsf{pk},\mathsf{vk})$: $\mathsf{p}{\mathsf{k}}_{\mathsf{fs}},\mathsf{v}{\mathsf{k}}_{\mathsf{fs}}\leftarrow \mathsf{NIFS}.\mathcal{K}(pp,s_{F^{\prime }})$ and $\mathsf{pk},\mathsf{vk}\leftarrow ((F,\mathsf{p}{\mathsf{k}}_{\mathsf{fs}}),(F,\mathsf{v}{\mathsf{k}}_{\mathsf{fs}}))$
• $\mathcal{P}(pk,(i,z_0,z_i),{\omega }_i,{\Pi }_i)\to {\Pi }_{i+1}$
• $\mathcal{V}(\mathsf{vk},(i,z_0,z_i),{\Pi }_i)\to \{0,1\}$

• Nova works on 2 R1CS constraint systems defined as ${\text{R1CS}}^{(1)},{\text{R1CS}}^{(2)}$
• For each constraint system, relaxed R1CS instance consist of $(\mathbb{U}=(\bar{E},s,\bar{W},x),\mathbb{W}=(E,W))$.
• Prover derives new $\mathbb{W}$ after each iteration and verifier derives $\mathbb{U}$.
• Augmented circuit $F^{\prime }$ consists of relations ${\mathcal{R}}_1,{\mathcal{R}}_2$ that takes as input relaxed r1cs instance and relation witness pair: $u_i=(\bar{E},s,\bar{W},x=(x_0,x_1\in {\mathbb{F}}_1)),{\hat{w}}_i=(i,z_0,z_i,z_{i+1}\leftarrow F(z_i),{\mathbb{U}}_i^{(2)},u_i^{(2)},{\bar{T}}_i^{(2)}\in {\mathbb{G}}_2)$. At each step:
  • folding verifier folds: ${\mathbb{U}}_{i+1}^{(2)}\leftarrow {\text{Fold}}_{\mathcal{V}}(vk,u_i^{(2)},{\mathbb{U}}_i^{(2)},{\bar{T}}^{(2)})$
  • and generates new relaxed instance: $u_{i+1}^{(1)}=(u_i^{(2)}.x_0,H_1(vk),(i+1),z_0,z_{i+1},{\mathbb{U}}_{i+1}^{(2)})$
  • ${\mathbb{U}}_{i+1}^{(2)}$ gets transferred to next ${\mathcal{R}}_1$ step and $u_{i+1}^{(1)}$ is passed as input to ${\mathcal{R}}_2$ step.
• determine why non-native field implementation is used in Nova?
• IVC verifier: after the final iteration verifies following:
  • Input:
    • index and evaluations: $i,z_0^{(1)},z_0^{(2)},z_i^{(1)},z_i^{(2)}$
    • function $F_1,F_2$ with auxiliary inputs: ${\text{aux}}_i^{(1)},{\text{aux}}_i^{(2)}$
    • Proof ${\pi }_i:=((u_i^{(2)},w_i^{(2)}),({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))$
  • Verifies:
    • index > 0
    • $u_i^{(2)}.x_0=H_1(vk,z_0,z_i,{\mathbb{U}}_i^{(2)})$
    • $u_i^{(2)}.x_1=H_2(vk,z_0,z_i,{\mathbb{U}}_i^{(1)})$
    • ${\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}$ satisfies R1CS
    • ${\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}$ satisfies R1CS
    • $u_i^{(2)},w_i^{(2)}$ strictly satisfies ${\text{R1CS}}^{(2)}$
• IVC prover:
  • Input:
    • $F_1,F_2$, converts this into augmented circuits relation ${\text{R1CS}}^{(1)},{\text{R1CS}}^{(2)}$
    • $z_0^{(1)},z_0^{(2)},z_i^{(1)},z_i^{(2)}$
    • proof ${\pi }_i:=((u_i^{(2)},w_i^{(2)}),({\mathbb{U}}_i^{(1)},{\mathbb{W}}_i^{(1)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))$
  • Computes:
    • folds prior pairs: $({\bar{T}}_i^{(1)},{\mathbb{U}}_{i+1}^{(2)},{\mathbb{W}}_{i+1}^{(2)}):={\text{Fold}}_{\mathcal{P}}(pk,(u_i^{(2)},w_i^{(2)}),({\mathbb{U}}_i^{(2)},{\mathbb{W}}_i^{(2)}))$
    • creates relation witness ${\hat{w}}_i^{(1)}$, runs augmented circuit to extend witness to $w_{i+1}^{(1)}$
    • commit to witness ${\bar{w}}_{i+1}^{(1)}$
    • define $u_{i+1}^{(1)}=(\bar{0},1,{\bar{w}}_{i+1}^{(1)},x=(x_0,x_1)$ and $w_{i+1}^{(1)}=({\vec{0}}^{(1)},w_{i+1}^{(1)})$
    • similar for ${\text{R1CS}}^{(2)}$

Let’s talk about costs:

• P’s complexity:
  • $\mathcal{O}(m)\mathbb{F}$ operations: combining W, E
  • 1 MSM: $\overline{T}$
• V’s complexity: $|F|+o(2G+2H+R)$
  • $|F|$ constraints to encode computation
  • 2 MSM ($\overline{W},\overline{E})$
  • 2 Hash functions for $u_i.x,U_i.x$
  • 1 Random Oracle for $r$
• communication: 4 EC point $(u_i.\overline{W},u_i.\overline{E},U_i.\overline{W},U_i.\overline{W})$, 2 $\mathcal{O}(m)$ vectors: $w,W$

Proof compression using SNARK

In the next step, to circumvent succinctness and zero-knowledge, nova attaches the IVC proof in a SNARK. Uses Spartan, but any SNARK for NP can be used. It uses following steps to compress the proofs:

• $\mathcal{G}(1^{\lambda })\to pp$
• $\mathcal{K}(pp,F)\to (\mathsf{pk},\mathsf{vk})$
  • $NIFS.K(\mathsf{pp},{\mathsf{s}}_{\mathsf{F}})\to (\mathsf{p}{\mathsf{k}}_{\mathsf{NIFS}},\mathsf{v}{\mathsf{k}}_{\mathsf{NIFS}})$
• $\mathcal{P}(pk,(i,z_0,z_i),\Pi )\to \pi$
  • uses $NIFS.P(\Pi )$ into ${\mathsf{U}}^{\prime },{\mathsf{W}}^{\prime },\overline{T}$
  • take $SNARK.P(\mathsf{pk},{\mathsf{U}}^{\prime },{\mathsf{W}}^{\prime })\to {\pi }_{U^{\prime }}$
  • $\pi =(U,u,\overline{T},{\pi }_{U^{\prime }})$
• $\mathcal{V}(vk,(i,z_0,z_i),\pi )\to \{0,1\}$
  • uses $NIFS.V(\mathsf{v}{\mathsf{k}}_{\mathsf{NIFS}},U,u,\overline{T})$ to get folded instance $U^{\prime }$
  • uses $SNARK.V(\mathsf{v}{\mathsf{k}}_{\mathsf{SNARK}},U^{\prime },{\pi }_{U^{\prime }})=1$

Another very interesting paper identified a soundness bug in nova proving on a cycle of curves. Why is a cycle of curves necessary? because output of one circuit is in scalar field while the input is in base field of the elliptic curve used for commitments.

So, you have to send the commitments to next curve layer, where it’s accumulated and $x_0$ is verified and $x_1$ is sent to next layer.

SNARK for committed relaxed R1CS

modifies spartan’s equation for relaxed R1CS. performs 6 sumcheck protocol to get values of multilinear polynomials.

Costs:

• Prover work: 4 sumcheck protocol where polynomial has degree at most $\mathcal{O}(\log m)$. Prover work is $\log m$ and
• IOP communication complexity is also $\log m$
• V work:
  • calculate $eq(\tau ,r_x)$ in $\mathcal{O}(\log m)$

converts a polynomial IOP into SNARK by using a PCS for multilinear polynomials.

nova-2021-370, p.26

Furthermore, there is a polynomial commitment scheme for log m-variate multilinear polynomials if there exists an argument protocol to prove an inner product computation between a committed vector and an m-sized public vector ((r1, 1 − r1) ⊗ … ⊗ (rlog m, 1 − rlog m)), where r ∈ F log m is an evaluation point

still don’t understand this properly

Supernova

supernova generalised nova’s folding scheme to a list of functions, such that at any point of time, prover can fold execution of any function selected through a mux.

Let $F_1,\dots ,F_l$ be polynomial time computable functions, and a program counter $\phi$. Goal of the prover is to take ${\Pi }_i$ for NIVC statement: $i,z_0,z_i$ and generate proof ${\Pi }_{i+1}$ for statement: $i+1,z_0,z_{i+1}$.

Augmented Function: $F_j^{\prime }(i,z_0,z_i,w_i,p{c}_i,U_i)\to (z_{i+1},U_{i+1},p{c}_{i+1})$

• Runs $F_j(i,z_i,w_i)\to z_{i+1}$
• runs folding verifier to fold $u_i,U_i[p{c}_i]$ into $U_i[p{c}_i]$
• runs $\phi (p{c}_i,w_i)\to p{c}_{i+1}$

Verifier $V((u_i,w_i),({\mathbb{U}}_i,{\mathbb{W}}_i))$:

• $u_i$ contains $p{c}_i$ in its public output, so use that to verify that $u_i,w_i$ is satisfying constraints $F_{p{c}_i}^{\prime }$
• for each $j\in \left\{0,\dots ,l\right\}$, verify that $U_i[j],W_i[j]$ satisfies $F_j^{\prime }$

Prover ${\Pi }_i\to {\Pi }_{i+1}$:

• $i=0$: base case
  • Initialise all running instances as empty, i.e. $U\to \perp$
  • run circuit for step 0
  • runs
• else:
  • Parse ${\Pi }_i$ as $((u_i,w_i),(U_i,W_i),p{c}_i)$
  • Runs NIFS.P to obtain: $U_{i+1},W_{i+1},{\bar{T}}_i$
  • runs $F_j^{\prime }$ to get $z_{i+1},p{c}_{i+1},U_{i+1}$
  • compute $p{c}_{i+1}\leftarrow \phi (z_i,w_i)$
  • compute $(u_{i+1},w_{i+1})\leftarrow \text{trace}(F_{p{c}_{i+1}}^{\prime },(vk,U_i,i,z_0,z_i,w_i,\bar{T}))$

Cyclefold

In Nova, a NIFS verifier has to run in augmented circuit on opposite curve. This, arguably adds ~10k mul gates on both circuits.

cyclefold-2023-1192, p.1

CycleFold’s starting point is the observation that folding-scheme-based recursive arguments can be efficiently instantiated without a cycle of elliptic curve

how?

Cyclefold improves the performance of IVC prover by reducing the size of the secondary circuit on another curve. Second curve is used to perform a single scalar multiplication (1000-1500 mul gates).

cyclefold-2023-1192, p.1

CycleFold then folds invocations of that tiny circuit on the first curve in the cycle.

didn’t understand this. Why does it folds the circuit on first curve? don’t we just run folding verifier to get new relaxed R1CS instance?

Use secondary circuit to perform curve operations for primary circuit, verifiability of which is delegated back to augmented circuit which runs a NIFS verifier.

• Run a folding scheme verifier that performs folding for a relation.
• scalar mult operations for folding is delegated to a secondary circuit which uses opposite curve for efficient computation.
• result of operation is verified and folded by a Nova NIFS.V and output used by primary folding scheme verifier.

cyclefold-2023-1192, p.6

Remark 3

did not understand this remark. authors are referring to higher degree constraints to encode $u_{\text{EC}}$ which would result in higher constraints.

Sangria

TODO

Hypernova

Prerequisite: CCS

similar to any proof system with two entities: $\mathcal{P},\mathcal{V}$ where prover is trying to prove

Protostar

TODO

Protogalaxy

TODO

Nebula

MicroNova

Twist & Shout

Interesting questions:

what's the difference between halo style recursion/accumulation vs nova style folding scheme?

resources

• Lurk Lab’s Awesome Folding
• carlos’ ccs
• origami
• arnau’s hypernova notes