Hacker Dōjo Workshop：
研究种类：密码学，数字签名与KZG承诺
资助金额：100 usdt
Bounty链接：Hacker Dōjo|课题研究：数字签名与KZG承诺 | Bounties | DoraHacks
创作者：Lynndell
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com
4 数字签名与KZG承诺
1.BLS签名与聚合签名
BLS 签名仅1 个随机因子，即私钥。
BLS 签名扩展
令M’={M | r}
签名：δ=H(M’)a
广播：（M，δ，pk，r）
数据拼接：M‘←{M | r}
验证公式：e(δ, g) = e(H(M’),h)
验证：
双线性映射：计算复杂度很高；尽量少算；一次
其他群运算计算复杂度很低，可以多算。
Schwartz–Zippel 引理
P为有限域F上的多项式P=F(x1,…,xn)，其阶为d。令S为有限域F的子集，从S中选择随机数r1,…,rn，则多项式等于零的概率可忽略，即
在单变量情况下，等价于多项式的阶为，则最多有个根。
使用随机数进行对签名进行线性组合，根据Schwartz –Zippel 引理，发生碰撞的概率可忽略。
2.Schnorr签名
签名： 消息为m，选择随机数r，计算承诺R=r·G ，
计算挑战e:=hash(R, PK, m)
计算响应s:=(r+e·x)mod q
签名为（R，s）
验证： 重新计算挑战e=hash(R, PK, m) ，然后校验sG==R+e·PK
3.EdDSA签名算法
初始化： 椭圆曲线生成元为G，阶为q
密钥生成： 私钥为x，公钥为PK=x·G
签名： 消息为m，计算随机数r=hash(x,m)，计算承诺R=r·G ，
计算挑战e:=hash(R,PK,m)
计算响应s:=(r +e·x)modq
签名为(R,s)
验证： 重新计算挑战e:=hash(R,PK,m) ，然后校验sG==R+e·PK
与ECDSA最大的区别在于没有使用随机数， 这样产生的签名结果是确定性的，即每次对同一消息签名结果相同。一般说来随机数是安全措施中重要的一种方法，但是随机数的产生也是安全隐患，著名的索尼公司产品PS3密钥泄露事件，就是随机数产生的问题导致的。
4.ECDSA原理
初始化： 椭圆曲线生成元为G，标量域为Fr，基域为Fq。
密钥生成： 输入安全参数λ，输出私钥x∈Fr和公钥PK，满足离散对数关系PK=x·G
签名： 输入任意消息M，计算m:=Hash(M)mod|Fr|；
选择随机数k∈Fr，计算承诺：
挑战： 取横坐标为
**响应：
则签名为(r, s)。
验证： 输入消息M，计算m:=Hash(M)；校验r,s∈Fr，计算R’:=(s-1m)·G+(s-1r)·PK
取横坐标为
；校验r=r’。如果相等，则接受，否则拒绝。
公式推导过程如下：
5.承诺
5.1 承诺概念
第1 步：承诺阶段：选择x ，计算 y=f(x)，发送函数值y
第2步：打开阶段：发送原象x
第3步：校验阶段：y=f(x)
第4 步：多点打开
第5 步：校验多点打开
对函数是有一定要求：
- 函数求逆具有NP 困难 ，需要暴力搜索，需要指数时间。
- 但是校验简单。
5.2 哈希承诺
第1步：承诺阶段：广播哈希值y
第2步：打开阶段：广播原象x
第3步：校验阶段：验证一致性y==hash(x)
5.3 Merkle承诺与Merkle证明
第1步：承诺：发送Merkle root
第2步：打开：发送叶子节点x_i 和path_i
第3步：校验：校验
且检查root在以太坊合约上。
证明方需要证明其知道每个叶子节点的值
树高度为100
低效做法：
第1步：承诺阶段：发送Merkle root
第2步：打开阶段：发送所有叶子节点
第3步：校验阶段：校验
且检查root在以太坊合约上。
高效做法：
检测n 个点即可。没必要打开所有。即使知道所有值，也不必打开所有叶子。
打开了足够多的点，校验足够多的点。就没必要打开整个多项式。
整个多项式的阶2^25–2^30
整个多项式是对的，则等价于交易是对的。
For i=0,i++,i<=100 {
第1步：承诺阶段：发送Merkle root
第2步：打开阶段：发送叶子节点x_i和path_i
第3步：校验阶段：校验，且检查root在以太坊合约上。校验复杂度非常低。
}
每个叶子节点的值就是0或1
1/2^100
核心思想：从概率角度，不必打开每个叶子节点，打开1024 个点，每次都正确，则伪造成功概率呈指数降低。验证方相信证明方知道了所有叶子节点。
Merkle证明
第1步：证明知道sk。拥有token
第2步：基于叶子节点和path计算merkle root
第3步：检测merkle root在以太坊上。
5.4 Sigma零知识证明中的承诺
承诺 A、挑战、响应r 、校验
r 使用了，但是没打开 。使用方法：基于承诺值计算一个响应值z
基于承诺值进行计算，打开计算值，使用了r。
5.5.Pedersen承诺
6多项式承诺
论文：Constant-Size Commitments to Polynomials and Their Applications
6.1 困难假设
6.2 多项式承诺定义
多项式承诺方案包括：Setup, Commit, Open, VerifyPoly, CreateWitness, VerifyEval.
CreateWitness 打开100 个随机点
VerifyEval 校验100 个随机点
如果校验出这些随机点都正确的，则整个多项式错误概率可忽略，则接受，否则拒绝。这里引入概率与统计。
6.3 多项式承诺性质
7.KZG承诺
公式推导过程如下：
7.1KZG承诺批量验证A
（t个多项式，打开一个随机点）
以下是KZG承诺在同一个横坐标 上的批量验证。
公式推导过程如下：
7.2KZG承诺批量验证B
（t个多项式，多个打开点）
以下是KZG承诺在不同横坐标z1,z2上的批量验证。
公式推导过程如下：
8.Dan Boneh承诺
8.1Dan Boneh承诺批量验证A
论文：Efficient polynomial commitment schemes for multiple points and polynomials
Dan Boneh承诺多点批量验证的计算复杂度低于KZG承诺。Open与VerifyPoly和KZG承诺相同，省略。
Dan Boneh 承诺使用条件③。因此，如果条件③成立，则条件①成立。
举例：
公式推导过程如下：
反之，如果双线性验证成功，则表明对于索引z∈S，r(z)=f(z)
承诺了所有值，随机打开了一些值是正确的，则所有值都是正确的。
8.2Dan Boneh承诺批量验证B
优势与缺点：增加了证明长度，降低验证方的计算复杂度。
以下是方案计算复杂度、证明长度的对比
关于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