ZKP Understanding Nova 2 Relaxed R1CS

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 scalars
  pub 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 generators
  pub 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 elements
  pub 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 generators
    pub 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 one
    pub 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 length
    pub 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 one
    pub 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 u
      let 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,
      }
    }
  }