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 所示。其中 \(x\) 是私钥, \(k\) 随机产生, \(m\) 是待签名消息的哈希;而签名数据由 \(r,s\) 两部分组成。

multiparty_gdsa.gif

Figure 1: Generic DSA

2.1. ECDSA 门限签名的难点

从前面介绍的标准 ECDSA 签名算法可知,签名中涉及了椭圆曲线上的乘法、加法、求逆等运算, 如何把这些运算改造为分布式方式是 ECDSA 门限签名的难点。

3. 主要思路

下面以 \((3,n)\) 门限为例,介绍一下 3 个参与者共同完成 ECDSA 签名的思路。首先把 ECDSA 签名算法中的随机数 \(k\) 拆成由 3 份相加组成 \(k=k_1 + k_2 + k_3\) ,把私钥 \(x\) 拆成由 3 份相加组成 \(x = w_1 + w_2 + w_3\) (详情参考节 4.2)。每个参与者 \(P_i\) 都只知道自己的那部分数据:

k_1, w_1         # 参与者 P_1 掌握,不泄露给别人
k_2, w_2         # 参与者 P_2 掌握,不泄露给别人
k_3, w_3         # 参与者 P_3 掌握,不泄露给别人

再想方设法去构造签名数据 \(r,s\) 。

3.1. 求签名中的 r

只要计算出 \(R\) ,就容易求出 \(r\) 。下面介绍一下求 \(R = g^{k^{-1}}\) 的思路:
\[\begin{aligned} R &= g^{k^{-1}} \\ &= g^{\gamma k^{-1} \gamma^{-1}} \\ &= g^{\left(\sum \gamma_i \right) k^{-1} \gamma^{-1}} \\ &= \left( g^{(\sum \gamma_i)} \right)^{(k \gamma)^{-1}} \\ &= \left( \prod g^{\gamma_i} \right)^{(k \gamma)^{-1}} \end{aligned}\]

求 \(R\) 的思路是:

  1. 引入一个变量 \(\gamma\) ,同样由 3 份(每份由参与者 \(P_i\) 自己随机生成)相加组成 \(\gamma = \gamma_1 + \gamma_2 + \gamma_3\) ,每个参与者单独计算 \(g^{\gamma_i}\) ,这个是可以公开的,因为由 \(g^{\gamma_i}\) 反推不出 \(\gamma_i\) ,这样,大家就可以算出 \(\prod g^{\gamma_i}\) 了。
  2. 那如何求解 \(k \gamma = (\sum{k_i})(\sum{\gamma_i})\) 呢?每个参与者 \(P_i\) 手里只有 \(k_i, \gamma_i\) ,且需要保证这两个值的机密,如何一起配合求得 \((\sum{k_i})(\sum{\gamma_i})\) 呢?使用一种技巧可以实现,把 \(k \gamma\) 拆分为 3 份之和,即 \(k \gamma = \delta_1 + \delta_2 + \delta_3\) ,每个参与者 \(P_i\) 计算 \(\delta_i\) ,并公开 \(\delta_i\) 给其它参与者,这不会泄密 \(k_i, \gamma_i\) ,这样每个参与者都可以计算 \(k \gamma\) 了 ,其详情可参考节 4.2.2.1

有了上面这两个信息, \(R\) 就可以计算出来了,从而 \(r\) 也可以计算出来了。

3.2. 求签名中的 s

签名中的另一部分 \(s= k (m + x r)\) ,其中 \(m\) 是消息的哈希, \(x\) 是私钥, \(r\) 在上一节已经求得了。下面介绍一下求 \(s\) 的思路 :
\[\begin{aligned} s &= k (m + x r) \\ &= (k_1 + k_2 + k_3)m + kxr \\ &= (k_1 + k_2 + k_3)m + (\sigma_1 + \sigma_2 + \sigma_3) r \\ &= (m k_1 + r \sigma_1) + (m k_2 + r \sigma_2) + (m k_3 + r \sigma_3) \\ \end{aligned}\]

求 \(s\) 的主要思路是使用一种技巧把 \(kx\) 拆分为 3 份之和(至于怎么拆分可参考节 4.2.2.2,其实这和上一节求解 \(k\gamma\) 时,把 \(k\gamma\) 拆分为 3 份之和的原理是一样的),即 \(kx = \sigma_1 + \sigma_2 + \sigma_3\) ,每个参与者 \(P_i\) 单独计算自己的那个 \(s_i = mk_i + r \sigma_i\) ,并公开给其它参与者,这样每个参与者就都可以得到 \(s=s_1+s_2+s_3\) 了。

4. 协议描述

下面仅描述 GG18 协议的“主要逻辑”,有细节省略。

4.1. Distributed Key Generation

假设系统中有 4 个参与者(Alice/Bob/Carol/Dave),其中任意 3 个人可以完成签名,而少于 3 个人无法签名。

下面介绍一个 Distributed Key Generation 流程:
1、每个参与者 \(P_i\) 随机选择一个 \(u_i\) ,这就是每个参与者自己的秘密值,需要各参与者自己保存好。假设 Alice/Bob/Carol/Dave 分别选择了:

u_1 = 120
u_2 = 10
u_3 = 30
u_4 = 80

整体的秘密(私钥)就是 \(x = \sum u_i = u_1 + u_2 + u_3 + u_4 = 120 + 10 + 30 + 80 = 240\) ,每个参与者都不知道这个秘密值,下面将在不引入 Trusted Dealer 的情况下,把秘密值 \(x=240\) 以 \((3,4)\) 门限的方式分散给 Alice/Bob/Carol/Dave。

2、每个参与者 \(P_i\) 把自己的秘密值 \(u_i\) 通过 \((t, n)\) Feldman-VSS 分享给其它所有参与者。每个参与者把自己收到的所有分享全部加起来得到 \(x_i\) ,容易知道 \(x_i\) 是 \(x\) 的 \((t,n)\) 分享。比如,Alice 选择一个 2 次多项式 \(f_a(x) = 3 x^2 - 10x + u_1 = 3 x^2 - 10x + 120\) 把 120 分享给所有参与者,计算:

f_a(1) = 113       # Alice 自己留着
f_a(2) = 112       # 发送给 Bob
f_a(3) = 117       # 发送给 Carol
f_a(4) = 128       # 发送给 Dave

类似地,Bob 选择一个 2 次多项式 \(f_b(x) = 6 x^2 + x + u_2 = 6 x^2 + x + 10\) 把 10 分享给所有参与者,计算:

f_b(1) = 17        # 发送给Alice
f_b(2) = 36        # Bob 自己留着
f_b(3) = 67        # 发送给 Carol
f_b(4) = 110       # 发送给 Dave

Carol 选择一个 2 次多项式 \(f_c(x) = 7 x^2 - x + u_3 = 7 x^2 - x + 30\) 把 30 分享给所有参与者,计算:

f_c(1) = 36        # 发送给 Alice
f_c(2) = 56        # 发送给 Bob
f_c(3) = 90        # Carol 自己留着
f_c(4) = 138       # 发送给 Dave

Dave 选择一个 2 次多项式 \(f_d(x) = x^2 + 2x + u_4 = x^2 + 2x + 80\) 把 80 分享给所有参与者,计算:

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_i\) :

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 已经通过 \((3,4)\) 门限的方式分散到了 Alice/Bob/Carol/Dave 4 个参与者中,也就是说 \((1, 249), (2, 292), (3, 369), (4, 480)\) 这 4 个点中任意找 3 个点通过拉格朗日插值得到的多项式,它在 0 处的值就是秘密值 240, 如图 2 所示。

multiparty_gdsa_keygen.svg

Figure 2: Key Generation,这些点在一个 2 次多项式上(多项式次数为最小阈值减 1),这个曲线(2 次多项式)是由 4 个参与者各自的曲线(2 次多项式)相加而成

可以把上面过程认为是一种“不需要 Trusted Dealer 的 Shamir秘密分享”。

上面介绍了如何把私钥(即 240)分散保存到 4 个参与者中。但如何在不知道 240 这个私钥的情况下,各参与者得到公钥呢?其实很简单,每个参者与公开自己的 \(u_i * G\) (这并不会导致 \(u_i\) 泄露),公钥就是:

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。

不过,1999 年,Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin 在论文 Secure Distributed Key Generation for Discrete-Log Based Cryptosystems 中指出 Pedersen's DKG 不是安全的,具体来说就是:如果 Pedersen's DKG 过程中攻击者控制了 2 个参与者(共 \(n\) 个参与者),那攻击者可以使私钥的分布不再是均匀分布。后来在 2003 年,Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin 在论文 Secure Applications of Pedersen’s Distributed Key Generation Protocol 中指出,Pedersen's DKG 在某些场景下也足够安全。

GG18 中的 DKG 算法是在 Pedersen's DKG 的基础上增加了零知识证明来确保各个参与者按照协议规定的方式运行。

4.1.1. DKG 总结

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

gg18_dkg.gif

Figure 3: GG18 DKG

GG18 DKG 包含 2 部分内容:

  1. 各个参与者通过 Pedersen's DKG 协议(图 3 中黄色下划线部分)得到 \(x_i\) ,它是完整私钥 \(x\) 的 Shamir 分片, \(g^{x_i}\) 公开给别人。通过零知识证明,参与者不泄露 \(x_i\) 的情况下证明他确实知道 \(x_i\) (图 3 中绿色下划线部分)。
  2. 各个参与者生成一个 Paillier 公钥(图 3 中蓝色下划线部分)发送给别人(签名过程中 MtA 协议会用到 Paillier 同态加密,在 DKG 过程中需要提前分发 Paillier 公钥)。通过零知识证明,参与者不泄露 Paillier 公钥所对应的私钥的情况下证明他确实知道 Paillier 的私钥(图 3 中红色下划线部分)。

上面有两个零知识证明,分别如下:

  1. 如何不泄露 \(x_i\) 情况下证明他确实知道公钥 \(g^{x_i}\) 背后的私钥 \(x_i\) 呢?可以采用 Schnorr’s protocol。
  2. 如何不泄露 Paillier 私钥的情况下证明他确实知道 Paillier 公钥 \(N_i\) 背后的私钥(素数 \(p_i,q_i\) )呢?可以使用论文 Efficient Noninteractive Certification of RSA Moduli and Beyond 第 3.2 节介绍的协议。在另一篇论文 Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody 第 6.2.3 节中也对此进行了说明。

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

4.2. Signature Generation

现在,Alice/Bob/Carol 这 3 个人想要进行签名,他们手头的“部分秘密”分别为 249,292,369。它们是整体秘密 \(x=240\) 的 \((3, 4)\) Feldman-VSS 分享方案,我们先求得整体秘密(即 \(x=240\) )的 3 人 Additive Sharing 分享方案。即求 \(w_1, w_2, w_3\) ,且满足 \(w_1 + w_2 + w_3 = 240\) ,其细节可参考节 8.2,这里直接给出答案:

w_1 = 747
w_2 = -876
w_3 = 369

4.2.1. Phase 1

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\)

4.2.2. Phase 2

每两个人都进行两次 MtA 协议(参考节 8.1),具体介绍如下。

4.2.2.1. 第一次 MtA 协议(为求 kγ 做准备)

第一次 MtA 协议: \(P_i,P_j\) 对 \(k_i,\gamma_j\) 使用 MtA,把 \(P_i\) 得到的结果记为 \(\alpha_{ij}\) , \(P_j\) 得到的结果记为 \(\beta_{ij}\) ,也就是满足 \[k_i \gamma_j = \alpha_{ij} + \beta_{ij}\]

具体演示(下面的 \(\alpha_{ij}, \beta_{ij}\) 的值是满足要求情况下随意写的)如下:

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

定义 \(\delta_i \triangleq k_i \gamma_i + \sum_{j \neq i} \alpha_{ij} + \sum_{j \neq i} \beta_{ji}\) ,则:
\[\begin{aligned} \delta_1 &= k_1 \gamma_1 + \alpha_{12} + \alpha_{13} + \beta_{21} + \beta_{31} \\ &= 30 * 19 + 100 + 120 + 699 + 257 \\ &= 1746 \\ \delta_2 &= k_2 \gamma_2 + \alpha_{21} + \alpha_{23} + \beta_{12} + \beta_{32} \\ &= 41 * 8 + 80 + 117 + 140 + 170 \\ &= 835 \\ \delta_3 &= k_3 \gamma_3 + \alpha_{31} + \alpha_{32} + \beta_{13} + \beta_{23} \\ &= 25 * 16 + 218 + 30 + 360 + 539 \\ &= 1547 \\ \end{aligned}\]

可以推出 \(k \gamma = \left( \sum k_i \right) \cdot \left( \sum \gamma_i \right)= \sum \delta_i\) 。

Alice (即 \(P_1\) )公开 \(\delta_1\) 给 Bob 和 Carol;而 Bob (即 \(P_2\) )公开 \(\delta_2\) 给 Alice 和 Bob;Carol (即 \(P_3\) )公开 \(\delta_3\) 给 Alice 和 Bob。这样,Alice/Bob/Carol 在不公开自己拥有的 \(k_i, \gamma_i\) 的情况下,都可以计算出 \(k \gamma\) 了。

4.2.2.2. 第二次 MtA 协议(为求 s_i 做准备)

第二次 MtA 协议: \(P_i,P_j\) 对 \(k_i,w_j\) 使用 MtA,把 \(P_i\) 得到的结果记为 \(\mu_{ij}\) , \(P_j\) 得到的结果记为 \(\nu_{ij}\) ,也就是满足 \[k_i w_j = \mu_{ij} + \nu_{ij}\]

具体演示(下面的 \(\mu_{ij}, \nu_{ij}\) 的值是满足要求情况下随意写的)如下:

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

定义 \(\sigma_i \triangleq k_i w_i + \sum_{j \neq i} \mu_{ij} + \sum_{j \neq i} \nu_{ji}\) ,则:

\begin{aligned} \sigma_1 &= k_1 w_1 + \mu_{12} + \mu_{13} + \nu_{21} + \nu_{31} \\ &= 30 * 747 + (-51000) + 4000 + 9175 + 3938 \\ &= -11477 \\ \sigma_2 &= k_2 w_2 + \mu_{21} + \mu_{23} + \nu_{12} + \nu_{32} \\ &= 41 * (-876) + 21452 + 3413 + 24720 + 8100 \\ &= 21769 \\ \sigma_3 &= k_3 w_3 + \mu_{31} + \mu_{32} + \nu_{13} + \nu_{23} \\ &= 25 * 369 + 14737 + (-30000) + 7070 + 11716 \\ &= 12748 \\ \end{aligned}

可以推出 \(k x = \left( \sum k_i \right) \cdot \left( \sum w_i \right)= \sum \sigma_i\) 。

4.2.3. Phase 3(求 r)

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

4.2.4. Phase 4(求 r)

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

4.2.5. Phase 5(求 s)

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

5. GG18 VS. GG20

Rosario Gennaro 和 Steven Goldfeder 于 2020 年发表论文 One Round Threshold ECDSA with Identifiable Abort,被称为 GG20。它比 GG18 更优秀:

  1. Rounds 数量更少;GG18 的 sign 过程需要 9 rounds,而 GG20 的 sign 过程只需要 7 rounds(前 6 个 rounds 和待签名的 msg 无关,可提前进行;最后一个 round 才和 msg 相关)。关于 GG20 的 7 rounds 中每个 round 的细节可参考论文 UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
  2. 可识别恶意参与者。GG18 协议,如果有恶意参与者,那么协议会终止,但在某些场景下却不知道谁是恶意参与者。在 GG20 协议中,只要默认失败,就可识别出是谁的责任。

6. 开源实现

GG18, GG20 的开源实现可以参考:

  1. https://github.com/bnb-chain/tss-lib GG18 实现
  2. https://gitlab.com/thorchain/tss/tss-lib GG20 实现
  3. https://github.com/ZenGo-X/multi-party-ecdsa GG18 和 GG20 实现

7. 扩展阅读

7.1. Multi-Party Reshare(动态改变门限 t)

Distributed Key Generation 结束后,门限 \(t\) 就确定了,以后还可以改变吗?比如从 \((3,4)\) 改为新门限设置 \((5,7)\) ?答案是肯定的,不过在 GG18 论文中没有提到这一点。

具体做法是分两步:

  1. 从 \((3,4)\) 变为 3 人 Additive Sharing,参考节 8.2
  2. 把 3 人的 Additive Sharing 当作是 DKG(参考节 4.1)过程中的随机数 \(u_i\) (由于新门限的 \(n\) 值是 7,设置多出来的 4 个节点其 \(u_i=0\) 即可),再接着运行 DKG 即可得到新门限设置 \((5,7)\) 的 DKG 结果。

在论文 Attacking Threshold Wallets 的 3.1 节中介绍了这个过程。

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 中提出了一种门限签名 ECSA 算法,一种称为 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 是在论文 CL15CLT18 中提出的同态加密算法。

8. Appendix

8.1. Multiplicative-to-Additive(MtA)协议

假设 Alice 有个秘密值 \(a \in \mathbb{Z}_q\) ,而 Bob 有个秘密值 \(b \in \mathbb{Z}_q\) ,下面介绍一个协议可以在 Alice 不泄露 \(a\) ,Bob 不泄露 \(b\) 的情况下,Alice 和 Bob 分别得到另外一个秘密值 \(\alpha \in \mathbb{Z}_q,\beta \in \mathbb{Z}_q\) ,满足: \[ab = \alpha+\beta \bmod q\] 这个协议称为乘法到加法的转换协议(MtA)。

4 是 MtA 协议的示意图,协议中用到了 Paillier 同态加密。

multiparty_ecdsa_mta.svg

Figure 4: Multiplicative-to-Additive(MtA)协议的示意图

Alice 把 \(a\) 使用 Alice 公钥进行加密后,给 Bob;而 Bob 利用 Paillier 同态加密性质,把加密(当然也是 Alice 公钥加密)后的 \(ab-\beta\) 给 Alice。这样 Alice 使用私钥解密后得到的值记为 \(\alpha\) ,它们会满足 \(ab = \alpha+\beta \bmod q\) (注:这里不是很严谨,Paillier 解密后得到的值是 \(ab - \beta \bmod N\) ,而 MtA 协议要求的是对 \(q\) 取模,下一节会介绍当 \(ab - \beta < N\) 时,对 \(q\) 取模也一样成立)。

8.1.1. MtA 完整描述

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

multiparty_ecdsa_mta_formal.jpg

Figure 5: Multiplicative-to-Additive(MtA)协议

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 比特位长度。

MtA 协议中省略 Range Proof 可能造成完整私钥的泄露,相关攻击可参考论文:Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations

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 \(\Pi\) 。

这里不介绍 Range Proof 协议的细节。需要指出:在执行 Range Proof 协议时,需要 3 个参数 \(\tilde{N}, h_1, h_2\) ,它们需要在 Key Generation 过程中准备好。也就是说,包含了 Range Proof 的 GG18 实现,在 DKG 过程(节 4.1.1)中需要增加 \(\tilde{N}, h_1, h_2\) 的创建和验证步骤(对于 \(\tilde{N}, h_1, h_2\) 创建和验证相关的实现源码可参考 two_dln_proof in Safeheron crypto-zkp-cppdln proof in Binance tss-lib)。

8.2. 转换 (t,n) 秘密为 Additive Sharing

Alice/Bob/Carol 手头分别有部分秘密 \(x_1=249, x_2=292, x_3=369\) ,它们是整体秘密 \(x=240\) 的 \((3, 4)\) Feldman-VSS 分享方案,现在想把它变为整体秘密 \(x=240\) 的 3 人 additive sharing 分享方案。也就是 Alice/Bob/Carol 通过计算分别得到另外一个部分秘密 \(w_1,w_2,w_3\) ,要满足 \(w_1 + w_2 + w_3 = 240\) 。

具体来说, \(w_i\) 可以通过拉格朗日系数乘以 \(x_i\) 得到:

\[\begin{aligned} w_1 &= \lambda_1 \cdot x_1 = \frac{0-2}{1-2} \cdot \frac{0-3}{1-3} \cdot x_1 = 3 \cdot 249 = 747 \\ w_2 &= \lambda_2 \cdot x_2 = \frac{0-1}{2-1} \cdot \frac{0-3}{2-3} \cdot x_2 = -3 \cdot 292 = -876 \\ w_3 &= \lambda_3 \cdot x_3 = \frac{0-1}{3-1} \cdot \frac{0-2}{3-2} \cdot x_3 = 1 \cdot 369 = 369 \\ \end{aligned}\]

显然满足 \(w_1 + w_2 + w_3 = 747-876+369 = 240\) 。

为什么 \(w_1 + w_2 + w_3 = \lambda_1 \cdot x_1 + \lambda_2 \cdot x_2 + \lambda_3 \cdot x_3 = \lambda_1 \cdot f(1) + \lambda_2 \cdot f(2) + \lambda_3 \cdot f(3)\) 会恰好等于完整私钥 \(f(0)\) 呢?这是因为已知 3 个点的值 \(f(1)=249,f(2)=292,f(3)=369\) ,其拉格朗日插值多项式为:
\[L(x) = f(1) \cdot \frac{x-2}{1-2} \cdot \frac{x-3}{1-3} + f(2) \cdot \frac{x-1}{2-1} \cdot \frac{x-3}{2-3} + f(3) \cdot \frac{x-1}{3-1} \cdot \frac{x-2}{3-2} \]

而 \(f(0) = L(0) = \underbrace{f(1) \cdot \frac{0-2}{1-2} \cdot \frac{0-3}{1-3}}_{w_1} + \underbrace{f(2) \cdot \frac{0-1}{2-1} \cdot \frac{0-3}{2-3}}_{w_2} + \underbrace{f(3) \cdot \frac{0-1}{3-1} \cdot \frac{0-2}{3-2}}_{w_3}\)

8.3. 和 RFC 6979 不兼容

RFC 6979 定义了一种确定性 \(k\) 的方案,在这个方案中, \(k\) 由私钥和待签名消息来确定, \(k\) 不再是随机的。在 GG18 中,每次签名时使用的 \(k\) 都是随机的。

9. 参考

Author: cig01

Created: <2020-11-28 Sat>

Last updated: <2023-03-20 Mon>

Creator: Emacs 27.1 (Org mode 9.4)