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

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

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第1张

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第2张

Coda举办的零知识证明挑战奖金高达10万美金。但参与挑战的亮点除了奖金,整个挑战的内容本身也是极好的学习材料。

本系列旨在讨论零知识证明范畴的各个证明实现与相关技术剖析。

一起学习:理论梳理 – 技术优化- 代码实现

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第3张

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

总奖金为10w美金 

https://coinlist.co/build/coda。

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第4张

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第5张

此次SNARK挑战分为两期:

第一期基础知识挑战(5/20~6/03)

第二期是正式挑战(6/03~7/15

此次挑战内容本身就是学习SNARK的好的教程

第一期(上篇)的基础知识挑战是整个挑战活动的热身,总奖金为200美金。

挑战又分为四小题

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

01
第一题 – 域计算(大数模乘)

要求:使用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

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第9张

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第10张

02
第二题 – 二次扩展

二次扩展域上的加法和乘法定义为:

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第12张

可以看出,二次域上的加法和乘法也是有一系列的大数乘法和加法组成。

03
第三题 – 三次扩展

三次扩展域上的加法和乘法定义为:

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第13张

可以看出,三次域上的加法和乘法也是有一系列的大数乘法和加法组成(只是更复杂些)。

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

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第14张

由椭圆曲线的方程,以及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算法的好教材。

—上卷完—

零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第17张

【IPFS原力区】

总部位于上海,聚集基于分布式网络&存储的众多技术大咖和爱好者,深耕基于 IPFS 的商业生态建设和社区发展。
每周二举办“分布式存储网络”主题沙龙,聚集了众多技术大咖和 IPFS 爱好者,通过持续输出全面、精细、优质的IPFS咨询和技术支持,将生态中的爱好者转化为IPFS支持者和参与者,共建IPFS生态的健康发展。
零知识证明 - Coda SNARK挑战剖析 · 上篇 IPFS 第18张

本文来自公众号星想法,经授权后发布,本文观点不代表IPFSER立场,转载请联系原作者。

发表评论

登录后才能评论

联系我们

在线咨询:点击这里给我发消息

邮件:ipfsforce@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code