IPFS星想法|零知识证明 – bellman源码分析

bellman是Zcash团队用Rust语言开发的一个zk-SNARK软件库,实现了Groth16算法。项目地址:

https://github.com/zcash/librustzcash/tree/master/bellman

1. 总体流程

2020070207235842

总体流程大致可以分为以下几个步骤:

1.将问题多项式拍平(flatten),构建对应的电路(Circuit)

(这一步是由上层应用程序配置的)

2.根据电路生成R1CS(Rank 1 Constraint System)

3.将R1CS转化为QAP(Quadratic Arithmetic Program)。传统做法是通过拉格朗日插值,但是为了降低计算复杂度,可以通过快速傅立叶变换来实现。

4.初始化QAP问题的参数,即CRS(Common Reference Strings)

5.根据CRS和输入创建proof

6.验证proof

下面依次介绍各个步骤的细节。

2. Setup阶段:

2020070207243657

2.1 参数数据结构

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

IPFS星想法|零知识证明 - bellman源码分析

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

IPFS星想法|零知识证明 - bellman源码分析

2.2 变量类型

Variable类型代表输入数据中的每一个值,分为公开的statement数据和私有的witness数据:

  • Input类型:即statement数据
  • Aux类型:即witness数据

pub enum Index {
Input(usize),
Aux(usize)
}
pub struct Variable(Index);

2.3 ConstraintSystem

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是statement,a和b是witness,需要验证a * b = c这个Circuit。

如果想验证a + b = c,需要写成下面这样:

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

2.4 构建R1CS

Circuit的synthesize()会调用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

后面6个字段就对应R1CS中的A、B、C矩阵:

2020070207251054

2.5 构建QAP

接下来就是要完成R1CS到QAP的转换。其中有一步会利用逆离散快速傅立叶变换实现拉格朗日插值:

powers_of_tau.ifft(&worker);

let powers_of_tau = powers_of_tau.into_coeffs();

2020070207281452

2020070207295799

2.6 准备验证参数

2020070207303219

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

 

3. 创建Proof阶段

2020070207394152

IPFS星想法|零知识证明 - bellman源码分析

生成proof的时候使用的是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>
}

IPFS星想法|零知识证明 - bellman源码分析

IPFS星想法|零知识证明 - bellman源码分析

首先,获取上一节的计算结果:

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

然后,通过3次iFFT获取多项式系数,计算在coset上的值,再通过3次FFT获取偏移后的点:

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

IPFS星想法|零知识证明 - bellman源码分析

4. 验证阶段

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

2020070207384871

至此,bellman源码的基本流程就分析完毕了,欢迎一起交流讨论~

本文来自投稿,不代表IPFS中文资讯网立场,如若转载,请注明出处:http://www.ipfsnews.cn/3547.html

发表评论

登录后才能评论