Understanding Nova

Kothapalli, Abhiram, Srinath Setty, and Ioanna Tzialla. “Nova: Recursive zero-knowledge arguments from folding schemes.” Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022.

Nova: Paper Code

2. Understanding Relaxed R1CS

• R1CS
  

/// A type that holds a witness for a given R1CS instance
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct R1CSWitness<E: Engine> {W: Vec<E::Scalar>,
}/// A type that holds an R1CS instance
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "")]
pub struct R1CSInstance<E: Engine> {pub(crate) comm_W: Commitment<E>,pub(crate) X: Vec<E::Scalar>,
}impl<E: Engine> R1CSWitness<E> {/// A method to create a witness object using a vector of scalarspub fn new(S: &R1CSShape<E>, W: &[E::Scalar]) -> Result<R1CSWitness<E>, NovaError> {if S.num_vars != W.len() {Err(NovaError::InvalidWitnessLength)} else {Ok(R1CSWitness { W: W.to_owned() })}}/// Commits to the witness using the supplied generatorspub fn commit(&self, ck: &CommitmentKey<E>) -> Commitment<E> {CE::<E>::commit(ck, &self.W)}
}impl<E: Engine> R1CSInstance<E> {/// A method to create an instance object using consitituent elementspub fn new(S: &R1CSShape<E>,comm_W: &Commitment<E>,X: &[E::Scalar],) -> Result<R1CSInstance<E>, NovaError> {if S.num_io != X.len() {Err(NovaError::InvalidInputLength)} else {Ok(R1CSInstance {comm_W: *comm_W,X: X.to_owned(),})}}
}

• Relaxed R1CS
  

/// A type that holds a witness for a given Relaxed R1CS instance
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct RelaxedR1CSWitness<E: Engine> {pub(crate) W: Vec<E::Scalar>,pub(crate) E: Vec<E::Scalar>,
}/// A type that holds a Relaxed R1CS instance
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "")]
pub struct RelaxedR1CSInstance<E: Engine> {pub(crate) comm_W: Commitment<E>,pub(crate) comm_E: Commitment<E>,pub(crate) X: Vec<E::Scalar>,pub(crate) u: E::Scalar,
}impl<E: Engine> RelaxedR1CSWitness<E> {/// Produces a default `RelaxedR1CSWitness` given an `R1CSShape`pub fn default(S: &R1CSShape<E>) -> RelaxedR1CSWitness<E> {RelaxedR1CSWitness {W: vec![E::Scalar::ZERO; S.num_vars],E: vec![E::Scalar::ZERO; S.num_cons],}}/// Initializes a new `RelaxedR1CSWitness` from an `R1CSWitness`pub fn from_r1cs_witness(S: &R1CSShape<E>, witness: &R1CSWitness<E>) -> RelaxedR1CSWitness<E> {RelaxedR1CSWitness {W: witness.W.clone(),E: vec![E::Scalar::ZERO; S.num_cons],}}/// Commits to the witness using the supplied generatorspub fn commit(&self, ck: &CommitmentKey<E>) -> (Commitment<E>, Commitment<E>) {(CE::<E>::commit(ck, &self.W), CE::<E>::commit(ck, &self.E))}/// Folds an incoming `R1CSWitness` into the current onepub fn fold(&self,W2: &R1CSWitness<E>,T: &[E::Scalar],r: &E::Scalar,) -> Result<RelaxedR1CSWitness<E>, NovaError> {let (W1, E1) = (&self.W, &self.E);let W2 = &W2.W;if W1.len() != W2.len() {return Err(NovaError::InvalidWitnessLength);}let W = W1.par_iter().zip(W2).map(|(a, b)| *a + *r * *b).collect::<Vec<E::Scalar>>();let E = E1.par_iter().zip(T).map(|(a, b)| *a + *r * *b).collect::<Vec<E::Scalar>>();Ok(RelaxedR1CSWitness { W, E })}/// Pads the provided witness to the correct lengthpub fn pad(&self, S: &R1CSShape<E>) -> RelaxedR1CSWitness<E> {let mut W = self.W.clone();W.extend(vec![E::Scalar::ZERO; S.num_vars - W.len()]);let mut E = self.E.clone();E.extend(vec![E::Scalar::ZERO; S.num_cons - E.len()]);Self { W, E }}
}impl<E: Engine> RelaxedR1CSInstance<E> {/// Produces a default `RelaxedR1CSInstance` given `R1CSGens` and `R1CSShape`pub fn default(_ck: &CommitmentKey<E>, S: &R1CSShape<E>) -> RelaxedR1CSInstance<E> {let (comm_W, comm_E) = (Commitment::<E>::default(), Commitment::<E>::default());RelaxedR1CSInstance {comm_W,comm_E,u: E::Scalar::ZERO,X: vec![E::Scalar::ZERO; S.num_io],}}/// Initializes a new `RelaxedR1CSInstance` from an `R1CSInstance`pub fn from_r1cs_instance(ck: &CommitmentKey<E>,S: &R1CSShape<E>,instance: &R1CSInstance<E>,) -> RelaxedR1CSInstance<E> {let mut r_instance = RelaxedR1CSInstance::default(ck, S);r_instance.comm_W = instance.comm_W;r_instance.u = E::Scalar::ONE;r_instance.X = instance.X.clone();r_instance}/// Initializes a new `RelaxedR1CSInstance` from an `R1CSInstance`pub fn from_r1cs_instance_unchecked(comm_W: &Commitment<E>,X: &[E::Scalar],) -> RelaxedR1CSInstance<E> {RelaxedR1CSInstance {comm_W: *comm_W,comm_E: Commitment::<E>::default(),u: E::Scalar::ONE,X: X.to_vec(),}}/// Folds an incoming `RelaxedR1CSInstance` into the current onepub fn fold(&self,U2: &R1CSInstance<E>,comm_T: &Commitment<E>,r: &E::Scalar,) -> RelaxedR1CSInstance<E> {let (X1, u1, comm_W_1, comm_E_1) =(&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());let (X2, comm_W_2) = (&U2.X, &U2.comm_W);// weighted sum of X, comm_W, comm_E, and ulet X = X1.par_iter().zip(X2).map(|(a, b)| *a + *r * *b).collect::<Vec<E::Scalar>>();let comm_W = *comm_W_1 + *comm_W_2 * *r;let comm_E = *comm_E_1 + *comm_T * *r;let u = *u1 + *r;RelaxedR1CSInstance {comm_W,comm_E,X,u,}}
}