注册
关闭
区块链大帝

区块链大帝

发布于 2周前 阅读数 3595

探讨:在实际项目中,PGHR13算法是具体的什么步骤?

编者注:原标题为《关于zk-snark算法,想和您探讨一下。》

前言

了解零知识证明的读者,可能都拜读过V神的文章,整个系列由浅入深,很有条理,相对其他文章更容易理解一下【1】。其实V神讲解的算法是PGHR13算法的整体步骤,此算法也被应用于知名项目Zcash中,现在,就让我们去一起探究,在实际项目中,PGHR13算法是具体的什么步骤呢?【2】

 

建议

阅读本文前,假设您已经熟读并理解V神的关于零知识证明的讲解过程【1】。

PGHR13

在Zcash的Sapling版本升级之前,其采用的零知识证明算法的主体就是PGHR13,并因为效率和安全问题,做了一些改动。算法的具体内容如下图所示:

探讨:在实际项目中,PGHR13算法是具体的什么步骤?

1. Public paraments : 素数r,阶为r椭圆曲线群G1,G2,用于非对称双线性配对;非对称双线性配对效率最高

2. Key generator:主要生成CRS(pk,vk)

a. 输入算术环路C,其中n为pub_input size,h为witness size,l为output size

b. 向量A,B,C,元素为多项式,个数为m + 3个,m为算术环路wire的数量

c. Z为目标多项式

d. 向量A,B,C扩展到m+3的目的是为了保护多项式变量的取值τ

e. τ,ρ等随机数都是私有数据,生成完CRS后,要销毁

f. τ是多项式的取值

g. α等主要用来保证多项式A/B/C的valid commitment

h. β主要用来保证数据安全,使pkK独立于pkA,pkB,pkC

I. γ主要用来保证A,B,C使用同一组系数

关于向量以及最终生成的pkvk的直观效果如下图所示:

探讨:在实际项目中,PGHR13算法是具体的什么步骤?

3. Prove:生成证据π,7个群1的元素,1个群2的元素

a. s是系数向量,对应算术环路里每条wire所carry的值,元素个数和wire的数量一致

b. pkA和pk`A前n个置0的目的是为了防止明文攻击,通过改变公开的信息,导致证明的等式变化,但是验证也能通过。通俗的讲,就是本来你证明的是x^3 +x +5 = 35,攻击者可以通过修改public input的值,使得证明的等式变成x^3 +x +6 = 36,验证同样会通过

c. δ等值和(2.d)结合,保证τ的安全性

d. c向量,多项式的组合系数向量

关于向量以及生成结果的直观展示如下图所示:

探讨:在实际项目中,PGHR13算法是具体的什么步骤?

4. Verify:证明证据π成立

a. 计算vkx,保证公开信息没有被篡改

b. 校验A,B,C知识承诺的有效性,即A, B, C 是多项式的组合形式,采用d-KCA算法

c. 校验A,B,C使用的是同一组系数,类似于乘法分配律,等式左边是A,B,C单个元素累加再线性组合的结果,右边是A,B,C先线性组合再累加的结果,如相等,在系数相同。

d. 校验等式是否成立。

验证过程,关于向量的直观展示及验证过程如下图所示:

探讨:在实际项目中,PGHR13算法是具体的什么步骤?

总结

曾有人问道,想要实现零知识证明,我直接用同态隐藏技术不就可以实现么?为啥要想PGHR13算法那样复杂?

参考Zcash官网上给的解释【3】,我认为:同态隐藏函数一般是公开的固定的单向映射函数,当攻击者知道输入的大概范围后,可以通过暴力碰撞,得到你原始的隐藏值是什么。而在PGHR13算法中,利用多项式承诺计算方式对隐私数据进行隐藏,要隐藏的信息存在于多项式的系数当中;同态隐藏函数在此算法中只是被用来隐藏多项式的一个随机点τ,并且利用了离散对数,q-SDH及随机偏移δ的方式来保证τ的隐私性

 

参考:

1. v神讲解zk-snark https://www.jianshu.com/go-wild?ac=2&url=https%3A%2F%2Fmedium.com%2F%40VitalikButerin%2Fzk-snarks-under-the-hood-b33151a013f6

2. 25页展示具体的PGHR13协议 https://eprint.iacr.org/2013/879.pdf

3. Zcash的zk-snark详解过程,和V神的可以结合着看,更易理解的更加透彻。https://z.cash/technology/zksnarks/

  • 0
区块链大帝
区块链大帝

0 条评论