李星

高级会员

  • 主题

    16

  • 帖子

    16

  • 关注者

    0

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

1. 总体流程



总体流程大致可以分为以下几个步骤:
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阶段:


2.1 参数数据结构

pubstructVerifyingKey{
pubalpha_g1:E::G1Affine,
pubbeta_g1:E::G1Affine,
pubbeta_g2:E::G2Affine,
pubgamma_g2:E::G2Affine,
pubdelta_g1:E::G1Affine,
pubdelta_g2:E::G2Affine,
pubic:Vec
}


pubstructParameters{
pubvk:VerifyingKey,
pubh:Arc>,
publ:Arc>,
puba:Arc>,
pubb_g1:Arc>,
pubb_g2:Arc>
}




2.2 变量类型

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

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

pubenumIndex{
Input(usize),
Aux(usize)
}
pubstructVariable(Index);
2.3 ConstraintSystemConstraintSystem是一个接口,定义了下面几个函数用于产生不同类型的变量:

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

alloc_input(): 产生Input类型的变量,索引递增

示例:

leta=cs.alloc(...)
letb=cs.alloc(...)
letc=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的参数会保存在其成员变量中:

structKeypairAssembly{
num_inputs:usize,
num_aux:usize,
num_constraints:usize,
at_inputs:Vec>,
bt_inputs:Vec>,
ct_inputs:Vec>,
at_aux:Vec>,
bt_aux:Vec>,
ct_aux:Vec>
}

以上面的a * b = c为例:
num_inputs = 1
num_aux = 2
num_constraints = 1
后面6个字段就对应R1CS中的A、B、C矩阵:



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

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







2.6 准备验证参数



fninverse(&self)->Option{
if::is_zero(self){
None
}else{
Some(self.pow(&[(MODULUS_R.0asu64)-2]))
}
}

3. 创建Proof阶段




生成proof的时候使用的是ConstraintSystem的另外一个实现ProvingAssignment来调用Circuit的synthesize()函数。

structProvingAssignment{
...
a:Vec>,
b:Vec>,
c:Vec>,
input_assignment:Vec,
aux_assignment:Vec
}





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

letmuta=EvaluationDomain::from_coeffs(prover.a)?;
letmutb=EvaluationDomain::from_coeffs(prover.b)?;
letmutc=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);





4. 验证阶段
Groth16算法的proof验证公式如下:



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

43do5gvplal.png

43do5gvplal.png
本文由:李星 发布于:2019-07-22 12:04:42 0 位用户参与了讨论
分享淘帖
回复

使用道具

成为第一个回贴人

B Color Link Quote Code Smilies
Copyright © 2001-2019 · 挖矿网 ·   京ICP备12010892号-1 -