The SNARK Challenge,通过GPU或者CPU指令集优化SNARK(Groth16算法)生成时间。时间从5月20号到7月15号。这项挑战也由Tezos,Filecoin,ZCash,0x等项目赞助。

Coda举办的零知识证明挑战奖金高达10万美金。但参与挑战的亮点除了奖金,整个挑战的内容本身也是极好的学习材料。
本系列旨在讨论零知识证明范畴的各个证明实现与相关技术剖析。
一起学习:理论梳理 – 技术优化- 代码实现

由Coda以及Dekrypt资本发起一项挑战:The SNARK Challenge,通过GPU或者CPU指令集优化SNARK(Groth16算法)生成时间。时间从5月20号到7月15号。这项挑战也由Tezos,Filecoin,ZCash,0x等项目赞助。
总奖金为10w美金
https://coinlist.co/build/coda。
此次SNARK挑战分为两期:
第一期基础知识挑战(5/20~6/03)
第二期是正式挑战(6/03~7/15)
此次挑战内容本身就是学习SNARK的好的教程
第一期(上篇)的基础知识挑战是整个挑战活动的热身,总奖金为200美金。
挑战又分为四小题
https://codaprotocol.github.io/snark-challenge/tutorial.html
要求:使用GPU将素数阶域的元素数组相乘。给定一个域上的n组数,计算相乘的结果。两个域

https://codaprotocol.github.io/snark-challenge/MNT4753.html
https://codaprotocol.github.io/snark-challenge/MNT6753.html
SNARK证明所需要的基本操作是乘法和加法。大数计算的位数比一般的计算使用的32位和64位要大的多。MNT4753和MNT6753的数为753位,也就是需要最少96个字节表示。753位,可以采用12个64位整数或者24个32位整数表示。其中的64位整数或者32位整数称为“limb”。
大数模乘,采用蒙哥马利规约(Reduction)算法(14.3章节)。
https://cacr.uwaterloo.ca/hac/about/chap14.pdf
二次扩展域上的加法和乘法定义为:
可以看出,二次域上的加法和乘法也是有一系列的大数乘法和加法组成。
三次扩展域上的加法和乘法定义为:
可以看出,三次域上的加法和乘法也是有一系列的大数乘法和加法组成(只是更复杂些)。
由椭圆曲线的方程,以及P/Q的直线方程,可以推导出(注意p和q的x相等的话,下面的公式不成立):
https://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html
在雅可比坐标系下,引入了Z坐标,线性坐标(x,y)可以变换成(X,Y,Z),满足:
x=X/Z
y=Y/Z
在点的Z坐标取值是否等于1的情况下,有不同的优化计算公式。以Z不等于1的情况下为例,计算公式如下:
Y1Z2 = Y1*Z2
X1Z2 = X1*Z2
Z1Z2 = Z1*Z2
u = Y2*Z1-Y1Z2
uu = u2
v = X2*Z1-X1Z2
vv = v2
vvv = v*vv
R = vv*X1Z2
A = uu*Z1Z2-vvv-2*R
X3 = v*A
Y3 = u*(R-A)-vvv*Y1Z2
Z3 = vvv*Z1Z2
总结:
Coda SNARK挑战的上篇介绍了SNARK算法的基础,大数算术(大数模乘)以及椭圆曲线群运算。SNARK挑战的本身也是很好的入门学习SNARK算法的好教材。
—上卷完—

【IPFS原力区】

本文来自公众号星想法,经授权后发布,本文观点不代表IPFS原力区立场,转载请联系原作者。
提示:投资有风险,入市须谨慎。本资讯不作为投资理财建议。