Blockchain and cryptography （区块链与密码学）学习笔记5：Groth16证明系统

Dora Dōjo
1

Hacker Dōjo Workshop：
研究种类：密码学，Groth16证明系统
资助金额：100 usdt
Bounty链接：Hacker Dōjo|课题研究：零知识证明--Groth16证明系统 | Bounties | DoraHacks
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

1 零知识证明基础
1.1 预备知识
交互式零知识证明：证明方P发送数据给验证方V，也需要验证方V发送数据给证明方P。与TCP/IP协议的交互式一样。

非交互式证明：证明方P生成证明，发送给验证方V；验证方V验证一致性即可。该过程没有其他额外的数据交互。与用户将ECDSA签名发送出去而共识节点进行一致性验证过程一样，整个过程只有一次数据发送。

多项式时间算法：能够快速计算出结果的算法Polynomial-Time-Algorithms。

  1. 倍点算法：已知私钥sk和椭圆曲线基点G，能够快速计算出公钥PK
    PK:=sk⋅G
  2. 哈希运算：已知原象x和哈希函数SHA256，能够快速计算出函数值y
    y:=SHA256(x)

非多项式时间算法：包括指数时间算法、亚指数时间算法。以下计算需要指数时间：

  1. 离散对数：已知公钥PK和椭圆曲线基点G，不能够在多项式时间内计算出私钥sk，而需要指数时间才能计算出私钥sk，使得以下等式成立
    PK=sk⋅G

  2. 哈希求逆：已知函数值y和哈希函数SHA256，不能够在多项式时间内计算出原象x，而需要指数时间才能计算出原象x，使得以下等式成立
    y=SHA256(x)

根据维基百科，目前，学术届还没有区分P问题是否等于NP问题。为方便理解zkSnark，从应用角度出发，我们认为P问题不等于NP问题。

P问题：在多项式时间内可解的问题P-NP。以下问题多项式时间内可求解：

  1. 求公钥？已知私钥sk和椭圆曲线基点G，求满足以下离散对数关系的公钥PK
    PK=sk⋅G

  2. 求哈希值？已知原象x和哈希函数SHA256，求满足以下计算关系的函数值y
    y=SHA256(x)

NP问题：（1）多项式时间内不可计算的问题，需要指数时间或亚指数时间。（2）但是，一旦已知解，则能够在多项式时间内验证解是否正确P-NP。以下是3个典型的NP问题：

  1. 求私钥？已知公钥PK和基点G，求私钥sk。要求私钥与公钥满足以下离散对数关系
    PK=sk⋅G
    不能在多项式时间内求解出私钥sk，需要指数时间。但是，一旦给出私钥sk，则能够在多项式时间内验证该私钥sk与公钥PK是否满足离散对数关系。
  2. 求哈希原象？已知函数值y和哈希函数SHA256，求原象x。要求原象x和函数值y满足以下SHA256计算关系
    y=SHA256(x)
    不能在多项式时间内求解出原象x，需要指数时间。但是，一旦给出原象x，则能够在多项式时间内验证该原象x与函数值y是否满足SHA256计算关系。

因此，NP问题的本质是单向性，不可快速逆向求解，但是能够快速正向验证。
第3个重要的NP问题：多项式整除问题
给定一系列的多项式u0 (x),u1 (x),…,um (x);v0 (x), v1 (x),…,vm (x),w0 (x)，w1 (x),…,wm (x)，且给定一个目标多项式z(x)=(x-1)…(x-n)，找出这些多项式的线性组合能整除目标多项式。
求向量
image
满足以下整除关系
image
**原理分析:**向量s分别对三组多项式u0 (x),u1 (x),…,um (x);v0 (x), v1 (x),…,vm (x),w0 (x)，w1 (x),…,wm (x)进行线性组合，分别得到三个线性组合多项式
image
然后，将前两个线性组合多项式相乘并减去第三个多项式。这两个过程称为组合运算。
向量s的维度为m。如果每个元素si的取值空间为a，则将
image
称为二次算法多项式，简称QAP多项式。QAP多项式的构造为指数空间am。如果元素si的取值空间为0或1，则将
image
称为二次扩张多项式，或二次布尔多项式，简称QSP多项式。QSP多项式的构造为指数空间2m。因此，这两个组合运算的计算时间均是指数时间。

多项式z(x)等于零有n个解，而QAP/QSP多项式等于零的解数量为2n-2。所以，除z(x)=0的n个解以外，QAP/QSP多项式还有n-2个其他解。因此，可以计算出商多项式，且商多项式本质上就是QAP/QSP多项式等于零的n-2个其他解构成的多项式。
如果不知道向量，则只能随机选择一个向量，计算QAP/QSP多项式，然后检测与之是否满足整除关系。如果满足，则接受，否则拒绝。因此，需要指数时间才能够暴力搜索出向量。但是，一旦给定向量，则能够快速基于向量构造出QAP/QSP多项式，并快速验证与构造出的QAP/QSP多项式是否满足整除关系。因此，多项式z(x)与QAP/QSP多项式的整除关系，满足单项性，构成NP问题。 该构造至关重要，本文后续的举例需使用多项式整除关系构造NP问题。
image
运算关系公开 ，则需要提供正确的数据s1,…sn，使得数据s1,…sn满足运算关系。
image
image
对于第1个NP问题【求私钥】，可使用经典的Σ协议证明证明方P知道私钥sk而不泄露私钥sk。第2个问题【求哈希原象】无法使用Σ协议进行证明，但是可以将第2个NP问题等价转换为第3个NP问题【多项式整除关系】，然后将多项式系数放到椭圆曲线离散对数点上（即多项式承诺），形成离散对数困难，使得验证方能够重构整除关系。最后，验证方验证了向量s ⃗的正确性，但是证明方没泄露向量s 。
注意：如果私钥sk的位宽、哈希函数原象x的位宽、向量s ⃗的维度比较小，则对应的指数计算复杂度较低，则容易被暴力破解。如果足够大，则对应的计算复杂度较高，能够抵抗暴力破解。为方便展示计算过程，本文在第2.3节的举例使用方程对应的向量s 的维度比较小，容易暴力破解。但是，如果方程的阶很高，对应的向量s 维度很大，则不会被暴力破解。

1.2 零知识证明

零知识证明引言
对于第1个NP问题：证明方P向验证方V证明其拥有私钥sk，但不泄露sk。

  1. 证明方P用私钥sk和随机数k，计算ECDSA签名σ=(r,s)。
  2. 验证方V基于(r,s)构造椭圆曲线点，结合公钥PK重构线性关系，则验证成功。
    则验证方V认可证明方P有私钥sk而不知道该私钥sk。
    该举例使用数字签名实现零知识证明，可见零知识证明由数字签名发展而来。数字签名中的私钥天然满足对公钥的离散对数关系，但是零知识证明中的秘密ω满足任意计算规则y=F(ω)。因此，零知识证明对离散对数关系进行了巨大的扩展，使得零知识证明有了广泛的应用范畴。

定义1：零知识证明：令R为一个高效可计算的二元关系。对于一对二元组(x,ω)∈R，x为声明，ω为秘密见证。对于二元运算关系R，证明系统包括系统参数生成SysGen，证明P和验证V。
一个具体的知识证明协议ZK{ω|(x,ω)∈R}包括5个多项式时间算法，系统参数生成SysGen，承诺Commitment，挑战Challenge，响应Response和验证Verify。对于一个固定的安全参数λ，这5个算法如下运行：
系统参数：安全多方计算生成系数所需公共参数CRS
CRS←SysGen(1^λ)
• 承诺：证明方P选择一个随机数r，计算并发送承诺
C←Com(x,ω;r)
• 挑战：验证方V选择从某个域中一个随机数作为挑战e并发送给证明方P。
• 响应：证明方P对验证方V输出响应
z←Response(x,ω;e,r)
• 验证：验证方V基于承诺、挑战和响应计算并输出判断结果
Valid/Invalid←Verify(x,C,e,z)

ZK{ω|(x,ω)∈R}协议具有完备性，如果满足以下性质：
image
ZK{ω|(x,ω)∈R}协议具有知识提取鲁棒性，如果满足以下性质：
image
对秘密证明2次，则可以提取秘密，说明秘密确实使用了。承诺的随机数使用2次，挑战不同，影响不同，则可以解方程组。

ZK{ω|(x,ω)∈R}协议具有诚实验证方零知识，如果满足以下性质：
image
定义：如果协议ZK{ω|(x,ω)∈R}具有完成性、知识提取的鲁棒性和诚实验证方零知识，则协议ZK{ω|(x,ω)∈R}是一个Σ协议。

1.3 协议

Σ协议包括： （1）生成系统参数CRS，（2）承诺，（3）挑战，（4）响应，（5）验证。其中，系统参数CRS由多方安全计算生成。

系统参数CRS： 群G的阶为q，生成元为G；公开输入为Q∈G。在该系统下，证明方P证明：其知道ω满足离散对数关系Q=ω⋅G。

交互式零知识证明
承诺：证明方P选择随机数r，计算并发送：C:=r⋅G；
挑战：验证方V选择随机数e，发送e；
响应：证明方P计算并发送：z:=r+e⋅ω；
验证：验证方V验证
z⋅G=C+e⋅Q
如果等式成立，则接受，否则拒绝。
image
协议思想：

  1. 如图1所示，证明方P将ω与随机数e进行线性组合z:=r+e⋅ω，生成随机数z；
  2. 验证方V基于随机数z,e构造椭圆曲线离散对数点z⋅G,e⋅Q，并与点C，在椭圆曲线离散对数上重构线性关系，实现一致性验证。

非交互式零知识证明
承诺：证明方P选择随机数r，计算：C:=r⋅G；
挑战：证明方P计算随机数：e:=Hash(Q,C)；（此处有变化）
响应：证明方P计算z:=r+e⋅ω，发送：C,e,z
验证：验证方V计算e:=H(C)，然后验证
z⋅G=C+e⋅Q
如果等式成立，则接受，否则拒绝。

数字签名定义：
Alice用私钥sk对消息m签名，验证方Verifier用Alice的公钥PK对消息签名对(m,σ)进行一致性验证
image
非交互式零知识证明扩展为数字签名
对于离散对数关系Q=ω⋅G，把ω看作私钥sk，Q看作公钥PK。
承诺：证明方P选择随机数r，计算：C:=r⋅G；
挑战：证明方P计算随机数：e:=Hash(C,m)；（此处有变化）
响应：证明方P计算z:=r+e⋅ω，发送：C,e,z,m；
验证：验证方V计算e:=Hash(C,m)，然后验证
z⋅G=C+e⋅Q
如果等式成立，则接受，否则拒绝。

保密随机数的作用等价于私钥。举例：tornado cash就是zk证明知道承诺的随机数r，就可以提币。

核心思想： 第3步的数据等价于Alice的对消息的签名，第4步等价于验证方使用Alice的公钥对消息与签名的一致性验证。因此，该协议满足数字签名的定义。

本质上该协议是证明：（1 ）Alice 拥有私钥 ，且（2） ω与消息m具有绑定关系e=Hash(A,m)。
Σ协议：证明方P证明其知道ω满足离散对数关系Q=ω⋅G。由于Q=ω⋅G即是天然的NP问题，又是天然的离散对数关系，所以可以直接基于这个NP问题在椭圆曲线离散对数点上构造线性关系，形成离散对数困难问题。最后，验证方V验证了NP问题的解的正确性，但是证明方P没泄露ω。
zk-SNARK协议：需要证明ω满足任意多项式时间计算关系y=F(ω)。该任意计算包括NP问题和P问题。

  1. NP问题：已知函数值y和哈希函数SHA256，求原象x；已知Merkle根，求Merkle树的叶子和路径；
  2. P问题：已知两个布尔值a,c，求布尔值b，使得等式a⊕b=c成立；已知方程x4+x3+x2+x=120，求解x；
    这4个算法中，
    哈希函数的原象x、Merkle树的叶子和路径、布尔值b、方程解x=3以及计算过程的中间状态值就是秘密，记为ω或witness。
    哈希函数值y、Merkle根、布尔运算结果c和方程的值120，记为statement。

为不泄露秘密，需使用R1CS约束（电路约束）等价描述算法的运算规则。公开R1CS约束（电路约束），然后将满足公开的计算关系等价转化 为满足R1CS约束并合并R1CS 约束 ，再等价转化为向量与多维向量的內积，再等价转化为向量与矩阵的內积，再等价转化为向量对三组多项式的组合运算，再等价转化为目标多项式整除QAP多项式（ 构成NP 问题 ），再等价转化为基于这三个多项式的系数计算椭圆曲线离散对数点（即多项式承诺），形成离散对数困难问题；最后，验证方基于椭圆曲线离散对数点（多项式承诺）重构整除关系，验证了向量的正确性，但是证明方没泄露向量。
zk-SNARK协议的7 个核心等价转化关系 ，如图2所示
image
接下来对zk-SNARK协议中的核心等价转换关系进行详细叙述。

2 多项式时间算法等价转换为阶为1的等式

2.1 哈希函数等价于阶为1的等式

哈希函数SHA256输入512bits的数据，通过与、或、非、异或、循环移位等基础运算的耦合，进行线性变换与非线性变换(扩张与有损压缩)，输出256bits的随机数。以下是SHA256的运算原理，循环64次后输出函数值。其中，x,y,z位宽均为32bits，Si循环右移i bits，Ri循环右移i bits。
image
以下对布尔值和异或运算进行等价转化：
布尔值a和b，如下拆为阶为1的等式
image
位异或运算a⊕b=c，如下拆为4个阶为1的等式
image
推论1 ：布尔值 和 等价于阶为1 的等式2 ；
推论2 ：位异或运算 等价于4 个阶为1 的等式3 。
因此，基于推论2.1和2.1，可以得出以下推论：
推论3 ：哈希函数SHA256 或公式1 等价于 某些阶为1 的等式 。 a*b=c
推论4 ：Merkle 树等价于某些阶为1 的等式。

上述3 个阶为1 的等式就是电路约束。这3 个阶为1 的等式是乘法等式，所以是乘法约束。 公式3的前3个乘法约束限定输入为布尔值，第4个乘法约束实现异或运算的等价功能。一方面：可以基于这****4 个等式，设计实际的硬件电路或FPGA 。另一方面：可以用程序表达这4 个运算规则，则等价于表达出电路约束，等价于实现电路运算原理。因此，算法的运算规则等价于电路约束。
a和b是输入值，c是输出值。证明方把a,b,c发送给验证方，则验证方根据a,b,c和上述阶为1的等式（电路约束）成功验证，则验证方认可证明方是对布尔值a和b诚实进行异或运算。类似地，证明方把哈希函数的原象x和函数值y发送给验证方，验证方根据x,y和阶为1的等式成功验证，则能够确定证明方诚实计算哈希函数，且原象x和函数值y是正确的。
在零知识证明协议中，witness是布尔值a,b或原象x，statement是c或哈希值y，算法的计算规则就是电路约束（R1CS约束）。因此，上述证明与验证过程存在2个缺点：

  1. 秘密泄露：布尔值a,b或原象x泄露，缺乏零知识，后续通过离散对数解决。
  2. 验证方的计算复杂度没降低：阶为1的等式的计算复杂度等于原算法的计算复杂度，所以验证方的计算量没降低。后续通过多项式放到离散对数上解决。
    计算压缩：
    数据压缩：向量s={0jkdshgfgfshk}
    Proof长度是固定的几个椭圆曲线点。

2.2 数字签名等价于阶为1的等式

（一）预备知识

  1. 椭圆曲线离散对数困难问题：已知基点G=(x0,y0)和公钥Q=(xq,yq)，计算私钥是困难的
    Q=sk⋅G
    因此，密码学提供计算安全，是相对安全，而不是绝对安全。
  2. 已知私钥sk和基点G=(x0,y0)，可在多项式时间内计算公钥Q=(xq,yq)。
    （二）数字签名
    ECDSA签名：用户的私钥为d，对于消息M，选择随机数k∈[1,…,n-1]，如下计算：
    image
    则签名为σ=(r,s)。广播(M,σ,Q)，其中Q是公钥。
    ECDSA签名原理解析：
  3. 选择一个随机数k，计算椭圆曲线离散对数k⋅G。随机数k对私钥d进行随机化，防止攻击者计算出私钥d。
  4. 计算出两个随机数(r,s)就是签名。这两个随机数(r,s)是随机数k-1、私钥d、消息的摘要值SHA(M)和横坐标r的线性组合
    image
    因此，攻击者无法根据(r,s)计算出随机数k与私钥sk。

ECDSA 验证： 验证方基于如下计算：
image
如果等式r=x1modn成立，则接受，否则拒绝。
ECDSA验证原理解析：

  1. 基于两个随机数(r,s)和消息M计算出u1,u2；
  2. 基于u1,u2、基点G和公钥Q进行倍点运算，计算出2个椭圆曲线点u1⋅G,u2⋅Q；
  3. 对这两个椭圆曲线离散对数点u1⋅G,u2⋅Q进行点加运算，则结果为(x1,y1)；
  4. 新椭圆曲线点的横坐标x_1与随机数r应该相等的，则验证成功。

ECDSA思想精华： 用户从私钥角度计算椭圆曲线离散对数点(x1,y1)，并产生两个随机数(r,s)，使得验证方能够从公钥的角度重新计算出椭圆曲线离散对数点(x1,y1)。
ECDSA算法包括3个基本的运算，分别为椭圆曲线离散对数点加运算u_1⋅G+u_2⋅Q、倍点运算k⋅G、域元素相乘的模n运算。
为方便后续分析，将点加运算(x1,y1):=u_1⋅G+u_2⋅Q进行如下修改：
(x3,y3):=(x1,y1)+(x2,y2)
点加运算：
已知两个椭圆曲线离散对数点(x1,y1),(x2,y2)，求第三个点(x3,y3)， 计算过程如下：
image
上面是求值：求值电路。

其中，a=-1,d=-168696/168700是两个常量。
当x1=x2,y1=y2，就是倍点运算，因此以下仅讨论点加运算。
将上述点加运算公式6拆为7个阶为1的等式
image
验证电路 ：把结果放到电路里面去了。

推论5 ：点加运算公式6 与等式1.7 等价。
推论6 ：ECDSA 能够等价拆为阶为1 的等式。或ECDSA 与某些阶为1 的等式等价。
这些阶为1 的等式就是电路约束。其中，阶为1 的乘法等式就是乘法约束，阶为1 的加法等式就是加法约束。这7 个约束实现点加运算的等价功能。一方面：可以基于这7 个阶为1 的等式（R1CS 约束），设计实际的运算电路或FPGA 。另一方面：可以用程序表达这7 个运算规则，则等价于表达出电路约束，等价于实现电路运算原理。因此，算法的运算规则就是电路约束。
证明方把(x1,y1),(x2,y2),(x3,y3),A1,A2,A3,A4,A5,A6发送给验证方，则验证方根据阶为1的等式1.8成功验证，则验证方确定证明方是诚实进行点加运算的。
类似地，证明方把消息M、签名值σ和公钥Q发送给验证方，验证方根据某些阶为1的等式进行验证，则能够确定证明方诚实计算了ECDSSA签名。

但是，仍存在以下两个缺点：
1. 消息太多：或秘密泄露。交易消息M、签名值σ和公钥Q泄露。解决方案：仅存储交易消息M中的公开数据pubdata和Merkle根，剩余的所有消息隐藏起来，如签名和公钥当作witness。
2. 验证方的计算复杂度没降低：阶为1的等式的计算复杂度等于签名验证计算复杂度。后续通过多项式和离散对数解决该问题。

推论7：任意多项式时间算法均能够拆为阶为1的等式。或任意多项式时间算法与某些阶为1的等式等价。

2.3 多项式时间算法等价于阶为1的等式

任意多项式时间算法（包括上述SHA256和ECDSA）均有一个对应的阶为1的等式（R1CS约束）。此处，将多项式时间算法限定为一个方程，将方程拆为阶为1的等式。该举例有2个作用：（1）解该方程是P问题，体现了基于P问题构造NP问题；（2）能够较好的展现出对R1CS约束的优化。
方程x4+x3+x2+x=120如下拆为阶为1的等式
image

关键结论：x=3 满足方程的解，等价于x=3 满足电路约束。

关键结论：x 满足任意多项式时间运算y=f(x) ，等价于x 满足电路约束。

这6 个阶为1 的等式限定了方程的运算规则，能够用电路约束表达同样的运算规则。电路约束即能用硬件电路或FPGA 实现，也可以用软件实现等价的功能。阶为1 的等式= 电路约束，阶为1 的乘法等式= 乘法约束，阶为1 的加法等式= 加法约束。
关键术语： 阶为1 的等式（Rank 1 Constraint System, R1CS ）。

以下术语是等价描述：阶为1的等式、R1CS约束、电路约束。

上述6个阶为1的等式包含3个乘法等式和3个加法等式，可使用3个乘法约束和3个加法约束实现运算原理，如图1(a)所示。此外，可以将加法约束优化到乘法约束中，则上述6个阶为1的等式8化简为以下3个阶为1的乘法等式9。仅使用3个乘法约束即可实现等价的运算规则，如图1(b)所示。
image
image
推论8 ：方程 (多项式时间算法)等价于R1CS约束，形式化表达如下
image
因此，可以得出以下推论：
推论9：任意多项式时间算法（哈希函数SHA256、Merkle树、ECDSA验证、方程等）均可等价为阶为1的等式（也称为：R1CS约束、电路约束）。

3 witness满足R1CS约束的等价转化

预备知识
image

3.1 witness等价于向量s
本节将witness即方程的解x=3（也可以是哈希函数原象x，Merkle树的叶子和节点、ECDSA中的消息M、签名σ和公钥Q）等价转化为向量
image
image
对约束等式10
image
的(b)，有以下等价关系
image
可见R1CS约束等式(b)中的向量需要包含更多的中间状态变量s3,s4,s5。在下一节，R1CS约束等式(b)对应的矩阵维度也更大，进而在后续步骤中会产生阶数更高的多项式和更复杂的拉格朗日插值多项式（或傅里叶变换）。因此，下一节的R1CS约束约束等价转化为矩阵时，使用优化的R1CS约束等式(c)。
业务语言：隐私数据（方程的解x=3、哈希函数原象x，Merkle树的叶子和节点、ECDSA数据M签名σ和公钥Q）就是零知识证明中的witness。

在实际应用时，为防止证明方P欺骗验证方V，不能将所有数据隐藏起来，需要公开局部参数。所以，1,out需要公开， x,s1,s2,s3隐藏。因此，将向量s ⃗拆为公开数据与隐私数据。公开数据记为statement=(1,out)，隐私数据记为witness=(x,s1,s2,s3)。这里的out是方程的计算结果120。对于Layer2技术，out则是Merkle根。
image

3.2 witness满足R1CS约束等价于向量內积

对于第1个阶为1的等式（R1CS约束）s1=x*x，如下进行向量內积等价转化：
image

image
image711×670 11.8 KB

image

3.3 向量內积等价转化为向量与矩阵的內积

image
image640×559 9.57 KB

4 向量与矩阵內积的等价转化

命题2：多项式值表达等价于多项式系数表达。
证明： 设阶多项式为
image
已知多项式的值f0,…,fm和横坐标x0,…,xm，可以计算出多项式的系数a0,…,am；计算方法包括解方程组、拉格朗日插值法、快速傅里叶逆变换等。反之，已知多项式的系数a0,…,am和横坐标x0,…,xm，可以计算出多项式的值f0,…,fm。因此，多项式值表达等价于多项式系数表达。快速计算方法：快速傅里叶变换。

4.1 向量对三组多项式的组合运算

将方程x4+x3+x2+x=120转换为R1CS约束后，得到以下三个矩阵
image
将矩阵中的元素当作多项式的值，如对矩阵W
image
对于多项式值表达等价转化为多项式系数表达，以下介绍的拉格朗日插值法不是最优算法，但在理解上是最直观的。最优算法是快速傅里叶变换、基4时分的Cooley-Tukey 蝶形变换，运算可并行化，并使用GPU/FPGA 等加速。

对于多项式的值，每一列有3个函数值，所以取任意3个变量，如，作为横坐标。可使用拉格朗日插值多项式，基于多项式的值计算多项式的系数
image
如下计算多项式的系数表达
image
则多项式
image
以此类推，可以计算出多项式
image
则有以下等价关系
image
image

4.2 目标多项式整除QAP多项式构造NP问题

上述拉格朗日插值多项式引入横坐标为x=1,2,3，则能够构造多项式
z(x)=(x-1)(x-2)(x-3)
z(x)称为目标多项式。可以取任意横坐标变量，如令x=4,5,6，则重新使用拉格朗日插值定理计算函数值并令目标多项式为z(x)=(x-4)(x-5)(x-6)。
image

image
image673×586 19.2 KB

KZG承诺：y=f(z)函数点运算正确
基于现有的运算构造出多项式，进行多项式承诺打开某些点。F(x)
120=f(x=3)，确实知道秘密x=3，提供了正确数据。

z(x)*Q(x)=QAP(X)，基于PK，a，z(a)*G1
z(x)=3x^3+2x^2+x
PK=a^3G1,a^2G1,aG1
a^3G2,a^2G2,aG
e(z(a)*G1,Q(a) *G2)=e(QAP(a) *G1,G2)
z(a)*Q(a)=QAP(a)
image
反之，如果验证方V能够基于椭圆曲线离散对数点（多项式承诺）重构整除关系，则向量s对三组多项式的组合运算是正确的，则向量与矩阵的內积运算正确，则向量与多维向量的內积正确，则witness满足R1CS约束，则x=3是方程的解（或x是哈希函数的原象，a,b是布尔值，叶子与节点满足Merkle树），则证明方P对数据的运算是正确，则用户提交了正确交易数据。因此，用户交易会成功。

5 zk-SNARK协议框架

image
image
分析

  1. 将QAP多项式、目标多项式和商多项式的系数放到椭圆曲线的离散对数上，验证方在椭圆曲线点上重构整除关系，实现正确性验证，却不知道多项式的系数（或不知道解向量s ⃗），即零知识。

  2. 计算复杂度很高的任意多项式时间算法，等价转化为R1CS约束、矩阵、多项式。最后与向量对三组项式组合运算生成QAP多项式，并与目标多项式、商多项式的系数均放到椭圆曲线离散对数点上（多项式承诺），所以证明方P的计算复杂度很高；而验证方仅需要使用椭圆曲线点重构整除关系，则实现向量s 的正确性验证，所以计算复杂度较低。

算法评价
1：Groth16的CRS包含R1CS约束等价转化来的多项式W(x),U(x),V(x)，非常具体。
优点：证明方P直接使用CRS中的多项式W(x),U(x),V(x)生成证明，速度很快。
缺点：这个CRS包含的多项式W(x),U(x),V(x)是由R1CS约束转换而来，已经固化，只能表达唯一电路，不能表达其他电路，所以表达能力极差。如果对layer2的电路进行修改，则步骤7的初始化b局部CRS也需要修改，则Layer1的合约参数CRS也需要对应修改才能够进行一致性验证。

2：PLONK的CRS不包含R1CS约束多项式，而只包含大量的椭圆曲线离散对数点。
优点：CRS的表达能力很强，能够用于任意多项式时间电路生成证明。
缺点：CRS表达能力太强，R1CS约束力不够，不足以防止证明方P作弊，所以引入额外的线约束。线约束计算复杂度很高，导致证明生成缓慢。

6 Groth16协议详解

6.1 协议原理

image
注意：x是具体值，所以多项式u(x),v(x),w(x)是具体的多项式值；σ_1,σ_2中与多项式u(x),v(x),w(x)无关的项在步骤0完成，与电路多项式u(x),v(x),w(x)相关的项在步骤7完成。注意：此处的多项式u(x),v(x),w(x)就是上一节讨论的多项式W(x),U(x),V(x)。
ECDSA的验证算法写成了电路；则用户提交正确的交易单就是s
image
image

6.2 协议分析

（一）、一致性

image
image619×537 12.2 KB

（三）、证明方无法作弊：
image
image541×506 12.8 KB

原理分析

  1. α和β迫使证明A,B,C必须采用同一套向量statement=a0,…,a0参数，而不能是其他参数。反之：如果A采用第1套参数 a0,…,am参数。B采用第2套参数a0‘,…,am’，那么C应该采用第1套还是第2套参数呢？答：不管C采用第1套还是第2套参数，等式都不会成立。如果C采用第1套参数，计算出来的表达式与A有对应关系，却与B没有对应关系，等式肯定不成立。

  2. 对于A,B,C的构造，需要证明方选择随机数r,s。如果不添加随机数r,s，那么证明A,B,C就失去了随机性，验证方可以根据等式求解出witness。因此，算法中添加随机数的算法功能叫作：盲化或随机化，让对方计算不出witness。

    image
    image571×645 15.8 KB

    image

关于Dorahacks
DoraHacks 是一个全球范围内的极客运动、全球黑客马拉松组织者，也是全球最活跃的多链 Web3 开发者平台之一。DoraHacks.io平台使得世界各地的Hacker和开源开发者可以参与黑客马拉松、Bounty、Grant、Grant DAO，以及公共物品质押等加密原生协议和基础设施进行协作并获得资助。到目前为止，DoraHacks 社区的 4000 多个项目已经获得了来自全球行业支持者超过 3000 万美元的资助。大量开源社区、DAO 和 超过50个主要区块链生态系统正在积极使用 Dora 的基础设施（DoraHacks.io）进行开源融资和社区治理。

关于Dorahacks DAO Bounty
Dorahacks DAO Bounty，为各类DAO和组织赋能！
Bounty计划为DAO和组织提供了一个强大的平台，通过社区激励的形式，发布问题，协调任务，鼓励用户积极参与。
作为Bounty发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：How to publish a bounty and easily fund bounty hunters
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：DAO Bounties | DoraHacks

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：Dora Dōjo - Dora Community Forum

目前Hacker Dōjō已分享的主题有：

  • 密码学：基础专题（对称加密算法、哈希函数、群和公钥加密、数字签名和KZG承诺、零知识证明、非对称密码算法、分布式密码学）
  • 密码学：算法代码专题（Halo、Halo2、Plonk、Groth16、分布式密钥生成）
  • 密码学：抗量子计算破解算法专题
  • Layer1架构：Move系列、模块化公链、共识协议Bullshark、内存池协议Narwhal和共识协议Tusk、Aptos共识与交易并行执行
  • Layer2架构：zkSync研究、Layer2的支付通道扩容方法、Polygon Hermez、Optimism、StarkWare技术与生态梳理
  • IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
  • 量子计算系列：量子计算基础、Qiskit专题（Qiskit入门、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷积神经网络、量子傅里叶变换、量子相位）、Pennylane专题（利用变分量子电路拟合傅里叶级数）、实验法观测宏观量子叠加态
  • AIGC系列：ChatGPT比较语料评测、GPT-4论文解读

加入Dōjō的Hacker可以提出自己的学习期望，主动提案自己擅长的技术话题，由Dōjō组织分享。同时，Hacker Dōjō推出Web3前沿课题研究计划，定期选题，由Hacker进行研究和讲解，并以bounty形式奖励研究贡献者。欢迎各位Hacker认领Bounty：DAO Bounties | DoraHacks

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com

2 Likes
2

学习了，帮助很大。请问推算一致性的这些图片源地址在哪。

3

讲的非常好，第一次发现了这个宝藏网站，thanks