Schnorr阈值签名方案：FROST

# Schnorr阈值签名方案：FROST

## 介绍

FROST(Flexible Round-Optimized Schnorr Threshold Signatures)是一种灵活的回合优化Schnorr阈值签名方案，它减少了签名操作中的网络开销，同时改进了Schnorr阈值签名协议的技术水平，因为它可以在单轮中安全地执行签名操作而不限制签名操作的并发性，但又允许真正的阈值签名，因此签名操作只需要阈值数量的参与者。

FROST既可以作为签署者总共发送和接收两条信息的两轮协议，也可以优化为具有预处理阶段的（非广播）单轮签署协议。FROST在没有参与者行为不当的乐观情况下，实现了效率的提高。因为预处理回合可以与签名回合分开进行，所以签名操作可以异步进行；一旦预处理回合完成，签名者只需要接收并最终回复一个消息就可以创建一个签名。

FROST实现其效率改进的部分原因是允许协议在存在行为不端的参与者时中止（该参与者随后被识别并被排除在未来的操作之外）--这是实际部署场景的合理模式。在协议过程中，如果有行为不端的参与者提供畸形的值，诚实的各方可以识别并排除行为不端的参与者，并重新运行协议。FROST的灵活设计使其能够支持阈值签名的许多实际使用情况。此外，虽然一些阈值方案要求所有参与者在签名操作期间都是活跃的，并将协议的阈值属性仅仅称为安全属性，但FROST允许任何阈值数量的参与者产生有效签名。因此，FROST可以支持参与者（或参与设备）的一个子集可以保持离线的用例，这一属性在实践中往往是安全所需要的。

## 背景

### 阈值签名方案

阈值签名方案是一种密码学基本原理，用于促进一组参与者对私钥的共同所有权，这样一来，阈值数量的参与者必须合作签发一个可由单一公共密钥验证的签名。阈值签名在一系列需要在一组同等信任的各方之间建立分布式信任根的情况下是有用的。与单方环境中的签名操作类似，阈值签名方案的一些实现需要在大规模和重负荷下执行签名操作。例如，阈值签名可以被一组签名者用来验证加密货币中的金融交易，或签署由一组受信机构产生的网络共识。在这两个例子中，随着签署方或签署操作数量的增加，除了每个签署者所经历的负载增加外，参与者之间为产生联合签名所需的通信轮数也成为性能瓶颈。当签名者利用网络有限的设备或不可靠的网络进行传输，或希望允许签名者异步参与签名操作的协议时，这个问题会进一步恶化。因此，优化签名操作的网络开销对阈值签名的实际应用非常有利。

### Shamir密钥共享

许多阈值方案建立在Shamir秘密共享的基础上，这是一个(t,n)的阈值签名方案，依靠拉格朗日插值来恢复秘密。在Shamir秘密共享中，一个受信任的中央经销商将一个秘密s分发给n个参与者，其方式是任何合作的t个参与者的子集都可以恢复该秘密。为了分配这个秘密，庄家首先随机选择t-1个系数a1，...，at-1，并使用随机选择的值作为系数来定义一个度数为t-1的多项式f（x）=s+SUM（ai xi，i=1...t-1），其中f（0）=s，随后每个参与者Pi的秘密份额是（i，f（i）），庄家被信任为诚实地分配给每个参与者P1，...，Pn。为了重建秘密，至少有t个参与者进行拉格朗日插值来重建多项式，从而找到值s=f(0)。然而，少于t个参与者的小组不能重建秘密，因为至少需要t个点来重建t-1度的多项式。

### Feldman的可验证密钥共享

Feldman的可验证秘密共享（VSS）方案建立在Shamir秘密共享的基础上，增加了一个验证步骤，以证明参与者的共享与公共承诺的一致性，该承诺被认为对所有参与者是正确可见的。为了验证一个共享的形成，每个参与者用这个承诺来验证他们的共享。如果验证失败，参与者可以对经销商发出投诉，并采取诸如向所有其他参与者广播这一投诉的行动。FROST也同样使用了这种技术。在Feldman的方案中产生的承诺如下。如同之前的Shamir秘密分享一样，庄家对t-1个随机值（a1，...，at-1）进行采样，并将这些值作为系数来定义一个度数为t-1的多项式fi，使得f(0)=s。然而，在向每个参与者Pi分发私人份额（i，f(i)）的同时，庄家也分发了公共承诺C = < A0, ..., At-1 >，其中A0 = gs，Aj = g^{aj}。

请注意，在分布式设置中，每个参与者Pi必须确保与所有其他参与者对C有相同的看法。在实践中，实现者通过使用一些技术来保证参与者观点的一致性，例如将承诺发布到一个集中的服务器上，该服务器被信任为向所有参与者提供单一的观点，或者增加另一个协议回合，参与者比较他们收到的承诺值以确保它们是相同的。

### 分布式密钥生成

与Shamir秘密共享等依赖于可信交易商的阈值方案不同，分布式密钥生成（DKG）确保每个参与者对共享秘密的生成做出同等贡献。在协议运行结束时，所有参与者共享一个联合公钥Y，但每个参与者只持有相应秘密的份额，因此没有任何一组小于阈值的参与者知道。分布式密钥生成（DKG）通过使每个参与者对共享秘密的生成做出同等贡献来支持这种威胁模型。在协议运行结束时，所有参与者共享一个联合公钥Y，但每个参与者只持有相应秘密s的一个份额si，这样就没有小于阈值的参与者集合知道s。

### Schnorr签名

通常，由阈值签名操作产生的签名最好与单个参与者产生的签名无法区分，从而与现有系统保持向后兼容，并防止个别签名者身份的隐私泄露。由FROST签名操作产生的签名与Schnorr签名不可区分，因此可使用标准的Schnorr验证操作进行验证。为此，我们现在描述单签名者设置中的Schnorr签名和验证操作[Sch89]。

Schnorr签名生成:

)

第一步生成随机数k，然后用k生成随机点R

第二步通过哈希随机点R和公钥Y和消息m生成挑战c

第三步用私钥s通过k+s*c计算出z

第四步将R和z组合生成签名

Schnorr签名验证:


第一步从签名中解析出R和z，然后计算出c

第二步由Z = R + Y*c计算出R'，Z是由z生成的点

第三步判断计算出的R'与解析出的R是否一致

### 加法秘密共享

与上述的单签类似，FROST要求为每个签名操作生成一个随机数 k。然而，在阈值签名中，应该是每个参与者都要参与k的生成，但不知道它的结果。虽然Shamir秘密共享和其派生结构要求共享在秘密多项式f上，其中f(0)=s，但加法秘密共享方案允许t个参与者共同计算一个共享秘密s，每个参与者Pi贡献一个值si，这样得到的共享秘密是s=SUM(si, i=1...t)，即每个参与者的份额之和。因此，这种t-out-of-t的秘密共享可以非交互式地进行；每个参与者直接选择自己的si。其中，si是s的加性秘密共享，那么s是si的总和，那么(si)/(Li)是相同s的Shamir秘密共享，其中Li是Lagrange系数。在FROST中，参与者在签名操作中使用这种技术非交互式地生成一个一次性的秘密nonce，它是所有t个签名参与者之间共享的Shamir秘密。

## FROST方案

我们现在描述 FROST 协议，这是一种灵活的轮次优化 Schnorr 阈值签名方案，它最大限度地减少了在阈值设置中生成 Schnorr 签名的网络开销，同时允许签名操作的不受限制的并行性和签名参与者的阈值数量。

### 密钥生成

Round 1:

1.每个参与者Pi都会抽取t个随机值（ai0, ..., ai(t-1)）) <-$-Zq，并使用这些值作为系数来定义Zq上度数为t-1的多项式fi(x) = SUM(aij xj, j=0...t-1)。

2.每个 Pi 通过使用 ai0 作为密钥计算 Schnorr 签名 SIGi = (wi, ci) 来计算对应秘密 ai0 的知识证明，使得 k <-$- Zq, Ri = gk, ci = H(i, CTX, g^{ai0}, Ri), wi = k + ai0* ci，其中 CTX 是防止重放攻击的上下文字符串。

3.每个参与者Pi计算一个公共承诺Ci = < Ai0, ..., Ai(t-1) >，其中Aij = g^{aij}, 0 <= j <= t-1

4.每个Pi向所有其他参与者广播Ci, SIGi。

5.在收到来自参与者1 <= p <= n, p != i的Cp、SIGp后，参与者Pi验证SIGp = (wp, cp)，失败时终止，检查：cp =?= H(p, CTX, Ap0, g^{wp} * Ap0^{ cp})

Round2：

1.每个Pi向其他参与者Pp安全地发送一个秘密份额（p，fi(p)），并为自己保留（i，fi(i)）。

2.每个 Pi 通过计算：g^{fp(i)} =?= PROD(Apk(i^k mod q),k=0...t-1) 来验证他们的份额，如果检查失败则中止。

3.每个Pi通过计算si = SUM(fp(i), p=1...n)来计算他们长期存在的私人签名份额，并安全地存储si。

4.每个 Pi 计算他们的公共验证份额 Yi = g^{si}，以及该组的公钥 Y = PROD(Aj0, j=1...n)。任何参与者都可以通过计算 Yi = PROD( (Ajk)(i^k mod q), j=1...n, k=0...t-1) 来计算任何其他参与者的公开验证份额。

### 预处理


1.创建一个空列表 Li。然后，对于 1 <= j <= Q，执行以下操作：

- 单次使用的nonces样本（dij, eij）<-$- Zq* x Zq*

- 得出承诺份额（Dij，Eij）=（g^{dij}^，g^{eij}^）

- 将（Dij, Eij）附加到Li。存储((dij, Dij), (eij, Eij))，以便以后在签名操作中使用

2.将(i, Li)发布到一个预定的位置，这个位置由实施者指定。

### 签名


令SA表示签名集合者（他自己可以是t个签名参与者之一），S是被选中用于该签名操作的参与者的集合，B = < (i, Dij, Eij) for i in S> 表示对应于每个参与者Pi的参与者索引的有序列表，Li是在预处理阶段公布的Pi的可用承诺值的集合。每个标识符i与Pi公布的第j个承诺（Dij，Eij）相耦合，这些承诺将用于这个特定的签名操作。让H1、H2是哈希函数，其输出在Zq*。

1.SA 首先从 Li 获取 S 中每个参与者 Pi 的下一个可用承诺并构造 B。

2.对于 S 中的每个 i，SA 向 Pi 发送元组 (m, B)。

3.收到 (m, B) 后，每个 Pi 首先验证消息 m，然后检查 G* 中的 Dp j、Ep j 以获取 B 中的每个承诺，如果任一检查失败则中止。

4.然后，每个Pi计算出绑定值的集合rp = H1(p, m, B), p在S中。然后每个Pi得出组承诺R = PROD(Dpj * (Epj)^{rp}, p在S中)，以及挑战c = H2(m, R)。

5.每个Pi通过计算zi = dij + (eij * ri) + Li * si * c，使用他们的长期秘密共享si计算他们的响应，使用S来确定Li。

6.每个Pi从他们的本地存储中安全地删除((dij，Dij),(eij，Eij))，然后将zi返回给SA。

7.签名聚合器 SA 执行以下步骤：

- 推导出ri = H1(i,m,B)，Ri = Dij * (Eij)^{ri}，用于S中的i，随后R=PROD(Ri, i in S)，c = H2(m,R)

- 通过检查 g^{zi} =?= Ri * {Yi}^{c * Li} 为每个签名共享 zi, i 在 S 中验证每个响应的有效性。如果不相等，首先识别并报告行为不当参与者，然后中止。否则，继续

- 计算组的响应 z = SUM(zi, i in S)

- 将签名SIG = (z, c) 与信息m一起发布

SA最后检查每个参与者报告的zi与他们的承诺份额（Dij，Eij）和他们的公钥份额Yi是否一致。如果每个参与者都发出了正确的zi，那么zi值的总和与c一起构成了m上的Schnorr签名。这个签名将被一个不知道FROST被用来生成签名的验证者正确验证，他用标准的单方Schnorr验证方程与Y作为公钥进行验证（第2.4节）。

处理短暂的未决份额。由于在预处理算法中描述的预处理阶段产生的每个nonce和承诺份额最多只能使用一次，参与者在签字操作中使用这些值后将其删除，如签字算法的步骤5所示。一个意外重用的(dij, eij)会导致参与者的长期秘密si的暴露，所以参与者必须安全地删除它们，并像任何Schnorr签名的实现一样防御快照回滚攻击。然而，如果SA在签名协议期间选择重新使用一个承诺集（Dij，Eij），这样做只是导致参与者Pi中止协议，因此不会增加SA的权力。

## 总结

总的来说，FROST通过定义一个可以优化为具有预处理阶段的（非广播）单轮操作的签名协议，改进了Schnorr阈值签名的技术状况。 与许多先前的Schnorr阈值方案不同，FROST在不限制签名操作的并发性的情况下，对已知的伪造攻击仍然安全。