Hacker  Dōjō Web3前沿技术 workshop文稿

研究种类：密码学-数字签名与KZG承诺

资助金额：100 USDT

Bounty链接：https://dorahacks.io/zh/daobounty/140

Workshop回顾：https://b23.tv/s9ngLNw

内容贡献者：密码学专家 Lynndell

本项目由Hacker Dōjō 资助，文章转载请注明出处。

🔸学习量子计算、密码学、Space等Web3前沿技术

🔸认领Bounty，赚取赏金

🔸参与Hackathon，获得资助

更多Web3精彩技术分享尽在Dōjō👇

WeChat: @HackerDojo0

密码学专题一课程安排

第一课：对称加密 （DES、AES、五种加密模式）

第二课：哈希函数 （SHA2、SHA3、MiMC、Rescue、Poseidon）

第三课：群与公钥加密 （群，椭圆曲线群，Diffie-Hellman密钥交换，ElGamal加密）

第四课：数字签名 （BLS、Schnorr、EdDSA、ECDSA）

第五课：零知识证明 （Sigma零知识证明、Groth16、PLONK）

第四课：数字签名与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.1 KZG承诺批量验证A

（t个多项式，打开一个随机点）
以下是KZG承诺在同一个横坐标 上的批量验证。

公式推导过程如下：

7.2 KZG承诺批量验证B

（t个多项式，多个打开点）
以下是KZG承诺在不同横坐标z1,z2上的批量验证。

公式推导过程如下：

8.Dan Boneh承诺

8.1 Dan 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.2 Dan Boneh承诺批量验证B

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

以下是方案计算复杂度、证明长度的对比

关于Hacker Dōjō 

Hacker Dōjō 是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō 会以直播/音频/文字等形式定期组织分享session, 分享主题主要覆盖L1和L2的共识算法，架构，GitHub repo相关内容，包括不限于以下话题：Scroll / Polygon zkEVM、 Eigen的混合证明系统、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密码学(零知识证明、公钥加密、哈希函数、格密码) 、 分布式系统、 以太坊协议栈、 量子计算和量子信息、卫星通信系统和航天器系统设计等。

✨Bounty详情及认领进度详情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c

✨加入 Dōjō 中文社区微信联系：@HackerDojo0

有关DoraHacks

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

官网：https://dorahacks.io/