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

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原力区】