【1701vip黄金城集团】Groth16计算详解

  • 时间:
  • 浏览:541
本文摘要:Groth16算法是zkSNARK的典型算法,目前在ZCash,Filecoin,Coda等项目中用于。

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计算出来量比较较小。


本文关键词:1701vip黄金城集团,官方网站

本文来源:1701vip黄金城集团-www.pralii.com