零知识证明 - Coda SNARK挑战（Stage2）

显示全部楼层 · 发表于 2019-7-25 18:06:15

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

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

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

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

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

01BG18算法的验证

https://codaprotocol.github.io/snark-challenge/verifier.html

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

02BG18算法的证明生成

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

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

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个点

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

总结：

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

4ewh2knueko.png