Groth16计算详解_体育外围

企业新闻 | 2021-04-13
本文摘要:Groth16算法是zkSNARK的典型算法,目前在ZCash、Filecoin、Coda等项目中使用。

Groth16算法是zkSNARK的典型算法,目前在ZCash、Filecoin、Coda等项目中使用。本文从计算量的观点详细分析计算了Groth16。Groth16被分成三个部分: Setup对电路分解Pk/Vk (证明/验证密钥),在Prove与witness/statement等价的情况下分解证明,通过Vk验证证明Verify是否正确。本文中的所有术语和数学符号与Groth16论文一致(onthesizeofpairing-based non-interactive arguments )明确计算见17/18页):https://eprint.iacr.org 260 .通过PDF解读Groth16算法:零科学知识证明-通过Groth16算法记述基于libSnark代码的可读Relation的语言有R1CS、QAP、tinyRAM、bacs等很多。

现在开发出来了,电路一般用R1CS语言描述。R1CS相对直观。

体育外围

A*B=C(A/B/C分别是输出变量的线性组合)。但是,为了应用于Groth16算法,R1CS描述的电路必须转换为QAP描述。两种电路描述语言的转换称为Reduction。

1.1 R1CS叙述等价m '个变量(最初的变量誓言是常数1 )和n '个制约,所有的R1CS记述都可以如下响应:每行一个制约。例如,第一行约束是在1.2 QAP转换为讲义并明确转换之前,介绍非常简单的术语、拉格朗日插值和拉格朗日basis。通过等价一系列x和y的对应关系、网桌新闻网、拉格朗日插值方式,可以确认多项式: 1.3 domain自由选择对每个变量已经告诉了n个y值。

如何自由选择这些y值、对应的x值? 这是domain的自由选择。自由选择domain,主要考虑1/拉格朗日插值2/FFT和iFFT两种计算性能。libfqfft的源代码取得了几个domain:1 ) basic radix-2 ) extended radix-23 ) step radix-24 ) arithmetic sequence5) geo mence。

为了支持特定域的计算,域的步骤(m )不会稍稍变大。确认domain,确认domain上的元素s:2. Setup的集合是Vk。其他部分是Pk。

可以看出,Vk大小各不相同的公共输出变量的数量相对较少。Pk的数据量大小和所有变量的个数有关。计算过程主要由scalarMul构成。3. Prove计算domain自由选择后,U*V=W现在可以转换为分解证明的计算量主要由4个Multiexp组成(A-1,B-1,C-2 )的多项式方程。

体育外围

在一个大型电路中,分解证明的时间很宽(秒级,甚至分级)。4. Verify计算在未知证明或Vk的情况下,通过挖掘函数,可以更容易地计算下式是否正式成立。计算是毫秒级。

总结: Groth16算法的主要计算量由FFT/iFFT和MultiExp两部分组成。分解证明时必须计算4次iFFT和3次FFT。Setup需要大量的MultiExp来计算和分解证明。

Verify的计算量比较小。


本文关键词:体育外围

本文来源:体育外围-www.oktopuscali.com