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(快速傅立叶变换)。