DKG分布式密鑰生成
Hacker?Dōjō Web3前沿技術(shù) workshop文稿
資助金額：150 USDT
Bounty鏈接：https://dorahacks.io/daobounty/182
Workshop回顧：https://b23.tv/K06BwHV
內(nèi)容貢獻(xiàn)者：Whiskoy，2022萬向黑客松冠軍，獨(dú)立投研開發(fā)者
本項(xiàng)目由Hacker Dōjō 資助，文章轉(zhuǎn)載請注明出處。
??學(xué)習(xí)量子計(jì)算、密碼學(xué)、Space等Web3前沿技術(shù)
??認(rèn)領(lǐng)Bounty，賺取賞金
??參與Hackathon，獲得資助
更多Web3精彩技術(shù)分享盡在Dōjō??
WeChat: @HackerDojo0
一、DKG是什么
DKG（分布式密鑰生成）提供了一種去中心化的方法，使各個(gè)參與方在不相互信任的情況下生成共享密鑰，以確保安全通信和多方參與的機(jī)密性。
DKG技術(shù)的關(guān)鍵思想是使用多方計(jì)算（secure multiparty computation）和秘鑰共享（secret sharing）的概念。
秘鑰共享?則將密鑰分割成多個(gè)部分，每個(gè)參與方只持有其中的一部分，需要達(dá)到一定閾值才能重構(gòu)出完整的密鑰；
多方計(jì)算?使得多個(gè)參與方能夠共同執(zhí)行計(jì)算任務(wù)，而不泄露私有輸入。
DKG技術(shù)在「需要多方參與」和「分布式信任」的領(lǐng)域得到應(yīng)用：
共識協(xié)議：DKG可用于生成共識協(xié)議所需的密鑰，確保在分布式環(huán)境中節(jié)點(diǎn)之間的通信和交互的安全性和可靠性。例如，Algorand 和 Dfinity 等區(qū)塊鏈項(xiàng)目使用 DKG 來生成節(jié)點(diǎn)的共識密鑰，從而實(shí)現(xiàn)拜占庭容錯(cuò)和安全的共識算法。
密鑰管理和安全多方計(jì)算：DKG技術(shù)可用于密鑰管理方案中，以生成和分發(fā)用于加密通信和身份驗(yàn)證的密鑰。此外，它也可以用于安全多方計(jì)算場景（Secure Multiparty Computation，SMC），使多個(gè)參與方能夠在不泄露私有數(shù)據(jù)的情況下進(jìn)行協(xié)作計(jì)算。
分布式存儲系統(tǒng)：DKG可用于分布式存儲系統(tǒng)中，用于生成和管理用于數(shù)據(jù)保護(hù)和訪問控制的密鑰，以確保數(shù)據(jù)的機(jī)密性和完整性。
門限密碼學(xué)：DKG是門限密碼學(xué)方案中的關(guān)鍵組成部分，例如門限簽名方案和門限加密方案。它用于在門限數(shù)量的參與方之間生成共享密鑰，從而實(shí)現(xiàn)高度安全和魯棒的密碼方案。
二、DKG密碼學(xué)細(xì)節(jié)
論文《Distributed Key Generation for the Internet》鏈接：https://cypherpunks.ca/~iang/pubs/DKG.pdf
指出，盡管許多論文都提出了同步通信模型和廣播信道，但工程實(shí)現(xiàn)方面的問題被忽略了，文章提出了異步的 DKG 工程解決方案。
2.1 DKG 技術(shù)通常包括以下步驟
參與方注冊：
每個(gè)參與方生成自己的私鑰和公鑰對。
參與方向系統(tǒng)注冊，并與其他參與方建立通信渠道（broadcast channel）。
公開承諾：
每個(gè)參與方公開其生成的公鑰的承諾，以確保后續(xù)步驟中公鑰不會被更改。
公開承諾是通過在公開的通道上發(fā)布承諾的哈希值實(shí)現(xiàn)的。
秘鑰共享：
每個(gè)參與方將其私鑰分割成多個(gè)部分，并與其他參與方共享。
秘密共享使用分散密鑰生成方案（secret sharing scheme）實(shí)現(xiàn)，常見的方案包括Shamir秘密共享方案和Pedersen秘密共享方案。
參與方之間的秘密共享確保沒有單個(gè)參與方可以獨(dú)立恢復(fù)出完整的私鑰。
共享驗(yàn)證：
參與方對其他參與方分享的私鑰部分進(jìn)行驗(yàn)證，以確保這些分享的私鑰部分滿足一致性和正確性。
共享驗(yàn)證可以通過使用零知識證明（zero-knowledge proofs）來實(shí)現(xiàn)，以驗(yàn)證其他參與方擁有有效的私鑰分享。
公鑰重構(gòu)：
參與方使用多方計(jì)算協(xié)議和其他參與方分享的私鑰部分來重構(gòu)出完整的共享密鑰。
多方計(jì)算協(xié)議確保在不泄露私鑰的情況下進(jìn)行計(jì)算，通常使用的協(xié)議包括安全多方計(jì)算協(xié)議（Secure Multiparty Computation, SMC）和安全多方計(jì)算電路（Secure Multiparty Computation Circuits）。
2.2?以 ElGamal 加密算法為例
密鑰生成：
首先，選擇一個(gè)大素?cái)?shù)p作為有限域的模數(shù)，并選擇一個(gè)原根g作為生成元。
然后，選擇一個(gè)私鑰x，其取值范圍在[1, p-1]之間，作為加密和解密的私鑰。
計(jì)算公鑰 y，其中 y ≡ g^x (mod p) ，知道私鑰 x 可以推出 公鑰 y 。
加密：
發(fā)送者隨機(jī)選擇一個(gè)加密密鑰 k（0 < k < p-1）。
發(fā)送者需要獲取接收者的公鑰（p, g, y）
計(jì)算出密文 c1 = g^k mod p 和 c2 = my^k mod p，其中m是明文。
發(fā)送者將密文（c1, c2）發(fā)送給接收者。
解密：
接收者收到密文（c1, c2）。
接收者使用私鑰x進(jìn)行解密計(jì)算。
a. 首先計(jì)算 c1^x mod p，即對密文c1進(jìn)行私鑰x的冪次運(yùn)算模p。這可以使用模冪運(yùn)算的算法（如快速冪算法）來高效計(jì)算。
b. 計(jì)算 c2/c1^x mod p，即將密文c2除以c1^x，并對結(jié)果取模p。這一步實(shí)際上是將密文c2還原為加密前的my^k，然后除以c1^x以消除加密過程中的影響。
c. 最終計(jì)算結(jié)果 m = c2/c1^x mod p 即為解密后的明文。
2.3 Proactive VSS
Proactive VSS（Proactive Verifiable Secret Sharing）是一種擴(kuò)展的可驗(yàn)證秘密共享方案，旨在解決傳統(tǒng)可驗(yàn)證秘密共享方案中的一些局限性。傳統(tǒng)的可驗(yàn)證秘密共享方案僅允許在特定時(shí)間點(diǎn)進(jìn)行秘密共享，而Proactive VSS引入了周期性的更新機(jī)制，以確保分享的秘密在長期使用中的安全性和可靠性。
在Proactive VSS中，參與方周期性地進(jìn)行更新，生成新的分享，并將舊的分享替換為新的分享。這種周期性的更新可以基于時(shí)間或者一些預(yù)定的事件觸發(fā)，例如預(yù)定的時(shí)間間隔或者特定的閾值。通過這種方式，Proactive VSS可以解決傳統(tǒng)VSS中的一些問題，如單個(gè)參與方的私鑰泄露、長期使用導(dǎo)致的安全性下降等。
Proactive VSS的優(yōu)點(diǎn)包括：
安全性增強(qiáng)：通過定期更新分享，即使某些參與方的私鑰泄露，也可以確保秘密的安全性。新的分享會取代舊的分享，從而消除已泄露私鑰的影響。
長期可靠性：Proactive VSS考慮了長期使用的情況，通過定期更新分享，保證分享的秘密在長期使用中保持可靠性。這對于需要長時(shí)間持續(xù)運(yùn)行的系統(tǒng)非常重要。
更好的可擴(kuò)展性：由于Proactive VSS可以適應(yīng)新的參與方加入或離開系統(tǒng)，因此具有更好的可擴(kuò)展性。它可以在系統(tǒng)的整個(gè)生命周期內(nèi)維護(hù)可驗(yàn)證秘密共享方案。
請注意，DKG 和Proactive VSS之間存在密切關(guān)聯(lián)，因?yàn)镻roactive VSS方案通常需要借助DKG來生成和更新分享。
2.4 Asynchronous VSS
Asynchronous VSS（異步可驗(yàn)證秘密共享）是一種可驗(yàn)證秘密共享方案，旨在解決在異步網(wǎng)絡(luò)環(huán)境下的可靠性和安全性問題。在異步網(wǎng)絡(luò)中，參與方之間的通信可能受到延遲、丟包和不可靠的因素的影響，傳統(tǒng)的同步可驗(yàn)證秘密共享方案可能無法適應(yīng)這種情況。
在異步VSS中，參與方不需要在嚴(yán)格的同步時(shí)鐘下操作，而是允許參與方在各自的節(jié)奏下執(zhí)行協(xié)議的各個(gè)步驟。這意味著參與方可以獨(dú)立地生成和發(fā)送消息，而無需等待其他參與方的響應(yīng)。
異步VSS 的關(guān)鍵挑戰(zhàn)是解決參與方之間的通信不可靠性所帶來的問題，包括消息的延遲、重排序和丟失。為了應(yīng)對這些問題，異步VSS方案通常使用了一些技術(shù)和機(jī)制，例如：
容錯(cuò)性：異步VSS方案需要具備容錯(cuò)機(jī)制，以處理消息的延遲、重復(fù)和丟失。常見的技術(shù)包括重傳機(jī)制、超時(shí)處理和錯(cuò)誤糾正碼。
狀態(tài)管理：由于參與方的操作是異步的，異步VSS方案需要有效地管理和維護(hù)參與方的狀態(tài)信息。這可以通過記錄參與方的狀態(tài)和執(zhí)行順序來實(shí)現(xiàn)。
一致性協(xié)議：為了在異步環(huán)境中達(dá)成一致，異步VSS方案通常依賴于一致性協(xié)議，例如拜占庭容錯(cuò)協(xié)議和分布式共識算法。
請注意，DKG 和異步VSS是兩個(gè)相關(guān)但不完全相同的概念。DKG是一種在分布式環(huán)境中生成密鑰的技術(shù)，而異步VSS專注于在異步網(wǎng)絡(luò)中共享秘密的可驗(yàn)證方案。兩者可以結(jié)合使用，以實(shí)現(xiàn)安全的分布式密鑰生成和共享。
三、DKG在區(qū)塊鏈的應(yīng)用
3.1 Algorand
Algorand使用了一個(gè)基于密鑰生成的拜占庭多數(shù)共識（BAV）算法。
參與者使用DKG生成密鑰對，并將公鑰發(fā)布到區(qū)塊鏈網(wǎng)絡(luò)中。然后，通過基于VRF（可驗(yàn)證的隨機(jī)函數(shù)）的隨機(jī)抽簽過程，選舉出一個(gè)權(quán)威節(jié)點(diǎn)集合，該集合由具有拜占庭容錯(cuò)性質(zhì)的節(jié)點(diǎn)組成。這些權(quán)威節(jié)點(diǎn)使用其私鑰參與區(qū)塊的生成和共識過程。通過使用DKG生成的共識密鑰，Algorand能夠確保共識過程的安全性和正確性，即使在存在惡意節(jié)點(diǎn)的情況下也能保證系統(tǒng)的可靠性。
3.2 Dfinity
Dfinity是一個(gè)去中心化的計(jì)算平臺，旨在構(gòu)建一個(gè)安全、可擴(kuò)展的區(qū)塊鏈網(wǎng)絡(luò)。
在Dfinity中，參與者使用DKG生成密鑰對，并將公鑰發(fā)布到網(wǎng)絡(luò)中。通過 Threshold Relay（門限共識）算法，選舉出一個(gè)權(quán)威節(jié)點(diǎn)集合，這些節(jié)點(diǎn)負(fù)責(zé)網(wǎng)絡(luò)的共識過程和驗(yàn)證區(qū)塊的有效性。這些權(quán)威節(jié)點(diǎn)使用其私鑰進(jìn)行簽名和驗(yàn)證，確保共識過程的安全性和正確性。使用DKG生成的共識密鑰，Dfinity能夠?qū)崿F(xiàn)高度去中心化的共識，同時(shí)具備拜占庭容錯(cuò)性質(zhì)，從而保證系統(tǒng)的安全性和可靠性。
3.3 SSV Network
SSV（Secret Shared Validator）全稱秘密共享驗(yàn)證器，SSV 的核心理念就是實(shí)現(xiàn)將驗(yàn)證者的私鑰進(jìn)行碎片后給到多個(gè)運(yùn)營商，相當(dāng)于多簽的邏輯，后續(xù) SSV 經(jīng)過不斷的討論和發(fā)展延伸升級為 DVT ，所以 SSV 是 DVT 的前身，SSV 也是一個(gè)技術(shù)名詞。
分布式密鑰生成（DKG）：operator 通過運(yùn)行 SSV 程序計(jì)算生成了一個(gè)共享的公私鑰集。每個(gè) operator 只擁有私鑰的單一部分，確保沒有一個(gè)運(yùn)營商可以影響或控制整個(gè)私鑰做出單方面的決定。
Shamir 的私鑰共享：私鑰共享指的是私鑰被拆分并被分配給不同參與者，如果需要重設(shè)私鑰，則需要需要組合預(yù)定義的份額閾值（例如，4 份中的 3 份）。
多方計(jì)算（MPC）：多方計(jì)算在分布式驗(yàn)證器技術(shù)中最為關(guān)鍵。多方計(jì)算 (MPC) 是一種加密工具，它允許多方使用他們的組合數(shù)據(jù)進(jìn)行計(jì)算，而無需透露他們的個(gè)人輸入，也就是不需要透露私鑰碎片。
共識達(dá)成：容錯(cuò)是通過閾值簽名方案 Beacon 節(jié)點(diǎn)間的共識算法達(dá)成的，ETH 驗(yàn)證器 與 Beacon 節(jié)點(diǎn)連接后，即可達(dá)成共識。
四、參考資料
“Distributed Key Generation, Key Derivation, and Threshold Cryptosystems”（1997）- 由Rosario Gennaro、Stanislaw Jarecki、Hugo Krawczyk和Tal Rabin撰寫的論文，介紹了DKG的基本概念和協(xié)議。
“Practical Threshold Signatures”（2002）- Adi Shamir的論文，詳細(xì)介紹了基于DKG的實(shí)用閾值簽名方案。
“Secure Distributed Key Generation for Discrete-Log Based Cryptosystems”（2003）- Ivan Damg?rd、Martin Geisler和Mikkel Kr?igaard的論文，討論了基于離散對數(shù)密碼體制的安全分布式密鑰生成方案。
“Robust Threshold DSS Signatures”（2003）- Ronald Cramer、Ivan Damg?rd和Berry Schoenmakers的論文，介紹了基于DKG的魯棒閾值DSS簽名方案。
“Efficient and Secure DKG Protocols for Threshold Cryptosystems”（2012）- Stefan Dziembowski、Kristián Gj?steen和Jesper Buus Nielsen的論文，探討了在實(shí)際應(yīng)用中高效且安全的DKG協(xié)議。
“Distributed Key Generation in the Wild”（2017）- Eleftherios Kokoris-Kogias等人的論文，研究了實(shí)際部署的分布式密鑰生成方案的性能和安全性。
Distributed Key Generation for the Internet。??https://cypherpunks.ca/~iang/pubs/DKG.pdf
??關(guān)于Dorahacks
DoraHacks 是一個(gè)全球范圍內(nèi)的極客運(yùn)動、全球黑客馬拉松組織者，也是全球最活躍的多鏈 Web3 開發(fā)者平臺之一。DoraHacks.io平臺使得世界各地的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ū)治理。
??關(guān)于Dorahacks DAO Bounty
Dorahacks DAO Bounty，為各類DAO和組織賦能！
Bounty計(jì)劃為DAO和組織提供了一個(gè)強(qiáng)大的平臺，通過社區(qū)激勵(lì)的形式，發(fā)布問題，協(xié)調(diào)任務(wù)，鼓勵(lì)用戶積極參與。
作為Bounty發(fā)布者，您可以根據(jù)我們的指南，發(fā)布社區(qū)相關(guān)的懸賞任務(wù)，解決問題的同時(shí)，提升社區(qū)活躍度：https://dorahacks.io/blog/guides/publish-a-bounty/
作為賞金獵人，您可以在DAO Bounty計(jì)劃中發(fā)揮自己的專長和能力，認(rèn)領(lǐng)懸賞，解決問題，獲得酬金：https://dorahacks.io/daobounty
??關(guān)于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技術(shù)開源知識社區(qū)。Dōjō會以直播/音頻/文字等形式定期組織分享session，內(nèi)容包括Web3領(lǐng)域前沿技術(shù)論文解讀、技術(shù)研討、工作坊、技術(shù)領(lǐng)袖研討會等。歡迎在Hacker Dōjo社區(qū)討論、學(xué)習(xí)和交流：Dora Dōjo - Dora Community Forum: https://community.dorahacks.io/c/buidl-dorahacks-io/6
目前Hacker Dōjō已分享的主題有：
密碼學(xué)：基礎(chǔ)專題（對稱加密算法、哈希函數(shù)、群和公鑰加密、數(shù)字簽名和KZG承諾、零知識證明、非對稱密碼算法、分布式密碼學(xué)）
密碼學(xué)：抗量子計(jì)算破解算法專題
Layer1架構(gòu)：Move系列、模塊化公鏈、共識協(xié)議Bullshark、內(nèi)存池協(xié)議Narwhal和共識協(xié)議Tusk、Aptos共識與交易并行執(zhí)行
Layer2架構(gòu)：zkSync研究、Layer2的支付通道擴(kuò)容方法、Polygon Hermez、Optimism、StarkWare技術(shù)與生態(tài)梳理
IRS系列：Interest Rate Swap and DeFi Platforms、Interest Rate Swap and Perpetual Swap、The Future Dencentralized Interest Rate Swap
量子計(jì)算系列：量子計(jì)算基礎(chǔ)、Qiskit專題（Qiskit入門、Deutsch-Jozsa算法、Bernstein-Vazirani算法、Simon算法、量子卷積神經(jīng)網(wǎng)絡(luò)、量子傅立葉變換、量子相位）、Pennylane專題（利用變分量子電路擬合傅里葉級數(shù)）、實(shí)驗(yàn)法觀測宏觀量子疊加態(tài)
AIGC系列：ChatGPT比較語料評測、GPT-4論文解讀
加入Dōjō的Hacker可以提出自己的學(xué)習(xí)期望，主動提案自己擅長的技術(shù)話題，由Dōjō組織分享。同時(shí)，Hacker Dōjō推出Web3前沿課題研究計(jì)劃，定期選題，由Hacker進(jìn)行研究和講解，并以bounty形式獎(jiǎng)勵(lì)研究貢獻(xiàn)者。歡迎各位Hacker認(rèn)領(lǐng)Bounty：https://dorahacks.io/zh/daobounty
聯(lián)系我們：
Telegram:?@DoraDojo0
WeChat:?@HackerDojo0
E-mail:?hackerdojo0@gmail.com
