Multiparty Threshold ECDSA (GG18)
Table of Contents
1. 简介
本文讨论多个参与者如何共同完成 ECDSA 门限签名,主要讨论 2018 年 Rosario Gennaro 和 Steven Goldfeder 在论文 Fast Multiparty Threshold ECDSA with Fast Trustless Setup 中提出的方案,简称 GG18 方案。
2. Generic DSA signature
GG18 作者提出了一个通用的签名方案(G-DSA),它统一了 DSA 签名和 ECDSA 签名的表示方法。
G-DSA 如图 1 所示。其中
Figure 1: Generic DSA
2.1. ECDSA 门限签名的难点
从前面介绍的标准 ECDSA 签名算法可知,签名中涉及了椭圆曲线上的乘法、加法、求逆等运算, 如何把这些运算改造为分布式方式是 ECDSA 门限签名的难点。
3. 主要思路
下面以
k_1, w_1 # 参与者 P_1 掌握,不泄露给别人 k_2, w_2 # 参与者 P_2 掌握,不泄露给别人 k_3, w_3 # 参与者 P_3 掌握,不泄露给别人
再想方设法去构造签名数据
3.1. 求签名中的 r
求
- 引入一个变量
,同样由 3 份(每份由参与者 自己随机生成)相加组成 ,每个参与者单独计算 ,这个是可以公开的,因为由 反推不出 ,这样,大家就可以算出 了。 - 那如何求解
呢?每个参与者 手里只有 ,且需要保证这两个值的机密,如何一起配合求得 呢?使用一种技巧可以实现,把 拆分为 3 份之和,即 ,每个参与者 计算 ,并公开 给其它参与者,这不会泄密 ,这样每个参与者都可以计算 了 ,其详情可参考节 4.2.2.1。
有了上面这两个信息,
3.2. 求签名中的 s
签名中的另一部分
求
4. 协议描述
下面仅描述 GG18 协议的“核心思想”,有细节省略。
4.1. Distributed Key Generation
假设系统中有 4 个参与者(Alice/Bob/Carol/Dave),其中任意 3 个人可以完成签名,而少于 3 个人无法签名。
下面介绍一个 Distributed Key Generation 流程:
1、每个参与者
u_1 = 120 u_2 = 10 u_3 = 30 u_4 = 80
整体的秘密(私钥)就是
2、每个参与者
f_a(1) = 113 # Alice 自己留着 f_a(2) = 112 # 发送给 Bob f_a(3) = 117 # 发送给 Carol f_a(4) = 128 # 发送给 Dave
类似地,Bob 选择一个 2 次多项式
f_b(1) = 17 # 发送给Alice f_b(2) = 36 # Bob 自己留着 f_b(3) = 67 # 发送给 Carol f_b(4) = 110 # 发送给 Dave
Carol 选择一个 2 次多项式
f_c(1) = 36 # 发送给 Alice f_c(2) = 56 # 发送给 Bob f_c(3) = 90 # Carol 自己留着 f_c(4) = 138 # 发送给 Dave
Dave 选择一个 2 次多项式
f_d(1) = 83 # 发送给 Alice f_d(2) = 88 # 发送给 Bob f_d(3) = 95 # 发送给 Carol f_d(4) = 104 # Dave 自己留着
然后,Alice/Bob/Carol/Dave 分别计算他们的
x_1 = f_a(1) + f_b(1) + f_c(1) + f_d(1) = 113+17+36+83 = 249 # Alice 计算并保存 x_2 = f_a(2) + f_b(2) + f_c(2) + f_d(2) = 112+36+56+88 = 292 # Bob 计算并保存 x_3 = f_a(3) + f_b(3) + f_c(3) + f_d(3) = 117+67+90+95 = 369 # Carol 计算并保存 x_4 = f_a(4) + f_b(4) + f_c(4) + f_d(4) = 128+110+138+104 = 480 # Dave 计算并保存
至此, 私钥 240 已经通过
Figure 2: Key Generation。这 4 个点
可以把上面过程看作是一种“不需要 Trusted Dealer 的 Shamir秘密分享”。
上面介绍了如何把私钥(即 240)分散保存到 4 个参与者中。但如何在不知道 240 这个私钥的情况下,各参与者得到公钥呢?其实很简单,每个参者与公开自己的
y = u_1 * G + u_2 * G + u_3 * G + u_4 * G = (u_1 + u_2 + u_3 + u_4) * G
上面描述的 DKG 过程是 1991 年 Pedersen 在论文 A Threshold Cryptosystem without a Trusted Party 中提出的,可称为 Pedersen's DKG(又可称为 Joint Feldman DKG,或者简称 JF DKG)。
不过,1999 年,Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin 在论文 Secure Distributed Key Generation for Discrete-Log Based Cryptosystems 中指出 Pedersen's DKG(Joint Feldman DKG)不是安全的,具体来说就是:如果 Pedersen's DKG(Joint Feldman DKG)过程中攻击者控制了 2 个参与者(共
GG18 中的 DKG 算法是在 Pedersen's DKG(Joint Feldman DKG)的基础上增加了零知识证明来确保各个参与者按照协议规定的方式运行。
4.1.1. DKG 总结
论文对 DKG 的描述如图 3 所示。
Figure 3: GG18 DKG(没有包含 MtA 子协议中 Range Proof 所需要的参数)
GG18 DKG 包含 2 部分内容:
- 各个参与者通过 Pedersen's DKG(Joint Feldman DKG)协议(图 3 中黄色下划线部分)得到
,它是完整私钥 的 Shamir 分片, 公开给别人。需要通过零知识证明,参与者不泄露 的情况下证明他确实知道 (图 3 中绿色下划线部分)。 - 各个参与者生成一个 Paillier 公钥(图 3 中蓝色下划线部分)发送给别人(签名过程中 MtA 子协议会用到 Paillier 同态加密,在 DKG 过程中需要提前分发 Paillier 公钥)。需要通过零知识证明,参与者不泄露 Paillier 公钥所对应的私钥的情况下证明他确实知道 Paillier 的私钥。不过,GG18 中并没有要求这一点,只在图 3 中红色下划线处要求 Paillier 公钥
是一个 Square-free 整数(不包含平方因子的整数),也就是说 GG18 协议只要求 Paillier 公钥 不包含平方因子。比如,对于 有多个素因子的情况 ,GG18 并不能检测这种情况。 GG18 没有严格地校验 Paillier 公钥 的合法性(即 必须是两个较大的安全素数的乘积),这导致了 GG18 出现了安全漏洞 CVE-2023-33241。 关于这个安全漏洞的细节可参考节 8.3。
上面过程涉及的零知识证明有:
- 如何不泄露
情况下证明他确实知道公钥 背后的私钥 呢?可以采用 Schnorr’s protocol。 - 如何不泄露 Paillier 私钥的情况下证明他确实知道 Paillier 公钥
背后的私钥(素数 )呢?需要证明 确实是两个安全素数 的乘积,且这两个安全素数确实满足 Paillier 私钥的要求,即 和 互素,关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 4.3 节 Paillier-Blum Modulus ZK。为了更好的安全性,我们还要通过零知识证明协议证明 没有小的素因子,即 都是比较大的素数,关于这个零知识证明协议可以参考 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/
4.2. Signature Generation
现在,Alice/Bob/Carol 这 3 个人想要进行签名,他们手头的“部分秘密”分别为 249,292,369。它们是整体秘密
w_1 = 747 w_2 = -876 w_3 = 369
4.2.1. Phase 1
Alice/Bob/Carol 选择
k_1 = 30 # Alice 随机选择 k_2 = 41 # Bob 随机选择 k_3 = 25 # Carol 随机选择 γ_1 = 19 # Alice 随机选择 γ_2 = 8 # Bob 随机选择 γ_3 = 16 # Carol 随机选择
定义
4.2.2. Phase 2
每两个人都进行两次 MtA 协议(参考节 8.1),具体介绍如下。
4.2.2.1. 第一次 MtA 协议(为求 kγ 做准备)
第一次 MtA 协议:
具体演示(下面的
k_1 * γ_2 = α_{12} + β_{12} => 30 * 8 = 100 + 140 k_1 * γ_3 = α_{13} + β_{13} => 30 * 16 = 120 + 360 k_2 * γ_1 = α_{21} + β_{21} => 41 * 19 = 80 + 699 k_2 * γ_3 = α_{23} + β_{23} => 41 * 16 = 117 + 539 k_3 * γ_1 = α_{31} + β_{31} => 25 * 19 = 218 + 257 k_3 * γ_2 = α_{32} + β_{32} => 25 * 8 = 30 + 170
定义
可以推出
Alice (即
4.2.2.2. 第二次 MtA 协议(为求 s_i 做准备)
第二次 MtA 协议:
具体演示(下面的
k_1 * w_2 = μ_{12} + ν_{12} => 30 * (-876) = -51000 + 24720 k_1 * w_3 = μ_{13} + ν_{13} => 30 * 369 = 4000 + 7070 k_2 * w_1 = μ_{21} + ν_{21} => 41 * 747 = 21452 + 9175 k_2 * w_3 = μ_{23} + ν_{23} => 41 * 369 = 3413 + 11716 k_3 * w_1 = μ_{31} + ν_{31} => 25 * 747 = 14737 + 3938 k_3 * w_2 = μ_{32} + ν_{32} => 25 * (-876) = -30000 + 8100
定义
可以推出
4.2.3. Phase 3(求 r)
Alice/Bob/Carol 公开
4.2.4. Phase 4(求 r)
Alice/Bob/Carol 公开
4.2.5. Phase 5(求 s)
在第二次 MtA 协议后,Alice/Bob/Carol 各自计算出了
5. GG18 VS. GG20
Rosario Gennaro 和 Steven Goldfeder 于 2020 年发表论文 One Round Threshold ECDSA with Identifiable Abort,被称为 GG20。它比 GG18 更优秀:
- Rounds 数量更少;GG18 的 sign 过程需要 9 rounds,而 GG20 的 sign 过程只需要 7 rounds(前 6 个 rounds 和待签名的 msg 无关,可提前进行;最后一个 round 才和 msg 相关)。
- 可识别恶意参与者。GG18 协议,如果有恶意参与者,那么协议会终止,但在某些场景下却不知道谁是恶意参与者。在 GG20 协议中,只要协议失败,就可识别出是谁的责任。
6. 开源实现
GG18, GG20 的开源实现可以参考:
- https://github.com/bnb-chain/tss-lib GG18 实现
- https://gitlab.com/thorchain/tss/tss-lib GG20 实现
- https://github.com/ZenGo-X/multi-party-ecdsa GG18 和 GG20 实现
7. 扩展阅读
7.1. Resharing(动态改变门限 t)
Distributed Key Generation 结束后,门限
具体做法是分两步:
- 从
变为 3 人 Additive Sharing(如 ),参考节 8.2 ; - 把 3 人的 Additive Sharing 当作是 DKG(参考节 4.1)过程中的随机数
(由于新门限的 值是 7,设置多出来的 4 个新参与者其 即可,也就是说 ),再接着运行 DKG 即可得到新门限设置 的 DKG 结果。
在论文 Attacking Threshold Wallets 的 3.1 节中介绍了这个过程。
注:上面的第 2 步也可以采用其它方案,比如让 3 个旧参与者
7.2. 其它 ECDSA 门限签名算法
除 GG18/GG20 外,还有其它一些 ECDSA 门限签名算法,可参考:A Survey of ECDSA Threshold Signing
7.2.1. CCLST
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,就是由于明文消息空间(即
7.3. 和 RFC 6979 不兼容
RFC 6979 定义了一种确定性
7.4. 对 BIP32 的支持
BIP32 有两种推导方式:Normal (Non-Hardened) Derivation 和 Hardened Derivation。
对于 Normal Derivation 来说,推导子地址时,不需要访问父私钥;而对于 Hardened Derivation 来说,推导子地址时,需要访问父私钥。由于在门限方案中完整私钥是不存在于某个单点的,这导致门限钱包支持 Hardened Derivation 要麻烦很多。这里仅介绍一下门限钱包如何支持 Normal Derivation。
门限钱包支持 BIP32 Normal Derivation 的思路如下:
- 在 Keygen 过程中,各个参与者要协商(后面会介绍具体步骤)出一个共同的 Chain Code,作为 Master Chain Code。
- 有了 Master Chain Code 后,又因为整体公钥是公开的,各个参与者可以本地计算出子私钥和父私钥的偏移量 Delta 及新的 Chain Code。具体方法是把 HMAC-SHA512(Key=Chain Code, Data=parent_pubkey||index) 的左 256 比特位作为 Delta,而右 256 比特位作为新的 Chain Code。
- 有了 Delta 后,各个参与者可以利用本地的父 Key Share 创建新的子 Key Share。这里是进行 Normal Derivation,并不需要 MPC 过程。具体方法如下:假设
门限方案 Keygen 结束后,3 个参与者本地保存的父 Key Share 和其它数据为:
# 3 个参与者的父 Key Share Party 1: keyshare private data: f(1) keyshare public data: [f(2) G, f(3) G] other data: Paillier related data, etc Party 2: keyshare private data: f(2) keyshare public data: [f(1) G, f(3) G] other data: Paillier related data, etc Party 3: keyshare private data: f(3) keyshare public data: [f(1) G, f(2) G] other data: Paillier related data, etc
当我们要推导一个子地址时,通过前面步骤已经计算出了 Delta,则各个参与者可以通过下面方式本地生成 Child Key Share:
# 3 个参与者的子 Key Share(Normal Derivation) Party 1: keyshare private data: f(1) + delta keyshare public data: [f(2) G + delta G, f(3) G + delta G] other data: Paillier related data, etc Party 2: private data: f(2) + delta public data: [f(1) G + delta G, f(3) G + delta G] other data: Paillier related data, etc Party 3: private data: f(3) + delta public data: [f(1) G + delta G, f(2) G + delta G] other data: Paillier related data, etc
参与者也并不需要保存这个 Child Key Share,只用保存最原始的 Master Chain Code,需要 Child Key Share 时,实时生成即可。
7.4.1. 生成 Master Chain Code
前面提到参与者要协商出一个共同的 Master Chain Code。这要如何做到呢?可以用下面简单的思路:
- 各个参与者本地生成一个 Chain Code i,然后把它的 Commitent 发送给其它参与者;
- 收到其它参与者发来的 Commitent 以后,才把自己的 Chain Code i 发送给其它参与者;
- 收到其它参与者发来的 Chain Code i,校验是否和之前收到的 Commitent 一致,如果一致则最终的 Chain Code 等于所有收到的 Chain Code i 及自己的那个 Chain Code 的异或。
注:为什么要收到所有其它人发来的 Commitent 后,才公布自己的 Chain Code i 呢?这是为了避免某个参与者根据其它人传来的 Chain Code i 来调整自己的 Chain Code i,从而这个参与者可以完全地决定最终的 Chain Code。
门限钱包支持 BIP32 Normal Derivation 的实现可参考:taurusgroup 库 multi-party-sig。
8. Appendix
8.1. Multiplicative-to-Additive(MtA)协议
假设 Alice 有个秘密值
图 4 是 MtA 协议的示意图,协议中用到了 Paillier 同态加密。
Figure 4: Multiplicative-to-Additive(MtA)协议的示意图
Alice 把
8.1.1. MtA 完整描述
前面图 4 仅仅是 MtA 协议的示意图,完整的 MtA 协议如图 5 所示。
Figure 5: Multiplicative-to-Additive(MtA)协议
图 5 和前面示意图 4 的一个明显不同是图 5 中加入了 Range Proof,下面介绍为什么需要它。
MtA 协议中使用了 Paillier 同态加密,Alice 和 Bob 的 Paillier 公钥在 Key Generation 阶段就已经传给了对方。Paillier 加密算法要求待加密的明文必须小于 Paillier 公钥
如果
如果
也就是说: 为了使 MtA 协议成立,
怎样才能保证
在区块链实践中,
8.1.2. Range Proof
前面介绍了为什么使用 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
这里不介绍 Range Proof 协议的细节。需要指出:在执行 Range Proof 协议时,Prover 需要准备好 Paillier 公钥
MtA 协议中省略 Range Proof 会造成完整私钥的泄露,相关攻击可参考论文:Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations, 2.2 Attack on absent range proofs(文中提到了 8 次签名能盗走私钥的方法)。
8.2. 转换 (t,n) 秘密为 Additive Sharing
Alice/Bob/Carol 手头分别有部分秘密
具体来说,
显然满足
为什么
而
8.2.1. 从多个 Shamir 分片恢复出完整私钥
在
其基本原理上节已经介绍过。以
8.3. CVE-2023-33241
在节 4.1.1 中提到,GG18 协议没有严格地校验 Paillier 公钥
参考:
Practical Key-Extraction Attacks in Leading MPC Wallets 4.2 6ix1een Attack
Small Leaks, Billions Of Dollars: Practical Cryptographic Exploits That Undermine Leading Crypto Wallets
https://www.fireblocks.com/blog/gg18-and-gg20-paillier-key-vulnerability-technical-report/
8.3.1. 攻击原理
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 协议要很小心地处理,因为协议的输入输出都是敏感数据:
CVE-2023-33241 有两个关键点:
- 攻击关键点 1:MtA 协议中 Alice 使用更大的
,让 不再起到 mask 的作用。也就是说 Alice 使用更大的 会导致 MtA 中 Bob 的秘密 被泄露(Alice 知道 后可以恢复出完整私钥)。 - 攻击关键点 2:Alice 伪造
的 Range Proof。MtA 协议中 Alice 需要提供 的 Range Proof。但在实施攻击关键点 1 后,由于 变大了,所以无法正常提供 Range Proof,需要伪造。
下面介绍一下第 1 个攻击关键点。为什么 MtA 协议中 Alice 使用更大的
首先看一下,Alice 让
而 如果 Alice 让
关于第 2 个攻击关键点,即就是 Alice 如何伪造
8.3.2. 攻击细节
下面以
- 在 DKG 阶段,Alice 按下面方式构造一个非法的 Paillier 公钥:
。其中 是 Alice 随机选择的大小为 的小素数(即这些素数都是 16 个比特位长);然后 Alice 随机选择一个大素数 ,这个 不能太大,也不能太小,让 恰好可以满足对它的比特位长度要求即可( 是 2048 个比特位长)。 - 假设
是 Bob 手头的私钥分片(即节 4.2.2.2 中的 Addtive Share ),它是 256 比特位。Alice 和 Bob 每进行一次 MPC 签名,Alice 可以利用式子(后文会证明这个公式的正确性) 获得一个 ,其中 。进行完 16 次签名后,Alice 就知道了 然后利用中国剩余定理,可以计算出 ,由于每个 都是 16 比特位,所以乘积 是 256 比特位,使用中国剩余定理可以计算出 256 比特位的 。
下面介绍一下 MPC 签名时,攻击者 Alice 获得值
下面回顾一下 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 得到
注:在 GG18 中要求 Alice 提供一个零知识范围证明(参见 GG18 论文 A.1 Range Proof),Alice 需要证明她随机产生的
下面介绍一下为什么
因为
下面开始推导
注:GG18 论文有两个版本(初始版本和 2021 年的修订版本,如表 1 所示),前面提到了攻击依赖于
GG18 版本 | 论文中要求 |
攻击 |
---|---|---|
初始版本 | 通过 16 次签名可计算出 |
|
2021 年修订版本 | Death by 1M Cuts. 经过 1 百万次签名尝试可能盗走 |
8.3.2.1. 伪造 Range Proof
GG18 中的 Range Proof 如图 6 所示。
Figure 6: GG18 Range Proof
当 Alice 使用 Range Proof 证明她的
Bob 会校验下面式子是否成立:
Alice 发送给 Bob 的
这带来了一个新问题。因为 Alice 发送给 Bob 的
上面推导中用到了结论
8.3.3. 修复方案
根据攻击原理,我们可以得到下面的修复方案:
- 参与者公布 Paillier 公钥
给其它参与者时,需要证明 是合法的 Paillier 公钥,也就是说 确实是两个安全素数 的乘积,且这两个安全素数确实满足 Paillier 私钥的要求(即 和 互素),关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 4.3 节 Paillier-Blum Modulus ZK。 - 使用零知识证明协议证明
没有小因子,即 都是比较大的素数,关于这个零知识证明协议可以参考 UC Non-Interactive, Proactive, Threshold ECDSA (CMP) 的 B.4 节 No Small Factor Proof。
节 4.1.1 中也提到了这些修复方案。
9. 参考
Fast Multiparty Threshold ECDSA with Fast Trustless Setup
A Threshold Cryptosystem without a Trusted Party
Secure Distributed Key Generation for Discrete-Log Based Cryptosystems
Distributed Key Generation and Its Applications, by Aniket Pundlik Kate
A Survey of ECDSA Threshold Signing
https://www.youtube.com/watch?v=PdfDZIwuZm0
https://www.youtube.com/watch?v=wtxH3PuMAgQ
https://www.fireblocks.com/blog/gg18-and-gg20-paillier-key-vulnerability-technical-report/