MPC-TSS lib

https://github.com/okx/threshold-lib/blob/main/docs/Threshold_Signature_Scheme.md

1、Background

Currently, there are two main types of protocols for ECDSA threshold signatures. The first type is the 2/2 signature proposed in the Lindell 17’ paper[1], and the second is the t/n signature represented by GG18[2] and GG20[3]. The t/n threshold signature protocol is relatively complex, requiring multiple rounds of communication between the parties during the generation and signing phases. It is not fast enough to meet the needs of high-traffic web3 use cases. In contrast, the 2/2 signature scheme proposed in the Lindell 17’ paper has a higher signing efficiency. However, if a key share is accidentally lost, the user’s asset will be unrecoverable. In view of this, we propose a 2/n signature scheme as an improvement on the Lindell 17’ protocol to balance signing efficiency and meet the business requirement of web3 use cases.

info

目前，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、Overview of the Solution

We propose an ECDSA 2/n signature scheme based on Feldman's Verifiable Secret Sharing scheme (Feldman's VSS) and the Lindell 17’ protocol. When generating private key shares, we use the Feldman's VSS to generate individual private key share. During the signing phase, we use the Lindell 17’ protocol for two-party signatures to ensure the efficiency of the signing process. In the event of a lost or leaked key share, the user's assets will remain secure. Additionally, we support bip32 non-hardened key derivation, which only requires one key generation and can support multiple cryptocurrencies. If a key share is lost or leaked by one party, or if a new participant joins, we support resetting the key share to a new set of private key shares.

info

我们提出了一种基于 Feldman 可验证秘密共享方案（Feldman's VSS）和 Lindell 17' 协议的 ECDSA 2/n 签名方案。

• 在生成私钥共享时，我们使用 Feldman 的 VSS 来生成单独的私钥共享。
• 在签名阶段，我们使用 Lindell 17’协议进行两方签名，以保证签名过程的效率。
• 如果密钥共享丢失或泄露，用户的资产将保持安全。
• 此外，我们还支持 bip32 非强化密钥派生，只需生成一次密钥即可支持多种加密货币。
• 如果密钥共享丢失或被一方泄露，或者有新参与者加入，我们支持将密钥共享重置为一组新的私钥共享。

3、Supported Functionalities

This library implements the following functions:

1. Key generation: Generates {2,n} key shares using Feldman's VSS. In the case of ECDSA signing, additional key negotiation between the two parties is required to meet the Lindell 17’ two-party signature rule.
2. Key share refresh: If a key share is lost or leaked by one party, or if a new participant joins, all parties regenerate new random shares of the existing shared key and void the old shares.
3. Bip32 key derivation: None of the parties know the complete private key. Only non-hardened key derivation is supported. Chaincode is jointly generated by multiple parties in the keygen phase.
4. 2-party ECDSA signing: Uses the Lindell 17’ protocol to perform 2-party signatures according to the key generation rule. Neither party alone can generate a complete signature.
5. 2-party ed25519 signing: A variant of EdDSA and Schnorr, where both parties jointly compute the complete signature.

info

该库实现了以下功能：

1. 密钥生成：使用 Feldman 的 VSS 生成 {2,n} 密钥共享。在 ECDSA 签名的情况下，需要双方进行额外的密钥协商，以满足 Lindell 17 的两方签名规则。
2. 密钥共享刷新：如果一方丢失或泄露密钥共享，或者有新参与者加入，则所有各方都会重新生成现有共享密钥的新随机共享，并使旧共享失效。
3. Bip32 密钥派生：各方都不知道完整的私钥。仅支持非强化密钥派生。 Chaincode 是在 keygen 阶段由多方共同生成的。
4. 2 方 ECDSA 签名：使用 Lindell 17'协议根据密钥生成规则进行 2 方签名。任何一方都无法单独生成完整的签名。
5. 2 方 ed25519 签名：EdDSA 和 Schnorr 的变体，双方共同计算完整签名。

info

2-party ECDSA signing 和 2-party ed25519 signing 之间是替代方案？

在描述的库中，"2-party ECDSA signing"和"2-party ed25519 signing"确实可以视为替代方案，因为它们都是用于生成数字签名的协议，但是使用的加密算法不同。这两种签名方法都是基于两方计算协议，如 Lindell 17’协议，来实现的，确保没有任何一方能够独立地生成完整的签名。下面是关于这两种签名方法的更多细节：

2-party ECDSA signing

• 算法基础: ECDSA（椭圆曲线数字签名算法）是一种广泛使用的数字签名算法，基于椭圆曲线密码学。
• 适用场景: 适用于大多数现有的区块链技术，如比特币和以太坊，这些系统内置了对 ECDSA 的支持。
• 特点: ECDSA 签名过程涉及随机数生成、椭圆曲线点的乘法等计算密集型操作。
• 安全性: 在 Lindell 17’协议下，两方共同生成签名，增强了密钥管理的安全性。

2-party ed25519 signing

• 算法基础: ed25519 是一种基于 Schnorr 签名的变体，它使用 EdDSA（Edwards-curve Digital Signature Algorithm）进行签名。EdDSA 是一种更现代的签名算法，设计时考虑了更高的安全性和更好的性能。
• 适用场景: 适用于需要高安全性和高性能的应用场景，如某些新的区块链平台和安全敏感的通信协议。
• 特点: ed25519 优化了计算过程，签名生成和验证速度快，同时对侧信道攻击具有较强的抵抗力。
• 安全性: 在两方协议下，同样保证了没有单一方能够控制完整的私钥或独立生成签名。

替代关系

这两种签名方法在功能上是相似的，都是为了在不共享完整私钥的情况下，通过两方合作生成数字签名。选择哪一种方法主要取决于特定的应用需求、目标平台的兼容性以及对安全性和性能的要求。例如，如果目标平台是以太坊，可能更倾向于使用 ECDSA；而如果安全性和性能是首要考虑，可能会选择 ed25519。

因此，这两种方法可以视为针对不同需求和环境的替代方案，开发者可以根据具体的应用场景和需求来选择最适合的签名技术。

4、Cryptographic Tools

BIP32 从单个种子生成无限数量的公钥和私钥对

BIP32 (Bitcoin Improvement Proposal 32) is a standard for creating hierarchical deterministic (HD) wallets in Bitcoin and other cryptocurrencies. It allows users to generate an infinite number of public and private key pairs from a single seed, making it easier to manage and secure cryptocurrency funds.

1. Master Key Generation: A random 256-bit seed is generated, which serves as the master private key. The corresponding master public key is derived from the master private key using elliptic curve multiplication.

2. Key Derivation: Each child key is derived from its parent key with a hardened or non-hardened derivation method. Hardened derivation is used when a parent key wants to create a child key that cannot be used to derive other child keys, while non-hardened derivation allows child keys to be derived from other child keys.

BIP32（比特币改进提案 32）是用于在比特币和其他加密货币中创建分层确定性 (HD) 钱包的标准。它允许用户从单个种子生成无限数量的公钥和私钥对，从而更轻松地管理和保护加密货币资金。

1. 主密钥生成：生成随机的 256 位种子，作为主私钥。相应的主公钥是使用椭圆曲线乘法从主私钥导出的。
2. 密钥派生：每个子密钥均通过强化或非强化派生方法从其父密钥派生。
   1. 当父密钥想要创建不能用于派生其他子密钥的子密钥时，使用强化派生，强化派生，不能继续派生
   2. 而非强化派生允许从其他子密钥派生子密钥。非强化派生，可继续派生

Commitment Schemes 🔥 承诺-揭示

Commitment schemes are cryptographic protocols that allow a party to commit to a value without revealing it, and later reveal the value while proving that it has not been changed. A commitment scheme involves two phases: commitment and opening, shown below:

承诺方案是一种加密协议，允许一方在不透露该值的情况下承诺该值，然后在证明该值未被更改的同时透露该值。承诺方案分为承诺和开放两个阶段，如下所示：

承诺-揭示

$Commitment: C = commit(m, r)$

where:

• m is the value to be committed
• r is a random string
• C is the commitment string

$Opening: (m', r') = open(C)$

where:

• m' is the revealed value
• r' is the revealed random string

ECDSA Signing 🔥 椭圆签名算法

ECDSA signing is the process of creating a digital signature for a message using the signer's private key. The digital signature is used to authenticate the sender of the message and ensure the integrity of its content. ECDSA signature scheme allows the public key to be recovered from the signed message together with the signature.

Key Generation

1. Choose an elliptic curve with a generator point G, and order n.
2. Generate a random private key a, such that 1 < a < n.
3. Compute the public key A = a⋅G.

Sign

1. Hashing: The message m is hashed using a cryptographic hash function to produce a fixed-length message digest H(m).
2. Random Number Generation: A random number k is generated between 1 and the order n of the curve.
3. Point Computation: The signer computes the point R = k⋅G on the elliptic curve.
4. Scalar Computation: The signer computes the scalar $s = (k^-1 _ (H(m) + a _ r)) mod n$, where r is the x-coordinate of R.
5. Signature Generation: The signer generates the digital signature (r, s).

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

info

ECDSA（椭圆曲线数字签名算法）签名过程是使用椭圆曲线密码学为消息生成数字签名的方法，该方法提供了消息的完整性、真实性和不可否认性。下面，我将详细解释每个步骤是如何为签名过程做出贡献的。

ECDSA 签名过程详解

密钥生成

1. 选择椭圆曲线和生成元点 G：根据安全需求选择椭圆曲线。生成元点 $G$ 是曲线上的一个预定义点，其具有已知的阶 $n$，$n$ 是一个大质数。
2. 生成随机私钥 $a$：私钥 $a$ 是从范围 $1 < a < n$ 中随机选择的整数。必须保密。
3. 计算公钥 $A$：公钥 $A$ 计算为 $A = a \cdot G$。这是通过将生成元点 $G$ 自身加 $a$ 次得到的曲线上的一个点。

签名过程

1. 哈希处理：首先使用密码学哈希函数（如 SHA-256）对消息 $m$ 进行哈希处理，生成固定长度的消息摘要 $H(m)$。这一步确保可以签名任何长度的消息，并有助于保护消息的完整性。
2. 随机数生成：生成一个随机数 $k$。关键是每个签名的 $k$ 必须是唯一的，以防止签名方案的漏洞。
3. 点计算：计算点 $R = k \cdot G$。这涉及到将生成元点 $G$ 自身加 $k$ 次。
4. 标量计算：使用公式 $s = k^{-1} \cdot (H(m) + a \cdot r) \mod n$ 计算标量 $s$，其中 $r$ 是点 $R$ 的 x-坐标。这里，$k^{-1}$ 是 $k$ 模 $n$ 的逆元，$a \cdot r$ 将签名与私钥关联起来。
5. 签名生成：签名是对 $(r, s)$，可以与消息一起传输。

验证过程（在您的描述中未详细说明，但对于理解签名的使用至关重要）

1. 接收 $(r, s)$ 和消息 $m$：验证者接收到签名和原始消息。
2. 哈希消息：使用与签名者相同的哈希函数计算 $H(m)$。
3. 验证签名：验证者使用签名者的公钥 $A$、消息摘要 $H(m)$ 和签名 $(r, s)$ 来确认 $s$ 是否正确计算。这包括几个椭圆曲线操作，并检查涉及 $A$、$r$ 和 $s$ 的方程是否成立。

这种验证确保签名是由私钥持有者创建的，并且自签名以来消息未被更改。从签名和消息中恢复公钥的能力是某些 ECDSA 实现的特定功能，这在需要最小化公钥基础设施（PKI）开销的系统中特别有用。

ED25519 Signing 🔥 椭圆签名算法

Ed25519[4] is a public-key digital signature algorithm based on elliptic curve cryptography. Ed25519 uses a twisted Edwards curve and a modified version of the Schnorr signature scheme. The algorithm has several advantages over other digital signature algorithms, including resistance to side-channel attacks, immunity to timing attacks, and a compact signature size of only 64 bytes.

Key Generation

1. Generate a random 256-bit private key k.
2. Compute H(k), where H is the SHA-512 hash function. Store the lower 32 bytes of the digest in a buffer.
3. Prune the buffer: Clear the lowest three bits and the highest bit. Set the second highest bit. The resulting buffer is interpreted as little-endian integer b.
4. Compute the public key A = b⋅G.

Sign

1. Hashing: Compute H(k) again. Store the higher 32 bytes of the digest in prefix.
2. Random Number Generation: The signer computes the scalar r = H(prefix || H(m)), where m is the message to be signed.
3. Point Computation: The signer computes the point R = r⋅G on the ED25519 curve.
4. Scalar Computation: The signer computes the scalar s = r + H(R || A || m) * b mod n.
5. Signature Generation: The signer generates the digital signature (R, s).

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

info

Ed25519 是基于椭圆曲线密码学的公钥数字签名算法。Ed25519 使用了一个扭曲的 Edwards 曲线和 Schnorr 签名方案的改进版本。与其他数字签名算法相比，该算法具有多个优点，包括抵抗侧信道攻击、免疫计时攻击，并且具有仅 64 字节的紧凑签名大小。

密钥生成

1. 生成随机的 256 位私钥 k。
2. 计算 H(k)，其中 H 是 SHA-512 哈希函数。将摘要的下 32 字节存储在缓冲区中。
3. 修剪缓冲区：清除最低的三个比特和最高的比特。设置次高位。结果缓冲区被解释为小端整数 b。
4. 计算公钥 A：公钥 A 计算为 $A = b \cdot G$，其中 G 是曲线上的生成点。

签名过程

1. 哈希处理：再次计算 H(k)。将摘要的上 32 字节存储在 prefix 中。
2. 随机数生成：签名者计算标量 r = H(prefix | | H(m))，其中 m 是要签名的消息。
3. 点计算：签名者计算 ED25519 曲线上的点 $R = r \cdot G$。
4. 标量计算：签名者计算标量 $s = (r + H(R \| \| A \| \| m) \cdot b) \mod n$。
5. 签名生成：签名者生成数字签名 $(R, s)$。

Ed25519 签名函数表示

$Ed25519\_{sign}(msg, privKey) \rightarrow (R, s)$

说明

• SHA-512 的使用：Ed25519 使用 SHA-512 哈希函数以确保消息的完整性和随机数的生成。
• 缓冲区的修剪：通过修剪以确保私钥 b 满足特定的格式要求，这是为了优化和安全性。
• 紧凑的签名：生成的签名包括点 R（32 字节）和标量 s（32 字节），共 64 字节，非常适合在网络环境中传输。

Ed25519 的设计注重安全性和效率，使其在需要高安全性和高性能的应用中非常受欢迎。

Feldman's VSS 🔥 密钥份额与验证

Feldman's Verifiable Secret Sharing (VSS) is a cryptographic protocol that enables a dealer to distribute a secret among a group of participants, in such a way that it can be reconstructed only if a minimum number of parties cooperate. It involves four steps as follows:

1. Setup: Choose a large prime p and a generator g of a subgroup of order q, where q is a prime that divides p-1. Let x be the secret value and compute y = g^x mod p.
2. Share distribution: The dealer randomly selects a polynomial f(x) of degree t-1 such that f(0) = x, and sends the shares (i, s_i) to the participants, where s_i = f(i) mod p for i = 1 to n. The dealer also computes the corresponding polynomial g(x) = f(x) + r(x) mod p, where r(x) is a random polynomial of degree t-1, and sends the commitments (i, C_i) to the participants, where C_i = gⁱ mod p for i = 1 to n.
3. Verification: Each participant verifies the validity of their share s_i by checking that y^s_i * g^-i mod p = 1, and the validity of the commitments by checking that C_i = gⁱ mod p for i = 1 to n.
4. Reconstruction: Any subset of t or more qualified participants can reconstruct the secret x by using Lagrange interpolation on their shares.

info

费尔德曼的可验证秘密共享（VSS）是一种密码协议，它使一个经销商能够在一组参与者中分发一个秘密，这样只有当最少数量的参与者合作时，才能重构这个秘密。它涉及以下四个步骤：

4. 设置：选择一个大质数 p 和一个生成元 g，g 是阶为 q 的子群的生成元，其中 q 是一个质数，能整除 p-1。设 x 为秘密值，并计算 y = g^x mod p。
5. 份额分发：经销商随机选择一个 t-1 次的多项式 f(x)，使得 f(0) = x，并向参与者发送份额 (i, s_i)，其中 s_i = f(i) mod p 对于 i = 1 到 n。经销商还计算相应的多项式 g(x) = f(x) + r(x) mod p，其中 r(x) 是一个 t-1 次的随机多项式，并向参与者发送承诺 (i, C_i)，其中 C_i = g^i mod p 对于 i = 1 到 n。
6. 验证：每个参与者通过检查 y^(s_i) * g^(-i) mod p = 1 来验证他们份额 s_i 的有效性，并通过检查 C_i = g^i mod p 对于 i = 1 到 n 来验证承诺的有效性。
7. 重构：任何 t 或更多合格参与者的子集可以通过对他们的份额使用拉格朗日插值来重构秘密 x。

解释与细节

• 选择质数 p 和生成元 g：这是确保在给定的群中进行安全计算的基础。
• 多项式 f(x) 的选择：这个多项式的选择关键在于它的常数项是秘密 x，确保了秘密的嵌入。
• 份额的分发：通过计算 f(i) mod p，确保每个参与者的份额都是秘密多项式的一个评估，且在模 p 的限制下保持秘密性。
• 承诺的生成与分发：承诺 C_i = g^i mod p 用于在不暴露秘密多项式的情况下验证份额的正确性。
• 份额的验证：通过特定的验证方程式，参与者可以独立确认他们接收到的份额以及承诺的正确性，增加了协议的透明度和安全性。
• 秘密的重构：当足够数量的参与者合作时，可以通过拉格朗日插值法恢复原始的秘密 x，这是一种数学方法，用于基于给定点集恢复多项式。

费尔德曼 VSS 的设计提供了一种既安全又有效的方式来分发和管理秘密数据，适用于需要高安全性的分布式系统和应用程序。

Paillier Encryption

Paillier encryption is a public-key encryption scheme that enables secure computation on encrypted data without decrypting. Paillier encryption provides additive homomorphic encryption, meaning that the sum of two encrypted messages can be computed as the product of their ciphertexts.

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

1. Key Generation: Choose two large prime numbers p and q, and compute N = pq. Choose a random g that is relatively prime to N, and compute λ = lcm(p-1, q-1), where lcm is the least common multiple. The public key is (N, g), and the private key is λ.

2. Encryption: To encrypt a plaintext message m, choose a random value r that is less than N, and compute the ciphertext c as follows:

   $c = g^m \cdot r^N mod N^2$

3. Decryption: To decrypt the ciphertext c, compute the plaintext message m as follows:

   $m = L(c^λ mod N^2) / L(g^λ mod N^2) mod N$

   where

   $L(x) = (x-1) / N$

info

Paillier 加密是一种公钥加密方案，具有一些特殊的性质，使其在保护数据隐私和进行安全计算方面非常有用。下面我将逐步解释 Paillier 加密的三个主要步骤：密钥生成、加密和解密，以及它的同态性质。

1. 密钥生成

• 选择两个大素数 p 和 q。这两个素数是保证加密安全的基础。
• 计算 N = p * q。这个 N 将用于后续的模运算，确保运算在一个有限的数域中进行。
• 选择一个随机数 g，这个数要与 N 互质（即 gcd(g, N) = 1，其中 gcd 是最大公约数）。
• 计算 λ = lcm(p-1, q-1)，其中 lcm 表示最小公倍数。这个 λ 是解密过程中的关键参数。
• 公钥和私钥：公钥是 (N, g)，私钥是 λ。

2. 加密

• 选择消息 m，这是你想加密的明文。
• 选择一个随机数 r，这个数需要小于 N。
• 计算密文 c 如下： $c = g^m \cdot r^N \mod N^2$ 这里的模运算确保了结果仍然在有限的数域内。

3. 解密

• 使用私钥 λ 来解密： $m = \frac{L(c^\lambda \mod N^2)}{L(g^\lambda \mod N^2)} \mod N$ 其中函数 L(x) 定义为 (x - 1) / N。

同态性质

• Paillier 加密的一个重要特点是它的加法同态性质。这意味着你可以在密文上进行操作，这些操作对应于明文上的加法操作。
• 如果你有两个密文 c1 和 c2，分别对应于两个明文 m1 和 m2，那么密文的乘积（在模 N^2 下）将对应于明文的和： $c1 \cdot c2 = g^{m1} \cdot r_1^N \cdot g^{m2} \cdot r_2^N \mod N^2 = g^{m1+m2} \cdot (r_1 \cdot r_2)^N \mod N^2$ 这表明 c1 * c2 解密后会得到 m1 + m2。

这种同态性质使得 Paillier 加密特别适用于需要在加密数据上进行计算的场景，如在不泄露个人数据的情况下进行数据分析或在保密投票中计算总票数等。

Schnorr Proof 零知识证明

Schnorr non-interactive zero-knowledge (NIZK) proof[5] is a non-interactive variant of the three-pass Schnorr identification scheme. The Schnorr NIZK proof allows one to prove the knowledge of a discrete logarithm without leaking any information about its value, with steps as follows:

1. Alice publishes her public key A = a⋅G, where a is the private key and G is the generator
2. Alice chooses a random number v, computes V = v⋅G, and sends V to Bob
3. Alice computes the challenge c = H(G || V || A)
4. Alice computes r = v – a * c mod n and sends it to Bob
5. Bob verifies V = r⋅G + c⋅A

info

Schnorr 非交互式零知识证明（NIZK）是三步 Schnorr 身份认证方案的非交互式变体。Schnorr NIZK 证明允许一个人证明他们知道一个离散对数的知识，而不泄露有关其值的任何信息。具体步骤如下：

1. 公钥发布：Alice 发布她的公钥 $( A = a \cdot G )$，其中 $a$ 是私钥，$G$ 是生成元。
2. 随机数选择和计算：Alice 选择一个随机数 $v$，计算 $V = v \cdot G$，并将 $V$ 发送给 Bob。
3. 挑战计算：Alice 计算挑战值 $c = H(G \| V \| A)$，其中 $H$ 是一个哈希函数，用于将输入的数据映射成固定大小的输出，这里的输入包括生成元 $G$，临时公钥 $V$ 和 Alice 的公钥 $A$。
4. 响应计算：Alice 计算响应 $r = v - a \cdot c \mod n$，其中 $n$ 是群的阶，然后将 $r$ 发送给 Bob。
5. 验证：Bob 验证 $V$ 是否等于 $r \cdot G + c \cdot A$。具体来说，Bob 通过将 Alice 发来的 $r$ 和 $c$ 代入等式，检查等式左边 $V$ 和右边 $r \cdot G + c \cdot A$ 是否相等，以此验证 Alice 的证明。

零知识证明的关键特性

• 零知识：Bob 通过验证过程，无法得知 $a$ 的任何信息，即 Alice 的私钥信息被保护。
• 非交互性：与传统的交互式证明不同，Schnorr NIZK 证明不需要 Alice 和 Bob 之间有多轮的交互。Alice 只需发送 $V$ 和 $r$，Bob 即可独立完成验证。
• 简洁性和效率：Schnorr NIZK 证明由于其数学结构简单，计算和验证步骤都非常高效，适用于需要快速验证的场景。

Schnorr NIZK 证明是密码学中一个重要的工具，广泛应用于各种安全协议中，特别是在身份验证和数字签名等领域。这种证明方法不仅保护了用户的隐私，还提高了协议的执行效率。

5、Threshold Scheme Overview

After describing all the cryptographic primitives and tools used in our solution, we will now describe the details of the protocol.

ECDSA 🔥

Key shares are generated according to Feldman's VSS scheme, and two-party signatures are performed according to the Lindell 17’ protocol. In the original Lindell 17’ protocol definition, the private key x = x1*x2 is not easily extendable to 2/n signature scheme. Therefore, we make a modification by changing the definition of private key to x = x1 + x2. The details of the modification are as follows:

             original                                 modify
privateKey  x = x1*x2                                x = x1 + x2
publicKey   X = x1*x2*G = x1*X2 = x2*X1              X = X1 + X2 = x1*G + x2*G
sign
            k = k1*k2                                k = k1*k2
            s = (h + r*x1*x2)/(k1*k2) mod q          s = (h + r*(x1+x2))/(k1*k2) mod q

Distributed Key Generation

Each party generates an ECDSA key share to be used for signing, as follows:

1. n participants each generate their own key share using the Feldman's VSS protocol based on the 2/n signature scheme, and output (ld, share_i, publicKey, chaincode).
2. The signing rule is determined to specify which two parties will jointly participate in signing. When two parties sign, one acts as Alice and the other as Bob. Alice and Bob each perform a Lagrange interpolation calculation on their own share_i to obtain x1 and x2, respectively. The private key is x = x1 + x2.
3. Alice randomly generates a Paillier public-private key pair and uses the Paillier public key to encrypt x1. Alice also proves to Bob that she knows x1 with zero knowledge. E_x1 represents the ciphertext, and Alice sends E_x1 and the Paillier public key to Bob.
4. Alice outputs her Paillier private key and (ld, share_i, publicKey, chaincode).
5. Bob outputs the Paillier public key and (ld, share_i, publicKey, chaincode, E_x1).

Signing

After obtaining the message to be signed, Alice and Bob jointly generate the signature using the Lindell 17’ protocol, as follows:

1. Alice and Bob generate random numbers k1 and k2, and both learn $R = k1*k2*G$ . Commitments and zero-knowledge proofs are used to ensure the security of the learning process.
2. Given $R = (rx, ry)$ , Alice and Bob can each compute r = rx mod q .
3. Bob computes the partial signature of m under the Paillier homomorphic encryption scheme: $(m + r(x1 + x2))/k2 mod q$, and sends the partial signature to Alice.
4. Alice decrypts the partial signature using her Paillier private key and computes the full signature: (m + r*(x1 + x2))/(k1*k2) mod q . Then, she verifies the signature using the public key. If the signature is valid, she outputs the signature; otherwise, the signature fails.

info

获得待签名消息后，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 。然后，她使用公钥验证签名。如果签名有效，她输出签名；否则签名失败。

info

这个要生成以太坊交易签名，所以 这里的 Alice 是 密钥片段 2（用户手机上），Bob 是密钥片段 1（远程服务器）？

在以太坊交易签名的应用场景中，使用 Lindell 17’协议进行多方签名确实可以是一种安全的选择，特别是在分布式应用和服务中。在您的描述中，将 Alice 定义为持有密钥片段 2 的用户手机，而 Bob 定义为持有密钥片段 1 的远程服务器，这是一个合理的安排，具体原因如下：

1. 用户控制权：用户通过其设备（如手机）持有密钥的一部分，这增加了用户对交易签名过程的直接控制。这种设置使用户能够在交易过程中发挥更积极的作用，同时也提高了用户对整个交易过程的信任。

2. 服务器的角色：远程服务器作为另一个密钥持有者，可以提供额外的安全措施，如密钥保护和安全的计算环境。服务器通常具有更强大的硬件和更专业的安全措施，可以有效地防止密钥被泄露或被非法利用。

3. 风险分散：通过在两个不同的实体（用户设备和服务器）之间分散密钥，可以降低密钥泄露的风险。即使其中一个部分被泄露，没有另一部分的密钥，攻击者也无法生成有效的签名。

4. 符合多方计算的原则：多方计算（MPC）的基本原则是没有任何单一参与者可以单独重构整个密钥或单独完成签名过程。这种密钥分割方法符合 MPC 的原则，增强了整个系统的安全性。

在实际操作中，Alice 和 Bob 需要通过安全的通信渠道交换必要的信息，如随机数、部分签名、以及零知识证明等，以确保整个签名过程的安全性。此外，实现这种方案需要考虑到网络安全、端点安全、以及密钥管理等多个方面的安全措施，以防止任何潜在的安全威胁。

总之，您的设定在以太坊交易签名的背景下是合理的，可以有效提高交易的安全性和用户的控制力。这种方法利用了多方计算的优势，同时考虑了实际操作中的安全和便利性。

Ed25519

Generate key shares for each party using Feldman's VSS protocol. After obtaining the message to be signed m, any two parties can jointly generate a signature as follows:

1. Alice and Bob respectively compute x1 and x2 by performing a Lagrange interpolation on their own share_i. The complete private key x=x1+x2.
2. Alice and Bob respectively generate random numbers r1 and r2, and respectively compute R1=r1⋅G, R2=r2⋅G. Then both Alice and Bob learn R=R1+R2. Commitments and zero-knowledge proofs are used to ensure the security of the learning process.
3. Each party can compute h=sha512(R, pub, m), where pub is the public key corresponding to the complete private key x.
4. Alice and Bob each compute their own signature si=ri+h*xi, and send the signature result to the other party.
5. Compute the complete signature s=s1+s2, and verify the signature using the public key.

info

在您提到的过程中，描述了使用 Ed25519 签名方案在多方（特别是 Alice 和 Bob）之间共同生成数字签名的方法。这种方法结合了阈值密码学和安全多方计算的元素，确保没有单一方拥有完整的私钥。下面是该过程的逐步解释：

步骤 1：计算私钥的个人份额

• 拉格朗日插值：Alice 和 Bob 各自对他们的私钥份额执行拉格朗日插值。这种插值是秘密共享方案的一部分，其中私钥$x$被分割成多个份额，这样任何份额的子集都可以组合重建原始的密钥。在这种情况下，Alice 计算$x_1$，Bob 计算$x_2$，然后他们一起重建完整的私钥$x = x_1 + x_2$。

步骤 2：生成随机标量和曲线上对应的点

• 随机标量：Alice 和 Bob 各自独立生成随机数$r_1$和$r_2$。
• 曲线乘法：他们分别计算$R_1 = r_1 \cdot G$和$R_2 = r_2 \cdot G$，其中$G$是 Ed25519 曲线的基点。
• 点的组合：然后他们合作计算点的和$R = R_1 + R_2$。这个操作使用了承诺和零知识证明来确保双方都不会了解对方的随机标量，维护安全和隐私。

步骤 3：计算哈希

• 哈希函数：每一方计算哈希$h = \text{sha512}(R, \text{pub}, m)$，其中$R$是前一步骤中组合的点，$\text{pub}$是对应于完整私钥$x$的公钥，$m$是要签名的消息。

步骤 4：计算部分签名

• 部分签名：Alice 计算她的部分签名$s_1 = r_1 + h \cdot x_1$，Bob 计算他的部分签名$s_2 = r_2 + h \cdot x_2$。这些部分签名然后在双方之间交换。

步骤 5：计算完整签名和验证

• 完整签名：完整签名$s$计算为$s = s_1 + s_2$。这个签名$s$连同$R$形成了最终签名$(R, s)$对消息$m$的签名。
• 验证：使用公钥$\text{pub}$验证签名，检查$s \cdot G = R + h \cdot \text{pub}$，确保签名是由拥有与$\text{pub}$对应的私钥的人创建的。

这种方法允许 Alice 和 Bob 共同签署一条消息，而无需任何一方向另一方透露其私钥部分，增强了在信任可能不是绝对的环境中的安全性。这在分布式系统或需要对密钥妥协有额外保护的场景中特别有用。

Reshare

If a party's share is lost or leaked, or if new participants join, a new set of key shares can be generated. The refresh process only requires the participation of the two previously generated shares, and the process is similar to the private key generation process, with the chaincode remaining unchanged.

info

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

Key Derivation

The derivation rule is similar to BIP32, where no party knows the complete private key and can only perform non-hardened derivation. The chaincode is generated jointly by multiple parties during the key generation phase and is not changed during the refresh phase.

After Key Generation, each party has its own share, and all shares are correlated and on the same curve. Each share can be derived along the same path to obtain a child key share, which is also on the same curve, resulting in a new set of key shares.

info

推导规则类似于 BIP32，任何一方都不知道完整的私钥，只能进行非硬化推导。链码在密钥生成阶段由多方共同生成，在刷新阶段不会更改。

密钥生成后，各方都有自己的份额，并且所有份额都是相关的并且位于同一条曲线上。每个共享可以沿着相同的路径导出以获得子密钥共享，该子密钥共享也在同一条曲线上，从而产生一组新的密钥共享。

info

是的，您的理解是正确的。在多方密钥共享系统中，每个密钥碎片（或称为密钥份额）都是整个私钥的一部分，并且每个份额都是密切相关的。这种系统通常设计为，只有当所有相关的密钥份额正确组合在一起时，才能有效地执行密钥相关的操作（如签名或解密）。如果其中任何一个密钥份额被更新或更改，那么与旧份额的任何组合都将不再有效。

这里有几个关键点需要注意：

1. 密钥碎片的协同工作

在多方密钥共享系统中，所有的密钥份额必须彼此配合。如果一个份额被更新（如服务端的密钥碎片 1），那么其他份额（如本地的密钥碎片 2 和 3）也需要相应地更新，以保证它们能够一起正确地生成有效的签名或执行其他加密操作。

2. 签名的有效性

在使用如 ECDSA（椭圆曲线数字签名算法）这类基于密钥份额的签名算法时，签名的生成依赖于所有密钥份额的整合。如果服务端更新了密钥碎片 1，而本地仍然使用旧的密钥碎片 2 和 3，那么这些份额的组合将不再对应原有的完整私钥，从而无法生成有效的签名。

3. 密钥同步和更新

为了维护系统的安全性和功能性，当任何一个密钥份额发生变更时，所有相关的密钥份额通常需要进行同步更新。这确保了所有参与方都持有最新的、可以相互配合的密钥份额，从而保障了加密操作的正确性和安全性。

4. 安全协议的设计

在设计多方密钥共享系统时，通常会包括密钥更新机制，以应对密钥泄露、参与方变更或安全策略更新等情况。这种更新机制需要确保所有密钥份额的同步更新，以避免出现某些份额是新的而另一些是旧的情况。

因此，确实如您所述，当服务端的密钥碎片 1 更新后，需要确保所有其他相关的密钥份额（如本地的密钥碎片 2 和 3）也进行相应的更新，以维持整个系统的功能性和安全性。

6、Summary 🔥

Based on the Lindell 17’ protocol, we propose improvements for secure multi-party computation of ECDSA, extending 2/2 signatures to 2/n signatures. Private key shares are generated using Feldman’s VSS scheme, and the Lindell 17’ protocol is used for two-party signature generation, balancing signature efficiency and meeting the practical requirements of business scenarios. This library also supports bip32 key derivation and private key refreshing for key shares, making it easy for developers to learn and use.

info

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

7、Reference

[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