Blockchain and cryptography (区块链与密码学)学习笔记4:数字签名与KZG承诺

Hacker Dōjo Workshop:
研究种类:密码学,数字签名与KZG承诺
资助金额:100 usdt
Bounty链接:https://dorahacks.io/zh/daobounty/140
创作者:Lynndell
本项目由Hacker Dōjo资助,文章转载请联系
Telegram: @HackerDojo0
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)


image
验证:
image

双线性映射:计算复杂度很高;尽量少算;一次
其他群运算计算复杂度很低,可以多算。
image
Schwartz–Zippel 引理
P为有限域F上的多项式P=F(x1,…,xn),其阶为d。令S为有限域F的子集,从S中选择随机数r1,…,rn,则多项式等于零的概率可忽略,即
image
在单变量情况下,等价于多项式的阶为,则最多有个根。

使用随机数进行对签名进行线性组合,根据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,计算承诺:
image

挑战: 取横坐标为
image

**响应:image
则签名为(r, s)。

验证: 输入消息M,计算m:=Hash(M);校验r,s∈Fr,计算R’:=(s-1m)·G+(s-1r)·PK
取横坐标为
image
;校验r=r’。如果相等,则接受,否则拒绝。
公式推导过程如下:
image

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步:校验:校验
image
且检查root在以太坊合约上。
证明方需要证明其知道每个叶子节点的值
image
树高度为100
低效做法:
第1步:承诺阶段:发送Merkle root
第2步:打开阶段:发送所有叶子节点
第3步:校验阶段:校验
image
且检查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 个点,每次都正确,则伪造成功概率呈指数降低。验证方相信证明方知道了所有叶子节点。
image
Merkle证明
第1步:证明知道sk。拥有token
第2步:基于叶子节点和path计算merkle root
第3步:检测merkle root在以太坊上。

5.4 Sigma零知识证明中的承诺

image
承诺 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 个随机点
如果校验出这些随机点都正确的,则整个多项式错误概率可忽略,则接受,否则拒绝。这里引入概率与统计。
image

6.3 多项式承诺性质

image
image

7.KZG承诺



公式推导过程如下:
image

7.1KZG承诺批量验证A

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


image
公式推导过程如下:
image

7.2KZG承诺批量验证B

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



公式推导过程如下:
image

8.Dan Boneh承诺

8.1Dan Boneh承诺批量验证A

论文:Efficient polynomial commitment schemes for multiple points and polynomials
Dan Boneh承诺多点批量验证的计算复杂度低于KZG承诺。Open与VerifyPoly和KZG承诺相同,省略。


Dan Boneh 承诺使用条件③。因此,如果条件③成立,则条件①成立。
举例:
image

公式推导过程如下:
image
反之,如果双线性验证成功,则表明对于索引z∈S,r(z)=f(z)
承诺了所有值,随机打开了一些值是正确的,则所有值都是正确的。

8.2Dan Boneh承诺批量验证B

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


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


关于我们
: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:DoraHacks
:small_orange_diamond:转载文章:请保留Hacker Dōjo Workshop介绍并联系我们hackerdojo0@gmail.com。