DKG分布式密钥生成（Distrbuted Key Generation）

Dora Dōjo
1

Hacker Dōjō workshop文稿
资助金额：150 USDT
Bounty 链接：Hacker Dōjō|课题研究：分布式密钥生成(DKG) | Bounties | DoraHacks
内容贡献者：Whiskoy
2022万向黑客松冠军，独立投研开发者
赏金发布：https://bscscan.com/tx/0xf49d368de0ddc64778491f0fb3652fc89088e2a48bfbe30f70289be59c8e7a13
本项目由Hacker Dōjō 资助，文章转载请注明出处。
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com

一、DKG是什么

DKG（分布式密钥生成）提供了一种去中心化的方法，使各个参与方在不相互信任的情况下生成共享密钥，以确保安全通信和多方参与的机密性。

DKG技术的关键思想是使用多方计算（secure multiparty computation）和秘钥共享（secret sharing）的概念。

  • 秘钥共享 则将密钥分割成多个部分，每个参与方只持有其中的一部分，需要达到一定阈值才能重构出完整的密钥；
  • 多方计算 使得多个参与方能够共同执行计算任务，而不泄露私有输入。

DKG技术在「需要多方参与」和「分布式信任」的领域得到应用：

  1. 共识协议：DKG可用于生成共识协议所需的密钥，确保在分布式环境中节点之间的通信和交互的安全性和可靠性。例如，Algorand 和 Dfinity 等区块链项目使用 DKG 来生成节点的共识密钥，从而实现拜占庭容错和安全的共识算法。
  2. 密钥管理和安全多方计算：DKG技术可用于密钥管理方案中，以生成和分发用于加密通信和身份验证的密钥。此外，它也可以用于安全多方计算场景（Secure Multiparty Computation，SMC），使多个参与方能够在不泄露私有数据的情况下进行协作计算。
  3. 分布式存储系统：DKG可用于分布式存储系统中，用于生成和管理用于数据保护和访问控制的密钥，以确保数据的机密性和完整性。
  4. 门限密码学：DKG是门限密码学方案中的关键组成部分，例如门限签名方案和门限加密方案。它用于在门限数量的参与方之间生成共享密钥，从而实现高度安全和鲁棒的密码方案。

二、DKG密码学细节

论文《Distributed Key Generation for the Internet》指出，尽管许多论文都提出了同步通信模型和广播信道，但工程实现方面的问题被忽略了，文章提出了异步的 DKG 工程解决方案。

2.1 DKG 技术通常包括以下步骤

  1. 参与方注册：
    • 每个参与方生成自己的私钥和公钥对。
    • 参与方向系统注册，并与其他参与方建立通信渠道（broadcast channel）。
  2. 公开承诺：
    • 每个参与方公开其生成的公钥的承诺，以确保后续步骤中公钥不会被更改。
    • 公开承诺是通过在公开的通道上发布承诺的哈希值实现的。
  3. 秘钥共享：
    • 每个参与方将其私钥分割成多个部分，并与其他参与方共享。
    • 秘密共享使用分散密钥生成方案（secret sharing scheme）实现，常见的方案包括Shamir秘密共享方案和Pedersen秘密共享方案。
    • 参与方之间的秘密共享确保没有单个参与方可以独立恢复出完整的私钥。
  4. 共享验证：
    • 参与方对其他参与方分享的私钥部分进行验证，以确保这些分享的私钥部分满足一致性和正确性。
    • 共享验证可以通过使用零知识证明（zero-knowledge proofs）来实现，以验证其他参与方拥有有效的私钥分享。
  5. 公钥重构：
    • 参与方使用多方计算协议和其他参与方分享的私钥部分来重构出完整的共享密钥。
    • 多方计算协议确保在不泄露私钥的情况下进行计算，通常使用的协议包括安全多方计算协议（Secure Multiparty Computation, SMC）和安全多方计算电路（Secure Multiparty Computation Circuits）。

2.2 以 ElGamal 加密算法为例

  1. 密钥生成：
    • 首先，选择一个大素数p作为有限域的模数，并选择一个原根g作为生成元。
    • 然后，选择一个私钥x，其取值范围在[1, p-1]之间，作为加密和解密的私钥。
    • 计算公钥 y，其中 y ≡ g^x (mod p) ，知道私钥 x 可以推出 公钥 y 。
  2. 加密：
    • 发送者随机选择一个加密密钥 k（0 < k < p-1）。
    • 发送者需要获取接收者的公钥（p, g, y）
    • 计算出密文 c1 = g^k mod p 和 c2 = my^k mod p，其中m是明文。
    • 发送者将密文（c1, c2）发送给接收者。
  3. 解密：

    1. 接收者收到密文（c1, c2）。

    2. 接收者使用私钥x进行解密计算。

      a. 首先计算 c1^x mod p，即对密文c1进行私钥x的幂次运算模p。这可以使用模幂运算的算法（如快速幂算法）来高效计算。

      b. 计算 c2/c1^x mod p，即将密文c2除以c1^x，并对结果取模p。这一步实际上是将密文c2还原为加密前的my^k，然后除以c1^x以消除加密过程中的影响。

      c. 最终计算结果 m = c2/c1^x mod p 即为解密后的明文。

2.3 Proactive VSS

Proactive VSS（Proactive Verifiable Secret Sharing）是一种扩展的可验证秘密共享方案，旨在解决传统可验证秘密共享方案中的一些局限性。传统的可验证秘密共享方案仅允许在特定时间点进行秘密共享，而Proactive VSS引入了周期性的更新机制，以确保分享的秘密在长期使用中的安全性和可靠性。

在Proactive VSS中，参与方周期性地进行更新，生成新的分享，并将旧的分享替换为新的分享。这种周期性的更新可以基于时间或者一些预定的事件触发，例如预定的时间间隔或者特定的阈值。通过这种方式，Proactive VSS可以解决传统VSS中的一些问题，如单个参与方的私钥泄露、长期使用导致的安全性下降等。

Proactive VSS的优点包括：

  1. 安全性增强：通过定期更新分享，即使某些参与方的私钥泄露，也可以确保秘密的安全性。新的分享会取代旧的分享，从而消除已泄露私钥的影响。
  2. 长期可靠性：Proactive VSS考虑了长期使用的情况，通过定期更新分享，保证分享的秘密在长期使用中保持可靠性。这对于需要长时间持续运行的系统非常重要。
  3. 更好的可扩展性：由于Proactive VSS可以适应新的参与方加入或离开系统，因此具有更好的可扩展性。它可以在系统的整个生命周期内维护可验证秘密共享方案。

请注意，DKG 和Proactive VSS之间存在密切关联，因为Proactive VSS方案通常需要借助DKG来生成和更新分享。

2.4 Asynchronous VSS

Asynchronous VSS（异步可验证秘密共享）是一种可验证秘密共享方案，旨在解决在异步网络环境下的可靠性和安全性问题。在异步网络中，参与方之间的通信可能受到延迟、丢包和不可靠的因素的影响，传统的同步可验证秘密共享方案可能无法适应这种情况。

在异步VSS中，参与方不需要在严格的同步时钟下操作，而是允许参与方在各自的节奏下执行协议的各个步骤。这意味着参与方可以独立地生成和发送消息，而无需等待其他参与方的响应。

异步VSS 的关键挑战是解决参与方之间的通信不可靠性所带来的问题，包括消息的延迟、重排序和丢失。为了应对这些问题，异步VSS方案通常使用了一些技术和机制，例如：

  1. 容错性：异步VSS方案需要具备容错机制，以处理消息的延迟、重复和丢失。常见的技术包括重传机制、超时处理和错误纠正码。
  2. 状态管理：由于参与方的操作是异步的，异步VSS方案需要有效地管理和维护参与方的状态信息。这可以通过记录参与方的状态和执行顺序来实现。
  3. 一致性协议：为了在异步环境中达成一致，异步VSS方案通常依赖于一致性协议，例如拜占庭容错协议和分布式共识算法。

请注意，DKG 和异步VSS是两个相关但不完全相同的概念。DKG是一种在分布式环境中生成密钥的技术，而异步VSS专注于在异步网络中共享秘密的可验证方案。两者可以结合使用，以实现安全的分布式密钥生成和共享。

三、DKG在区块链的应用

3.1 Algorand

Algorand使用了一个基于密钥生成的拜占庭多数共识（BAV）算法。

参与者使用DKG生成密钥对，并将公钥发布到区块链网络中。然后，通过基于VRF（可验证的随机函数）的随机抽签过程，选举出一个权威节点集合，该集合由具有拜占庭容错性质的节点组成。这些权威节点使用其私钥参与区块的生成和共识过程。通过使用DKG生成的共识密钥，Algorand能够确保共识过程的安全性和正确性，即使在存在恶意节点的情况下也能保证系统的可靠性。

3.2 Dfinity

Dfinity是一个去中心化的计算平台，旨在构建一个安全、可扩展的区块链网络。

在Dfinity中，参与者使用DKG生成密钥对，并将公钥发布到网络中。通过 Threshold Relay（门限共识）算法，选举出一个权威节点集合，这些节点负责网络的共识过程和验证区块的有效性。这些权威节点使用其私钥进行签名和验证，确保共识过程的安全性和正确性。使用DKG生成的共识密钥，Dfinity能够实现高度去中心化的共识，同时具备拜占庭容错性质，从而保证系统的安全性和可靠性。

3.3 SSV Network

SSV（Secret Shared Validator）全称秘密共享验证器，SSV 的核心理念就是实现将验证者的私钥进行碎片后给到多个运营商，相当于多签的逻辑，后续 SSV 经过不断的讨论和发展延伸升级为 DVT ，所以 SSV 是 DVT 的前身，SSV 也是一个技术名词。

image
image1232×560 66.2 KB

  • **分布式密钥生成（DKG）：**operator 通过运行 SSV 程序计算生成了一个共享的公私钥集。每个 operator 只拥有私钥的单一部分，确保没有一个运营商可以影响或控制整个私钥做出单方面的决定。
  • Shamir 的私钥共享：私钥共享指的是私钥被拆分并被分配给不同参与者，如果需要重设私钥，则需要需要组合预定义的份额阈值（例如，4 份中的 3 份）。
  • 多方计算（MPC）：多方计算在分布式验证器技术中最为关键。多方计算 (MPC) 是一种加密工具，它允许多方使用他们的组合数据进行计算，而无需透露他们的个人输入，也就是不需要透露私钥碎片。
  • 共识达成：容错是通过阈值签名方案 Beacon 节点间的共识算法达成的，ETH 验证器 与 Beacon 节点连接后，即可达成共识。

四、参考资料

  1. “Distributed Key Generation, Key Derivation, and Threshold Cryptosystems”（1997）- 由Rosario Gennaro、Stanislaw Jarecki、Hugo Krawczyk和Tal Rabin撰写的论文，介绍了DKG的基本概念和协议。
  2. “Practical Threshold Signatures”（2002）- Adi Shamir的论文，详细介绍了基于DKG的实用阈值签名方案。
  3. “Secure Distributed Key Generation for Discrete-Log Based Cryptosystems”（2003）- Ivan Damgård、Martin Geisler和Mikkel Krøigaard的论文，讨论了基于离散对数密码体制的安全分布式密钥生成方案。
  4. “Robust Threshold DSS Signatures”（2003）- Ronald Cramer、Ivan Damgård和Berry Schoenmakers的论文，介绍了基于DKG的鲁棒阈值DSS签名方案。
  5. “Efficient and Secure DKG Protocols for Threshold Cryptosystems”（2012）- Stefan Dziembowski、Kristián Gjøsteen和Jesper Buus Nielsen的论文，探讨了在实际应用中高效且安全的DKG协议。
  6. “Distributed Key Generation in the Wild”（2017）- Eleftherios Kokoris-Kogias等人的论文，研究了实际部署的分布式密钥生成方案的性能和安全性。
  7. Distributed Key Generation for the Internet

关于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发布者，您可以根据我们的指南，发布社区相关的悬赏任务，解决问题的同时，提升社区活跃度：https://dorahacks.io/blog/guides/publish-a-bounty/
作为赏金猎人，您可以在DAO Bounty计划中发挥自己的专长和能力，认领悬赏，解决问题，获得酬金：https://dorahacks.io/daobounty

关于Hacker Dōjō
Hacker Dōjō是由Hacker共建的加密、Web3前沿技术开源知识社区。Dōjō会以直播/音频/文字等形式定期组织分享session，内容包括Web3领域前沿技术论文解读、技术研讨、工作坊、技术领袖研讨会等。欢迎在Hacker Dōjo社区讨论、学习和交流：https://community.dorahacks.io/c/buidl-dorahacks-io/6

目前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：https://dorahacks.io/zh/daobounty

联系我们：

Telegram: @DoraDojo0

WeChat: @HackerDojo0

E-mail: hackerdojo0@gmail.com