零知识证明 – Coda SNARK挑战剖析 · 下篇

Coda举办的零知识证明挑战奖金高达10万美金。但参与挑战的亮点除了奖金，整个挑战的内容本身也是极好的学习材料。

本系列旨在讨论零知识证明范畴的各个证明的实现与相关技术的剖析。

一起学习：理论梳理 – 技术优化- 代码实现

上篇请查看《零知识证明 – Coda SNARK挑战剖析 · 上篇》

SNARK挑战的第二阶段（下篇）挑战的主要内容是：Groth16算法的证明生成和验证性能的优化。第二阶段的挑战又分成两部分内容：Groth16算法的证明生成以及Groth16算法的验证。

SNARK挑战使用的零知识证明算法是：BG18。BG18是Groth16算法的一种变种算法，由Zcash的团队在2018年发表。

https://eprint.iacr.org/2018/187.pdf

BG18的证明的生成，比Groth16算法增加了z变量。

BG18的验证，比Groth16算法增加了一个验证：

挑战的主要内容：优化JS或者WebAssembly，提高BG18算法的验证性能。这部分不需要GPU优化。不详细介绍。主要介绍一下，证明生成的挑战内容。

https://codaprotocol.github.io/snark-challenge/problem-07-groth16-prover-challenges.html

BG18算法的证明生成逻辑涉及到以下相关的计算：

G1/G2椭圆曲线的点加和多点加法求和以及快速FFT（快速傅立叶变换）。

• d （uint64)

可以理解成门电路多项式的最高项的阶，也可以理解成门的个数

• m （uint64）

m+1可以理解成整个电路向量的大小

• A （G1， m+1）

G1椭圆曲线上m+1个点

• B1（G1，m+1）

G1椭圆曲线上m+1个点

• B2（G2，m+1）

G2椭圆曲线上m+1个点

• L（G1，m-1）

G1椭圆曲线上m+1个点，可以理解成witness的部分

• T（G1，d）

G1椭圆曲线上d个点

以上的信息，可以理解成电路的相关信息。再提供以下的输入信息：

计算BG18的证明信息：A（G1），B（G2），C（G1）。计算公式如下：

注意以上的计算公式，并不是完整的BG18或者Groth16的计算公式，但是，绝大部分的计算量已经体现。

总的来说，需要三次傅立叶变换和4次傅立叶逆变换获取H多项式的系数。整个证明生成，还需要G1椭圆曲线上的4次多点加法求和计算和G2椭圆曲线上的一次多点加法求和计算。

总结：

第二阶段的挑战是对BG18（Groth16）算法的性能优化。计算量涉及点加和多点加法求和以及快速FFT（快速傅立叶变换）。

—全文完—

【IPFS原力区】