Blockchain and cryptography (区块链与密码学)学习笔记6:Plonk证明系统

Hacker Dōjo Workshop:
研究种类:密码学,Plonk证明系统
资助金额:100 usdt
Bounty链接:https://dorahacks.io/zh/daobounty/147
创作者:Lynndell
本项目由Hacker Dōjo资助,文章转载请联系
Telegram: @HackerDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com


内容概要:
一、Fflonk
二、门约束与线约束
三、Plonk核心协议
四、聚合证明
五、递归零知识证明

多项式承诺与打开

KZG承诺A

一个多项式打开一个点
初始化:椭圆曲线双线性群为image,随机数image,t+1元组 image,令输出为image

将setup分为2个集合:第一个集合为PK,第二个集合为VK。这两个集合会重叠,不是互斥关系。

承诺: 对于一个多项式image,计算多项式承诺
image
打开一个随机点: 计算商多项式
image
基于多项式的系数和PK,计算商多项式承诺
image
输出image
关键结论:商多项式存在等价于双线性映射成立
校验一个随机点: 如果以下等式成立,则接受,否则拒绝
image
反之,如果双线性映射验证成功,则在索引i,多项式的值确实是image
校验n个点,每次都正确,则每次都猜对概率为image,概率可忽略。

KZG承诺B

多个多项式打开多个点
承诺:对t1个多项式image ,计算t1个多项式承诺
image

对t2个多项式 image,计算t2个多项式承诺
image
打开2 个随机点: 基于上述多项式与承诺,基于transcript计算2个随机数image。计算商多项式
image
计算2个商多项式承诺
image
输出image
验证2 个随机点: 同样基于上述多项式与承诺,基于transcript计算2个随机数image选择随机数image,分别计算t1,t2 承诺和函数值承诺的累加值
image
缺点:验证复杂度与打开点数相关、与多项式的个数相关。打开点数越多,倍点运算越多。多项式越多,倍点运算越多。
如果以下等式成立,则接受,否则拒绝
image
条件 对于每个打开点image,两个多项式的值相等image
(验证复杂度与打开点数相关、与多项式个数相关)

条件 多项式image是多项式image的因子(验证复杂度仅与多项式个数相关)

条件
image(验证复杂度仅与多项式个数相关,进一步降低)

Dan承诺批量验证A

多个多项式打开多个点
Setup: 双线性群为image,随机数image, d+t元组
image,令输出为
image
多项式承诺:对t个多项式image,分别计算t个多项式承诺image
打开S 个随机点: 基于上述多项式与承诺,基于transcript计算随机数。计算商多项式
image
计算并发送1 商多项式承诺
image
验证S 个随机点: 对于
image
如果以下等式成立,则接受,否则拒绝
image
验证复杂度image
Dan Boneh 承诺优点:验证复杂度仅与多项式个数相关, 与随机打开点数无关。

Dan承诺批量验证B

优势与缺点:增加了证明长度,降低验证方的计算复杂度。

多个多项式打开多个点
Setup: 双线性群为image,随机数image, d+t元组image,令输出为
image
Commit: 对t个多项式image, 分别计算t个多项式承诺
image
打开S 个随机点: 基于上述多项式与承诺,基于transcript计算随机数。计算商多项式
image
计算并发送1个商多项式承诺W1
image
基于上述多项式承诺计算随机数 z。
计算多项式
image
由于image,则image
计算并发送1个商多项式承诺W2
image
发送了一个辅助线性多项式

验证S 个随机点: 基于transcript计算随机数r。如果以下等式成立,则接受,否则拒绝
image
Dan Boneh 承诺优点:验证复杂度仅与多项式个数相关,与随机打开点数无关。

Dan承诺批量验证C

优势与缺点:增加了证明长度,降低验证方的计算复杂度。

Dan Boneh 承诺优点:验证复杂度仅与多项式个数相关,与随机打开点数无关。

多个多项式打开多个点
image

Dan承诺批量验证D

多个多项式打开多个点
image

Fflonk多个多项式组合

令D为某个域。
image
多项式上的操作
image
多项式的线性组合与线性分解
image
image
对于向量多项式


Fflonk 将多个多项式单点打开等价转化为1 个多项式多点打开。
image

Plonk证明系统

Plonk门约束和线约束

image

门约束

image


image

image

线约束

在电路系统中,上述多项式方程实现了信号在电路门之间的运算约束。使用多项式相等表达信号在同一条导线之间的处处相等。在同一条导线上信号处处相等,则两个相等的信号在运算上是可以进行置换的,所以线约束也称为置换约束。

核心知识:坐标对累加器
image


因此,得出以下关键结论1。
image


image

约束汇总

Plonk证明系统

门约束



image

Plonk核心协议


image
image



image

聚合证明

基于Plonk验证算法开发为验证电路,对应的验证密钥为VK‘存储到以太坊一层,输入多组 image,输出Proof’,将Proof’发生给验证方,则验证方校验image,等价于完成对多组image 的校验。

难点:验证算法是双线性映射
在电路上表达双线性映射原理,涉及millier-loop。循环次数取决于计算出来的随机数,而不是固定值。因此,循环发生变化,导致电路也发生变化,导致 发生变化。以太坊一层矿工使用变化 校验有风险。因为证明方修改电路,也会导致 发生变化。证明方可以基于有漏洞的电路生成 提交到一层,实现作弊。所以矿工必须要使用一个固定的 ,代表一个固定的验证算法电路。
解决方案:验证电路只验证其他固定部分,不验证双线性映射。把多组双线性映射进行线性组合,耦合到 中,使得以太坊一层的矿工在进行1个双线性映射验证时,等价于把多组的双线性映射的线性组合也验证了。

递归零知识证明

Bn256 曲线标量域小于基域

难点1:基域和标量域之间的转换问题

人类十进制与计算机二进制位宽问题,用4个二进制表达十进制。

难点2:双线性映射的电路

在电路上表达双线性映射的原理,涉及一个millier-loop。循环次数取决于计算出来的随机数,而不是固定值。因此,循环发生变化,导致电路也发生变化,导致VK发生变化。将多个双线性映射的线性组合,然后提交,矿工验证双线性映射,等价于验证了10个双线性映射。则不需要写双线性映射的电路。

zcash使用递归曲线,标量域=基域

难点3:任意长for循环的电路约束

For循环变化,导致电路变化,导致VK变化;

将proof和VK输入到验证电路,验证电路是确定的,则验证电路对应的VK’是确定的,则可以存到以太坊一层合约中。


关于我们
:small_orange_diamond:Hacker Dōjo是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjo会以直播/音频/文字等形式定期组织分享session,内容包括Web3领域前沿技术论文解读、技术研讨、工作坊等。欢迎在Hacker Dōjo社区讨论、学习和交流。加入Dōjo的Hacker可以提出自己的学习期望,主动提案自己擅长的技术话题,由Dōjo组织分享。同时,Hacker Dōjo推出Web3前沿课题研究计划,定期选题,由hacker进行研究和讲解,并以bounty形式奖励研究贡献者。
合作事项
:small_orange_diamond:认领Bounty:https://dorahacks.io/zh/daobounty
:small_orange_diamond:转载文章:请保留Hacker Dōjo Workshop介绍并联系我们hackerdojo0@gmail.com。

good job! very useful!