Hacker??Dōjō?Web3前沿技術(shù) workshop文稿

研究種類：密碼學(xué)-數(shù)字簽名與KZG承諾

資助金額：100 USDT

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

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

內(nèi)容貢獻(xiàn)者：密碼學(xué)專家?Lynndell

本項(xiàng)目由Hacker?Dōjō?資助，文章轉(zhuǎn)載請(qǐng)注明出處。

??學(xué)習(xí)量子計(jì)算、密碼學(xué)、Space等Web3前沿技術(shù)

??認(rèn)領(lǐng)Bounty，賺取賞金

??參與Hackathon，獲得資助

更多Web3精彩技術(shù)分享盡在Dōjō??

WeChat: @HackerDojo0

密碼學(xué)專題一課程安排

第一課：對(duì)稱加密?（DES、AES、五種加密模式）

第二課：哈希函數(shù)?（SHA2、SHA3、MiMC、Rescue、Poseidon）

第三課：群與公鑰加密?（群，橢圓曲線群，Diffie-Hellman密鑰交換，ElGamal加密）

第四課：數(shù)字簽名?（BLS、Schnorr、EdDSA、ECDSA）

第五課：零知識(shí)證明?（Sigma零知識(shí)證明、Groth16、PLONK）

第四課：數(shù)字簽名與KZG承諾

1.BLS簽名與聚合簽名

BLS?簽名僅1?個(gè)隨機(jī)因子，即私鑰。
BLS?簽名擴(kuò)展
令M’={M | r}
簽名：δ=H(M’)a
廣播：（M，δ，pk，r）
數(shù)據(jù)拼接：M‘←{M | r}
驗(yàn)證公式：e(δ, g) = e(H(M’),h)

雙線性映射：計(jì)算復(fù)雜度很高；盡量少算；一次
其他群運(yùn)算計(jì)算復(fù)雜度很低，可以多算。

Schwartz–Zippel?引理
P為有限域F上的多項(xiàng)式P=F(x1,…,xn)，其階為d。令S為有限域F的子集，從S中選擇隨機(jī)數(shù)r1,…,rn，則多項(xiàng)式等于零的概率可忽略，即

在單變量情況下，等價(jià)于多項(xiàng)式的階為，則最多有個(gè)根。

使用隨機(jī)數(shù)進(jìn)行對(duì)簽名進(jìn)行線性組合，根據(jù)Schwartz?–Zippel?引理，發(fā)生碰撞的概率可忽略。

2.Schnorr簽名

簽名：?消息為m，選擇隨機(jī)數(shù)r，計(jì)算承諾R=r·G?，

計(jì)算挑戰(zhàn)e:=hash(R, PK, m)

計(jì)算響應(yīng)s:=(r+e·x)mod q

簽名為（R，s）

驗(yàn)證：?重新計(jì)算挑戰(zhàn)e=hash(R, PK, m) ，然后校驗(yàn)sG==R+e·PK

3.EdDSA簽名算法

初始化：?橢圓曲線生成元為G，階為q
密鑰生成：?私鑰為x，公鑰為PK=x·G
簽名：?消息為m，計(jì)算隨機(jī)數(shù)r=hash(x,m)，計(jì)算承諾R=r·G ，

計(jì)算挑戰(zhàn)e:=hash(R,PK,m)

計(jì)算響應(yīng)s:=(r +e·x)modq

簽名為(R,s)

驗(yàn)證：?重新計(jì)算挑戰(zhàn)e:=hash(R,PK,m) ，然后校驗(yàn)sG==R+e·PK
與ECDSA最大的區(qū)別在于沒有使用隨機(jī)數(shù)，?這樣產(chǎn)生的簽名結(jié)果是確定性的，即每次對(duì)同一消息簽名結(jié)果相同。一般說來隨機(jī)數(shù)是安全措施中重要的一種方法，但是隨機(jī)數(shù)的產(chǎn)生也是安全隱患，著名的索尼公司產(chǎn)品PS3密鑰泄露事件，就是隨機(jī)數(shù)產(chǎn)生的問題導(dǎo)致的。

4.ECDSA原理

初始化：?橢圓曲線生成元為G，標(biāo)量域?yàn)镕r，基域?yàn)镕q。

密鑰生成：?輸入安全參數(shù)λ，輸出私鑰x∈Fr和公鑰PK，滿足離散對(duì)數(shù)關(guān)系PK=x·G

簽名：?輸入任意消息M，計(jì)算m:=Hash(M)mod|Fr|；

選擇隨機(jī)數(shù)k∈Fr，計(jì)算承諾：

挑戰(zhàn)：?取橫坐標(biāo)為

**響應(yīng)：

則簽名為(r, s)。

驗(yàn)證：?輸入消息M，計(jì)算m:=Hash(M)；校驗(yàn)r,s∈Fr，計(jì)算R’:=(s-1m)·G+(s-1r)·PK
取橫坐標(biāo)為

校驗(yàn)r=r’。如果相等，則接受，否則拒絕。

公式推導(dǎo)過程如下：

5.承諾

5.1 承諾概念

第1?步：承諾階段：選擇x?，計(jì)算?y=f(x)，發(fā)送函數(shù)值y
第2步：打開階段：發(fā)送原象x
第3步：校驗(yàn)階段：y=f(x)
第4步：多點(diǎn)打開
第5步：校驗(yàn)多點(diǎn)打開
對(duì)函數(shù)是有一定要求：

• 函數(shù)求逆具有NP困難?，需要暴力搜索，需要指數(shù)時(shí)間。

• 但是校驗(yàn)簡(jiǎn)單。

5.2 哈希承諾

第1步：承諾階段：廣播哈希值y
第2步：打開階段：廣播原象x
第3步：校驗(yàn)階段：驗(yàn)證一致性y==hash(x)

5.3 Merkle承諾與Merkle證明

第1步：承諾：發(fā)送Merkle root

第2步：打開：發(fā)送葉子節(jié)點(diǎn)x_i?和path_i

第3步：校驗(yàn)：校驗(yàn)

且檢查root在以太坊合約上。
證明方需要證明其知道每個(gè)葉子節(jié)點(diǎn)的值

樹高度為100
低效做法：
第1步：承諾階段：發(fā)送Merkle root
第2步：打開階段：發(fā)送所有葉子節(jié)點(diǎn)
第3步：校驗(yàn)階段：校驗(yàn)

且檢查root在以太坊合約上。

高效做法：
檢測(cè)n?個(gè)點(diǎn)即可。沒必要打開所有。即使知道所有值，也不必打開所有葉子。
打開了足夠多的點(diǎn)，校驗(yàn)足夠多的點(diǎn)。就沒必要打開整個(gè)多項(xiàng)式。
整個(gè)多項(xiàng)式的階2^25–2^30
整個(gè)多項(xiàng)式是對(duì)的，則等價(jià)于交易是對(duì)的。
For i=0,i++,i<=100 {
第1步：承諾階段：發(fā)送Merkle root
第2步：打開階段：發(fā)送葉子節(jié)點(diǎn)x_i和path_i
第3步：校驗(yàn)階段：校驗(yàn)，且檢查root在以太坊合約上。校驗(yàn)復(fù)雜度非常低。
}
每個(gè)葉子節(jié)點(diǎn)的值就是0或1
1/2^100
核心思想：從概率角度，不必打開每個(gè)葉子節(jié)點(diǎn)，打開1024?個(gè)點(diǎn)，每次都正確，則偽造成功概率呈指數(shù)降低。驗(yàn)證方相信證明方知道了所有葉子節(jié)點(diǎn)。

Merkle證明
第1步：證明知道sk。擁有token
第2步：基于葉子節(jié)點(diǎn)和path計(jì)算merkle root
第3步：檢測(cè)merkle root在以太坊上。

5.4 Sigma零知識(shí)證明中的承諾

承諾?A、挑戰(zhàn)、響應(yīng)r?、校驗(yàn)
r?使用了，但是沒打開?。使用方法：基于承諾值計(jì)算一個(gè)響應(yīng)值z(mì)
基于承諾值進(jìn)行計(jì)算，打開計(jì)算值，使用了r。

5.5.Pedersen承諾

6多項(xiàng)式承諾

論文：Constant-Size Commitments to Polynomials and Their?Applications

6.1 困難假設(shè)

6.2 多項(xiàng)式承諾定義

多項(xiàng)式承諾方案包括：Setup, Commit, Open, VerifyPoly, CreateWitness, VerifyEval.
CreateWitness?打開100?個(gè)隨機(jī)點(diǎn)
VerifyEval?校驗(yàn)100?個(gè)隨機(jī)點(diǎn)
如果校驗(yàn)出這些隨機(jī)點(diǎn)都正確的，則整個(gè)多項(xiàng)式錯(cuò)誤概率可忽略，則接受，否則拒絕。這里引入概率與統(tǒng)計(jì)。

6.3 多項(xiàng)式承諾性質(zhì)

7.KZG承諾

公式推導(dǎo)過程如下：

7.1 KZG承諾批量驗(yàn)證A

（t個(gè)多項(xiàng)式，打開一個(gè)隨機(jī)點(diǎn)）
以下是KZG承諾在同一個(gè)橫坐標(biāo) 上的批量驗(yàn)證。

公式推導(dǎo)過程如下：

7.2 KZG承諾批量驗(yàn)證B

（t個(gè)多項(xiàng)式，多個(gè)打開點(diǎn)）
以下是KZG承諾在不同橫坐標(biāo)z1,z2上的批量驗(yàn)證。

公式推導(dǎo)過程如下：

8.Dan Boneh承諾

8.1 Dan Boneh承諾批量驗(yàn)證A

論文：Efficient polynomial commitment schemes for multiple points and polynomials
Dan Boneh承諾多點(diǎn)批量驗(yàn)證的計(jì)算復(fù)雜度低于KZG承諾。Open與VerifyPoly和KZG承諾相同，省略。

Dan Boneh?承諾使用條件③。因此，如果條件③成立，則條件①成立。
舉例：

公式推導(dǎo)過程如下：

反之，如果雙線性驗(yàn)證成功，則表明對(duì)于索引z∈S，r(z)=f(z)
承諾了所有值，隨機(jī)打開了一些值是正確的，則所有值都是正確的。

8.2 Dan Boneh承諾批量驗(yàn)證B

優(yōu)勢(shì)與缺點(diǎn)：增加了證明長度，降低驗(yàn)證方的計(jì)算復(fù)雜度。

以下是方案計(jì)算復(fù)雜度、證明長度的對(duì)比

關(guān)于Hacker Dōjō?

Hacker Dōjō?是由Hacker共建的加密、Web3前沿技術(shù)開源知識(shí)社區(qū)。Dōjō?會(huì)以直播/音頻/文字等形式定期組織分享session, 分享主題主要覆蓋L1和L2的共識(shí)算法，架構(gòu)，GitHub repo相關(guān)內(nèi)容，包括不限于以下話題：Scroll / Polygon zkEVM、 Eigen的混合證明系統(tǒng)、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密碼學(xué)(零知識(shí)證明、公鑰加密、哈希函數(shù)、格密碼) 、 分布式系統(tǒng)、 以太坊協(xié)議棧、 量子計(jì)算和量子信息、衛(wèi)星通信系統(tǒng)和航天器系統(tǒng)設(shè)計(jì)等。

?Bounty詳情及認(rèn)領(lǐng)進(jìn)度詳情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c

?加入?Dōjō?中文社區(qū)微信聯(lián)系：@HackerDojo0

有關(guān)DoraHacks

DoraHacks 是一個(gè)全球范圍內(nèi)的極客運(yùn)動(dòng)，全球黑客馬拉松組織者，也是全球最活躍的多鏈 Web3 開發(fā)者平臺(tái)之一。DoraHacks.io平臺(tái)使得世界各地的Hacker和開源開發(fā)者可以參與黑客馬拉松、Bounty、Grant、Grant DAO，以及公共物品質(zhì)押等加密原生協(xié)議和基礎(chǔ)設(shè)施進(jìn)行協(xié)作并獲得資助。到目前為止，DoraHacks 社區(qū)的 4000 多個(gè)項(xiàng)目已經(jīng)獲得了來自全球行業(yè)支持者超過 3000 萬美元的資助。大量開源社區(qū)、DAO 和 超過50個(gè)主要區(qū)塊鏈生態(tài)系統(tǒng)正在積極使用 Dora 的基礎(chǔ)設(shè)施（DoraHacks.io）進(jìn)行開源融資和社區(qū)治理。

官網(wǎng)：https://dorahacks.io/