零知识证明 - Groth16计算详解 | 深入浅出区块链 | 技术博客

Groth16算法是zkSNARK的典型算法，目前在ZCash，Filecoin，Coda等项目中使用。本文从计算量的角度详细分析Groth16计算。Groth16计算分成三个部分：Setup针对电路生成Pk/Vk（证明/验证密钥），Prove在给定witness/statement的情况下生成证明，Verify通过Vk验证证明是否正确。

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 算法的理解可查看：

零知识证明 - Groth16 算法介绍

对 libSnark 代码库的理解可查看：

零知识证明 - 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 的对应关系，通过拉格朗日插值的方式，可以确定多项式：

其中l0​(x),l1​(x),...ln​(x)就称为拉格朗日 basis，计算公式如下：

简单的说，在给定一系列的 x/y 的对应关系后，可以通过拉格朗日插值表示成多项式。在 R1CS 的表达方式下，U/V/W 多项式很自然用拉格朗日 basis 表示，并不是以多项式的系数表示。
在 R1CS 转化为 QAP 之前，必须对现有约束进行增强，增加ai​∗0=0的约束。增加这些约束的原因是为了保证转化后的 QAP 的各个多项式不线性依赖。

1.3 domain 选择

针对每个变量，已经知道 N 个 y 值。如何选择这些 y 值，对应的 x 值？这个就是 domain 的选择。选择 domain，主要考虑两个计算性能：

1. 拉格朗日插值
2. FFT 和 iFFT。

libfqfft 的源码提供了几种 domain：

1. Basic Radix-2
2. Extended Radix-2
3. Step Radix-2
4. Arithmetic Sequence
5. Geometric Sequence

选择哪一种 domain 和输入个数（M）有关。为了配合特定 domain 的计算，domain 的阶（M）会稍稍变大。

确定了 domain，也就确定了 domain 上的一组元素 s：

2. Setup 计算

随机生成 α,β,γ,δ,x∈Fr​ 。注意这里的和上一节中的 x 含义不同，不要混淆。

2.1 拉格朗日插值

已知的情况下，通过 1.2 的公式，先通过 domain 计算拉格朗日 basis。再乘上系数，可以获得ui​(x),vi​(x),wi​(x)。这些多项式的阶是 M。

2.2 计算xi 和 t(x)

xi 的计算相对简单，注意幂次计算都是在Fr​的计算。在 domain 确定后，多项式 t 也确定，从而可以计算出t(x)。

2.3 生成 Pk/Vk

按照如下的公式，计算 Pk/Vk。σ1​ 是 G1 上的点，σ2​是 G2 上的点。

其中，

是 Vk。其他部分是 Pk。可以看出，Vk 的大小取决于公共输入的变量个数，相对来说数量比较小。Pk 的数据量大小和所有的变量个数相关。计算过程，主要由 scalarMul 组成。

3. Prove 计算

在 domain 选择后，U*V=W，可以变换为如下的多项式方程：

3.1 多项式系数ui​(x),vi​(x),wi​(x)多项式系数

通过 iFFT，在已知 domain 上元素 s 和值对应关系，可以计算出多项式系数。

3.2 ui​(x),vi​(x),wi​(x) 在 coset 的值

ui​(x),vi​(x),wi​(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∈Fr​，在已知ui​(x),vi​(x),wi​(x),h(x)的情况下，通过如下的公式计算证明 A，B，C：

其中，A 需要计算在 G1 上的点，B 需要计算在 G1/G2 上的点，C 需要计算 G1 上的点。C 中δh(x)t(x)​计算如下：

很显然，生成证明的计算量主要由四个 Multiexp 组成（A-1，B-1，C-2），和变量个数以及约束的个数有关。在一个大型电路中，生成证明的时间比较长（秒级，甚至分钟级）。

4. Verify 计算

在已知证明以及 Vk 的情况下，通过配对（pairing）函数，很容易计算如下的等式是否成立。计算在毫秒级。

Groth16 算法的主要计算量由两部分组成：FFT/iFFT 以及 MultiExp。在生成证明时，需要 4 次 iFFT 以及三次 FFT 计算。Setup 计算和生成证明时，需要大量的 MultiExp。Verify 计算量相对较小。

我是 Star Li，我的公众号星想法有很多原创高质量文章，欢迎大家扫码关注。

• 发表于 2019-12-19 09:11
• 阅读 ( 4093 )
• 学分 ( 20 )
• 分类：零知识证明