密码学之Schnorr签名、Frost、MPC钱包(二)

皓码
发布于 2025-07-09 15:12
阅读 633

Schnorr签名上篇文章讲了schnorr签名的原理，包括单签和多签，并对他们的安全性做了分析。本文继续讲一个新的阈值签名协议Frost，本文内容来自于这篇文章，FROST:FlexibleRound-OptimizedSchnorrThresholdSignatures

## Schnorr 签名
[上篇文章](https://learnblockchain.cn/article/17592)讲了schnorr 签名的原理，包括单签和多签，并对他们的安全性做了分析。本文继续讲一个新的阈值签名协议 Frost，本文内容来自于这篇文章，FROST: Flexible Round-Optimized Schnorr Threshold Signatures，是该文章的深刻解读。它是一种先进的阈值签名方案，基于 Schnorr 签名框架设计，专为多方安全计算和分布式系统进行优化。它允许一组参与者共同生成签名，而无需暴露各自的私钥分片，更无需恢复出完整的签名私钥，有效的保证了签名私钥的安全性，同时在效率、灵活性、容错率和安全性上达到了良好平衡。

该方案涉及 Shamir秘密分享、可验证的秘密分享、阈值签名、分布式密钥生成（DKG）、Schnorr签名等技术方案。
### 应用场景
1. 区块链：
   - 多签名钱包：如比特币的 MuSig2（FROST 的变种）。
   - 分布式验证节点：降低单点故障风险（如 Cosmos 的 Tendermint 共识）。
   - MPC 钱包：签名私钥分片存储，无需恢复完整签名私钥，容忍一定节点故障率。
2. 密钥管理系统：
   - 云服务提供商的密钥分片存储（如 AWS KMS）。
   - 企业级密钥备份与恢复。
3. 隐私保护协议：
   - 与零知识证明结合，实现匿名多方签名。
   - 去中心化身份认证（如 Sismo、Worldcoin）。
### 核心特性
1. 安全性
- 抗共谋攻击：少于 t 个参与者无法生成有效签名。
- 前向安全性：即使某个私钥分片泄露，过去的签名仍保持安全。
- 防篡改：任何参与者无法在其他参与者不知情的情况下修改签名。
2. 效率
- 通信复杂度：两轮通信，每轮仅需广播少量消息（承诺和签名分片）。
- 计算复杂度：每个参与者的计算量与传统 Schnorr 签名相当。
- 无限制并行性：节点之间可以互不影响独立的生成签名分片。
3. 灵活性
- 动态调整：支持添加 / 删除参与者，无需重新初始化整个系统。
- 门限调整：可动态调整阈值 t（需多数参与者同意）。
4. 轮次优化：仅需两轮通信（预计算 + 签名生成），低于传统方案的三轮。

### 实现与开源库
- Rust 实现：frost-rs（支持多种椭圆曲线）。
- JavaScript 实现：js-frost（用于浏览器环境）。
- 应用案例：
  - Zcash：计划用 FROST 改进其透明地址的多签功能。
  - Blockstream：在侧链技术中使用 FROST 增强安全性。
### Frost:灵活的轮数优化的Schnorr阈值签名原理
首先假设阈值签名方案拥有 $n$ 个参与者，要求至少 $t(t\leq n)$ 个参与者合作才能生成有效签名，记为 $(t,n)$ 阈值方案。本人给出一个使用Go语言开发的[多方签名代码含frost](https://github.com/Zhenhanyijiu/multisiggo)，功能持续完善中。
#### Frost KeyGen
图 1：Frost 协议的分布式密钥生成算法 KenGen 
![frost-keygen.png](https://img.learnblockchain.cn/attachments/2025/07/oDeB0eTP686e152eee5de.png)
KeyGen 采用 Pedersen 分布式密钥生成（DKG）算法，这部分是Frost协议全局初始化的过程，通过秘密分享每个参与者生成各自的签名私钥分片以及对应的验证公钥分片，每个参与者本地计算其他参与者的验证公钥，本地计算阈值组公钥。本部分分为两轮：
- 第一轮
1. 对于每个参与者 $P_i$ 随机生成一个 $t-1$ 次多项式，即多项式系数都是随机生成的，如下：
   $$
   \begin{aligned}
    f_i(x)=a_{i0}+a_{i1}x+\dots+a_{i,t-1}x^{t-1}
   \end{aligned}
   $$
   多项式要保密。
2. 每个参与者 $P_i$ 计算出一个对常数项秘密 $a_{i0}$ 的一个知识证明 $\sigma_i$ ，熟悉密码学的一眼就能看出来，知识的证明其实就是一个身份认证协议，也是schnorr签名形式，目的是防止 rogue key 攻击，这一步是很容易理解的。
3. 每个参与者 $P_i$ 计算所有多项式系数的承诺 $\vec{C_i}$ ，如图所示。
4. 每个参与者 $P_i$ 广播系数承诺 $\vec{C_i}$ 以及常数项系数的知识证明 $\sigma_i$ ，供其他参与者进行验证。
5. 对于每个参与者 $P_i$ 接收到其他参与者的系数承诺以及常数项的知识证明，按照图中的形式进行验证知识证明的正确性，只要有一个没有通过验证，则立马终止协议，可以对作恶者进行投诉，或者不带它继续玩，由于DKG这一步是Frost协议全局初始化的过程，必须保证DKG过程正确生成，即所有参与者都是诚实的。
- 第二轮
1. 这一步是秘密分享，每个参与者 $P_i$ 计算针对参与者 $P_l(l \ne i)$ 的秘密分享 $(l,f_i(l))$ 安全地秘密地发送给$P_l$，并删除$f_i$和 $(l,f_i(l))$，自己保存$((i,f_i(i)))$。
2. 每个参与者 $P_i$ 秘密的接收到 $(l,f_l(i))$ 值，会进行验证，如有验证失败，立马终止协议，并对作恶的参与者进行投诉或者将它从组内剔除。验证如下：
   $$
   \begin{aligned}
    g^{f_l(i)}&=g^{a_{l0}+a_{l1}i+\dots+a_{l,t-1}i^{t-1}}\\
    &=\phi_{l0}\cdot\phi_{l1}^{i}\cdot\dots\cdot\phi_{l,t-1}^{i^{t-1}}
   \end{aligned}
   $$

3. 每个参与者$P_i$计算各自的签名私钥分片$s_i=f_1(i)+f_2(i)+\dots+f_n(i)$，并将$s_i$安全的长期保存，并删除 $f_l(i)$。
4. 每个 $P_i$ 计算自己的签名验证公钥 $Y_i=g^{s_i}$，计算组公钥 $Y=\Pi_{j=1}^n\phi_{j0}$。对于其他参与者$P_l$的公钥都是公开可验证的，通过计算如下 $Y_l$ ，也就是说其它参与者的验证公钥也可以本地计算，无需通信。
   $$
   Y_l=g^{\sum\limits_{j=1}^{n}f_{j}(l)}
   =\prod\limits_{j=1}^{n}g^{f_{j}(l)}
   =\prod\limits_{k=0}^{t-1}\phi_{jk}^{l^{k}\text{mod q}}
   $$
   这种公开可验证性使得参与者无法作恶，一旦作恶就会被发现。
#### Frost 预处理协议
图2: 预处理协议
![frost-prepro.png](https://img.learnblockchain.cn/attachments/2025/07/b0oJTrXB686e157ea9fd5.png)
本部分是Frost签名的第一阶段，也叫做预处理阶段。对于每个参与者来说，执行预处理协议，输入是 $\pi$ ，输出是 $\pi$ 个承诺对，$\pi$ 表示一次性产生承诺对的数量，如图所述，使用 $L_i$ 表示参与者 $P_i$ 生成的所有承诺对的列表。最后在一个预定的位置将$(i,L_i)$公布出去。这里的承诺事实上是为了做schnorr签名做准备的，将会出现在schnorr签名的承诺位置。

这里有个在实现过程中的话题需要讨论
- 公布承诺
  预处理协议要求参与者在某个商定的位置发布他们的承诺，例如承诺服务器，该服务器可以根据要求提供正确的（即有效和未使用的）承诺份额。若是恶意的，它可能会执行拒绝服务攻击，或者代表诚实的参与者提供过时或格式错误的承诺值。然而，仅仅访问参与者的公开发布的承诺集并不能授予任何额外的能力。

#### Frost 签名协议
图3：Frost 签名
![frost-sign.png](https://img.learnblockchain.cn/attachments/2025/07/0tZvIxIW686e15b1d0acf.png)
这部分是frost签名的第二个阶段，也叫单轮签名协议，该协议的输入是一个消息，输出是该消息的一个签名。这里有个角色 $\mathcal{SA}$，该角色是一个半可信的签名聚合者，它可以是一个组内节点，也可以是一个组外的节点。

$\mathcal{AS}$ 选择 $\alpha(t\le\alpha\le n)$ 个参与者（可能包含它自己）组成一个集合 $\mathcal{S}$ ，该集合就是对消息进行签名操作的参与者。

1. $\mathcal{SA}$ 从集合 $\mathcal{S}$ 中的每个参与者获取下一个可用的承诺对，从而构造一个有序列表 $B=\{(i,D_i,E_i)|i\in S\}$。
2. $\mathcal{SA}$ 将 $(m,B)$ 发送给 $S$ 中的每个参与者 $P_i$。
3. 每个参与者接收到 $(m,B)$ 之后，会验证 $m$ 和 $B$ 中承诺的有效性，如果验证失败则立马终止协议。
4. 每个参与者计算 $\rho_l=H_1(l,m,B),l\in S$，并计算出组承诺 $R=\prod\limits_{l\in S}D_l\cdot E_{l}^{\rho_l}$ ，计算挑战 $c=H_2(R,Y,m)$
5. $P_i$ 使用各自的签名私钥 $s_i$ 计算 $z_i=d_i+\rho_i\cdot e_i+\lambda_i\cdot s_i\cdot c$，其中是 $S$ 中第 $i$ 个拉格朗日系数，不明白的可以去看这篇文章[阈值组签名、分布式密钥生成DKG、BLS签名](https://learnblockchain.cn/article/15604)。
6. $P_i$ 将 $(d_i,D_i),(e_i,E_i)$ 从本地存储中删除，并将发送给 $\mathcal{SA}$。
7. 签名聚合者 $\mathcal{SA}$ 接收 $z_i$，并验证 $g^{z_i}\xlongequal{?} R_i\cdot Y_i^{c\cdot \lambda_i}$，$R_i$ 是对应参与者的承诺分片，$Y_i$ 是公钥分片，$i\in S$。如果没有验证通过，则对相应的参与者进行通报和指出并终止协议。\
计算组签名 $z=\sum z_i$，并发布 $m$ 的组签名是 $\sigma=(R,z)$。\
    组签名的验证如下：
    $$
    \begin{aligned}
        g^z & \xlongequal{?} g^{\sum z_i}\\
        &=\prod\limits_{i\in S}g^{z_i}\\
        &=\prod\limits_{i\in S}g^{d_i+\rho_i\cdot   e_i+\lambda_i\cdot s_i\cdot c}\\
        &=(\prod\limits_{i\in   S}D_i\cdot(E_i)^{\rho_i})\cdot(g^{\sum\limits _{i\in S}\lambda_is_i})^c\\
        &=R\cdot Y^c
    \end{aligned}
    $$
    事实上，$Y=g^{\sum\limits_{i\in S}\lambda_i s_i}$，令 $F(x)=\sum\limits_{l=1}^{n}f_l(x)$，所以$s_i=F(i),i\in S$，根据拉格朗日插值，$F(x)=\sum\limits_{i\in S}s_i\cdot h_i(x)$，$h_i(x)$是插值多项式且$\lambda_i=h_i(0)$，所以 $Y=g^{F(0)}=g^{\sum\limits_{i\in S}\lambda_i s_i}$
#### 安全性
Frost 签名包含两个阶段，预处理阶段和单轮的签名阶段，当然了，这两个阶段也可以合并，变成一个两轮的协议，可以根据实际的应用场景，选择合适的实现方式。

先说结论，Frost 协议在选择消息攻击下是可证明安全的。大体思路是这样的：论文中证明了 Frost 在选择消息攻击下具有存在不可伪造性，为了证明敌手在随机谕示模型下自适应的选择消息攻击下伪造一个 Frost 签名是困难的，可以归约到计算离散对数的困难性上。
### 总结
MPC 钱包在实现过程中，可采用 FROST 协议等分布式密钥生成技术来生成和管理密钥。例如，通过 FROST 协议，MPC 钱包能让多个参与者各自持有密钥分片，共同生成一个组密钥（组私钥无需完整恢复，可以完成组签名），之后在签名交易时，各参与者使用自己的密钥分片对交易进行签名生成签名，再由签名聚合者 $\mathcal{SA}$ 合并为完整组签名，实现钱包的签名功能，用户也无需记住和保存完整的密钥，增强加密系统的安全性和抵御单点故障能力，保障交易安全。

Schnorr 签名

上篇文章讲了schnorr 签名的原理，包括单签和多签，并对他们的安全性做了分析。本文继续讲一个新的阈值签名协议 Frost，本文内容来自于这篇文章，FROST: Flexible Round-Optimized Schnorr Threshold Signatures，是该文章的深刻解读。它是一种先进的阈值签名方案，基于 Schnorr 签名框架设计，专为多方安全计算和分布式系统进行优化。它允许一组参与者共同生成签名，而无需暴露各自的私钥分片，更无需恢复出完整的签名私钥，有效的保证了签名私钥的安全性，同时在效率、灵活性、容错率和安全性上达到了良好平衡。

该方案涉及 Shamir秘密分享、可验证的秘密分享、阈值签名、分布式密钥生成（DKG）、Schnorr签名等技术方案。

应用场景

区块链：
- 多签名钱包：如比特币的 MuSig2（FROST 的变种）。
- 分布式验证节点：降低单点故障风险（如 Cosmos 的 Tendermint 共识）。
- MPC 钱包：签名私钥分片存储，无需恢复完整签名私钥，容忍一定节点故障率。
密钥管理系统：
- 云服务提供商的密钥分片存储（如 AWS KMS）。
- 企业级密钥备份与恢复。
隐私保护协议：
- 与零知识证明结合，实现匿名多方签名。
- 去中心化身份认证（如 Sismo、Worldcoin）。
  核心特性
安全性
- 抗共谋攻击：少于 t 个参与者无法生成有效签名。
- 前向安全性：即使某个私钥分片泄露，过去的签名仍保持安全。
- 防篡改：任何参与者无法在其他参与者不知情的情况下修改签名。
效率
- 通信复杂度：两轮通信，每轮仅需广播少量消息（承诺和签名分片）。
- 计算复杂度：每个参与者的计算量与传统 Schnorr 签名相当。
- 无限制并行性：节点之间可以互不影响独立的生成签名分片。
灵活性
- 动态调整：支持添加 / 删除参与者，无需重新初始化整个系统。
- 门限调整：可动态调整阈值 t（需多数参与者同意）。
轮次优化：仅需两轮通信（预计算 + 签名生成），低于传统方案的三轮。

实现与开源库

Rust 实现：frost-rs（支持多种椭圆曲线）。
JavaScript 实现：js-frost（用于浏览器环境）。
应用案例：
- Zcash：计划用 FROST 改进其透明地址的多签功能。
- Blockstream：在侧链技术中使用 FROST 增强安全性。
  Frost:灵活的轮数优化的Schnorr阈值签名原理
  
  首先假设阈值签名方案拥有 $n$ 个参与者，要求至少 $t(t\leq n)$ 个参与者合作才能生成有效签名，记为 $(t,n)$ 阈值方案。本人给出一个使用Go语言开发的多方签名代码含frost，功能持续完善中。
  
  Frost KeyGen
  
  图 1：Frost 协议的分布式密钥生成算法 KenGen KeyGen 采用 Pedersen 分布式密钥生成（DKG）算法，这部分是Frost协议全局初始化的过程，通过秘密分享每个参与者生成各自的签名私钥分片以及对应的验证公钥分片，每个参与者本地计算其他参与者的验证公钥，本地计算阈值组公钥。本部分分为两轮：
第一轮
1. 对于每个参与者 $P_i$ 随机生成一个 $t-1$ 次多项式，即多项式系数都是随机生成的，如下： $$ \begin{aligned} fi(x)=a{i0}+a{i1}x+\dots+a{i,t-1}x^{t-1} \end{aligned} $$ 多项式要保密。
2. 每个参与者 $Pi$ 计算出一个对常数项秘密 $a{i0}$ 的一个知识证明 $\sigma_i$ ，熟悉密码学的一眼就能看出来，知识的证明其实就是一个身份认证协议，也是schnorr签名形式，目的是防止 rogue key 攻击，这一步是很容易理解的。
3. 每个参与者 $P_i$ 计算所有多项式系数的承诺 $\vec{C_i}$ ，如图所示。
4. 每个参与者 $P_i$ 广播系数承诺 $\vec{C_i}$ 以及常数项系数的知识证明 $\sigma_i$ ，供其他参与者进行验证。
5. 对于每个参与者 $P_i$ 接收到其他参与者的系数承诺以及常数项的知识证明，按照图中的形式进行验证知识证明的正确性，只要有一个没有通过验证，则立马终止协议，可以对作恶者进行投诉，或者不带它继续玩，由于DKG这一步是Frost协议全局初始化的过程，必须保证DKG过程正确生成，即所有参与者都是诚实的。
第二轮
1. 这一步是秘密分享，每个参与者 $P_i$ 计算针对参与者 $P_l(l \ne i)$ 的秘密分享 $(l,f_i(l))$ 安全地秘密地发送给$P_l$，并删除$f_i$和 $(l,f_i(l))$，自己保存$((i,f_i(i)))$。
2. 每个参与者 $P_i$ 秘密的接收到 $(l,f_l(i))$ 值，会进行验证，如有验证失败，立马终止协议，并对作恶的参与者进行投诉或者将它从组内剔除。验证如下： $$ \begin{aligned} g^{fl(i)}&=g^{a{l0}+a{l1}i+\dots+a{l,t-1}i^{t-1}}\ &=\phi{l0}\cdot\phi{l1}^{i}\cdot\dots\cdot\phi_{l,t-1}^{i^{t-1}} \end{aligned} $$

每个参与者$P_i$计算各自的签名私钥分片$s_i=f_1(i)+f_2(i)+\dots+f_n(i)$，并将$s_i$安全的长期保存，并删除 $f_l(i)$。
每个 $P_i$ 计算自己的签名验证公钥 $Y_i=g^{si}$，计算组公钥 $Y=\Pi{j=1}^n\phi_{j0}$。对于其他参与者$P_l$的公钥都是公开可验证的，通过计算如下 $Y_l$ ，也就是说其它参与者的验证公钥也可以本地计算，无需通信。 $$ Yl=g^{\sum\limits{j=1}^{n}f{j}(l)} =\prod\limits{j=1}^{n}g^{f{j}(l)} =\prod\limits{k=0}^{t-1}\phi_{jk}^{l^{k}\text{mod q}} $$ 这种公开可验证性使得参与者无法作恶，一旦作恶就会被发现。
Frost 预处理协议

图2: 预处理协议本部分是Frost签名的第一阶段，也叫做预处理阶段。对于每个参与者来说，执行预处理协议，输入是 $\pi$ ，输出是 $\pi$ 个承诺对，$\pi$ 表示一次性产生承诺对的数量，如图所述，使用 $L_i$ 表示参与者 $P_i$ 生成的所有承诺对的列表。最后在一个预定的位置将$(i,L_i)$公布出去。这里的承诺事实上是为了做schnorr签名做准备的，将会出现在schnorr签名的承诺位置。

这里有个在实现过程中的话题需要讨论

公布承诺预处理协议要求参与者在某个商定的位置发布他们的承诺，例如承诺服务器，该服务器可以根据要求提供正确的（即有效和未使用的）承诺份额。若是恶意的，它可能会执行拒绝服务攻击，或者代表诚实的参与者提供过时或格式错误的承诺值。然而，仅仅访问参与者的公开发布的承诺集并不能授予任何额外的能力。

Frost 签名协议

图3：Frost 签名这部分是frost签名的第二个阶段，也叫单轮签名协议，该协议的输入是一个消息，输出是该消息的一个签名。这里有个角色 $\mathcal{SA}$，该角色是一个半可信的签名聚合者，它可以是一个组内节点，也可以是一个组外的节点。

$\mathcal{AS}$ 选择 $\alpha(t\le\alpha\le n)$ 个参与者（可能包含它自己）组成一个集合 $\mathcal{S}$ ，该集合就是对消息进行签名操作的参与者。

$\mathcal{SA}$ 从集合 $\mathcal{S}$ 中的每个参与者获取下一个可用的承诺对，从而构造一个有序列表 $B={(i,D_i,E_i)|i\in S}$。
$\mathcal{SA}$ 将 $(m,B)$ 发送给 $S$ 中的每个参与者 $P_i$。
每个参与者接收到 $(m,B)$ 之后，会验证 $m$ 和 $B$ 中承诺的有效性，如果验证失败则立马终止协议。
每个参与者计算 $\rho_l=H1(l,m,B),l\in S$，并计算出组承诺 $R=\prod\limits{l\in S}Dl\cdot E{l}^{\rho_l}$ ，计算挑战 $c=H_2(R,Y,m)$
$P_i$ 使用各自的签名私钥 $s_i$ 计算 $z_i=d_i+\rho_i\cdot e_i+\lambda_i\cdot s_i\cdot c$，其中是 $S$ 中第 $i$ 个拉格朗日系数，不明白的可以去看这篇文章阈值组签名、分布式密钥生成DKG、BLS签名。
$P_i$ 将 $(d_i,D_i),(e_i,E_i)$ 从本地存储中删除，并将发送给 $\mathcal{SA}$。
签名聚合者 $\mathcal{SA}$ 接收 $z_i$，并验证 $g^{z_i}\xlongequal{?} R_i\cdot Y_i^{c\cdot \lambda_i}$，$R_i$ 是对应参与者的承诺分片，$Y_i$ 是公钥分片，$i\in S$。如果没有验证通过，则对相应的参与者进行通报和指出并终止协议。\ 计算组签名 $z=\sum z_i$，并发布 $m$ 的组签名是 $\sigma=(R,z)$。\ 组签名的验证如下： $$ \begin{aligned} g^z & \xlongequal{?} g^{\sum zi}\ &=\prod\limits{i\in S}g^{zi}\ &=\prod\limits{i\in S}g^{d_i+\rho_i\cdot e_i+\lambda_i\cdot si\cdot c}\ &=(\prod\limits{i\in S}D_i\cdot(E_i)^{\rhoi})\cdot(g^{\sum\limits {i\in S}\lambda_isi})^c\ &=R\cdot Y^c \end{aligned} $$ 事实上，$Y=g^{\sum\limits{i\in S}\lambda_i si}$，令 $F(x)=\sum\limits{l=1}^{n}f_l(x)$，所以$si=F(i),i\in S$，根据拉格朗日插值，$F(x)=\sum\limits{i\in S}s_i\cdot h_i(x)$，$h_i(x)$是插值多项式且$\lambda_i=hi(0)$，所以 $Y=g^{F(0)}=g^{\sum\limits{i\in S}\lambda_i s_i}$
安全性

Frost 签名包含两个阶段，预处理阶段和单轮的签名阶段，当然了，这两个阶段也可以合并，变成一个两轮的协议，可以根据实际的应用场景，选择合适的实现方式。

先说结论，Frost 协议在选择消息攻击下是可证明安全的。大体思路是这样的：论文中证明了 Frost 在选择消息攻击下具有存在不可伪造性，为了证明敌手在随机谕示模型下自适应的选择消息攻击下伪造一个 Frost 签名是困难的，可以归约到计算离散对数的困难性上。

总结

MPC 钱包在实现过程中，可采用 FROST 协议等分布式密钥生成技术来生成和管理密钥。例如，通过 FROST 协议，MPC 钱包能让多个参与者各自持有密钥分片，共同生成一个组密钥（组私钥无需完整恢复，可以完成组签名），之后在签名交易时，各参与者使用自己的密钥分片对交易进行签名生成签名，再由签名聚合者 $\mathcal{SA}$ 合并为完整组签名，实现钱包的签名功能，用户也无需记住和保存完整的密钥，增强加密系统的安全性和抵御单点故障能力，保障交易安全。