Multiparty Threshold ECDSA (GG18)

论文对 DKG 的描述如图 3 所示。

GG18 DKG 包含 2 部分内容：

1. 各个参与者通过 Pedersen's DKG（Joint Feldman DKG）协议（图 3 中黄色下划线部分）得到 \(x_i\) ，它是完整私钥 \(x\) 的 Shamir 分片， \(g^{x_i}\) 公开给别人。需要通过零知识证明，参与者不泄露 \(x_i\) 的情况下证明他确实知道 \(x_i\) （图 3 中绿色下划线部分）。
   
2. 各个参与者生成一个 Paillier 公钥（图 3 中蓝色下划线部分）发送给别人（签名过程中 MtA 子协议会用到 Paillier 同态加密，在 DKG 过程中需要提前分发 Paillier 公钥）。需要通过零知识证明，参与者不泄露 Paillier 公钥所对应的私钥的情况下证明他确实知道 Paillier 的私钥。不过，GG18 中并没有要求这一点，只在图 3 中红色下划线处要求 Paillier 公钥 \(N_i\) 是一个 Square-free 整数（不包含平方因子的整数），也就是说 GG18 协议只要求 Paillier 公钥 \(N_i\) 不包含平方因子。比如，对于 \(N_i\) 有多个素因子的情况 \(N_i = p_1 p_2 p_3 \cdots p_n\) ，GG18 并不能检测这种情况。 GG18 没有严格地校验 Paillier 公钥 \(N_i\) 的合法性（即 \(N_i\) 必须是两个较大的安全素数的乘积），这导致了 GG18 出现了安全漏洞 CVE-2023-33241。 关于这个安全漏洞的细节可参考节 8.3。
   

上面过程涉及的零知识证明有：

1. 如何不泄露 \(x_i\) 情况下证明他确实知道公钥 \(g^{x_i}\) 背后的私钥 \(x_i\) 呢？可以采用 Schnorr’s protocol。
   
2. 如何不泄露 Paillier 私钥的情况下证明他确实知道 Paillier 公钥 \(N_i\) 背后的私钥（素数 \(p_i,q_i\) ）呢？需要证明 \(N_i\) 确实是两个安全素数 \(p_i,q_i\) 的乘积，且这两个安全素数确实满足 Paillier 私钥的要求，即 \(p_iq_i\) 和 \((p_i-1)(q_i-1)\) 互素，关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 4.3 节 Paillier-Blum Modulus ZK。为了更好的安全性，我们还要通过零知识证明协议证明 \(N_i\) 没有小的素因子，即 \(p_i,q_i\) 都是比较大的素数，关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 B.4 节 No Small Factor Proof。
   

注 1：GG18 签名过程中有个 MtA 子协议，它需要 Range Proof，GG18 中提到为了性能考虑可以省略 Range Proof，不过为了更好的安全论文中建议实现 Range Proof。有的 GG18 实现（如 Binance 的实现）包含了 Range Proof，而有的 GG18 实现（ZenGo 的实现）则没有包含 Range Proof。进一步的研究表明，没有 Range Proof 会导致私钥泄露，参考节 8.1.2。如果要包含 Range Proof，则 DKG 过程除图 3 描述的步骤外，还需要准备额外的一些参数，参考节 8.1.2。
注 2：零知识证明是必不可少，否则会导致完整私钥泄露，这里有个省略零知识证明造成私钥泄露的例子：https://www.fireblocks.com/blog/bitgo-wallet-zero-proof-vulnerability/

Alice/Bob/Carol 选择 \(k_i, \gamma_i\) ，例如：

k_1 = 30         # Alice 随机选择
k_2 = 41         # Bob 随机选择
k_3 = 25         # Carol 随机选择
γ_1 = 19         # Alice 随机选择
γ_2 = 8          # Bob 随机选择
γ_3 = 16         # Carol 随机选择

定义 \(k \triangleq \sum k_i = 30 + 41 + 25 = 96\) ，定义 \(\gamma \triangleq \sum \gamma_i = 19 + 8 + 16 = 43\)

每两个人都进行两次 MtA 协议（参考节 8.1），具体介绍如下。

Alice/Bob/Carol 公开 \(\delta_i\) ，这样，所有参与者都可以计算出 \(k \gamma=\sum \delta_i = 1746 + 835 + 1547 = 4128\) ， \(k \gamma\) 是求 \(r\) 所需要计算的东西，参考节 3.1 。

Alice/Bob/Carol 公开 \(g^\gamma_i\) ，这样可以求得 \(R\) ，从而求得 \(r\) 了，参考节 3.1 。

在第二次 MtA 协议后，Alice/Bob/Carol 各自计算出了 \(\sigma_i\) ，从而各自可以计算出 \(s_i \triangleq mk_i + r \sigma_i\) ，再公开（不是直接公开，还有一些防止别人做恶的手段，这里省略）给大家，这样大家就可以求得 \(s=s_1+s_2+s_3\) 了，参考节 3.2 。

2020 年，Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker 于在论文 Bandwidth-efficient Threshold EC-DSA 中提出了一种门限签名 ECDSA 算法，一般称为 CCLST。

CCLST 可以看作是 GG18 的变种，它和 GG18 的主要区别是：MtA 协议中使用的同态加密算法不一样，GG18 是使用 Paillier 同态加密算法，而 CCLST 是使用 CL Scheme 同态加密算法。 这样做的好处是： 使用 CL Scheme 同态加密算时，不再需要耗时的 Range Proof，因为 CL Scheme 的明文消息空间和椭圆曲线的 Order 是一样的。 注：使用 Paillier 同态加密时，之所以需要 Range Proof，就是由于明文消息空间（即 \(N\) ）和椭圆曲线的 Order（即 \(q\) ）可能不一样，详情参见节 8.1.1。

CL Scheme 是在论文 CL15 和 CLT18 中提出的同态加密算法。

前面图 4 仅仅是 MtA 协议的示意图，完整的 MtA 协议如图 5 所示。

图 5 和前面示意图 4 的一个明显不同是图 5 中加入了 Range Proof，下面介绍为什么需要它。

MtA 协议中使用了 Paillier 同态加密，Alice 和 Bob 的 Paillier 公钥在 Key Generation 阶段就已经传给了对方。Paillier 加密算法要求待加密的明文必须小于 Paillier 公钥 \(N\) （Paillier 解密算法最后有个 \(\bmod N\) 运算，这要求待加密的明文不能超过 \(N\) ）。MtA 协议中，Bob 会使用 Paillier 加密算法加密 \(ab + \beta'\) 后，发送给 Alice。Alice 解密后得到的值记为 \(\alpha'\) ，有 \(\alpha' = ab + \beta' \bmod N\) 。

如果 \(ab + \beta' < N\) ，那么 \(\bmod N\) 运算没有执行可以直接去掉，也就是说有 \(\alpha' = ab + \beta'\) ，从而 \(\alpha \triangleq \alpha' \bmod q = ab + \beta' \bmod q\) 。这时， \(\alpha\) 满足 MtA 的要求。

如果 \(ab + \beta' >= N\) ，那么 \(\bmod N\) 运算被执行了，从而 \(\alpha \triangleq \alpha' \bmod q = (ab + \beta' \bmod N) \bmod q\) 。这时， \(\alpha\) 并不满足 MtA 的要求。

也就是说： 为了使 MtA 协议成立， \(ab + \beta' < N\) 是必须满足的。

怎样才能保证 \(ab + \beta' < N\) 成立呢？GG 18 采用的办法是：让 \(a,b,\beta'\) 不能太大，而 \(N\) 不能太小。具体来说，在 Key Generation 阶段收到别人 Paillier 公钥 \(N\) 时，检查 \(N > q^8\) 是否满足，不满足报错；Alice 通过 Range Proofs 保证 \(a < q^3\) ，而 Bob 通过 Range Proof 保证 \(b < q^3, \beta' < q^7\) 。这个设置显然能保证 \(ab + \beta' < N\) 成立，因为 \(q^3 q^3 + q^7\) 肯定会小于 \(q^8\) 。这就是 MtA 协议中需要 Range Proof 的原因。

在区块链实践中， \(q\) 是 Secp256k1 的 order，它是 256 比特位长度；而 \(N\) 是 2048 比特位长度。

前面介绍了为什么使用 Paillier 同态加密的 MtA 协议中需要 Range Proof。那如何实现 Paillier 密文的 Range Proof 呢？也就是说 Prover 发给 Verifier 一个 Paillier 密文， Prover 在不泄露明文的情况下如何向 Verifier 证明这个 Paillier 密文对应的明文会属于某个整数范围中。

GG18 A.1 Range Proof 中给出了完整的 Range Proof 协议，这个协议并不是 Rosario Gennaro 和 Steven Goldfeder 原创的，而是来源于 Two-party generation of DSA signatures ，6.3 Proof \(\Pi\) 。论文 UC Non-Interactive, Proactive, Threshold ECDSA，1.2.6 Non-Interactive Zero-Knowledge 节对这个 Range Proof 进行了更加详细的描述。

这里不介绍 Range Proof 协议的细节。需要指出：在执行 Range Proof 协议时，Prover 需要准备好 Paillier 公钥 \(N\) ，发送给 Verifier；而 Verifier 需要准备好 3 个参数 \(\tilde{N}, h_1, h_2\) ，发送给 Prover。这些参数都需要在 Key Generation 过程中准备好，如果 GG18 实现中包含了 Range Proof，则在 DKG 过程（节 4.1.1）中需要增加 \(\tilde{N}, h_1, h_2\) 的创建和验证步骤（对于 \(\tilde{N}, h_1, h_2\) 创建和验证相关的实现源码可参考 dln_proof in Safeheron crypto-zkp-cpp 和 dln proof in Binance tss-lib）。

MtA 协议中省略 Range Proof 会造成完整私钥的泄露，相关攻击可参考论文：Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations, 2.2 Attack on absent range proofs（文中提到了 8 次签名能盗走私钥的方法）。

在 \((t,n)\) 门限方案中，已知任意 \(t\) 个 Shamir 分片，都可以恢复出完整私钥。

其基本原理上节已经介绍过。以 \((3,n)\) 为例，完整私钥 \(f(0) = \lambda_1 \cdot f(1) + \lambda_2 \cdot f(2) + \lambda_3 \cdot f(3)\) ，其中 \(f(1),f(2),f(3)\) 就是 3 个 Shamir 分片。而 \(\lambda_1,\lambda_2,\lambda_3\) 不是秘密值，仅由参与者的下标就可以计算出来。

MtA 协议是 GG18 中的一个重要子协议：

       Alice                                                                       Bob

在 Z_q 中随机生成 k_A
用 Alice 的公钥 N 加密 k_A，密文为 Enc(k_A)

                                     -------------Enc(k_A)------------->

                                                                   满足 β' < q^5 前提下随机选择 β'
                                                                   在密文 Enc(k_A) 上用 Paillier 同态加密得到密文 c = Enc(k_A x_B + β')
                                                                   记 β = -β'

                                     <---------Enc(k_A x_B + β')--------

Alice 用私钥解密 Enc(k_A x_B + β')，其明文记为 α

如果把 MtA 子协议看作是黑盒子，则这个黑盒子的两个输入和两个输出分别是：

k_A                 # 输入。Alice 随机产生，只有 Alice 知道
x_B                 # 输入。Bob 的私钥分片，只有 Bob 知道
α                   # 输出。Alice 的输出，只有 Alice 知道
β                   # 输出。Bob 的输出，只有 Bob 知道

MtA 协议要很小心地处理，因为协议的输入输出都是敏感数据： \(k_A,\alpha\) 只能让 Alice 知道， \(x_B,\beta\) 只能让 Bob 知道。CVE-2023-33241 是针对 MtA 协议进行的攻击，让 Alice 获得了 Bob 的秘密 \(x_B\) 。

CVE-2023-33241 有两个关键点：

1. 攻击关键点 1：MtA 协议中 Alice 使用更大的 \(k_A\) ，让 \(\beta'\) 不再起到 mask 的作用。也就是说 Alice 使用更大的 \(k_A\) 会导致 MtA 中 Bob 的秘密 \(x_B\) 被泄露（Alice 知道 \(x_B\) 后可以恢复出完整私钥）。
   
2. 攻击关键点 2：Alice 伪造 \(k_A\) 的 Range Proof。MtA 协议中 Alice 需要提供 \(k_A < q^3\) 的 Range Proof。但在实施攻击关键点 1 后，由于 \(k_A\) 变大了，所以无法正常提供 Range Proof，需要伪造。
   

下面介绍一下第 1 个攻击关键点。为什么 MtA 协议中 Alice 使用更大的 \(k_A\) 时，会导致 Bob 的 \(x_B\) 被泄露。

首先看一下，Alice 让 \(k_A\) 取正常值（较小值）时，Bob 通过随机的 \(\beta'\) 可以使 Alice 无法猜测出 \(x_B\) ： \[\begin{aligned} {\color{red}{k_A}} &= {\color{red}{\text{0x2381}}} \\ x_B &= \text{0x4193} \\ \beta'(\text{mask}) &= \text{0x4837813096} \\ {\color{red}{k_A}} \cdot x_B &= \text{0x9182413} \\ {\color{red}{k_A}} \cdot x_B + \beta' &= \text{0x48409954A9} \end{aligned}\]

而 如果 Alice 让 \(k_A\) 取较大值时，Bob 的 \(\beta'\) 将失去 mask 作用，导致 \(x_B\) 泄露（其实这里有个前提，即 \(\beta'\) 不能太大，如果 \(\beta'\) 比较大，那么 \(\beta'\) 将继续起到 mask 作用）： \[\begin{aligned} {\color{red}{k_A}} &= {\color{red}{\text{0x100000000000}}} \\ x_B &= {\color{blue}{\text{0x4193}}} \\ \beta'(\text{mask}) &= \text{0x4837813096} \\ {\color{red}{k_A}} \cdot x_B &= {\color{blue}{\text{0x4193}}}\text{00000000000} \\ {\color{red}{k_A}} \cdot x_B + \beta' &= \underbrace{{\color{blue}{\text{0x4193}}}}_{泄露了 x_B}\text{0}\underbrace{\text{4837813096}}_{\beta' 失去 mask 作用} \end{aligned}\]

关于第 2 个攻击关键点，即就是 Alice 如何伪造 \(k_A\) 的 Range Proof（参见 GG18 Section A.1）的细节可参考节 8.3.2.1。

下面以 \((2,n)\) 两方门限签名为例介绍一下攻击流程。假设两个参与者是 Alice 和 Bob，其中 Alice 为恶意攻击者。

1. 在 DKG 阶段，Alice 按下面方式构造一个非法的 Paillier 公钥： \(N=p_1p_2 \cdots p_{16}z\) 。其中 \(p_1,p_2,\cdots,p_{16}\) 是 Alice 随机选择的大小为 \(2^{16}\) 的小素数（即这些素数都是 16 个比特位长）；然后 Alice 随机选择一个大素数 \(z\) ，这个 \(z\) 不能太大，也不能太小，让 \(N\) 恰好可以满足对它的比特位长度要求即可（ \(N\) 是 2048 个比特位长）。
   
2. 假设 \(x_B\) 是 Bob 手头的私钥分片（即节 4.2.2.2 中的 Addtive Share \(w\) ），它是 256 比特位。Alice 和 Bob 每进行一次 MPC 签名，Alice 可以利用式子（后文会证明这个公式的正确性） \(x_B \bmod p_i = \frac{\alpha - (\alpha \bmod (N/p_i))}{N/p_i}\) 获得一个 \(x_B \bmod (N/p_i)\) ，其中 \(1\le i \le 16\) 。进行完 16 次签名后，Alice 就知道了 \[\begin{aligned} x_B & \bmod (N/p_1) \\ x_B & \bmod (N/p_2) \\ & \vdots \\ x_B & \bmod (N/p_{16}) \end{aligned}\] 然后利用中国剩余定理，可以计算出 \(x_B \bmod (p_1p_2\cdots p_{16})\) ，由于每个 \(p_i\) 都是 16 比特位，所以乘积 \(p_1p_2\cdots p_{16}\) 是 256 比特位，使用中国剩余定理可以计算出 256 比特位的 \(x_B\) 。
   

下面介绍一下 MPC 签名时，攻击者 Alice 获得值 \(x_B \bmod (N/p_i)\) 的细节。在 MPC 签名阶段，Alice 和 Bob 会利用 MtA 协议把积 \(k_A x_B\) 转换为两个数 \(\alpha\) 和 \(-\beta'\) 的和，也就是说 MtA 协议结束后有 \[k_Ax_B = \alpha + (- \beta')\] 其中 \(k_A\) 是 Alice 的秘密，而 \(x_B\) 是 Bob 的秘密（完整私钥的 Addtive Share）， \(\alpha\) 是 MtA 结束后 Alice 获得的秘密值， \(-\beta'\) 是 MtA 结束后 Bob 获得的秘密值。

下面回顾一下 MtA 协议：

       Alice                                                                       Bob

在 Z_q 中随机生成 k_A
用 Alice 的公钥 N 加密 k_A，密文为 Enc(k_A)

                                     -------------Enc(k_A)------------->

                                                                   满足 β' < q^5 前提下随机选择 β'
                                                                   在密文 Enc(k_A) 上用 Paillier 同态加密得到密文 c = Enc(k_A x_B + β')

                                     <---------Enc(k_A x_B + β')--------

Alice 用私钥解密 Enc(k_A x_B + β')，其明文记为 α

MtA 结束后 Alice 得到 \(\alpha = (k_A x_B + \beta') \bmod N\) 。 恶意攻击者 Alice 在进行攻击时，并不在 \(Z_q\) 中随机产生 \(k_A\) ，而是使用一个更大值 \(k_A = \frac{N}{p_i}\) ，这样 MtA 结束后 Alice 得到 \(\alpha=(\frac{N}{p_i} x_B + \beta') \bmod N\) 。

注：在 GG18 中要求 Alice 提供一个零知识范围证明（参见 GG18 论文 A.1 Range Proof），Alice 需要证明她随机产生的 \(k_A\) 满足 \(k_A < q^3\) ，也就是 Alice 要证明 \(\frac{N}{p_i} < q^3\) 。由于 \(N\) 是 2048 比特位，而 \(p_i\) 是 16 比特位， \(q\) 为 256 比特位，所以 \(\frac{N}{p_i}\) 约为 2032 比特位，它肯定会大于 \(q^3\) 。也就是说正常情况下 Alice 无法提供这个零知识范围证明。 CVE-2023-33241 漏洞发现者利用 \(N\) （它也是 Range Proof 的参数）含有小因子 \(p_i\) 的特点，提出了一种特殊的构造 Range Proof 的方式（参考节 8.3.2.1），可以骗过 Bob 对 Range Proof 的校验，这是 CVE-2023-33241 能顺利实施的关键。

下面介绍一下为什么 \[x_B \bmod p_i = \frac{\alpha - (\alpha \bmod (N/p_i))}{N/p_i}\] 会成立。 推导过程中利用了一个重要前提 \(\beta' < q^5\) ， 由于 \(q\) 是 256 比特位，显然 \(\beta'\) 的比特位不会超过 \(256 \times 5=1280\) 位，又由于 \(N\) 的比特位为 2048， \(p_i\) 的比特位为 16，所以一定有 \[\beta' < \frac{N}{p_i}\]

因为 \(\alpha = x_B \frac{N}{p_i} + \beta' \bmod N\) ，且 \(\frac{N}{p_i}\) 是 \(N\) 的因子，利用同余性质 \(a \equiv b{\pmod {cn}} \Rightarrow a \equiv b{\pmod {n}}\) ，所以 \(\alpha \bmod \frac{N}{p_i} = ( x_B \frac{N}{p_i} + \beta' ) \bmod \frac{N}{p_i} = 0 + \beta' \bmod \frac{N}{p_i}\) ，即有 \[\begin{aligned} \alpha \bmod \frac{N}{p_i} & = \underbrace{\beta'}_{< N/p_i} \bmod \frac{N}{p_i} \\ & = \beta' \end{aligned}\]

下面开始推导 \(x_B \bmod p_i = \frac{\alpha - (\alpha \bmod (N/p_i))}{N/p_i}\) ，从式子右边的分子开始推导 \[\begin{aligned} \alpha - (\alpha \bmod \frac{N}{p_i}) &= \alpha - \beta' \\ &= ((x_B \frac{N}{p_i} + \beta') \bmod N ) - \beta' \\ &= (x_B \frac{N}{p_i} \bmod N ) + (\beta' \bmod N) - \beta' \\ &= (x_B \frac{N}{p_i} \bmod N) + \beta' - \beta' \\ &=x_B \frac{N}{p_i} \bmod N \\ & \stackrel{?}{=} \frac{N}{p_i} (x_B \bmod p_i) \end{aligned}\] 所以有 \(x_B \bmod p_i = \frac{\alpha - (\alpha \bmod (N/p_i))}{N/p_i}\) 。不过上面推导中最后一步 \(x_B \frac{N}{p_i} \bmod N=\frac{N}{p_i} (x_B \bmod p_i)\) 为什么会成立呢？下面将证明这个等式。因为 \[x_B = \lfloor \frac{x_B}{p_i} \rfloor p_i + (x_B \bmod p_i)\] 对上式两边乘以 \(N/p_i\) ，有 \[x_B \frac{N}{p_i} = \lfloor \frac{x_B}{p_i} \rfloor p_i \frac{N}{p_i} +(x_B \bmod p_i) \frac{N}{p_i}\] 对上式两边取 \(\bmod N\) ，有 \[\begin{aligned} x_B \frac{N}{p_i} \bmod N &= 0 + \left( \underbrace{ \underbrace{(x_B \bmod p_i)}_{< p_i} \frac{N}{p_i}}_{< N} \bmod N \right) \\ &= (x_B \bmod p_i) \frac{N}{p_i} \end{aligned}\]

注：GG18 论文有两个版本（初始版本和 2021 年的修订版本，如表 1 所示），前面提到了攻击依赖于 \(\beta' < q^5\) ，这个前提只存在于 2021 的修订版本中，节 8.3.1 中也提到了当 \(\beta'\) 较大时，攻击是不能成功的。

根据攻击原理，我们可以得到下面的修复方案：

1. 参与者公布 Paillier 公钥 \(N_i\) 给其它参与者时，需要证明 \(N_i\) 是合法的 Paillier 公钥，也就是说 \(N_i\) 确实是两个安全素数 \(p_i,q_i\) 的乘积，且这两个安全素数确实满足 Paillier 私钥的要求（即 \(p_iq_i\) 和 \((p_i-1)(q_i-1)\) 互素），关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 4.3 节 Paillier-Blum Modulus ZK。
   
2. 使用零知识证明协议证明 \(N_i\) 没有小因子，即 \(p_i,q_i\) 都是比较大的素数，关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 B.4 节 No Small Factor Proof。
   

节 4.1.1 中也提到了这些修复方案。