Skip to main content

阈值签名方案（TSS）

1、背景​

当前，ECDSA 阈值签名主要有两种协议类型。第一种是 Lindell 17’ 论文[1]中提出的 2/2 签名方案，第二种是 GG18[2] 和 GG20[3] 代表的 t/n 签名方案。t/n 阈值签名协议相对复杂，在生成和签名阶段需要多轮通信，对于高流量的 web3 应用场景来说速度不够快。相比之下，Lindell 17’ 论文中的 2/2 签名方案签名效率更高，但如果一个密钥份额意外丢失，用户的资产将无法恢复。鉴于此，我们提出了一种 2/n 签名方案，作为对 Lindell 17’ 协议的改进，以平衡签名效率并满足 web3 应用场景的需求。

2、解决方案概述​

我们提出了一种基于 Feldman 的可验证秘密共享方案（Feldman's VSS）和 Lindell 17’ 协议的 ECDSA 2/n 签名方案。在生成私钥份额时，我们使用 Feldman's VSS 生成各自的私钥份额。在签名阶段，我们使用 Lindell 17’ 协议进行两方签名，以确保签名过程的效率。在密钥份额丢失或泄露的情况下，用户的资产仍然是安全的。此外，我们支持 BIP32 非硬化密钥派生，只需一次密钥生成即可支持多种加密货币。如果一方丢失或泄露了密钥份额，或者有新参与者加入，我们支持将密钥份额重置为一组新的私钥份额。

3、支持的功能​

该库实现了以下功能：

  1. 密钥生成：使用 Feldman's VSS 生成 {2,n} 密钥份额。在 ECDSA 签名的情况下，需要双方之间的额外密钥协商，以满足 Lindell 17’ 的两方签名规则。
  2. 密钥份额刷新：如果一方丢失或泄露了密钥份额，或者有新参与者加入，所有方重新生成现有共享密钥的新随机份额，并使旧份额作废。
  3. BIP32 密钥派生：各方均不知道完整的私钥。仅支持非硬化密钥派生。链码在密钥生成阶段由多方共同生成。
  4. 两方 ECDSA 签名：使用 Lindell 17’ 协议根据密钥生成规则执行两方签名。单独一方无法生成完整的签名。
  5. 两方 Ed25519 签名：EdDSA 和 Schnorr 的一种变体，双方共同计算完整签名。

4、加密工具​

BIP32​

BIP32（Bitcoin Improvement Proposal 32）是比特币和其他加密货币中创建分层确定性（HD）钱包的标准。它允许用户从单个种子生成无限数量的公钥和私钥对，从而更容易管理和保护加密货币资金。

  1. 主密钥生成：生成一个随机的 256 位种子，作为主私钥。使用椭圆曲线乘法从主私钥派生出相应的主公钥。
  2. 密钥派生：每个子密钥从其父密钥派生，使用硬化或非硬化派生方法。当父密钥希望创建一个无法用于派生其他子密钥的子密钥时，使用硬化派生，而非硬化派生允许从其他子密钥派生子密钥。

承诺方案​

承诺方案是允许一方在不透露值的情况下承诺一个值，并在稍后揭示该值的同时证明其未被更改的加密协议。承诺方案包括两个阶段：承诺和揭示，如下所示：

Commitment:C=commit(m,r)Commitment: C = commit(m, r) 其中：

  • m 是要承诺的值
  • r 是一个随机字符串
  • C 是承诺字符串

Opening:(m′,r′)=open(C)Opening: (m', r') = open(C) 其中：

  • m' 是揭示的值
  • r' 是揭示的随机字符串

ECDSA 签名​

ECDSA 签名是使用签名者的私钥为消息创建数字签名的过程。数字签名用于验证消息发送者的身份并确保其内容的完整性。ECDSA 签名方案允许从已签名的消息及签名中恢复公钥。

密钥生成
  1. 选择一个具有生成点 G 和阶 n 的椭圆曲线。
  2. 生成一个随机私钥 a，使得 1<a<n1 < a < n 。
  3. 计算公钥 A = a·G。
签名
  1. 哈希：使用加密哈希函数对消息 m 进行哈希处理，生成固定长度的消息摘要 H(m)。
  2. 随机数生成：生成一个介于 1 和曲线阶 n 之间的随机数 k。
  3. 点计算：签名者计算椭圆曲线上的点 R = k·G。
  4. 标量计算：签名者计算标量 s = (k-1 _ (H(m) + a _ r)) mod n，其中 r 是 R 的 x 坐标。
  5. 签名生成：签名者生成数字签名 (r, s)。

ECDSA_sign(msg,privKey)−−>(r,s)ECDSA\_{sign}(msg, privKey) --> (r, s)

ED25519 签名​

Ed25519[4] 是一种基于椭圆曲线密码学的公钥数字签名算法。Ed25519 使用一个扭曲的 Edwards 曲线和修改版的 Schnorr 签名方案。该算法相较于其他数字签名算法具有多种优势，包括对侧信道攻击的抵抗力、对定时攻击的免疫力以及仅 64 字节的紧凑签名大小。

密钥生成
  1. 生成一个随机的 256 位私钥 k。
  2. 计算 H(k)，其中 H 是 SHA-512 哈希函数。将摘要的低 32 字节存储在缓冲区中。
  3. 修剪缓冲区：清除最低的三位和最高位。设置第二高位。将结果缓冲区解释为小端整数 b。
  4. 计算公钥 A = b·G。
签名
  1. 哈希：再次计算 H(k)。将摘要的高 32 字节存储在前缀中。
  2. 随机数生成：签名者计算标量 r = H(prefix || H(m))，其中 m 是要签名的消息。
  3. 点计算：签名者计算 ED25519 曲线上的点 R = r·G。
  4. 标量计算：签名者计算标量 s = r + H(R || A || m) * b mod n。
  5. 签名生成：签名者生成数字签名 (R, s)。

Ed25519_sign(msg,privKey)−−>(R,s)Ed25519\_{sign}(msg, privKey) --> (R, s)

Feldman's VSS​

Feldman's 可验证秘密共享（VSS）是一种加密协议，允许一个分发者将一个秘密分发给一组参与者，只有在达到最低数量的参与者合作时才能重构该秘密。其包括四个步骤：

  1. 设置：选择一个大素数 p 和一个阶为 q 的子群生成元 g，其中 q 是 p-1 的素因子。设 x 为秘密值，计算 y = gx mod p。
  2. 份额分发：分发者随机选择一个度为 t-1 的多项式 f(x)，使得 f(0) = x，并将份额 (i, si) 发送给参与者，其中 si = f(i) mod p，i 从 1 到 n。分发者还计算相应的多项式 g(x) = f(x) + r(x) mod p，其中 r(x) 是一个度为 t-1 的随机多项式，并将承诺 (i, Ci) 发送给参与者，其中 Ci = gi mod p，i 从 1 到 n。
  3. 验证：每个参与者通过检查 ysi * g-i mod p = 1 验证其份额 si 的有效性，并通过检查 Ci = gi mod p 验证承诺的有效性。
  4. 重构：任何 t 或更多合格参与者的子集可以使用拉格朗日插值法重构秘密 x。

Paillier 加密​

Paillier 加密是一种公钥加密方案，允许在不解密的情况下对加密数据进行安全计算。Paillier 加密提供加性同态加密，这意味着两个加密消息的和可以通过其密文的乘积来计算。

c1∗c2=g(m1+m2)∗r(N2)modN2c1 * c2 = g^{(m1 + m2)} * r^{(N^2)} mod N^2

  1. 密钥生成：选择两个大素数 p 和 q，并计算 N = pq。选择一个与 N 互素的随机数 g，并计算 λ = lcm(p-1, q-1)，其中 lcm 是最小公倍数。公钥为 (N, g)，私钥为 λ。
  2. 加密：要加密明文消息 m，选择一个小于 N 的随机值 r，并计算密文 c 如下： c=gm∗rNmodN2c = g^m * r^N mod N^2
  3. 解密：要解密密文 c，计算明文消息 m 如下： m=L(cλmodN2)/L(gλmodN2)modNm = L(c^λ mod N^2) / L(g^λ mod N^2) mod N 其中 L(x)=(x−1)/NL(x) = (x-1) / N

Schnorr 证明​

Schnorr 非交互零知识（NIZK）证明[5] 是三次握手 Schnorr 识别方案的非交互变体。Schnorr NIZK 证明允许在不泄露其值的情况下证明离散对数的知识，其步骤如下：

  1. Alice 发布她的公钥 A = a·G，其中 a 是私钥，G 是生成元。
  2. Alice 选择一个随机数 v，计算 V = v·G，并将 V 发送给 Bob。
  3. Alice 计算挑战 c = H(G || V || A)。
  4. Alice 计算 r = v – a * c mod n，并将其发送给 Bob。
  5. Bob 验证 V = r·G + c·A。

5、阈值方案概述​

在描述了我们解决方案中使用的所有加密原语和工具后，我们将描述协议的详细信息。

ECDSA​

密钥份额根据 Feldman's VSS 方案生成，两方签名根据 Lindell 17’ 协议执行。在原始 Lindell 17’ 协议定义中，私钥 x = x1 * x2 不易扩展到 2/n 签名方案。因此，我们通过将私钥定义更改为 x = x1 + x2 进行了修改。修改的细节如下：

             原始定义                                修改定义
私钥        x = x1 * x2                              x = x1 + x2
公钥        X = x1 * x2 * G = x1 * X2 = x2 * X1      X = X1 + X2 = x1 * G + x2 * G
签名
            k = k1 * k2                              k = k1 * k2
            s = (h + r * x1 * x2) / (k1 * k2) mod q  s = (h + r * (x1 + x2)) / (k1 * k2) mod q

分布式密钥生成​

每个参与者生成一个 ECDSA 密钥份额以用于签名，步骤如下：

  1. n 个参与者分别使用基于 2/n 签名方案的 Feldman's VSS 协议生成各自的密钥份额，并输出 (ld, sharei, publicKey, chaincode)。
  2. 确定签名规则，指定哪两个参与者将共同参与签名。当两方签名时，一方作为 Alice，另一方作为 Bob。Alice 和 Bob 分别对各自的 sharei 进行拉格朗日插值计算，以获得 x1 和 x2。私钥为 x = x1 + x2。
  3. Alice 随机生成一个 Paillier 公私钥对，并使用 Paillier 公钥加密 x1。Alice 还通过零知识证明向 Bob 证明她知道 x1。Ex1 表示密文，Alice 将 Ex1 和 Paillier 公钥发送给 Bob。
  4. Alice 输出她的 Paillier 私钥和 (ld, sharei, publicKey, chaincode)。
  5. Bob 输出 Paillier 公钥和 (ld, sharei, publicKey, chaincode, Ex1)。

签名​

在获得要签名的消息后，Alice 和 Bob 使用 Lindell 17’ 协议共同生成签名，步骤如下：

  1. Alice 和 Bob 生成随机数 k1 和 k2，并共同学习 R = k1 _ k2 _ G。使用承诺和零知识证明确保学习过程的安全性。
  2. 给定 R = (rx, ry)，Alice 和 Bob 可以分别计算 r = rx mod q。
  3. Bob 在 Paillier 同态加密方案下计算消息 m 的部分签名：(m + r * (x1 + x2)) / k2 mod q，并将部分签名发送给 Alice。
  4. Alice 使用她的 Paillier 私钥加密部分签名，并计算完整签名：(m + r _ (x1 + x2)) / (k1 _ k2) mod q。然后，她使用公钥验证签名。如果签名有效，她输出签名；否则，签名失败。

Ed25519​

使用 Feldman's VSS 协议为每个参与者生成密钥份额。在获得要签名的消息 m 后，任意两个参与者可以共同生成签名，步骤如下：

  1. Alice 和 Bob 分别通过对各自的 sharei 进行拉格朗日插值计算 x1 和 x2。完整私钥 x = x1 + x2。
  2. Alice 和 Bob 分别生成随机数 r1 和 r2，并分别计算 R1 = r1·G，R2 = r2·G。然后 Alice 和 Bob 共同学习 R = R1 + R2。使用承诺和零知识证明确保学习过程的安全性。
  3. 每个参与者可以计算 h = sha512(R, pub, m)，其中 pub 是对应完整私钥 x 的公钥。
  4. Alice 和 Bob 分别计算各自的签名 si = ri + h * xi，并将签名结果发送给对方。
  5. 计算完整签名 s = s1 + s2，并使用公钥验证签名。

份额刷新​

如果一方的份额丢失或泄露，或者有新参与者加入，可以生成一组新的密钥份额。刷新过程仅需要之前生成的两个份额参与，过程类似于私钥生成过程，链码保持不变。

密钥派生​

派生规则类似于 BIP32，各方均不知道完整的私钥，只能进行非硬化派生。链码在密钥生成阶段由多方共同生成，在刷新阶段不变。

在密钥生成后，每个参与者都有自己的份额，所有份额是相关的并在同一曲线上。每个份额可以沿同一路径派生，获得一个子密钥份额，也在同一曲线上，生成一组新的密钥份额。

tss-bip32

6、总结​

基于 Lindell 17’ 协议，我们提出了对 ECDSA 安全多方计算的改进，将 2/2 签名扩展到 2/n 签名。使用 Feldman's VSS 方案生成私钥份额，并使用 Lindell 17’ 协议进行两方签名，平衡签名效率并满足实际业务需求。该库还支持 BIP32 密钥派生和私钥份额刷新，使开发者易于学习和使用。

7、参考文献​

[1] Lindell, Y. (2017). Fast Secure Two-Party ECDSA Signing. https://eprint.iacr.org/2017/552

[2] Gennaro, R. (2019). Fast Multiparty Threshold ECDSA with Fast Trustless Setup. https://eprint.iacr.org/2019/114

[3] Gennaro, R. (2020). One Round Threshold ECDSA with Identifiable Abort. https://eprint.iacr.org/2020/540

[4] Josefsson, S. (2017, January). RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA). https://www.rfc-editor.org/rfc/rfc8032

[5] Hao, F. (2017, September). RFC 8235: Schnorr Non-interactive Zero-Knowledge Proof. https://www.rfc-editor.org/rfc/rfc8235

[6] Lindell, Y. (2019). Unbound_Cryptocurrency_Wallet_Library_White_Paper