密码学之 Ecdsa 签名、GG18、MPC 钱包(三)

本文讨论多个参与者如何共同完成 ECDSA 阈值组签名，主要讨论 2018 年 Rosario Gennaro 和 Steven Goldfeder 在论文 Fast Multiparty Threshold ECDSA with Fast Trustless Setup 中提出的方案，简称 GG18 方案。专为多方安全计算（MPC）钱包设计，支持分布式密钥生成和签名，广泛应用于区块链资产托管领域。

GG18 协议在某些条件下存在安全漏洞（下面会讲到），为什么还要讲这篇文章呢？这是因为它首次实现了无需可信初始化的快速 ECDSA 阈值组签名协议。这一创新突破了传统阈值签名方案对可信第三方的依赖，大大提升了协议的实用性和安全性，为分布式密钥管理提供了更可靠的解决方案，使阈值签名技术更贴合实际应用场景。后续的 GG20 协议就是在 GG18 协议的基础上进行优化和改进的，GG20 协议将签名过程的 MPC 协议从多轮减少到 7 轮，其密钥生成过程与 GG18 协议相同，可见 GG18 协议是 ECDSA 阈值组签名协议发展过程中的重要里程碑。

注意：GG18 协议在解决和修复安全漏洞之后，它仍然是一个安全的阈值组签名方案。在实现这个协议的时候，需要注意以下几点

• 审计和验证各个参与方的 Paillier 公钥的正确性，使用 ZK 即可。
• 协议细节中多处使用 ZK，从论文中看至少有 8 处需要 ZK 甚至可能更多。

1 协议算法原理

1.1 数字签名算法（DSA）

数字签名算法（DSA）由 Kravitz 于 1991 年提出，并于 1994 年被 NIST 采纳为数字签名标准（DSS）。 我们知道 ECDSA 是 DSA 的椭圆曲线变体，近年来非常流行，特别是在区块链技术中。

本文所讲的内容所使用的代数结构是一般乘法循环群，这些内容同样适用于椭圆曲线群。假设 $G$ 是一个大素数阶 $q$ 的乘法循环群，$g$ 是一个生成元，两个安全的哈希函数 $H:{0,1}^{*}\rightarrow Z_q$，$H':G\rightarrow Z_q$。

• KeyGen: 输入安全参数

  • 私钥 $x \in_R Z_q$，计算公钥 $y=g^x$。

• Sign: 输入一个消息 $M$

  • 计算 $m=H(M)$
  • 选择 $k \in_R Z_q$
  • 计算 $R=g^{k^{-1}} \in G, r=H'(R) \in Z_q$
  • 计算 $s=k(m+xr) \text{ mod }q$
  • 输出签名 $\sigma=(r,s)$

• Verfy: 输入 $\sigma,y,M$

  • 计算 $m=H(M)$
  • 计算 $R'=g^{ms^{-1}\text{ mod }q}y^{rs^{-1}\text{ mod }q} \in G$
  • 验证 $r\xlongequal{?} H'(R')$

1.2 FVSS 和 DKG 协议

可以验证的秘密分享方案 FVSS 和 DKG 是阈值组签名的基础，当然 FROST 协议也用到这两个协议，关键技术是多项式插值、以及承诺，详细请看 DKG 文章和 Frost 文章，这里不再详细叙述。

1.3 NM-E-commitment

NM-E-commitment 是一个具有不可延展性和模糊性的承诺方案，详细内容请看承诺文章。

1.4 Paillier 加法同态

• KeyGen：输入安全参数

  • 生成 $(N,p,q)$，其中 $N=pq$，$p,q$ 是两个长度相等的大素数。公钥是 $N$，私钥是 $<N,\phi(N)>,\phi(N)=(p-1)(q-1)$

• Enc：输入消息 $m\in Z_N$，公钥 $N$

  • 随机选择 $r \in_R Z_N^{*}$，计算密文 $c=(1+N)^mr^N\text{ mod }N^2$

• Dec：输入密文 $c$，私钥 $\phi(N)$

  • 计算 $m=\frac{(c^{\phi(N)}\text{ mod }N^2)-1}{N}\cdot\phi(N)^{-1}\text{ mod N}$

• 很容易验证密文形式具有加法同态性

1.5 MtA 协议

MtA 协议即 Multiplicative-to-Additive，假设我们有两方 Alice 和 Bob 分别持有两个秘密 $a,b\in Z_q$，我们可以将其视为秘密 $x=ab\text{ mod }q$ 的乘法份额。Alice 和 Bob 想要计算秘密 $x$ 的加法份额 $\alpha,\beta$，它们是随机值，使得 $\alpha+\beta=x=ab\text{ mod }q$， Alice 持有 $\alpha,a$ 份额， Bob 持有 $\beta,b$ 份额。

实现这个功能，方法很多。

• 基于 2选1-OT 实现，想了解 OT 的可以看这篇文章。有空的时候专门做一期使用二选一 OT 去做乘法的加法分享的文章。

• 基于乘法三元组实现，基于 Breaver 乘法三元组去做。

• 基于同态加密实现。GG18 使用的是 Paillier 同态加密去做的。

  • Alice 计算 $c_A=E_A(a)$ 并发送给 Bob。

  • Bob 选择一个随机数 $\beta'\inR Z{q^5}$，计算 $c_B=b*c_A+E_A(\beta')=E_A(ab+\beta')$，并将 $c_B$ 发送给 Alice。令 $\beta=-\beta'$。

  • Alice 对 $c_B$ 进行解密得 $\alpha=D_A(c_B)$。

  很明显 $ab=\alpha+\beta$。不过需要注意得是双方都要使用 ZK 来确保双方所拥有的秘密是符合要求的，也就是说 $a,b$ 都是满足一定范围的。

1.6 GG18

1.6.1 KeyGen 协议

GG18 通过加法秘密分享拆分私钥 $sk$ 和临时随机数 $k$，而非传统 Shamir 分享。在 $(t,n)$ 阈值下（t为阈值，即最小签名节点个数），私钥碎片分散在 $n$ 个参与方中，任何 $t$ 个节点可合作生成有效 DSA 签名，但少于 $t$ 个节点无法重构签名。

• 每个参与者 $P_i$ 选择随机数 $u_i \in_R Z_q$，计算 $(KGC_i,KGD_i)=Com(g^{u_i})$， 这里解释下，等号右边表示对括号里的内容进行承诺，$KGC_i$ 表示承诺值，$KGD_i$ 表示打开承诺所需要的值(一定包含被承诺值)。举个例子，假设承诺的计算使用安全的哈希函数去做，那么 $KGC_i=H(g^{u_i})$，$KGD_i=g^{u_i}$。参与者 $P_i$ 生成 Paillier 公钥 $E_i$，并把 $KGC_i,E_i$ 广播出去。

• $P_i$ 广播 $KGD_i$，通过承诺打开算法得到 $y_i=g^{u_i}$，$P_i$ 执行关于秘密 $u_i$ 的 $(t,n)$ Feldman-VSS 协议。所以组公钥为 $y=\Pi_iy_i$，组私钥为 $x=\sum_iu_i$，即 $y=g^x$。令 $x_i$ 为秘密 $x$ 的 (t,n)-Shamir 秘密分片，也就是参与者 $P_i$ 的签名私钥，相应的签名公钥为 $X_i=g^{x_i}$，如果对这部分不熟悉的请看 DKG文章。

• 令 $N_i=p_iq_i$ 表示与 $E_i$ 相关的 RSA 算法模，2.2 节会详细说明这个 $N_i$ 所满足的要求，才不会产生安全漏洞，需要使用 ZK 技术确保 $N_i$ 符合安全要求，这里也体现出该方案的复杂性。

1.6.2 签名生成

接下来讨论签名生成协议，假设签名的消息是 $M$，计算 $m=H(M)$。$S\subseteq[1,2,\cdots,n]$ 表示参与阈值组签名的参与者集合，论文中定义其大小为 $|S|=t+1$，这样就变成 $S$ 中 $t+1$ 个参与者可以恢复出组签名，事实上阈值是 $t$，任意 $t$ 个参与者都可以恢复组签名，我认为这里 $S$ 的大小定义为 $t$ 也是可以的，这样还能提高计算效率。猜测 $t+1$ 是出于业务上的考虑，在线的节点数多于 $t$，容错性更大吧，不至于在线节点少于 $t$ 发生的概率变大。接下来讨论都是在 $S$ 中进行。

$\lambda_i$ 表示 $S$ 中参与者 $Pi$ 的拉格朗日系数，那么根据拉格朗日插值算法，组私钥可以表示为 $x=\sum{i\in S}\lambda_ixi=\sum{i\in S}\omega_i$，其中 $\omega_i=\lambda_ix_i$，由于 $X_i=g^{x_i}$ 和 $\lambda_i$ 是公开可计算的，所以所有的参与者都能计算 $W_i=g^{\omega_i}=X_i^{\lambda_i}$。

• 第一步：注入随机性

  每个参与者选择两个随机数 $k_i,\gamma_i \in_R Z_q$，并计算承诺 $(C_i,D_i)=Com(g^{\gamma_i})$，广播 $Ci$。定义 $k=\sum{i\in S}ki, \gamma=\sum{i\in S}\gammai$。所以， $$ \begin{aligned} k\gamma=\sum{i,j\in S}k_i\gammaj\text{ mod }q\ kx=\sum{i,j\in S}k_i\omega_j\textsf{ mod }q \end{aligned} $$

• 第二步：MtA 协议

  $P_i,P_j$ 两两执行 MtA 协议，执行结果 $Pi$ 拥有 $\alpha{ij}$ ，$Pj$ 拥有 $\beta{ij}$，且满足 $k_i\gammaj=\alpha{ij}+\beta_{ij}$。下面用一个表格直观的展示数据分片，假设有 3 个参与方

  	$P_1$	$P_2$	$P_3$
  	$k_1\gamma_1$	$k_2\gamma_2$	$k_3\gamma_3$
  $k_1\gamma_2$	$\alpha_{12}$	$\beta_{12}$	$\boxed{\times}$
  $k_1\gamma_3$	$\alpha_{13}$	$\boxed{\times}$	$\beta_{13}$
  $k_2\gamma_1$	$\beta_{21}$	$\alpha_{21}$	$\boxed{\times}$
  $k_2\gamma_3$	$\boxed{\times}$	$\alpha_{23}$	$\beta_{23}$
  $k_3\gamma_1$	$\beta_{31}$	$\boxed{\times}$	$\alpha_{31}$
  $k_3\gamma_2$	$\boxed{\times}$	$\beta_{32}$	$\alpha_{32}$
  	$\delta_1$	$\delta_2$	$\delta_3$

  参与者 $P_i$ 各自计算 $$\delta_i=k_i\gammai+\sum{j\ne i}\alpha{ij}+\sum{j\ne i}\beta_{ji}$$

  容易验证 $k\gamma=\sum_{i\in S}\delta_i$

  对于 $kx$ ，采用与上面同样的操作得到 $k_i\omegai=\mu{ij}+\nu_{ij}$，$P_i$ 计算 $$\sigma_i=k_i\omegai+\sum{j\ne i}\mu{ij}+\sum{j\ne i}\nu_{ji}$$

  容易验证 $kx=\sum_{i\in S}\sigma_i$

• 第三步：组承诺计算预处理

  $P_i$ 广播各自的 $\deltai$，于是所有的参与者都能计算出 $k\gamma$ 的乘积，令 $\delta=\sum{i\in S}\delta_i=k\gamma$，并计算出 $\delta^{-1}$。

• 第四步：计算组承诺

  计算组承诺 $R$，$P_i$ 广播 $D_i$，通过承诺打开算法得 $\Gamma_i=g^{\gammai}$，参与者计算 $$R=[\Pi{i\in S}\Gammai]^{\delta^{-1}}=g^{(\sum{i\in S}\gamma_i)k^{-1}\gamma^{-1}}=g^{k^{-1}}$$ 计算 $r=H'(R)$

• 第五步：生成签名分片

  • $P_i$ 计算 $s_i=mk_i+r\sigmai$。容易验证 $$\sum{i\in S}si=m\sum{i\in S}ki+r\sum{i\in S}\sigma_i=k(m+rx)=s$$

  • 这里还需做 ZK，来证明

    • $P_i$ 知道 $s_i$，

    • 且满足关系 $g^{\sum_{i\in S}si}R=g^my^r$（$\sum{i\in S}s_i=km+rkx$），$y$ 是组公钥。

    • 参与者一起验证签名分片的有效性。

  • 组签名为 $(r,s)$。

  签名验证： 计算 $R'=g^{ms^{-1}}y^{rs^{-1}}$，$H'(R')\xlongequal{?}r$

2 与 FROST 比较

2.1 基础原理与设计目标

• Paillier：半同态加密，用在 MtA 协议中

• NM-E-Commitment：Non-Malleable Equivocable Commitments，具有不可延展性的模糊的承诺方案，详情请看这篇文章，主要讲解了各种形式的承诺方案，事实上一种基于陷门的承诺就是一个具有不可延展性的模糊的承诺方案。

• MtA：乘法转换为加法的两方安全计算协议

• FVSS：Feldman’s VSS，可验证的秘密分享

• ZKP：零知识证明

设计差异本质：GG18 以安全多方计算（MPC）为核心，通过 Paillier 操作保护私钥分片，整体协议比较复杂但是不难；FROST 以阈值 Schnorr 签名为核心，通过 DKG 和轮次优化提升效率，整体协议比较简洁没有 GG18 复杂。

2.2 安全性与漏洞分析

1. GG18 关键漏洞（BitForge, CVE-2023-33241）
   • 攻击原理：攻击者构造含小因子的 Paillier 模数 N，通过使用中国剩余定理，可以窃取对方的私钥分片。
   • 影响范围：所有未修复的 GG18/GG20 实现（如早期 Binance tss-lib）。
   • 修复方案：
   • 强制使用零知识证明（ZKP）验证 Paillier 模数安全性，证明模数 N 只包含两个大素数，证明 N 中没有小素数因子。

表：BitForge 漏洞与 FROST 安全性对比

2. FROST 安全优势
   • 链下密钥管理：私钥永不完整恢复，分片泄露不影响系统。
   • 审计追踪：可定位恶意节点（GG20 引入，GG18 缺失）

2.3 性能与效率对比

性能瓶颈：GG18 的 MtA 协议在高并发场景延迟显著，需要两两交互生成乘法碎片，且需要多处 ZK；FROST 通过签名聚合器（SA） 减少带宽消耗，节点可以独立的完成计算无需两两交互，无需太多 ZK。

2.4 应用生态与开源支持

场景适配建议

• 区块链托管：

  • GG20（修复漏洞）适合 ECDSA 链（如以太坊）。
  • FROST 优先用于 Schnorr 链（比特币 Taproot、Solana）。

• 轻量设备/高并发：FROST（低通信开销）更优。

• 动态成员管理：理论上 FROST、GG18 都支持阈值动态调整。

2.5 最终建议：

• 新项目：优先选择 FROST（效率与安全平衡）或 GG18/GG20（需审计 Paillier 参数）。

• 存量系统：升级 GG18 至 GG20 并集成 CGGMP21 的零知识证明。

• 长期演进：关注 FROST 与零知识证明（ZKP）的结合，提升隐私与抗量子能力。

3 优缺点

3.1 优点

• 安全性基础扎实

  基于 Paillier 同态加密和椭圆曲线密码学，理论安全性依赖于复合剩余类问题和离散对数问题的困难性，在标准密码学假设下可证明安全。

• 功能完整性

  完整支持阈值密钥生成和签名流程，能实现 “无可信第三方” 的分布式密钥管理，私钥始终以分片形式存在，避免单点泄露风险。

• 签名效率较优

  相比早期的阈值 ECDSA 方案（如 CGGTP 协议），GG18 减少了交互轮次和计算开销，签名阶段的通信复杂度较低，适合实际场景部署。

• 兼容性强

  生成的签名与标准 ECDSA 签名格式完全兼容，可直接用于现有依赖 ECDSA 的系统（如区块链、数字证书等），无需修改验证逻辑。

3.2 缺点

• 存在潜在漏洞

  曾被披露存在 0-day 漏洞，攻击者可通过构造特殊 Paillier 密钥，在签名阶段逐步解析其他参与方的私钥分片。虽可通过额外的零知识证明（如引入 CMP20/CGGMP21 的验证机制）修复，但增加了实现复杂度。

• 密钥生成阶段复杂

  密钥生成过程涉及多轮交互和大量密码学操作（如 Paillier 密钥对生成、零知识证明验证等），计算和通信成本较高，尤其在参与方数量较多时效率下降明显。

• 实现难度大

  协议细节复杂，涉及同态加密、椭圆曲线运算、零知识证明、NM-E-承诺等多个密码学组件的协同，实际实现中容易因细节处理不当引入安全漏洞。

4 总结

GG18 奠定了 MPC 钱包的工程基础，但其安全性与效率问题催生了 GG20 等演进协议。当前实践中，强制零知识证明和原子化签名是规避 BitForge 的关键，而离线预处理可显著提升性能。对于高安全场景，建议优先选择 GG20 或结合 Schnorr 签名的 FROST 协议。

该协议存在在多处优化和改进的可能

• 去掉 Paillier，使用 OT、 VOLE、 以及乘法三元组都可以去做 MtA 协议，但是秘密值的范围是否符合要求仍然需要 ZK 去做。
• 个人认为工程实现的时候，集合 $S$ 的大小设置为 $t$ 即可，没必要多出一个设置为 $t+1$。
• ZK 的设计存在优化的可能性