零知识证明 - Groth16计算详解
source link: https://learnblockchain.cn/2019/12/19/zkp-Groth16/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Groth16算法是zkSNARK的典型算法，目前在ZCash，Filecoin，Coda等项目中使用。本文从计算量的角度详细分析Groth16计算。Groth16计算分成三个部分：Setup针对电路生成Pk/Vk（证明/验证密钥），Prove在给定witness/statement的情况下生成证明，Verify通过Vk验证证明是否正确。
本文中所有的术语和数学符号和Groth16论文保持一致（ On the Size of Pairing-based Non-interactive Arguments ，具体的计算在17/18页）：
对Groth16算法的理解可查看：
对libSnark代码库的理解可查看：
1. 电路描述
所有的电路描述有个专业的术语：Relation（变量和变量的关系描述）。描述Relation的语言很多：R1CS，QAP，tinyRAM，bacs等等。目前开发，电路一般采用R1CS语言描述。R1CS相对来说，非常直观。A*B=C（A/B/C分别是输入变量的线性组合）。但是，要应用Groth16算法，需要将R1CS描述的电路，转化为QAP描述。两种电路描述语言的转化，称为Reduction。
1.1 R1CS描述
给定M’个变量（第一个变量约定为恒量1），以及N’个约束，所有的R1CS描述可以表示如下：
每一行是一个约束。举例，第一行的约束表示的是：
1.2 QAP转化
介绍具体的转化之前，先介绍一个简单的术语，拉格朗日插值以及拉格朗日basis。
给定一系列的x和y的对应关系，通过拉格朗日插值的方式，可以确定多项式：
其中$ l_0(x),l_1(x),…l_n(x) $就称为拉格朗日basis，计算公式如下：
简单的说，在给定一系列的x/y的对应关系后，可以通过拉格朗日插值表示成多项式。在R1CS的表达方式下，U/V/W多项式很自然用拉格朗日basis表示，并不是以多项式的系数表示。
在R1CS转化为QAP之前，必须 对现有约束进行增强 ，增加$ a_i*0=0 $的约束。增加这些约束的原因是为了保证转化后的QAP的各个多项式不线性依赖。
1.3 domain选择
针对每个变量，已经知道N个y值。如何选择这些y值，对应的x值？这个就是domain的选择。选择domain，主要考虑两个计算性能：
- 拉格朗日插值
- FFT和iFFT。
libfqfft的源码提供了几种domain：
- Basic Radix-2
- Extended Radix-2
- Step Radix-2
- Arithmetic Sequence
- Geometric Sequence
选择哪一种domain和输入个数（M）有关。为了配合特定domain的计算，domain的阶（M）会稍稍变大。
确定了domain，也就确定了domain上的一组元素s：
2. Setup计算
随机生成 $ \alpha,\beta,\gamma,\delta,x \in F_r $ 。注意这里的和上一节中的x含义不同，不要混淆。
2.1 拉格朗日插值
已知的情况下，通过1.2的公式，先通过domain计算拉格朗日basis。再乘上系数，可以获得$ u_i(x),v_i(x),w_i(x) $。这些多项式的阶是M。
2.2 计算$ x^i $ 和$ t(x) $
$ x^i $ 的计算相对简单，注意幂次计算都是在$ F_r $的计算。在domain确定后，多项式t也确定，从而可以计算出$ t(x) $。
2.3 生成Pk/Vk
按照如下的公式，计算Pk/Vk。$ .\sigma_1 $是G1上的点，$ \sigma_2 $是G2上的点。
其中，
是Vk。其他部分是Pk。可以看出，Vk的大小取决于公共输入的变量个数，相对来说数量比较小。Pk的数据量大小和所有的变量个数相关。计算过程，主要由scalarMul组成。
3. Prove计算
在domain选择后，U*V=W，可以变换为如下的多项式方程：
3.1 $ u_i(x),v_i(x),w_i(x) $多项式系数
通过iFFT，在已知domain上元素s和值对应关系，可以计算出多项式系数。
3.2 $ u_i(x),v_i(x),w_i(x) $在coset的值
已知多项式系数，通过FFT，计算出多项式在coset的值。注意，元素s以及对应的coset是特殊设计的，便于FFT/iFFT的计算，和domain的选择有关系。
3.3 h(X)在coset的值
h(X)多项式的计算公式如下：
代入3.1/3.2，直接计算出h(X)在coset的值。
3.4 计算h(X)多项式系数
通过iFFT，获取h(X)的多项式系数，阶为N-2。
3.5 生成证明
随机选择$ r,s \in F_r $，在已知$ u_i(x),v_i(x),w_i(x),h(x) $的情况下，通过如下的公式计算证明A，B，C：
其中，A需要计算在G1上的点，B需要计算在G1/G2上的点，C需要计算G1上的点。C中$ \frac{h(x)t(x)}{\delta} $计算如下：
很显然，生成证明的计算量主要由四个Multiexp组成（A-1，B-1，C-2），和变量个数以及约束的个数有关。在一个大型电路中，生成证明的时间比较长（秒级，甚至分钟级）。
4. Verify计算
在已知证明以及Vk的情况下，通过配对（pairing）函数，很容易计算如下的等式是否成立。计算在毫秒级。
总结：
Groth16算法的主要计算量由两部分组成：FFT/iFFT以及MultiExp。在生成证明时，需要4次iFFT以及三次FFT计算。Setup计算和生成证明时，需要大量的MultiExp。Verify计算量相对较小。
本文作者为深入浅出区块链共建者：Star Li，他的公众号 星想法 有很多原创高质量文章，欢迎大家扫码关注。
深入浅出区块链 - 打造高质量区块链技术博客，学区块链都来这里，关注 知乎 、微博 掌握区块链技术动态。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK