当前位置
主页 > 新闻中心 > 行业新闻 >
Groth16计算详解
2021-09-28 00:09
本文摘要:Groth16算法是zkSNARK的典型算法,目前在ZCash,Filecoin,Coda等项目中用于。本文从计算出来量的角度详细分析Groth16计算出来。Groth16计算出来分为三个部分:Setup针对电路分解Pk/Vk(证明/检验密钥),Prove在等价witness/statement的情况下分解证明,Verify通过Vk检验证明否准确。

米乐m6app下载

Groth16算法是zkSNARK的典型算法,目前在ZCash,Filecoin,Coda等项目中用于。本文从计算出来量的角度详细分析Groth16计算出来。Groth16计算出来分为三个部分:Setup针对电路分解Pk/Vk(证明/检验密钥),Prove在等价witness/statement的情况下分解证明,Verify通过Vk检验证明否准确。

本文中所有的术语和数学符号和Groth16论文保持一致(On the Size of Pairing-based Non-interactive Arguments,明确的计算出来在17/18页):https://eprint.iacr.org/2016/260.pdf对Groth16算法的解读可查阅:零科学知识证明 - Groth16算法讲解对libSnark代码库的解读可查阅:零科学知识证明 - libsnark源代码分析1. 电路叙述所有的电路叙述有个专业的术语:Relation(变量和变量的关系叙述)。叙述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 2)Extended Radix-2 3) Step Radix-2 4) Arithmetic Sequence 5) Geometric Sequence自由选择哪一种domain和输出个数(M)有关。

为了因应特定domain的计算出来,domain的阶(M)不会稍微逆大。确认了domain,也就确认了domain上的一组元素s:2. Setup计算出来是Vk。其他部分是Pk。

可以显现出,Vk的大小各不相同公共输出的变量个数,相对来说数量较为小。Pk的数据量大小和所有的变量个数涉及。计算出来过程,主要由scalarMul构成。

3. Prove计算出来在domain自由选择后,U*V=W,可以转换为如下的多项式方程:很似乎,分解证明的计算出来量主要由四个Multiexp构成(A-1,B-1,C-2),和变量个数以及约束的个数有关。在一个大型电路中,分解证明的时间较为宽(秒级,甚至分钟级)。4. Verify计算出来在未知证明以及Vk的情况下,通过筛选(pairing)函数,很更容易计算出来如下的等式否正式成立。计算出来在毫秒级。

总结:Groth16算法的主要计算出来量由两部分构成:FFT/iFFT以及MultiExp。在分解证明时,必须4次iFFT以及三次FFT计算出来。Setup计算出来和分解证明时,必须大量的MultiExp。Verify计算出来量比较较小。


本文关键词:首页,Groth16,计算,详解,Groth16,算法,是,zkSNARK,的,典型

本文来源:米乐m6app下载-www.youtao1688.com

联系方式

电话:048-454742651

传真:0153-52009014

邮箱:admin@youtao1688.com

地址:山西省大同市广灵县建来大楼51号