链眼社区:专注于区块链安全,区块链数据分析, 区块链信息整合,区块链技术服务和区块链技术咨询。

ZKP-深入理解 Bellman 代码库
coinwang
2022-06-09 22:22:18

Bellman 是 Zcash 团队用 Rust 语言开发的 zk-SNARK 软件库,实现了 Groth16 算法。 https://github.com/zcash/librustzcash/tree/master/bellman

Groth16 证明方案的整体逻辑如图所示。并详细解释了bellman库中的数据结构以及证明创建和验证逻辑。

一. 总体流程

整个过程大致可以分为以下几个步骤: 1. 将问题多项式展平,构造相应的电路。此步骤由上层应用程序执行。 2. 根据电路生成 R1CS(Rank 1 Constraint System) 3. 将 R1CS 转换为 QAP(Quadratic Arithmetic Program)。传统的方法是使用拉格朗日插值,但为了降低计算复杂度,可以通过快速傅里叶变换来实现。 4.设置QAP问题的参数,即CRS(Common Reference Strings)。 5. 根据 CRS 和输入创建证明。 6. 验证证明。

下面依次描述每个步骤的细节。

二. 设置阶段

Setup阶段的主要工作是生成CRS数据。相关公式为:

笔记:

  1. 公式中的x对应代码中的变量tau,对应的x^i对应powers_of_tau。

由代码中的“powers_of_tau.z (& tau)”计算得出。

pub struct VerifyingKey<E: Engine> {
    pub alpha_g1: E::G1Affine,
    pub beta_g1: E::G1Affine,
    pub beta_g2: E::G2Affine,
    pub gamma_g2: E::G2Affine,
    pub delta_g1: E::G1Affine,
    pub delta_g2: E::G2Affine,
    pub ic: Vec<E::G1Affine>
}

where

pub struct Parameters<E: Engine> {
    pub vk: VerifyingKey<E>,
    pub h: Arc<Vec<E::G1Affine>>,
    pub l: Arc<Vec<E::G1Affine>>,
    pub a: Arc<Vec<E::G1Affine>>,
    pub b_g1: Arc<Vec<E::G1Affine>>,
    pub b_g2: Arc<Vec<E::G2Affine>>
}

where

最后三个参数 a、b_g1、b_g2 没有出现在公式中。实际上,它们是从 x^i 计算的 QAP 多项式的值。

2. 变量

Variable 类型表示输入数据中的每个值,分为公开声明数据和私有见证数据:

  • 输入类型:报表数据
  • 辅助类型:见证数据
pub enum Index { 
    Input(usize), 
    Aux(usize) 
} 
pub struct Variable(Index);

3. 约束系统

ConstraintSystem 是一个接口,它定义了以下用于生成不同类型变量的函数:

  • one ():产生一个 Input 类型的变量,索引为 0
  • alloc():产生Aux类型变量,索引递增
  • alloc_input():产生一个Input类型的变量,索引递增

例如

let a = cs.alloc(...)
let b = cs.alloc(...)
let c = cs.alloc_input(...)
cs.enforce(
    || "a*b=c",
    |lc| lc + a,
    |lc| lc + b,
    |lc| lc + c
);

在上面的例子中,c 是一个陈述,a 和 b 是见证人。示例电路用于验证 a * b = c。 如果要验证a + b = c,则需要编写如下电路:

cs.enforce(
    || "a*b=c",
    |lc| lc + a + b,
    |lc| lc + CS::one(),
    |lc| lc + c
);

4 构建 R1CS

Circuit的syntheticsize()会调用ConstraintSystem的enforce()来构建R1CS。 KeypairAssembly 是 ConstraintSystem 的一个实现。R1CS 的参数存储在其成员变量中:

struct KeypairAssembly<E: Engine> {
    num_inputs: usize,
    num_aux: usize,
    num_constraints: usize,
    at_inputs: Vec<Vec<(E::Fr, usize)>>,
    bt_inputs: Vec<Vec<(E::Fr, usize)>>,
    ct_inputs: Vec<Vec<(E::Fr, usize)>>,
    at_aux: Vec<Vec<(E::Fr, usize)>>,
    bt_aux: Vec<Vec<(E::Fr, usize)>>,
    ct_aux: Vec<Vec<(E::Fr, usize)>>
}

以上面的 a * b = c 为例: num_inputs = 1 num_aux = 2 num_constraints = 1 接下来的六个字段分别对应 R1CS 中的 A、B 和 C 矩阵:

5 构建 QAP

下一步是完成从 R1CS 到 QAP 的转换。一个步骤是使用逆离散快速傅里叶变换实现拉格朗日插值:

powers_of_tau.ifft(&worker);
let powers_of_tau = powers_of_tau.into_coeffs();

这是单位根的概念: 如果 ωⁿ = 1 ,则 omega 称为单位根。以复平面为例,ωⁱ实际上将单位圆分成n份。

现在我们处于有限循环群的条件下,根据费马小定理:如果 p 是素数且 ω 和 p 互素,则 ω ᵖ⁻¹ mod p= 1 。因此,与 p 互质的素数可以用作单位根。 同时,我们发现任何元素都可以用ω ⁻¹, ω⁻² , …, ω ᵖ⁻¹ 的线性组合来表示,即它们都可以作为环状基团之一。集团基地。我们利用这组基进行离散傅里叶逆变换,得到拉格朗日插值系数,并将R1CS转换为QAP。

6. 准备验证参数

最后需要下式中带括号的参数来验证证明:

为了快速验证,这些参数的值是预先计算好的。

pub fn prepare_verifying_key<E: Engine>( 
    vk: &VerifyingKey<E> 
) -> PreparedVerifyingKey<E> 
{ 
    let mut gamma = vk.gamma_g2; 
    gamma.negate(); 
    让 mut delta = vk.delta_g2; 
    delta.negate();
PreparedVerifyingKey { 
        alpha_g1_beta_g2: E::pairing(vk.alpha_g1, vk.beta_g2), 
        neg_gamma_g2: gamma.prepare(), 
        neg_delta_g2: delta.prepare(), 
        ic: vk.ic.clone() 
    } 
}

一个小细节:如何计算有限域中的除法? 显然,a⋅b = a⋅b⁻¹,如何计算乘法逆b⁻¹? 根据费马小定理:如果 p 是素数,并且 a 和 p 是素数,则 aᵖ⁻¹(mod p) = 1。 因此,在有限域中,b⁻¹ = bᵖ⁻²。

fn inverse(&self) -> Option<Self> { 
    if <Fr as Field>::is_zero(self) { 
        None 
    } else { 
        Some(self.pow(&[(MODULUS_R.0 as u64) - 2])) 
    } 
}

三. 创建证明阶段

Groth16 算法生成 Proof 的公式如下:

随机选择 r 和 s 并计算 [A]₁、[B]₂、[C]₁ 的三个值。

pub struct Proof<E: Engine> {
    pub a: E::G1Affine,
    pub b: E::G2Affine,
    pub c: E::G1Affine
}

公式中的其他参数是已知的。主要难点是计算h(x),下面会详细介绍。

1​计算s ⋅ A(x), s ⋅ B(x), s ⋅ C(x)

回顾QAP,我们需要通过拉格朗日插值将R1CS转化为一系列多项式:

并且需要验证:

因此,应计算 s⋅A(x)、s⋅B(x) 和 s⋅C(x)。一种方法是直接进行多项式运算,另一种是在ω⁰、ω¹、ω²…、ωⁿ⁻¹处计算它们的值,然后通过iFFT(快速傅里叶逆变换)获得多项式系数。

值得注意的是,当x取ω⁰,ω¹,ω²…,ωⁿ⁻¹时,A(x),B(x)和C(x)实际上是R1CS的结果。因此,s⋅A(x)实际上是左输入,s⋅B(x)是右输入,s⋅C(x)是电路的输出。我们可以重用Circuit的syntheticsize()函数进行计算。

在生成证明时,ConstraintSystem 的另一个实现 ProvingAssignment 用于调用 Circuit 的 synthesize() 函数。

struct ProvingAssignment<E: Engine> {
    ...
    a: Vec<Scalar<E>>,
    b: Vec<Scalar<E>>,
    c: Vec<Scalar<E>>,
input_assignment: Vec<E::Fr>,
    aux_assignment: Vec<E::Fr>
}

基本上类似于设置阶段:

-alloc():将见证数据发送到 aux_assignment -alloc_input():将语句数据发送到 input_assignment -enforce()/eval():计算 s⋅A(x)、s⋅B(x) 和 s⋅C(x) ,分别放入3个成员变量a、b、c中

然后通过iFFT可以得到对应的多项式系数。

2 计算H(x)

使用 sA(x)、sB(x) 和 sC(x),H(x) 可以计算为:

  • 定义 ω = σ⁽ʳ⁻¹⁾/ⁿ,则 σⁿ= 1(费马小定理)
  • 首先通过iFFT计算a、b、c的多项式系数3次
  • 计算 σω⁰、σω¹、σω²…、σωⁿ⁻¹ 上的多项式值。
  • 经过3次FFT,得到a',b',c'
  • 由于 t (σωⁿⁱ) = (σωⁱ)ⁿ-1= σⁿ-1,计算偏移集上的点 h (x)

  • 执行一次 iFFT 以计算具有 σ 偏移的多项式系数
  • 根据标度定理:

将上一步得到的结果除以σ,得到h(x)多项式系数。

根据以上分析,一共需要进行3次FFT和4次iFFT。我们来详细查看对应的源码:

首先,得到上一节的计算结果:

let mut a = EvaluationDomain::from_coeffs(prover.a)?;
let mut b = EvaluationDomain::from_coeffs(prover.b)?;
let mut c = EvaluationDomain::from_coeffs(prover.c)?;

然后,通过iFFT得到多项式系数,通过FFT计算陪集上的值:

a.ifft(&worker);
a.coset_fft(&worker);
b.ifft(&worker);
b.coset_fft(&worker);
c.ifft(&worker);
c.coset_fft(&worker);

接下来计算:

a.mul_assign(&worker, &b);
drop(b);
a.sub_assign(&worker, &c);
drop(c);
a.divide_by_z_on_coset(&worker);

最后,通过 iFFT 得到多项式系数并除以 σ:

a.icoset_fft(&worker);

此外,下一步是计算

作为 [C]₁ 的一部分:

multiexp(&worker, params.get_h(a.len())?, FullDensity, a)

四. 验证阶段

Groth16算法的证明验证公式如下:

检查以下代码求和(在 CRS 中使用 ic)以生成中间变量 acc:

let mut acc = pvk.ic[0].into_projective();
for (i, b) in public_inputs.iter().zip(pvk.ic.iter().skip(1)) {
        acc.add_assign(&b.mul(i.into_repr()));
    }

然后稍微变形公式,将问题转化为验证以下方程:

对应的代码如下:

Ok(E::final_exponentiation(
        &E::miller_loop([
            (&proof.a.prepare(), &proof.b.prepare()),
            (&acc.into_affine().prepare(), &pvk.neg_gamma_g2),
            (&proof.c.prepare(), &pvk.neg_delta_g2)
        ].into_iter())
    ).unwrap() == pvk.alpha_g1_beta_g2)