Hacker Dōjo Workshop：
研究种类：密码学，Plonk证明系统
资助金额：100 usdt
Bounty链接：Hacker Dōjo|课题研究：零知识证明--Plonk证明系统 | Bounties | DoraHacks
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com
内容概要：
一、Fflonk
二、门约束与线约束
三、Plonk核心协议
四、聚合证明
五、递归零知识证明
多项式承诺与打开
KZG承诺A
一个多项式打开一个点
初始化：椭圆曲线双线性群为
，随机数
，t+1元组 
，令输出为
将setup分为2个集合：第一个集合为PK，第二个集合为VK。这两个集合会重叠，不是互斥关系。
承诺： 对于一个多项式
,计算多项式承诺
打开一个随机点： 计算商多项式
基于多项式的系数和PK，计算商多项式承诺
输出
关键结论：商多项式存在等价于双线性映射成立
校验一个随机点： 如果以下等式成立，则接受，否则拒绝
反之，如果双线性映射验证成功，则在索引i，多项式的值确实是
校验n个点，每次都正确，则每次都猜对概率为
，概率可忽略。
KZG承诺B
多个多项式打开多个点
承诺：对t1个多项式
，计算t1个多项式承诺
对t2个多项式 
，计算t2个多项式承诺
打开2 个随机点： 基于上述多项式与承诺，基于transcript计算2个随机数
。计算商多项式
计算2个商多项式承诺
输出
验证2 个随机点： 同样基于上述多项式与承诺，基于transcript计算2个随机数
。选择随机数
，分别计算t1,t2个 承诺和函数值承诺的累加值
缺点：验证复杂度与打开点数相关、与多项式的个数相关。打开点数越多，倍点运算越多。多项式越多，倍点运算越多。
如果以下等式成立，则接受，否则拒绝
条件 ① 对于每个打开点
，两个多项式的值相等
（验证复杂度与打开点数相关、与多项式个数相关）
条件 ② 多项式
是多项式
的因子（验证复杂度仅与多项式个数相关）
条件 ③
（验证复杂度仅与多项式个数相关，进一步降低）
Dan承诺批量验证A
多个多项式打开多个点
Setup： 双线性群为
,随机数
, d+t元组
,令输出为
多项式承诺：对t个多项式
，分别计算t个多项式承诺
打开S 个随机点： 基于上述多项式与承诺，基于transcript计算随机数。计算商多项式
计算并发送1 个 商多项式承诺
验证S 个随机点： 对于
， 如果以下等式成立，则接受，否则拒绝
验证复杂度
Dan Boneh 承诺优点：验证复杂度仅与多项式个数相关， 与随机打开点数无关。
Dan承诺批量验证B
优势与缺点：增加了证明长度，降低验证方的计算复杂度。
多个多项式打开多个点
Setup： 双线性群为
,随机数
, d+t元组
，令输出为
Commit： 对t个多项式
, 分别计算t个多项式承诺
打开S 个随机点： 基于上述多项式与承诺，基于transcript计算随机数。计算商多项式
计算并发送1个商多项式承诺W1
基于上述多项式承诺计算随机数 z。
计算多项式
由于
，则
计算并发送1个商多项式承诺W2
发送了一个辅助线性多项式
验证S 个随机点： 基于transcript计算随机数r。如果以下等式成立，则接受，否则拒绝
Dan Boneh 承诺优点：验证复杂度仅与多项式个数相关，与随机打开点数无关。
Dan承诺批量验证C
优势与缺点：增加了证明长度，降低验证方的计算复杂度。
Dan Boneh 承诺优点：验证复杂度仅与多项式个数相关，与随机打开点数无关。
多个多项式打开多个点
Dan承诺批量验证D
多个多项式打开多个点
Fflonk多个多项式组合
令D为某个域。
多项式上的操作
多项式的线性组合与线性分解
对于向量多项式
Fflonk 将多个多项式单点打开等价转化为1 个多项式多点打开。
Plonk证明系统
Plonk门约束和线约束
门约束
线约束
在电路系统中，上述多项式方程实现了信号在电路门之间的运算约束。使用多项式相等表达信号在同一条导线之间的处处相等。在同一条导线上信号处处相等，则两个相等的信号在运算上是可以进行置换的，所以线约束也称为置换约束。
核心知识：坐标对累加器
因此，得出以下关键结论1。
约束汇总
Plonk证明系统
门约束
Plonk核心协议
聚合证明
基于Plonk验证算法开发为验证电路，对应的验证密钥为VK‘存储到以太坊一层，输入多组 
，输出Proof’，将Proof’发生给验证方，则验证方校验
，等价于完成对多组
的校验。
难点：验证算法是双线性映射
在电路上表达双线性映射原理，涉及millier-loop。循环次数取决于计算出来的随机数，而不是固定值。因此，循环发生变化，导致电路也发生变化，导致 发生变化。以太坊一层矿工使用变化 校验有风险。因为证明方修改电路，也会导致 发生变化。证明方可以基于有漏洞的电路生成 提交到一层，实现作弊。所以矿工必须要使用一个固定的 ，代表一个固定的验证算法电路。
解决方案：验证电路只验证其他固定部分，不验证双线性映射。把多组双线性映射进行线性组合，耦合到 中，使得以太坊一层的矿工在进行1个双线性映射验证时，等价于把多组的双线性映射的线性组合也验证了。
递归零知识证明
Bn256 曲线标量域小于基域
难点1：基域和标量域之间的转换问题
人类十进制与计算机二进制位宽问题，用4个二进制表达十进制。
难点2：双线性映射的电路
在电路上表达双线性映射的原理，涉及一个millier-loop。循环次数取决于计算出来的随机数，而不是固定值。因此，循环发生变化，导致电路也发生变化，导致VK发生变化。将多个双线性映射的线性组合，然后提交，矿工验证双线性映射，等价于验证了10个双线性映射。则不需要写双线性映射的电路。
zcash使用递归曲线，标量域=基域
难点3：任意长for循环的电路约束
For循环变化，导致电路变化，导致VK变化；
将proof和VK输入到验证电路，验证电路是确定的，则验证电路对应的VK’是确定的，则可以存到以太坊一层合约中。
关于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