Nova and its Implementation：A Deep Dive

• Nova and its Implementation：A Deep Dive
  • Code structure
  • r1cs mod
    • R1CS
    • Relaxed R1CS
    • Committed Relaxed R1CS
    • A Folding Scheme for Committed Relaxed R1CS
    • code
  • nifs mod
    • A Non-Interactive Folding Scheme
    • code
  • constants mod
  • circuit mod
    • code
  • lib.rs
    • A zkSNARK of a Valid IVC Proof
    • Idealized Relaxed R1CS
    • Polynomial IOP for Idealized Relaxed R1CS
  • bellpepper mod
  • dependencies
    • bellpepper

This article will analysis Nova's code implementation, and explain how the code works based on the relevant papers.

I will first deduce the formula according to the papers, until it corresponds to the code, and then explain the code, which will be clearer and easier to understand.

As of August 30, 2023, I refer to the code corresponding to the latest commit, and considering that the code comments should be located near the code as much as possible, so I created the Nova-Analysis repo to save the code comments. When there are code comments, I will prompt in this article

Code structure

// private modules
mod bellpepper;
mod circuit;
mod constants;
mod nifs;
mod r1cs;

// public modules
pub mod errors;
pub mod gadgets;
pub mod provider;
pub mod spartan;
pub mod traits;

According to its lib.rs, we know that Nova has these different mods. we explain these mods below.

r1cs mod

Here is a example on how r1cs works.

R1CS

a example

the relation:

private inputs

$\{w_1,w_2,w_3,w_4\}$ and public output

$x_1$ satisfy the following constraint relation:

$$(w_1+w_2)\ast (w_3\ast w_4)=x_1$$

Let's try to represent this relation in terms of R1CS.

the circuit:

the R1CS struct:

let

$Z=\left[\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\\ w_5\\ x_1\\ 1\end{array}\right]$, According to the definition in Nova

$Z=\left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]$, where

$W$ represents witness, including private input and intermediate values, that is

$w_i$ here.

$\mathsf{x}$ represents public inputs and outputs, that is

$x_1$ here. If there are constants in the relation, the 1 can be used to encode them.

Write the

$ABC$ matrix according to the circuit:

for multiplication gate #1, the left input is

$(w_1+w_2)=\left[\begin{array}{ccccccc}1& 1& 0& 0& 0& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\\ w_5\\ x_1\\ 1\end{array}\right]$

for multiplication gate #2, the left input is

$w_3=\left[\begin{array}{ccccccc}0& 0& 1& 0& 0& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\\ w_5\\ x_1\\ 1\end{array}\right]$

So, we get the left input matrix:

$$A=\left[\begin{array}{ccccccc}1& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\end{array}\right]$$

Matrix

$A$ consists of the left input of the all multiplication gates, and its number of rows is equal to the number of multiplication gates, and its number of columns is equal to the length of vector

$Z$.

Using the same approach, we can get the right input matrix:

$$B=\left[\begin{array}{ccccccc}0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 0\end{array}\right]$$

Matrix

$B$ consists of the right input of the all multiplication gates. Its shape is the same with

$A$.

$$C=\left[\begin{array}{ccccccc}0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 0\end{array}\right]$$

Matrix

$C$ consists of the output of the all multiplication gates. Its shape is the same with

$A$.

Let's check:

$$\begin{array}{rl}(A\cdot Z)\circ (B·Z)& =(\left[\begin{array}{ccccccc}1& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\\ w_5\\ x_1\\ 1\end{array}\right])\circ (\left[\begin{array}{ccccccc}0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 0\end{array}\right]\cdot \left[\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\\ w_5\\ x_1\\ 1\end{array}\right])\\ & =\left[\begin{array}{c}{w}_1+w_2\\ w_3\end{array}\right]\circ \left[\begin{array}{c}{w}_5\\ w_4\end{array}\right]=\left[\begin{array}{c}(w_1+w_2)w_5\\ w_3{w}_4\end{array}\right]=\left[\begin{array}{c}{x}_1\\ w_5\end{array}\right]=C\cdot Z\end{array}$$

R1CS Definition

According to Definition 10 (R1CS) in Nova paper:

Consider a finite field

$\mathbb{F}$. Let the public parameters consist of size bounds

$m,n,l\in \mathbb{N}$ where

$m>l$. The R1CS structure consists of sparse matrices

$A,B,C\in {\mathbb{F}}^{m\times m}$ with at most

$n=\mathrm{\Omega }(m)$ non-zero entries in each matrix. An instance

$\mathsf{x}\in {\mathbb{F}}^l$ consists of public inputs and outputs and is satisfied by a witness

$W\in {\mathbb{F}}^{m-l-1}$ if

$(A\cdot Z)\circ (B\cdot Z)=C\cdot Z$, where

$Z=(W,\mathsf{x},1)$.

R1CS's attempt:

There are different vector

$Z_1$ and

$Z_2$ for different instance witness pairs

$({\mathsf{x}}_{\mathsf{1}},W_1)$,

$({\mathsf{x}}_{\mathsf{2}},W_2)$ and so on, which need to be verified repeatedly

$(A\cdot Z_i)\circ (B·Z_i)=C·Z_i$.

It can be seen that matrix

$A,B,C$ representing constraints will not change. What Folding needs to solve is to reduce the number of verifications

$(A\cdot Z_i)\circ (B·Z_i)=C·Z_i$ by merging different instances

$Z_i$

So,

$Z=\left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]$, choose a random value

$r\in \mathbb{F}$, let

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

failed because

$Z\ne Z_1+r\cdot Z_2$

Relaxed R1CS

Relaxed R1CS Definition

According to Definition 11 (Relaxed R1CS) in Nova paper:

Consider a finite field

$\mathbb{F}$. Let the public parameters consist of size bounds

$m,n,l\in \mathbb{N}$ where

$m>l$. The relaxed R1CS structure consists of sparse matrices

$A,B,C\in {\mathbb{F}}^{m\times m}$ with at most

$n=\mathrm{\Omega }(m)$ non-zero entries in each matrix. A relaxed R1CS instance consists of an error vector

$E\in {\mathbb{F}}^m$, a scalar

$u\in \mathbb{F}$, and public inputs and outputs

$x\in {\mathbb{F}}^l$. An instance

$(E,u,\mathsf{x})$ is satisfied by a witness

$W\in {\mathbb{F}}^{m-l-1}$ if

$(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where

$Z=(W,\mathsf{x},u)$.

Relaxed R1CS's attempt:

From the definition, we can get:

$$\begin{array}{rl}(A\cdot Z_i)\circ (B\cdot Z_i)& =u_i\cdot (C\cdot Z_i)+E_i\\ Z& =(W,\mathsf{x},u)\end{array}$$

Choose a random value

$r\in \mathbb{F}$, if we perform a linear combination of two instances in the following way:

$$\begin{array}{rl}\mathsf{x}& \leftarrow {\mathsf{x}}_{\mathsf{1}}+r\cdot {\mathsf{x}}_{\mathsf{2}}\\ W& \leftarrow W_1+r\cdot W_2\\ u& \leftarrow u_1+r\cdot u_2\\ E& \leftarrow E_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-u_{1}C{Z}_2-u_{2}C{Z}_1)+r^2\cdot E_2\end{array}$$

We can deduce the following result:

$Z=(W,\mathsf{x},u)=\left[\begin{array}{c}W\\ \mathsf{x}\\ u\end{array}\right]=\left[\begin{array}{c}{W}_1+r{W}_2\\ {\mathsf{x}}_1+r{\mathsf{x}}_2\\ u_1+r{u}_2\end{array}\right]=Z_1+r\cdot Z_2$.

$$\begin{array}{rl}AZ\circ BZ& =A(Z_1+r\cdot Z_2)\circ B(Z_1+r\cdot Z_2)\\ & =A{Z}_1\circ B{Z}_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot A{Z}_2\circ B{Z}_2\\ & =u_1\cdot C{Z}_1+E_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot (u_2\cdot C{Z}_2+E_2)\\ & =u_1\cdot C{Z}_1+r{u}_2\cdot C{Z}_1-r{u}_2\cdot C{Z}_1+E_1+r\cdot (A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+r^2\cdot (u_2\cdot C{Z}_2+E_2)+r{u}_{1}C{Z}_2-r{u}_{1}C{Z}_2\\ & =(u_1+r{u}_2)C{Z}_1+E_1-r{u}_{2}C{Z}_1+r(A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1)+(u_1+r{u}_2)rC{Z}_2+r^2{E}_2-r{u}_{1}C{Z}_2\\ & =(u_1+r{u}_2)C(Z_1+r{Z}_2)+r(A{Z}_1\circ B{Z}_2+A{Z}_2\circ B{Z}_1-u_{2}C{Z}_1-u_{1}C{Z}_2)+E_1+r^2{E}_2\\ & =uCZ+E\end{array}$$

Success! we only need to verify whether

$Z$ satisfies the constraints

$(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$ to check whether both

$Z_1$ and

$Z_2$ satisfy the constraints.

Committed Relaxed R1CS

Committed Relaxed R1CS Definition

According to Definition 12 (Committed Relaxed R1CS) in Nova paper:

Consider a finite field

$\mathbb{F}$ and a commitment scheme

$\mathsf{Com}$ over

$\mathbb{F}$. Let the public parameters consist of size bounds

$m,n,l\in \mathbb{N}$ where

$m>l$, and commitment parameters

${\mathsf{pp}}_E$ and

${\mathsf{pp}}_W$ for vectors of size

$m$ and

$m-l-1$ respectively. The committed relaxed R1CS structure consists of sparse matrices

$A,B,C\in {\mathbb{F}}^{m\times m}$ with at most

$n=\mathrm{\Omega }(m)$ non-zero entries in each matrix. A committed relaxed R1CS instance is a tuple

$(\bar{E},u,\bar{W},\mathsf{x})$, where

$\bar{E}$ and

$\bar{W}$ are commitments,

$u\in \mathbb{F}$, and

$x\in {\mathbb{F}}^l$ are public inputs and outputs. An instance

$(\bar{E},u,\bar{W},\mathsf{x})$ is satisfied by a 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}({\mathsf{pp}}_E,E,r_E),\bar{W}=\mathsf{Com}({\mathsf{pp}}_W,W,r_W)$, and

$(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where

$Z=(W,\mathsf{x},u)$.

For more introduction to the commitment, please refer to the wiki.

A Folding Scheme for Committed Relaxed R1CS

According to Construction 1 (A Folding Scheme for Committed Relaxed R1CS) in Nova paper:

Consider a finite field

$\mathbb{F}$ and a succinct, hiding, and homomorphic commitment scheme

$\mathsf{Com}$ over

$\mathbb{F}$. We define the generator and the encoder as follows.
–

$\mathcal{G}(1^{\lambda })\to \mathsf{pp}$: output size bounds

$m,n,l\in \mathbb{N}$, and commitment parameters

${\mathsf{pp}}_E$ and

${\mathsf{pp}}_W$ for vectors of size

$m$ and

$m-l-1$ respectively.
–

$\mathcal{K}(\mathsf{pp},(A,B,C))\to (\mathsf{pk}\mathsf{,}\mathsf{vk})$: output

$\mathsf{pk}\leftarrow (\mathsf{pp},(A,B,C))$ and

$\mathsf{vk}\leftarrow \mathrm{\perp }$.

The verifier

$\mathcal{V}$ takes two committed relaxed R1CS instances

$(\overline{E_1},u_1,\overline{W_1},{\mathsf{x}}_1)$ and

$(\overline{E_2},u_2,\overline{W_2},{\mathsf{x}}_2)$. The prover

$\mathcal{P}$, in addition to the two instances, takes witnesses to both instances,

$(E_1,r_{E_1},W_1,r_{W_1})$ and

$(E_2,r_{E_2},W_2,r_{W_2})$. Let

$Z_1=(W_1,{\mathsf{x}}_1,u_1)$ and

$Z_2=(W_2,{\mathsf{x}}_2,u_2)$. The prover and the verifier proceed as follows.

1. $\mathcal{P}:$ Send
   $\bar{T}:=\mathsf{Com}({\mathsf{pp}}_E,T,r_T)$, wherer
   $r_T{\leftarrow }_R\mathbb{F}$ and with cross term
   
   $$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.$$
2. $\mathcal{V}:$ Sample and send challenge
   $r{\leftarrow }_r\mathbb{F}$.
3. $\mathcal{V}\mathcal{,}\mathcal{P}:$ Output the folded instance
   $(\bar{E},u,\bar{W},\mathsf{x})$ where
   
   $$\begin{array}{rl}\bar{E}& \leftarrow \overline{E_1}+r\cdot \bar{T}+r^2\cdot \overline{E_2}\\ u& \leftarrow u_1+r\cdot u_2\\ \bar{W}& \leftarrow \overline{W_1}+r\cdot \overline{W_2}\\ \mathsf{x}& \leftarrow {\mathsf{x}}_1+r\cdot {\mathsf{x}}_2\end{array}$$
4. $\mathcal{P}:$ Output the folded witness
   $(E,r_E,W,r_W)$, where
   
   $$\begin{array}{rl}E& \leftarrow E_1+r\cdot T+r^2\cdot E_2\\ r_E& \leftarrow r_{E_1}+r\cdot r_T+r^2\cdot r_{E_2}\\ W& \leftarrow W_1+r\cdot W_2\\ r_W& \leftarrow r_{W_1}+r\cdot r_{W_2}\end{array}$$

code

Next, we analyze the code of r1cs mod according to the above theory, located in src/r1cs.rs.

R1CS struct

pub struct R1CS<G: Group> { 
  _p: PhantomData<G>,
}

This structure only retains a generic G, which needs to implement the methods in the Group trait, and has no valid data other than that.

There is a method for R1CS:

• commitment_key, for a given circuit(certain
  $A,B,C$), it will call Group's CE type's setup method to get a CommitmentKey and return it.

R1CSShape struct

pub struct R1CSShape<G: Group> {
  pub(crate) num_cons: usize,
  pub(crate) num_vars: usize,
  pub(crate) num_io: usize,
  pub(crate) A: Vec<(usize, usize, G::Scalar)>,
  pub(crate) B: Vec<(usize, usize, G::Scalar)>,
  pub(crate) C: Vec<(usize, usize, G::Scalar)>,
}

R1CSShape means matrix

$A,B,C,$ that is, circuit constraints.

There are some fields in this structure:

• num_cons: Length of a column in the matrix, also the number of multiplication gates.
• num_vars: Length of witness
  $W$, and according to the previous, it equals
  $m-l-1$.
• num_io: Length of public input and output
  $x$, and according to the previous, it equals
  $l$.
• A, B, C: Represent the position and value of the non-zero value in the sparse matrix.

We can get length of a column in the matrix by num_vars + num_io + 1, so the three matrices

$A,B,C$ are completely determined by struct R1CSShape.

There are some methods for R1CSShape:

• new(): Receive num_cons, num_vars, num_io, A, B, C as parameters, then do some checks，and return R1CSShape. The checks's comments.
• check_regular_shape(): Checks regularity conditions on the R1CSShape, required in Spartan-class SNARKs. The checks's comments.
• multiply_vec(): Calculate and return them:
  $(A\cdot Z,B\cdot Z,C\cdot Z)$
• is_sat_relaxed(): Check
  $A\cdot Z\circ B\cdot Z=u\cdot C\cdot Z+E$,
  $\bar{W}=\mathsf{Com}({\mathsf{pp}}_W,W,ck)$ and
  $\bar{E}=\mathsf{Com}({\mathsf{pp}}_E,E,ck)$.
  $\bar{W}$ and
  $\bar{E}$ used the same commitment key.
• is_sat(): pass CommitmentKey, R1CSInstance and R1CSWitness as parameters, check
  $A\cdot \left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]\circ B\cdot \left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]=C\cdot \left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]$ and
  $\bar{W}=\mathsf{Com}({\mathsf{pp}}_W,W,ck)$
• commit_T():
  $\bar{T}:=\mathsf{Com}({\mathsf{pp}}_W,T,c{k}_T)$, wherer
  $r_T{\leftarrow }_R\mathbb{F}$ and with cross term
  
  $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$. first calculate
  $Z_1$ and
  $Z_2$ by
  $Z_i=(W_i,u_i,x_i)$
• pad(): make witness.len() = M.colume.len() = 2^k, required in Spartan-class SNARKs.

R1CSWitness struct

pub struct R1CSWitness<G: Group> {
  W: Vec<G::Scalar>,
}

R1CSWitness means

$W$, Witness of R1CS, which is a vector of length

$m-l-1$, the

$W$ in

$Z=\left[\begin{array}{c}W\\ \mathsf{x}\\ 1\end{array}\right]$

There are some methods for R1CSWitness:

• new(): Pass in an R1CSShape example S and a vector W. Because creating a Witness needs to know which R1CS's witness it is, and it will check that the length of W is equal to S.num_vars.
• commit(): Calculate
  $\bar{W}=\mathsf{Com}({\mathsf{pp}}_W,W,r_W)$. And the parameter ck, a CommitmentKey, means
  $r_W$.

R1CSInstance struct

pub struct R1CSInstance<G: Group> {
  pub(crate) comm_W: Commitment<G>,
  pub(crate) X: Vec<G::Scalar>,
}

R1CSInstance means

$(\bar{W},\mathsf{x})$

There are a method for R1CSInstance:

• new():
  $(\bar{W},\mathsf{x},1)$ and A.num_io should == x.len()

RelaxedR1CSWitness struct

pub struct RelaxedR1CSWitness<G: Group> {
  pub(crate) W: Vec<G::Scalar>,
  pub(crate) E: Vec<G::Scalar>,
}

RelaxedR1CSWitness means

$(W,E)$.

There are some methods for RelaxedR1CSWitness:

• default(), use zero value to init the
  $W,E$.
• from_r1cs_witness(), use zero value to init the
  $E$, and get the
  $W$ from parameter.
• commit(), return
  $\bar{W}/\bar{E}=\mathsf{Com}({\mathsf{pp}}_{W/E},W/E,ck)$, with the same comitment key ck.
• fold(), Calculate
  $W=W_1+r\cdot W_2$ and
  $E=E_1+r\cdot T$, used the same r. Why is not
  $E=E_1+r\cdot T+r^2\cdot E_2$ here? since
  $E_2$ of parameter's R1CSWitness is
  $\overrightarrow{0}$,
  $r^2\cdot E_2$ can be omitted.
• pad(): Pads the provided witness to the correct length.

RelaxedR1CSInstance struct

pub struct RelaxedR1CSInstance<G: Group> {
  pub(crate) comm_W: Commitment<G>,
  pub(crate) comm_E: Commitment<G>,
  pub(crate) X: Vec<G::Scalar>,
  pub(crate) u: G::Scalar,
}

RelaxedR1CSInstance means

$(\bar{W},\bar{E},\mathsf{x},u)$

There are some methods for RelaxedR1CSInstance:

• default(): Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
• from_r1cs_instance(): Initializes a new RelaxedR1CSInstance from an R1CSInstance, the u use one value
• from_r1cs_instance_unchecked(): Initializes a new RelaxedR1CSInstance from an R1CSInstance, the u use one value
• fold(): Folds an incoming R1CSInstance into the current one, calculate
  $\mathsf{x}={\mathsf{x}}_1+r\cdot {\mathsf{x}}_{\mathsf{2}}$ and
  $\bar{W}=\overline{W_1}+r\cdot \overline{W_2}$ and
  $\bar{E}=\overline{E_1}+r\cdot \bar{T}$ and
  $u=u_1+r$ used the same r. Why is not
  $\bar{E}=\overline{E_1}+r\cdot \bar{T}+r^2\cdot \overline{E_2}$ here? Since
  $\overline{E_2}$ of parameter's R1CSInstance is
  $\mathcal{O}$,
  $r^2\cdot \overline{E_2}$ can be omitted. and why is it
  $u=u_1+r\cdot u_2$? Since the
  $u_2$ from R1CSInstance is 1 in default.

nifs mod

A Non-Interactive Folding Scheme

According to Construction 2 (A Non-Interactive Folding Scheme) in Nova paper:

We achieve non-interactivity in the random oracle model using the strong Fiat-Shamir transform. Let

$\rho$ denote a random oracle sampled during parameter generation and provided to all parties. Let

$(\mathsf{G}\mathsf{,}\mathsf{K}\mathsf{,}\mathsf{P}\mathsf{,}\mathsf{V})$ represent our interactive folding scheme (Construction 1). We construct a non-interactive folding scheme

$\mathcal{(}\mathcal{G}\mathcal{,}\mathcal{K}\mathcal{,}\mathcal{P}\mathcal{,}\mathcal{V}\mathcal{)}$ as follows:
–

$\mathcal{G}(1^{\lambda })$: output

$\mathsf{pp}\leftarrow \mathsf{G}(1^{\lambda })$.
–

$\mathcal{K}(\mathsf{pp},(A,B,C))$:

$\mathsf{vk}\leftarrow \rho (\mathsf{pp},\mathsf{s})$ and

$\mathsf{pk}\leftarrow (\mathsf{pp},(A,B,C),\mathsf{vk})$; output

$(\mathsf{vk},\mathsf{pk})$.
–

$\mathcal{P}(\mathsf{pk},(u_1,w_1),(u_2,w_2))$: runs

$\mathsf{P}((\mathsf{pk}\mathsf{.}\mathsf{pp},\mathsf{pk}\mathsf{.}(A,B,C))$ to retrieve its first message

$\bar{T}$ , and sends

$\bar{T}$ to

$\mathcal{V}$; computes

$r\leftarrow \rho (\mathsf{vk},u_1,u_2,\bar{T})$, forwards this to

$\mathsf{P}$, and outputs the resulting output.
–

$\mathcal{V}(\mathsf{vk},u_1,u_2,\bar{T})$: runs

$\mathsf{V}$ with

$\bar{T}$ as the message from the prover and with randomness

$r\leftarrow \rho (\mathsf{vk},u_1,u_2,\bar{T})$, and outputs the resulting output.

Assumption 1 (RO instantiation):

Construction 2 is a non-interactive folding scheme that satisfies completeness, knowledge soundness, and zero-knowledge in the standard model when

$\rho$ is instantiated with a cryptographic hash function.

code

Next, we analyze the code of nifs mod, located in src/nifs.rs.

NIFS struct

pub struct NIFS<G: Group> {
  pub(crate) comm_T: CompressedCommitment<G>,
}

This structure contains

$\bar{T}$, where

$$\begin{gathered} T=A\cdot Z_1\circ B\cdot Z_2+A\cdot Z_2\circ B\cdot Z_1-u_1\cdot C\cdot Z_2-u_2\cdot C\cdot Z_1, \\ \bar{T}=\mathsf{Com}({\mathsf{pp}}_E,T,r_E) \end{gathered}$$ and there are two methods impl for NISF:

• prove(): Given ck, ro_consts, pp_digest, S
  $(A,B,C)$, U1
  $(\overline{W_1},\overline{E_1},{\mathsf{x}}_{\mathsf{1}},u_1)$, W1
  $(W_1,E_1)$, U2
  $(\overline{W_2},{\mathsf{x}}_2)$, W2(
  $W_2$), return NIFS ,
  $(W,E)$ and
  $(\bar{W},\bar{E},\mathsf{x},u)$, and the random r = ρ(ro_consts, pp_digest, U1, U2, comm_T)
• verify(): Given ro_consts, pp_digest, U1
  $(\overline{W_1},\overline{E_1},{\mathsf{x}}_{\mathsf{1}},u_1)$, U2
  $(\overline{W_2},{\mathsf{x}}_{\mathsf{2}})$, get
  $\bar{T}$ from self.comm_T, calculate random r = ρ(ro_consts, pp_digest, U1, U2, comm_T), return the new U = U1.fold(U2).

constants mod

pub(crate) const NUM_CHALLENGE_BITS: usize = 128;
pub(crate) const NUM_HASH_BITS: usize = 250;
pub(crate) const BN_LIMB_WIDTH: usize = 64;
pub(crate) const BN_N_LIMBS: usize = 4;
pub(crate) const NUM_FE_WITHOUT_IO_FOR_CRHF: usize = 17;
pub(crate) const NUM_FE_FOR_RO: usize = 24;

• NUM_CHALLENGE_BITS: Valid output bits when a random oracle is used to generate challenge value r.
• NUM_HASH_BITS: Valid output bits when a random oracle is used to generate hash
• BN_LIMB_WIDTH and BN_N_LIMBS: Use 4 * 64 bits to represent 256 bits.
• NUM_FE_WITHOUT_IO_FOR_CRHF
• NUM_FE_FOR_RO

circuit mod

According to Construction 3 (IVC) in Nova paper:

Let

$\mathsf{NIFS}=(\mathsf{G},\mathsf{K},\mathsf{P},\mathsf{V})$ be the non-interactive folding scheme for committed relaxed R1CS (Construction 2). Consider a polynomialtime function F that takes non-deterministic input, and a cryptographic hash function

$\mathsf{hash}$. We define our augmented function

$F^{\prime }$ as follows (all arguments to

$F^{\prime }$ are taken as non-deterministic advice):

$\underset{―}{F^{\prime }(\mathsf{vk},{\mathsf{U}}_i,{\mathsf{u}}_i,(i,z_0,z_i),w_i,\bar{T})\to \mathsf{x}:}$

If

$i$ is

$0$, output

$\mathsf{hash}(\mathsf{vk},1,z_0,F(z_0,w_i),{\mathsf{u}}_{\mathrm{\perp }})$;

otherwise,

$(1)$ check that

${\mathsf{u}}_i.\mathsf{x}=\mathsf{hash}(\mathsf{vk},i,z_0,z_i,{\mathsf{U}}_i)$, where

${\mathsf{u}}_i.\mathsf{x}$ is the public IO of

${\mathsf{u}}_i$,

$(2)$ check that

$({\mathsf{u}}_i.\bar{E},{\mathsf{u}}_i.u)=({\mathsf{u}}_{\mathrm{\perp }}.\bar{E},1)$,

$(3)$ compute

${\mathsf{U}}_{i+1}\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{V}(\mathsf{vk}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u},\bar{T})$, and

$(4)$ output

$\mathsf{hash}(\mathsf{vk},i+1,z_0,F(z_i,w_i),{\mathsf{U}}_{i+1})$.

$$ Because

$F^{\prime }$ can be computed in polynomial time, it can be represented as a committed relaxed R1CS structure

${\mathsf{s}}_{F^{\prime }}$. Let

$$({\mathsf{u}}_{i+1},{\mathsf{w}}_{i+1})\leftarrow \mathsf{trace}(F^{\prime },(\mathsf{vk},{\mathsf{U}}_i,{\mathsf{u}}_i,(i,z_0,z_i),w_i,\bar{T}))$$
denote the satisfying committed relaxed R1CS instance-witness pair

$({\mathsf{u}}_{i+1},{\mathsf{w}}_{i+1})$ for the execution of

$F^{\prime }$ on non-deterministic advice

$(\mathsf{vk},{\mathsf{U}}_i,{\mathsf{u}}_i,(i,z_0,z_i),w_i,\bar{T})$.

$$ We define the IVC scheme

$(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V})$ as follows.

$\underset{―}{\mathcal{G}(1^{\lambda })\to \mathsf{pp}}$: Output

$\mathsf{NIFS}\mathsf{.}\mathsf{G}(1^{\lambda })$.

$\underset{―}{\mathcal{K}(\mathsf{pp},F)\to (\mathsf{pk},\mathsf{vk})}$:

Compute

$({\mathsf{pk}}_{\mathsf{fs}},{\mathsf{vk}}_{\mathsf{fs}})\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{K}(\mathsf{pp},{\mathsf{s}}_{F^{\prime }})$ and output

$(\mathsf{pk}\mathsf{,}\mathsf{vk})\leftarrow ((F,{\mathsf{pk}}_{\mathsf{fs}}),(F,{\mathsf{vk}}_{\mathsf{fs}}))$.

$\underset{―}{\mathcal{P}(\mathsf{pk},(i,z_0,z_i),w_i,{\mathrm{\Pi }}_i)\to {\mathrm{\Pi }}_{i+1}}$:

Parse

${\mathrm{\Pi }}_i$ as

$(({\mathsf{U}}_i,{\mathsf{W}}_i),({\mathsf{u}}_i,{\mathsf{w}}_i))$ and then

$(1)$ if

$i$ is

$0$, compute

$({\mathsf{U}}_{i+1},{\mathsf{W}}_{i+1},\bar{T})\leftarrow ({\mathsf{u}}_{\mathrm{\perp }},{\mathsf{w}}_{\mathrm{\perp }},{\mathsf{u}}_{\mathrm{\perp }}.\bar{E})$;

$$ otherwise, compute

$({\mathsf{U}}_{i+1},{\mathsf{W}}_{i+1},\bar{T})\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{P}(\mathsf{pk},({\mathsf{U}}_i,{\mathsf{W}}_i),({\mathsf{u}}_i,{\mathsf{w}}_i))$,

$(2)$ compute

$({\mathsf{u}}_{i+1},{\mathsf{w}}_{i+1})\leftarrow \mathsf{trace}(F^{\prime },(\mathsf{vk},{\mathsf{U}}_i,{\mathsf{u}}_i,(i,z_0,z_i),w_i,\bar{T}))$, and

$(3)$ output

${\mathrm{\Pi }}_{i+1}\leftarrow (({\mathsf{U}}_{i+1},{\mathsf{W}}_{i+1}),({\mathsf{u}}_{i+1},{\mathsf{w}}_{i+1}))$.

$\underset{―}{\mathcal{V}(\mathsf{vk},(i,z_0,z_i),{\mathrm{\Pi }}_i)\to \{0,1\}}$:

If

$i$ is

$0$, check that

$z_i=z_0$;
otherwise,

$(1)$ parse

${\mathrm{\Pi }}_i$ as

$(({\mathsf{U}}_i,{\mathsf{W}}_i),({\mathsf{u}}_i,{\mathsf{w}}_i))$,

$(2)$ check that

${\mathsf{u}}_i.\mathsf{x}=\mathsf{hash}(\mathsf{vk},i,z_0,z_i,{\mathsf{U}}_i)$,

$(3)$ check that

$({\mathsf{u}}_i.\bar{E},\mathsf{u}.u)=({\mathsf{u}}_{\mathrm{\perp }}.\bar{E},1)$, and

$(4)$ check that

${\mathsf{W}}_i$ and

${\mathsf{w}}_i$ are satisfying witnesses to

${\mathsf{U}}_i$ and

${\mathsf{u}}_i$ respectively.

code

pub struct NovaAugmentedCircuitParams {
  limb_width: usize, // word size
  n_limbs: usize, // how many words
  is_primary_circuit: bool, // A boolean indicating if this is the primary circuit
}

pub struct NovaAugmentedCircuitInputs<G: Group> {
  params: G::Scalar, // Hash(Shape of u2, Gens for u2). Needed for computing the challenge.
  i: G::Base,
  z0: Vec<G::Base>,
  zi: Option<Vec<G::Base>>,
  U: Option<RelaxedR1CSInstance<G>>,
  u: Option<R1CSInstance<G>>,
  T: Option<Commitment<G>>,
}

params:

lib.rs

A zkSNARK of a Valid IVC Proof

Construction 4 (A zkSNARK of a Valid IVC Proof). Let

$\mathsf{IVC}$ denote the IVC scheme in Construction 3, let

$\mathsf{NIFS}$ denote the non-interactive folding scheme in Construction 2, and let

$\mathsf{hash}$ denote a randomized cryptographic hash function. Assume a zero-knowledge succinct non-interactive argument of knowledge (Definition 2),

$\mathsf{zkSNARK}$, for committed relaxed R1CS. That is, given public parameters

$\mathsf{pp}$, structure

$\mathsf{s}$, and instance

$\mathsf{u}$,

$\mathsf{zkSNARK}\mathsf{.}\mathsf{P}$ can convince

$\mathsf{zkSNARK}\mathsf{.}\mathsf{V}$ in zero-knowledge and with a succinct proof (e.g.,

$O_{\lambda }(\log N)$-sized proof) that it knows a corresponding witness

$\mathsf{w}$ such that

$(\mathsf{pp}\mathsf{,}\mathsf{s}\mathsf{,}\mathsf{u}\mathsf{,}\mathsf{w})$ is a satisfying committed relaxed R1CS tuple.

$$Consider a polynomial-time computable function

$F$. Suppose

$\mathsf{pp}\leftarrow \mathsf{IVC}\mathsf{.}\mathsf{G}(1^{\lambda })$ and

$(\mathsf{pk}\mathsf{,}\mathsf{vk})\leftarrow \mathsf{IVC}\mathsf{.}\mathsf{K}(\mathsf{pp},F)$. Suppose the prover

$\mathcal{P}$ and verifier

$\mathcal{V}$ are provided an instance

$(i,z_0,z_i)$. We construct a zkSNARK that allows the prover to show that it knows an IVC proof

${\mathrm{\Pi }}_i$ such that

$\mathsf{IVC}\mathsf{.}\mathsf{V}(\mathsf{vk},i,z_0,z_i,{\mathrm{\Pi }}_i)=1$.

$$In a nutshell, we leverage the fact that

$\mathrm{\Pi }$ is two committed relaxed R1CS instance-witness pairs. So,

$\mathcal{P}$ first folds instance-witness pairs

$(\mathsf{u}\mathsf{,}\mathsf{w})$ and

$(\mathsf{U}\mathsf{,}\mathsf{W})$ to produce a folded instance-witness pair

$({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime })$, using

$\mathsf{NIFS}\mathsf{.}\mathsf{P}$. Next,

$\mathcal{P}$ runs

$\mathsf{zkSNARK}\mathsf{.}\mathsf{P}$ to prove that it knows a valid witness for

${\mathsf{U}}^{\prime }$. In more detail, for polynomial-time computable function

$F$ and corresponding function

$F^{\prime }$ as defined in Construction 3 (and instantiated with

$\mathsf{hash}$), we define

$(\mathcal{G}\mathcal{,}\mathcal{K}\mathcal{,}\mathcal{P}\mathcal{,}\mathcal{V})$ as follows.

$\underset{―}{\mathcal{G}(1^{\lambda })\to \mathsf{pp}}$:

$(1)$ Compute

${\mathsf{pp}}_{\mathsf{NIFS}}\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{G}(1^{\lambda })$

$(2)$ Compute

${\mathsf{pp}}_{\mathsf{zkSNARK}}\leftarrow \mathsf{zkSNARK}\mathsf{.}\mathsf{G}(1^{\lambda })$

$(3)$ Output (

${\mathsf{pp}}_{\mathsf{NIFS}},{\mathsf{pp}}_{\mathsf{zkSNARK}})$

$\underset{―}{\mathcal{K}(\mathsf{pp},F)\to (\mathsf{pk}\mathsf{,}\mathsf{vk})}$:

$(1)$ Compute

$({\mathsf{pk}}_{\mathsf{NIFS}}\mathsf{,}{\mathsf{vk}}_{\mathsf{NIFS}})\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{K}(\mathsf{pp}\mathsf{.}{\mathsf{pp}}_{\mathsf{NIFS}},{\mathsf{s}}_{F^{\prime }})$.

$(2)$ Compute

$({\mathsf{pk}}_{\mathsf{zkSNARK}}\mathsf{,}{\mathsf{vk}}_{\mathsf{zkSNARK}})\leftarrow \mathsf{zkSNARK}\mathsf{.}\mathsf{K}(\mathsf{pp}\mathsf{.}{\mathsf{pp}}_{\mathsf{zkSNARK}},{\mathsf{s}}_{F^{\prime }})$.

$(3)$ Output

$(({\mathsf{pk}}_{\mathsf{NIFS}}\mathsf{,}{\mathsf{pk}}_{\mathsf{zkSNARK}}),({\mathsf{vk}}_{\mathsf{NIFS}}\mathsf{,}{\mathsf{vk}}_{\mathsf{zkSNARK}}))$.

$\underset{―}{\mathcal{P}(\mathsf{pk},(i,z_0,z_i),\mathrm{\Pi })\to \pi }$:
If

$i$ is

$0$, output

$\mathrm{\perp }$;
otherwise,

$(1)$ parse

$\mathrm{\Pi }$ as

$((\mathsf{U}\mathsf{,}\mathsf{W}),(\mathsf{u}\mathsf{,}\mathsf{w}))$

$(2)$ compute

$({\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime },\bar{T})\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{P}({\mathsf{pk}}_{\mathsf{NIFS}},(\mathsf{U}\mathsf{,}\mathsf{W}),(\mathsf{u}\mathsf{,}\mathsf{w}))$

$(3)$ compute

${\pi }_{{\mathsf{U}}^{\prime }}\leftarrow \mathsf{zkSNARK}\mathsf{.}\mathsf{P}({\mathsf{pk}}_{\mathsf{zkSNARK}}\mathsf{,}{\mathsf{U}}^{\prime }\mathsf{,}{\mathsf{W}}^{\prime })$

$(4)$ output

$(\mathsf{U}\mathsf{,}\mathsf{u},\bar{T},{\pi }_{{\mathsf{U}}^{\prime }})$.

$\underset{―}{\mathcal{V}(\mathsf{vk},(i,z_0,z_i),\pi )\to \{0,1\}}$:
If

$i$ is

$0$, check that

$z_0=z_i$;
otherwise,

$(1)$ parse

$\pi$ as

$(\mathsf{U}\mathsf{,}\mathsf{u},\bar{T},{\pi }_{{\mathsf{U}}^{\prime }})$,

$(2)$ check that

$\mathsf{u}\mathsf{.}\mathsf{x}=\mathsf{hash}({\mathsf{vk}}_{\mathsf{NIFS}},i,z_0,z_i,\mathsf{U})$,

$(3)$ check that

$(\mathsf{u}.\bar{E},\mathsf{u}.u)=({\mathsf{u}}_{\mathrm{\perp }}.\bar{E},1)$,

$(4)$ compute

${\mathsf{U}}^{\prime }\leftarrow \mathsf{NIFS}\mathsf{.}\mathsf{V}({\mathsf{vk}}_{\mathsf{NIFS}}\mathsf{,}\mathsf{U}\mathsf{,}\mathsf{u},\bar{T})$, and

$(5)$ check that

$\mathsf{zkSNARK}\mathsf{.}\mathsf{V}({\mathsf{vk}}_{\mathsf{zkSNARK}},{\mathsf{U}}^{\prime },{\pi }_{{\mathsf{U}}^{\prime }})=1$.

Polynomial Extension(MLE) see Notes for PAZK(MLE)

The Sum-Check Protocol see Notes for PAZK(Sum-Check)

Idealized Relaxed R1CS

Definition 14 (Idealized Relaxed R1CS). Consider a finite field

$\mathbb{F}$. Let the public parameters consist of size bounds

$m,n,l\in \mathbb{N}$ where

$m>l.$ The idealized relaxed R1CS structure consists of sparse matrices

$A,B,C\in {\mathbb{F}}^{m\times m}$ with at most

$n=\mathrm{\Omega }(m)$ non-zero entries in each matrix. A idealized relaxed R1CS instance consists of an error vector

$E\in {\mathbb{F}}^m$, a scalar

$u\in \mathbb{F}$, witness vector

$W\in {\mathbb{F}}^m$, and public inputs and outputs

$\mathsf{x}\in {\mathbb{F}}^l$. An instance

$(E,u,W,\mathsf{x})$ is satisfying if

$(A\cdot Z)\circ (B\cdot Z)=u\cdot (C\cdot Z)+E$, where

$Z=(W,\mathsf{x},u)$.

Polynomial IOP for Idealized Relaxed R1CS

Construction 5 (Polynomial IOP for Idealized Relaxed R1CS). Consider an idealized relaxed R1CS statement

$\phi$ consisting of public parameters

$(m,n,l)$, structure

$(A,B,C)$, and instance

$(E,u,W,\mathsf{x})$, Without loss of generality, we assume that

$m$ and

$n$ are powers of

$2$ and that

$m=2\cdot (l+1)$.

$$Let

$s=\log m$. We interpret the matrices

$A,B,C$ as functions with signature

$\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}\to \mathbb{F}$ in a natural manner. In particular, an input in

$\{0,1{\}}^{\log m}\times \{0,1{\}}^{\log m}$ is interpreted as the binary representation of an index

$(i,j)\in [m]\times [m]$, where

$[m]:=\{1,\dots ,m\}$ and the function outputs

$(i,j)$th entry of the matrix. As such, let

$\tilde{A},\tilde{B}$, and

$\tilde{C}$ denote multilinear extensions of

$A,B,$ and

$C$ interpreted as functions, so they are

$2\log m$-variate sparse multilinear polynomials of size

$n$. Similarly, we interpret

$E$ and

$W$ as functions with respective signatures

$\{0,1{\}}^{\log m}\to \mathbb{F}$ and

$\{0,1{\}}^{\log m-1}\to \mathbb{F}$. Furthermore, let

$\tilde{E}$ and

$\tilde{W}$ denote the multilinear extensions of

$E$ and

$W$ interpreted as functions, so they are multilinear polynomials in

$\log m$ and

$\log m-1$ variables respectively.

$$As noted earlier, the verifier has an oracle access to the following polynomials:

$\tilde{A},\tilde{B},\tilde{C},\tilde{E}$, and

$\tilde{W}$. Additionally, the verifier reads

$u$ and

$\mathsf{x}$ in entirety.

$$Let

$Z=(W,\mathsf{x},u)$. Similar to how we interpret matrices as functions, we interpret

$Z$ and

$(\mathsf{x},u)$ as functions with the following respective signatures:

$\{0,1{\}}^s\to \mathbb{F}$ and

$\{0,1{\}}^{s-1}\to \mathbb{F}$. Observe that the

$\text{MLE}$

$\tilde{Z}$ of

$Z$ satisfies

$$\tilde{Z}(X_1,\dots ,X_s)=(1-X_1)\cdot \tilde{W}(X_2,\dots ,X_s)+X_1\cdot \widetilde{(\mathsf{x},u)}(X_2,\dots ,X_s)(1)$$

$$Similar to [40, Theorem 4.1], checking if

$\phi$ is satisfiable is equivalent, except for a soundness error of

$\log m/|\mathbb{F}|$ over the choice of

$\tau \in {\mathbb{F}}^s$, to checking if the following identity holds:

$$0\stackrel{?}{=}\sum _{x\in \{0,1{\}}^s}\widetilde{\mathsf{eq}}(\tau ,x)\cdot F(x),(2)$$ where

$$F(x)=\left(\begin{array}{c}\sum _{y\in \{0,1{\}}^s}\tilde{A}(x,y)\cdot \tilde{Z}(y)\end{array}\right)\cdot \left(\begin{array}{c}\sum _{y\in \{0,1{\}}^s}\tilde{B}(x,y)\cdot \tilde{Z}(y)\end{array}\right)-\left(\begin{array}{c}u\cdot \sum _{y\in \{0,1{\}}^s}\tilde{C}(x,y)\cdot \tilde{Z}(y)+\tilde{E}(x)\end{array}\right),$$ and

$\widetilde{\mathsf{eq}}$ is the multilinear extension of

$\mathsf{eq}:\{0,1{\}}^s\times \{0,1{\}}^s\to \mathbb{F}$ where

$\mathsf{eq}(x,e)=1$ if

$x=e$ and

$0$ otherwise.

$$That is, if

$\phi$ is satisfiable, then Equation (2) holds with probability

$1$ over the choice of

$\tau$, and if not, then Equation (2) holds with probability at most

$O(\log m/|\mathbb{F}|)$ over the random choice of

$\tau$.

$$To compute the right-hand side in Equation (2), the prover and the verifier apply the sum-check protocol to the following polynomial:

$g(x):=\widetilde{\mathsf{eq}}(\tau ,x)\cdot F(x)$ From the verifier’s perspective, this reduces the task of computing the right-hand side of Equation (2) to the task of evaluating

$g$ at a random input

$r_x\in {\mathbb{F}}^s$. Note that the verifier can locally evaluate

$\widetilde{\mathsf{eq}}(\tau ,r_x)$ in

$O(\log m)$ field operations via

$\widetilde{\mathsf{eq}}(\tau ,r_x)=\prod _{i=1}^s({\tau }_i{r}_{x,i}+(1-{\tau }_i)(1-r_{x,i})).$ With

$\widetilde{\mathsf{eq}}(\tau ,r_x)$ in hand,

$g(r_x)$ can be computed in

$O(1)$ time given the four quantities:

$\sum _{y\in \{0,1{\}}^s}\tilde{A}(r_x,y)\cdot \tilde{Z}(y),\sum _{y\in \{0,1{\}}^s}\tilde{B}(r_x,y)\cdot \tilde{Z}(y),\sum _{y\in \{0,1{\}}^s}\tilde{C}(r_x,y)\cdot \tilde{Z}(y)$, and

$\tilde{E}(r_x)$.

$$The last quantity can be computed with a single query to polynomial

$\tilde{E}$. Furthermore, the first three quantities can be computed by applying the sum-check protocol three more times in parallel, once to each of the following three polynomials (using the same random vector of field elements,

$r_y\in {\mathbb{F}}^s$, in each of the three invocations):

$\tilde{A}(r_x,y)\cdot \tilde{Z}(y),\tilde{B}(r_x,y)\cdot \tilde{Z}(y)$, and

$\tilde{C}(r_x,y)\cdot \tilde{Z}(y)$.

$$To perform the verifier’s final check in each of these three invocations of the sum-check protocol, it suffices for the verifier to evaluate each of the above three polynomials at the random vector

$r_y$, which means it suffices for the verifier to evaluate

$\tilde{A}(r_x,r_y),\tilde{B}(r_x,r_y),\tilde{C}(r_x,r_y)$, and

$\tilde{Z}(r_y)$. The first three evaluations can be obtained via the verifier’s assumed query access to

$(\tilde{A},\tilde{B},\tilde{C})$.

$\tilde{Z}(r_y)$ can be computed (via Equation (1)) from a query to

$\tilde{W}$ and from computing

$\widetilde{(x,u)}$.

$$In summary, we have the following polynomial IOP.

1. $\mathcal{V}\to \mathcal{P}:\tau {\in }_R{\mathbb{F}}^s$
2. $\mathcal{V}\leftrightarrow \mathcal{P}$: run the sum-check protocol to reduce the check in Equation (2) to checking if the following hold, where
   $r_x,r_y$ are vectors in
   ${\mathbb{F}}^s$ chosen at random by the verifier over the course of the sum-check protocol:
   –
   $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A,\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$, and
   $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$;
   –
   $\tilde{E}(r_x)\stackrel{?}{=}{v}_E;$ and
   –
   $\tilde{Z}(r_y)\stackrel{?}{=}{v}_Z$.
3. $\mathcal{V}$:
   – check if
   $\tilde{A}(r_x,r_y)\stackrel{?}{=}{v}_A,\tilde{B}(r_x,r_y)\stackrel{?}{=}{v}_B$, and
   $\tilde{C}(r_x,r_y)\stackrel{?}{=}{v}_C$, with a query to
   $\tilde{A},\tilde{B},\tilde{C}$ at
   $(r_x,r_y)$;
   – check if
   $\tilde{E}(r_x)\stackrel{?}{=}{v}_E$ with an oracle query to
   $\tilde{E}$; and
   – check if
   $\tilde{Z}(r_y)\stackrel{?}{=}{v}_Z$ by checking if:
   $v_Z=(1-r_y[1])\cdot v_W+r_y[1]\cdot \widetilde{(x,u)}(r_y[2..])$, where
   $r_y[2..]$ refers to a slice of
   $r_y$ without the first element of
   $r_y$, and
   $v_W\leftarrow \tilde{W}(r_y[2..])$ via an oracle query (see Equation (1)).)

bellpepper mod

dependencies

bellpepper

see

https://hackmd.io/iR4lHIphQpeyZo1W3-VxQA?view