paper-Nova Recursive ZK Arguments from Folding Schemes.md

paper-Nova Recursive ZK Arguments from Folding Schemes.md

paper-Nova: Recursive ZK Arguments from Folding Schemes

argument highlight in [[#Reasoning]]

introduction

New approach for recursively proving correct execution of a program of the form $y=F^{(l)}(x)$. Folding schemes are not SNARKs or even arguments of knowledge, but can be used to combine several arguments of knowledge into one. This work introduces a folding scheme for an Argument constructed from an extension of R1CS, which characterizes NP.
Jump to 4 for core reasoning.

Comparison with Halo

mostly ignore this subnote

• at each incremental step, Halo's V circuit verified a partial snark, requiring Halo's P to perform |F| sized FFTs, and O(|F|) exponentiations. Nova's V folds an NP instance in an |F| sized circuit "computing" F. Nova's P needs only commit to the F sized circuit.
• Halo Infinite generalizes the approach in Halo to any homomorphic PCS.

Terms

• characterization of NP - I think this is interchangeable with any NP instance
• folding scheme - reduce checking of two statements to the checking of a single statement. Weaker, simpler, and more efficinet than SNARKs.
  • Formal: Both P,V hold two $N$-sized NP instances. Protocol: P,V output an $N$-sized NP instance, refered to as the folded instance, where the output instance is satisfiable iff the inputs are satisfiable.
• Nova folding scheme
  • Folding verifier is constant-sized, dominated by two group scalar muls.
  • Prover work is dominated by two multiexps of size O(|F|).
• Encoder - formal term for the algorithm outputing the verifier and prover keys
• verifier key - ?
• prover key - ?
• forking lemma - for folding schemes modifies the forking lemma. The forking lemma is typically used to prove knowledge soundness, abstracting away some of the probabilistic reasoning. The original forking lemma shows that it is sufficient to construct a PPT extractor taking a tree of accepting transcripts that outputs a satisfying witness.
• committed relaxed R1CS - the relaxed (foldable) R1CS scheme extended to a succinct and zk folding scheme.

2,3 Preliminaries, Definitions

Mostly skippable, worth writing down quick notes the definitions for quick reference and preview

• $\mathbb F$ of order $2^{\Theta(\lambda})$, with $\lambda$ the security param
• denote computational indistinguishability $\cong$ WRT a PPT adv.
• defn for a CS over vectors ![[Pasted image 20230510162719.png]]
• defn 2: NI AoK: algorithms for:
  • $G(1^{\lambda})$ generating public params, $pp$
  • $K(pp,s)\rightarrow (pk,vk)$, on input structure $s$, representing common structure among instances, output prover key $pk$ and verifier key $vk$
  • $P(pk,u,w)\rightarrow \pi$ produce proof $\pi$ on witness $w$ and instance $u$
  • $V(vk,u,\pi)\rightarrow {0,1}$ check instance $u$ for given proof $\pi$.
  • subdefinitions for completeness and knowledge soundness given.
• defn 3: zk
• defn 4: succinctness
• defn 5: IVC - is defined by PPT algorithms $(G,P,V)$ and deterministic encoder $K$. An IVC scheme $(G,K,P,V)$ should satisfy completeness and knowledge soundness for any PPT adversary A, as well as succinctness, if the proof $\Pi$ does not grow with the number of applications $n$.
• defn 6 - folding scheme - a folding scheme for relation $R$ consists of
  • $G(1^\lambda )\rightarrow pp$ a PPT generator algorithm generating the public parameters
  • $K(pp,s) \rightarrow (pk,vk)$ a deterministic encoder, taking structure $s$ between instances to be folded
  • $P(pk, (u_1,w_1),(u_2,w_2))\rightarrow (u,w)$ a PPT algorithm
  • $V(vk,u_1,u_2)\rightarrow u$
  • A transcript is accepting if $P$ outputs a satisfying folded witness $w$ for the folded instance $u$.
• defn 7 non-interactive Folding Scheme
• defn 8: zk Folding Scheme
• defn 9: public coin FS - if messages from $V$ to $P$ are sampled from a uniform distribution
• Lemma 1: forking lemma for folding schemes modifies the forking lemma. The forking lemma is typically used to prove knowledge soundness, abstracting away some of the probabilistic reasoning. The original forking lemma shows that it is sufficient to construct a PPT extractor taking a tree of accepting transcripts that outputs a satisfying witness.

4 A Folding scheme for NP

Definitions

• defn 10 R1CS: for field $\mathbb F$, params $m,n,l\in \mathbb N$, $m>l$, R1CS consists of sparse matrices $A,B,C\in \mathbb F^{m\times m}$ with at most $n=\Omega(m)$ non-zero entries in each matrix. An instance $x\in \mathbb F^l$ consists of public inputs and outputs and is satisfied by witness $W\in \mathbb F^{m-l-1}$ if: $$AZ\circ BZ = CZ$$ where $Z=(W,x,1)$, a conveniently defined vector for checking consistency.
• defn 11 relaxed R1CS: as above, but allowing for error vector $E\in \mathbb F^m$, and scalar $u\in \mathbb F$. Instance $(E,u,x)$ is satisfied by witness $W$ if: $$AZ\circ BZ = u(CZ)+E$$ where $Z=(W,x,u)$.

Reasoning

A naive attempt to construct folding for R1CS fails may follow: attempt to take a random linear combination of witnesses $W_1, W_2$. Both P,V compute: $$\begin{align} x\gets x_1+rx_2\ W\gets W_1+rW_2 \end{align}$$ Then set the new pair to simply $(x,W)$. Does this work? No. For $Z_i=(W_i,x_i,1)$, we have: $$\begin{align} AZ\circ BZ = CZ &= A(Z_1+rZ_2)\circ B(Z_1+rZ_2)\ &= AZ_1\circ BZ_1 + r(AZ_1\circ BZ_2+AZ_2\circ BZ_1) + r^2(AZ_2\circ BZ_2)\ &= CZ - r(AZ_1\circ BZ_2+AZ_2\circ BZ_1)\ &\ne CZ \end{align}$$ So a modified attempt should somehow account for the crossterm: $$E\approx r(AZ_1\circ BZ_2+AZ_2\circ BZ_1)$$ See defn 11, relaxed R1CS at top of this sec. Building on the prior attempt, the vector $E$ may accumulate cross terms. In the modified scheme, the prover and verifier additionally compute: $$\begin{align} u&\gets u_1 + ru_2 \ E&\gets E_1+ r(AZ_1\circ BZ_2+AZ_2\circ BZ_1 - u_1CZ_2-u_2CZ_1)+r^2E_2 \end{align}$$ And set the new witness pair to be $((E,u,x),W)$. Now the cross terms may be consumed: $$\begin{align} AZ\circ BZ = CZ &= A(Z_1+rZ_2)\circ B(Z_1+rZ_2)\ &= AZ_1\circ BZ_1 + r(AZ_1\circ BZ_2+AZ_2\circ BZ_1) + r^2(AZ_2\circ BZ_2)\ &= (u_1+ru_2)C(Z_1+rZ_2)+E\ &= uCZ+E \end{align}$$ some intermediate computation excluded after the second line.

Thereby realizing a folding scheme with witness $(W,E)$.

The scheme given above is non-succinct and not zero knowledge, but can be made so with the modifications in the next note. We may apply succinct, additively homomorphic vector commitmetns to W and E to construct a variant referred to as committed relaxed R1CS.

Extension to Committed Relaxed R1CS

• Defn 12 Committed Relaxed R1CS - extending defn 11, let commitment params $pp_w$ and $pp_E$ for vectors of size $m$ and $m-l-1$. a CRR1CS instance is a tuple $(\bar E,u,\bar W,x)$ where $\overline{E,W}$ denote commitments, $u$ and $x$ are public inputs and outputs. An instance is satisfied by witness $(E,r_E,W,r_W)\in (\mathbb F^m,\mathbb F, \mathbb F^{m-l-1},\mathbb F)$ if $$\bar E= \mathsf{Com}(pp_E,E,r_E),\bar W=\mathsf{Com}(pp_W,W,r_W), \text{ and } AZ\circ BZ=u(CZ)+E)$$ where $Z=(W,x,u)$.

• Construction 1, a folding scheme for CRR1CS The contents of this scheme are technically involved, but can be simply understood. Instead of publishing two witness $(W_i,r_{E_i},E_i, r_{W_i})$, the prover provides to the verifier two CRR1CS instances $(\bar E_i,u_i,\bar W_i, x_i)$, where the additive homomorphism preserves the structure of the above folding scheme, underneath a commitment. That is, the result of this section is that we may obtain succinctness and zero knowledge for the folding scheme presented above.

The result is a public coin folding scheme for CRRR1CS with perfect completeness, knowledge soundness, and zero knowledge. In more detail: ![[Pasted image 20230510173106.png]]

Fiat Shamir

the remainder of the section addresses rendering the scheme NI with the Fiat Shamir Transform.

5 Nova: An IVC Scheme with Proof Compression

To construct IVC, that $z_n=F^{(n)}(z_0)$, we construct an "augmented function", which computes $F$, as well as performing additional "bookkeeping" to fold proofs of proofs of prior invocations of itself.

• $F'(vk, U_i, u_i, (i,z_0,z_i), w_i, \bar T)$ - the augmented function takes non-deterministic advice arguments for:
  • vk - the verifier key
  • U, u - two CRR1CS instances.
• $F'$, the augmented function, computes $F$, and the updated proof $\Pi_{i+1}$. It procedes as follows:
  • first executes a step of the incremental computation. $F'$ outputs $z_{i+1}=F(z_i)$.
  • Second, $F'$ invokes the NI verifier to fold the checking of $u_i$ and $U_i$ into checking $U_{i+1}$.
  • The IVC prover then computes a new instance $u_{i+1}$ attesting to the correct execution of invocation i+1 of $F'$, which attests that $z_{i+1}$ and $U_{i+1}$ are correct invocation of $F'$. ![[Pasted image 20230511082127.png]] Top: $F'$ computes the nth iteration of $F$. bottom: there exists a CRR1CS st the bottom claims hold

The remainder of the section gives a complete definition for the function $F'$

The prover can produce a IVC proof and send the proof to the verifier, however, the proof is nut succinct or zk. However, the Prover can prove knowledge of a satisfying proof with any zkSNARK:

• Issue: an off-the-shelf SNARK would force the prover to prove knowledge of vectors whose commitments equal a particular value; this would require encoding a linear number of group scalar multiplications.
• Construction 4 gives a high level zkSNARK for a valid IVC proof.
  • For $\Pi$, a proof for two CR1CS, P first folds $(u,w), (U,W)$ to produce a folded instance witness pair $(U',W')$ with the NIFS prover
  • Then P runs the zkSNARK prover to prove knowledge of a valid witness for $U'$.

We still must give a convenient zkSNARK, which the authors adapt from Spartan in section 6.

6 a zkSNARK for Committed Relaxed R1CS

To transform the above IVC-enabled scheme into a fully powered zk-SNARK, we need to construct a argument scheme targeting CRR1CS.

• defn 13 polynomial extension (MLE) - for $f:{0,1}^l\rightarrow \mathbb F$, a polynomial extension for $f$ is a low-degree $l$-variate polynomial $\tilde f:\mathbb F^l\rightarrow \mathbb F$ such that $\tilde f(x) = f(x)$ for all $x\in {0,1}^l$.
• Lemma 5 Sumcheck protocol - For an $l$-variate polynomial $G$ over $\mathbb F$ with degree at most $\mu$ in each variable, Sumcheck is a public-coin interactive proof protocol, reducing the checking that: $$\Sigma_{x\in{0,1}^{l}}G(x)=T$$ to the task of checking that: $$G(r) = e \text{ for $r\in\mathbb F^l$} $$ The interaction consists of $l$ rounds, where in each round the verifier sends a single element of $\mathbb F$, and the prover responds with $\mu+1$ elements.

A polynomial IOP for Idealized relaxed R1CS

The penultimate section gives an adaptation of Spartan's polynomial IOP for relaxed R1CS. (bail)

Compliing P-IOPs to zkSNARKs

the final section gives a compilation from the adapted Spartan p-IOP into a zkSNARK using a PCS and the FiatS transform, giving candidate inner product arguments for PCS from Dory and Bulletproofs.

Using Dory or Bulletproofs, give PCS's to $m$-sized vectors over $\mathbb F$ can be made in $\log m$ variate multilinear polynomial, if there exist an argument protocol to prove inner product computation between a committed vector and an m-sized public vector, with $r$ as an evaluation point.

If the commitment scheme for vectors over $\mathbb F$ is Pedersen, bulletproofs are such a protocol. If the vectors are committed over a 2-tier matrix commitment, Dory provides an IPA. Spartan provides a compiler to transform existing PCS into those that may handle sparse ML polynomials.

related:

• topic:: [[topic-Folding Schemes]]