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

Groth16算法的证明生成和验证性能的优化。第二阶段的挑战又分成两部分内容:Groth16算法的证明生成以及Groth16算法的验证。

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

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

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

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

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

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

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

SNARK挑战的第二阶段(下篇)挑战的主要内容是:Groth16算法的证明生成和验证性能的优化。第二阶段的挑战又分成两部分内容:Groth16算法的证明生成以及Groth16算法的验证。

SNARK挑战使用的零知识证明算法是:BG18。BG18是Groth16算法的一种变种算法,由Zcash的团队在2018年发表。

https://eprint.iacr.org/2018/187.pdf

BG18的证明的生成,比Groth16算法增加了z变量。

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

BG18的验证,比Groth16算法增加了一个验证:

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

01
BG18算法的验证

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

挑战的主要内容:优化JS或者WebAssembly,提高BG18算法的验证性能。这部分不需要GPU优化。不详细介绍。主要介绍一下,证明生成的挑战内容。

02
BG18算法的证明生成

https://codaprotocol.github.io/snark-challenge/problem-07-groth16-prover-challenges.html

BG18算法的证明生成逻辑涉及到以下相关的计算:

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

G1/G2椭圆曲线的点加和多点加法求和以及快速FFT(快速傅立叶变换)。

  • 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个点

以上的信息,可以理解成电路的相关信息。再提供以下的输入信息:

计算BG18的证明信息:A(G1),B(G2),C(G1)。计算公式如下:

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

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

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

注意以上的计算公式,并不是完整的BG18或者Groth16的计算公式,但是,绝大部分的计算量已经体现。

总的来说,需要三次傅立叶变换和4次傅立叶逆变换获取H多项式的系数。整个证明生成,还需要G1椭圆曲线上的4次多点加法求和计算和G2椭圆曲线上的一次多点加法求和计算。

总结:

第二阶段的挑战是对BG18(Groth16)算法的性能优化。计算量涉及点加和多点加法求和以及快速FFT(快速傅立叶变换)。

—全文完—

零知识证明 - Coda SNARK挑战剖析 · 下篇 IPFS 第15张【IPFS原力区】

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

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

发表评论

登录后才能评论

联系我们

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

邮件:ipfsforce@qq.com

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

QR code