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

显示全部楼层 · 发表于 2019-7-8 12:03:24

前几个星期，由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的好的教程。

第一期（Stage1）的基础知识挑战是整个挑战活动的热身，总奖金为200美金。挑战又分为四小题。

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

01第一题 - 域计算（大数模乘）

02第二题 - 二次扩展

03第三题 - 三次扩展

04第四题 - 椭圆曲线群运算

由椭圆曲线的方程，以及P/Q的直线方程，可以推导出（注意p和q的x相等的话，下面的公式不成立）：

var curve_add = (p, q) => {
var s = (p.y - q.y) / (p.x - q.x);
var x = s*s - p.x - q.x;
return {
x: x,
y: s*(p.x - x) - p.y
};
};

http://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挑战的Stage1阶段介绍了SNARK算法的基础，大数算术（大数模乘）以及椭圆曲线群运算。SNARK挑战的本身也是很好的入门学习SNARK算法的好教材。

5jerrcgizyv.png