Nova开发库

请注意，本文编写于 196 天前，最后修改于 196 天前，其中某些信息可能已经过时。

参照$[1]$的演讲内容，主要学习R1CS.rs这个文件里面的内容

数据结构

首先来看一下R1CS.rs文件的内容，一共六个数据结构

// R1CS类
pub struct R1CS<G: Group>
pub struct R1CSShape<G: Group>

// R1CS实例与对应的Witness
pub struct R1CSWitness<G: Group>
pub struct R1CSInstance<G: Group>

// 松弛的R1CS实例与Witness
pub struct RelaxedR1CSWitness<G: Group>
pub struct RelaxedR1CSInstance<G: Group>

// 下面六个分别对应上面六个数据结构的实现
impl<G: Group> R1CS<G>
impl<G: Group> R1CSShape<G>
impl<G: Group> R1CSWitness<G>
impl<G: Group> R1CSInstance<G>
impl<G: Group> RelaxedR1CSWitness<G> 
impl<G: Group> RelaxedR1CSInstance<G>

这里我们一个个来看

R1CS

这个没什么太多的内容，就是一个PhantomData泛型

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

R1CSShape

pub struct R1CSShape<G: Group> {
  pub(crate) num_cons: usize, // R1CS中的约束数量，对应乘法门的个数
  pub(crate) num_vars: usize, // witness的大小
  pub(crate) num_io: usize,   // 公共输入（public input/output）的大小 

  // 三个矩阵，三个参数分别代表矩阵的行、列，矩阵元素的类型为G::Scalar
  pub(crate) A: Vec<(usize, usize, G::Scalar)>,
  pub(crate) B: Vec<(usize, usize, G::Scalar)>,
  pub(crate) C: Vec<(usize, usize, G::Scalar)>,

  // 这个OnceCell是有且仅有一次写的次数，确保矩阵无法被修改
  #[serde(skip, default = "OnceCell::new")]
  pub(crate) digest: OnceCell<G::Scalar>,
}

这里可以注意一下num_vars和num_io这两个变量，回顾一下R1CS的$\vec Z = (1,\vec x,\vec w)$，所以这里有$|\vec Z| = 1+num\_vars + num\_io$，也即$|\vec Z|$为矩阵的列数

R1CSWitness

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

这里用一个群元素向量表示Witness

R1CSInstance

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

R1CS实例，包含一个witness的承诺comm_W（单个群元素），以及公共输入输出向量X

RelaxedR1CSWitness

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

这个是松弛的R1CS Witness，可以看到和原版的R1CS区别在于多了一个error term，两者都是群元素向量

RelaxedR1CSInstance

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,
}

然后是松弛R1CS的实例，这里和论文中一样，需要对W和E进行承诺

这里的u就是折叠过程中会用到的标量（可以参考之前Nova的相关内容）

实现

这里主要看每个结构中比较关键的函数

R1CSShape

pub fn new 
// 用给定的R1CS对象M创建一个R1CSShape，这个函数还会检查num_io的数量是否为偶数，否则报错

pub(crate) fn check_regular_shape
// 这个函数用于检查R1CSShape是否合法，要求其是Spartan-Class的SNARK
// 该函数会检查num_cons、num_vars、num_op是否都是2的幂，且要求num_io > num_var

pub fn multiply_vec
// 内部实现R1CS系数矩阵与向量Z的乘法运算，也即计算Az、Bz、Cz
// 这个函数用到了rayon这个并行库来加速计算

然后是R1CSShape几个关键函数，先看一下R1CS和relaxed-R1CS的验证，分别对应is_sat和is_sat_relaxed这两个函数

pub fn is_sat_relaxed( // 检查给定的relaxed-R1CS实例是否是可满足的，也就是验证
    &self,
    ck: &CommitmentKey<G>,
    U: &RelaxedR1CSInstance<G>,
    W: &RelaxedR1CSWitness<G>,
  ) -> Result<(), NovaError> { 
    // 这里因为要折叠，所以先检查折叠前后的两个实例的长度是否相等，如果长度不等的话无法折叠
    assert_eq!(W.W.len(), self.num_vars);
    assert_eq!(W.E.len(), self.num_cons);
    assert_eq!(U.X.len(), self.num_io);

    // verify if Az * Bz = u*Cz + E
    // 然后验证relaxed-R1CS的实例是否满足上面这个等式
    let res_eq: bool = {
      let z = [W.W.clone(), vec![U.u], U.X.clone()].concat();
      let (Az, Bz, Cz) = self.multiply_vec(&z)?;
      assert_eq!(Az.len(), self.num_cons);
      assert_eq!(Bz.len(), self.num_cons);
      assert_eq!(Cz.len(), self.num_cons);

      // 这里就是用循环，判断矩阵的每一行（每一个约束）是否是可满足的，如果有一个不满足就返回错误
      let res: usize = (0..self.num_cons)
        .map(|i| usize::from(Az[i] * Bz[i] != U.u * Cz[i] + W.E[i]))
        .sum();

      res == 0 // res等于0表示约束是可满足的，这里就代表返回res_eq = 1
    };

    // verify if comm_E and comm_W are commitments to E and W
    // 这一步是验证Error term和Witness的承诺是否也是正确的，也是用并行库计算
    let res_comm: bool = {
      let (comm_W, comm_E) =
        rayon::join(|| CE::<G>::commit(ck, &W.W), || CE::<G>::commit(ck, &W.E));
      U.comm_W == comm_W && U.comm_E == comm_E
      // 如果承诺验证通过，则返回res_comm = 1
    };

    if res_eq && res_comm {
      Ok(()) // 如果约束也承诺都验证通过，则表示验证通过
    } else {
      Err(NovaError::UnSat)
    }
  }

// 这个是验证原版的R1CS是否可满足（上面是relaxed-R1CS的验证）
pub fn is_sat(
    &self,
    ck: &CommitmentKey<G>,
    U: &R1CSInstance<G>,
    W: &R1CSWitness<G>,
  ) -> Result<(), NovaError> {
    assert_eq!(W.W.len(), self.num_vars);
    assert_eq!(U.X.len(), self.num_io);

    // verify if Az * Bz = u*Cz
    let res_eq: bool = {
      let z = [W.W.clone(), vec![G::Scalar::ONE], U.X.clone()].concat();
      let (Az, Bz, Cz) = self.multiply_vec(&z)?;
      assert_eq!(Az.len(), self.num_cons);
      assert_eq!(Bz.len(), self.num_cons);
      assert_eq!(Cz.len(), self.num_cons);

      let res: usize = (0..self.num_cons)
        .map(|i| usize::from(Az[i] * Bz[i] != Cz[i]))
        .sum();

      res == 0
    };

    // verify if comm_W is a commitment to W
    // 这里可以看到，和relaxed-R1CS的区别在于，原版的R1CS只验证了Witness的承诺，不需要验证Error term的承诺（因为没有）
    let res_comm: bool = U.comm_W == CE::<G>::commit(ck, &W.W);

    if res_eq && res_comm {
      Ok(())
    } else {
      Err(NovaError::UnSat)
    }
  }

relaxed-R1CS中还需要对T这个项进行承诺，所以commit_T这个函数负责计算T的承诺值

pub fn commit_T(
    &self,
    ck: &CommitmentKey<G>,
    U1: &RelaxedR1CSInstance<G>,
    W1: &RelaxedR1CSWitness<G>,
    U2: &R1CSInstance<G>,
    W2: &R1CSWitness<G>,
  ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
  
    // 这里是预计算Z1和Z2与ABC三个矩阵的乘法
    let (AZ_1, BZ_1, CZ_1) = {
      let Z1 = [W1.W.clone(), vec![U1.u], U1.X.clone()].concat();
      self.multiply_vec(&Z1)?
    };

    let (AZ_2, BZ_2, CZ_2) = {
      let Z2 = [W2.W.clone(), vec![G::Scalar::ONE], U2.X.clone()].concat();
      self.multiply_vec(&Z2)?
    };

    // 然后计算交叉项的哈达玛乘积，paper里面的那个圈乘
    let AZ_1_circ_BZ_2 = (0..AZ_1.len())
      .into_par_iter()
      .map(|i| AZ_1[i] * BZ_2[i])
      .collect::<Vec<G::Scalar>>();
    let AZ_2_circ_BZ_1 = (0..AZ_2.len())
      .into_par_iter()
      .map(|i| AZ_2[i] * BZ_1[i])
      .collect::<Vec<G::Scalar>>();

    // 然后是用u计算T中与CZ相关的交叉项（u_1 * CZ_2和u_2 * CZ_1）
    let u_1_cdot_CZ_2 = (0..CZ_2.len())
      .into_par_iter()
      .map(|i| U1.u * CZ_2[i])
      .collect::<Vec<G::Scalar>>();
    let u_2_cdot_CZ_1 = (0..CZ_1.len())
      .into_par_iter()
      .map(|i| CZ_1[i]) // 这里u2 = 1?
      .collect::<Vec<G::Scalar>>();

    // 计算T中与AB矩阵相关的交叉项（AZ_1 * BZ_2和AZ_2 * BZ_1）
    // 同时把前面的u_1 * CZ_2和u_2 * CZ_1整合成一个向量
    let T = AZ_1_circ_BZ_2
      .par_iter()
      .zip(&AZ_2_circ_BZ_1)
      .zip(&u_1_cdot_CZ_2)
      .zip(&u_2_cdot_CZ_1)
      .map(|(((a, b), c), d)| *a + *b - *c - *d)
      .collect::<Vec<G::Scalar>>();

    // 用承诺密钥ck对T进行承诺，计算[T]
    let comm_T = CE::<G>::commit(ck, &T);

    Ok((T, comm_T)) // 返回T和[T]
  }

前面提到了，如果R1CS的长度不为2的幂次，则需要进行填充，这里用到pad这个函数

pub fn pad(&self) -> Self {
    // equalize the number of variables and constraints
    let m = max(self.num_vars, self.num_cons).next_power_of_two();

    // check if the provided R1CSShape is already as required
    if self.num_vars == m && self.num_cons == m {
      return self.clone();
    }

    // check if the number of variables are as expected, then
    // we simply set the number of constraints to the next power of two
    // 这里将长度扩展到下一个2的幂
    // 如果变量数与扩展后的长度一致，说明原来的矩阵大小不用修改，则直接用扩展长度代替原本的约束数量num_cons和变量数量num_vars
    // R1CS中的其他参数（公共输入数量num_io，电路矩阵ABC）不变，直接返回对应的拷贝
    if self.num_vars == m {
      return R1CSShape {
        num_cons: m,
        num_vars: m,
        num_io: self.num_io,
        A: self.A.clone(),
        B: self.B.clone(),
        C: self.C.clone(),
        digest: OnceCell::new(),
      };
    }

    // otherwise, we need to pad the number of variables and renumber variable accesses
    // 如果不一致的话，这里需要修改原始的三个矩阵，扩展三个矩阵的列数
    let num_vars_padded = m;
    let num_cons_padded = m;
    let apply_pad = |M: &[(usize, usize, G::Scalar)]| -> Vec<(usize, usize, G::Scalar)> {
      M.par_iter()
        .map(|(r, c, v)| {
          (
            *r,
            if c >= &self.num_vars {
              c + num_vars_padded - self.num_vars
            } else {
              *c
            },
            *v,
          )
        })
        .collect::<Vec<_>>()
    };

    let A_padded = apply_pad(&self.A);
    let B_padded = apply_pad(&self.B);
    let C_padded = apply_pad(&self.C);

    R1CSShape {
      num_cons: num_cons_padded,
      num_vars: num_vars_padded,
      num_io: self.num_io,
      A: A_padded,
      B: B_padded,
      C: C_padded,
      digest: OnceCell::new(),
    }
  }
}

R1CSInstance

一个new函数，没有太多内容，通过R1CSShape来创建R1CSInstance

过程中主要检查R1CSShape的num_io（公共输入输出数量）是否与X一致

RelaxedR1CSWitness

pub fn default
// 返回一个默认的Relaxed R1CSShape实例，默认Witness和Error都是零向量

pub fn from_r1cs_witness
// 通过R1CS实例创建
// 由于R1CS中没有error term，所以这个函数创建的RelaxedR1CSWitness中的E为零向量

pub fn commit 
// 用承诺密钥ck对W和E进行承诺，也即计算[W]和[E]

pub fn pad
// 对Witness作填充，确保长度一致，不一致的话无法折叠
// 填充的方式很简单，就是加0，使得Witness的长度与实例中指定的num_vars一致就行

然后是一个重点函数fold，用于折叠R1CS的Witness，这里需要注意，这个是RelaxedR1CSWitness的fold，后面的RelaxedR1CSInstance有自己的fold函数

pub fn fold(
    &self,
    W2: &R1CSWitness<G>,
    T: &[G::Scalar],
    r: &G::Scalar,
  ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
    let (W1, E1) = (&self.W, &self.E);
    let W2 = &W2.W;

    // 这里判断两个待折叠的Witness的长度是否一致，不一致的话无法折叠
    if W1.len() != W2.len() {
      return Err(NovaError::InvalidWitnessLength);
    }

    // 然后按照paper中的方式做折叠
    // W^* = W1 + r * W2
    // E^* = E1 + r * E2
    let W = W1
      .par_iter()
      .zip(W2)
      .map(|(a, b)| *a + *r * *b)
      .collect::<Vec<G::Scalar>>();
    let E = E1
      .par_iter()
      .zip(T)
      .map(|(a, b)| *a + *r * *b)
      .collect::<Vec<G::Scalar>>();
    Ok(RelaxedR1CSWitness { W, E })
    // 返回折叠后的Witness
  }

RelaxedR1CSInstance

pub fn default
// 通过承诺密钥ck和R1CSShape默认创建RelaxedR1CSInstance
// 其中u为0标量，X为长度为num_io的零向量

pub fn from_r1cs_instance
// R1CS实例转换至relaxed-R1CS实例
// 这里和paper原文写的一样
// 原始的R1CS相当于u = 1, E = vec![0]的relaxed-R1CS

pub fn from_r1cs_instance_unchecked
// 也是通过R1CSInstance来构建RelaxedR1CSInstance

然后是RelaxedR1CSInstance的fold函数

pub fn fold(
    &self,
    U2: &R1CSInstance<G>, // 要折叠的实例
    comm_T: &Commitment<G>, // 对应的承诺
    r: &G::Scalar, // 折叠用到的随机挑战值
  ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
    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) // 折叠X1和X2，X^* = X1 + r * X2
      .collect::<Vec<G::Scalar>>();
    let comm_W = *comm_W_1 + *comm_W_2 * *r; // 折叠W1和W2，W^* = W1 + r * W2
    let comm_E = *comm_E_1 + *comm_T * *r; // 折叠E，E^* = E1 + r * T
    let u = *u1 + *r; 

    Ok(RelaxedR1CSInstance {
      comm_W,
      comm_E,
      X,
      u,
    })
  }

others

还有三个其他的函数

TranscriptReprTrait // 这个函数用于将折叠后的Instance和Witness转换为交互脚本
AbsorbInROTrait // 转换为Random Oracle对象，这个函数有两个，一个是用于RelaxedR1CSInstance的，一个是用于R1CSInstance的
SimpleDigestible

References

$[1]$ Nova relaxed R1CS and it’s implementation - YouTube

$[2]$ microsoft/Nova: Nova: Recursive SNARKs without trusted setup (github.com)

Nova Folding Scheme

数据结构

R1CS

R1CSShape

R1CSWitness

R1CSInstance

RelaxedR1CSWitness

RelaxedR1CSInstance

实现

R1CSShape

R1CSInstance

RelaxedR1CSWitness

RelaxedR1CSInstance

others

References

添加新评论

评论列表

Nova开发库

数据结构

R1CS

R1CSShape

R1CSWitness

R1CSInstance

RelaxedR1CSWitness

RelaxedR1CSInstance

实现

R1CSShape

R1CSInstance

RelaxedR1CSWitness

RelaxedR1CSInstance

others

References

Testudo

Pasta Curve

添加新评论

评论列表