Schnorr Threshold Signature (FROST)

对于门限方案 \((t,n)\) ，当 Keygen 协议结束后，每个参与者 \(P_i, i=\{1,2,\cdots,n\}\) 会得到：

1. \(P_i\) 的私钥分片 \(s_i = F(i)\) ，而完整的私钥 \(s = F(0)\) ，其中 \(F(x)\) 是某个 \(t-1\) 次多项式。也就是说 \(n\) 个私钥分片就是 \(t-1\) 次曲线上的 \(n\) 个点 \((1, s_1), (2, s_2), \cdots, (n, s_n)\) 。
   
2. 所有参与者私钥分片 \(s_j, j=\{1,2,\cdots,n\}\) 所对应的 commitment \(Y_j = g^{s_j}\) 。
   

下面介绍一下完整私钥 \(s\) 和私钥分片 \(s_i\) 的关系。假设 \(\alpha\) 是参与签名的参与者数量，满足 \(t \le \alpha \le n\) ，这 \(\alpha\) 个参与者所拥有的私钥分片对应的 \(x\) 轴坐标的集合为 \(S=\{p_1, \cdots, p_{\alpha}\}\) ，设 \(\lambda_i\) 为拉格朗日系数，即： \[\lambda_i = \prod_{j=1,j \ne i}^{\alpha} \frac{p_j}{p_j - p_i}\] 根据拉格朗日插值相关知识可知 \(s\) 和 \(s_i\) 满足关系： \[s = \sum_{i\in S} \lambda_i \cdot s_i\]

下面通过实例来验证一下上面的结论。假设门限方案 \((t,n) = (3,5)\) ，也就是说共有 \(5\) 个参与者，至少需要 \(3\) 个参与者合作才能完成签名。Keygen 时的 \(t-1\) 次多项式为 \(F(x)=2x^{2} - 5x + 4\) ，Keygen 结束后得到的 \(5\) 个私钥分片分别为 \((1, 1),(2, 2),(3, 7),(4, 16),(5, 29)\) ，完整的私钥 \(s=F(0)=4\) ，假设某次签名时，选择了其中 \(4\) 个参与者 \(P_1, P_2, P_3, P_5\) ，这个例子中 \(S=\{1,2,3,5\}\) ，下面来验证一下 \[s \stackrel{?}{=} \lambda_1 s_1 + \lambda_2 s_2 + \lambda_3 s_3 + \lambda_5 s_5\] 是否成立。

由于 \[\begin{aligned} \lambda_1 \cdot s_1 &= \frac{2}{2-1} \cdot \frac{3}{3-1} \cdot \frac{5}{5-1} \cdot s_1 = \frac{15}{4} \cdot s_1 = \frac{15}{4} \\ \lambda_2 \cdot s_2 &= \frac{1}{1-2} \cdot \frac{3}{3-2} \cdot \frac{5}{5-2} \cdot s_2 = -5 \cdot s_2 = -10 \\ \lambda_3 \cdot s_3 &= \frac{1}{1-3} \cdot \frac{2}{2-3} \cdot \frac{5}{5-3} \cdot s_3 = \frac{5}{2} \cdot s_3 = \frac{35}{2} \\ \lambda_5 \cdot s_5 &= \frac{1}{1-5} \cdot \frac{2}{2-5} \cdot \frac{3}{3-5} \cdot s_5 = -\frac{1}{4} \cdot s_5 = -\frac{29}{4} \\ \end{aligned}\] 从而可知 \(\lambda_1 s_1 + \lambda_2 s_2 + \lambda_3 s_3 + \lambda_5 s_5 = 4\) ，显然它就是完整私钥 \(s\) 。

FROST 签名第一轮操作：每个签名参与者随机选择 \(d_i, e_i\) （需要暂存起来，第二轮操作时需要用到），计算出 \(D_i = g^{d_i}, E_i=g^{e_i}\) ，然后把 \(D_i, E_i\) 发送给 Signature Aggregator。

先介绍几个记号定义 \[\begin{aligned} k &= \sum_{i \in S} k_i \\ k_i &= d_i + e_i \cdot \rho_i \\ R_i &= g^{k_i} = g^{d_i + e_i \cdot \rho_i} = D_i \cdot (E_i)^{\rho_i} \end{aligned}\]

FROST 签名第二轮操作：Signature Aggregator 选择 \(\alpha (t \le \alpha \le n)\) 个参与者，记这个 \(\alpha\) 个参与者所拥有的私钥分片对应的 \(x\) 轴坐标的集合为 \(S\) ，Signature Aggregator 把收集来的 \(D_i, E_i\) 组成一个列表 \(B = \left<(i, D_i, E_i)\right>_{i \in S}\) ，然后和待签名消息 \(m\) 一起发送给这 \(\alpha (t \le \alpha \le n)\) 个参与者；签名参与者收到 \((m,B)\) 后，按图 2 中的方式计算出 \(z_i\) 后，把 \(z_i\) 发送给 Signature Aggregator；Signature Aggregator 收到 \(z_i\) 后，验证每个 \(z_i\) 对于 \(g^{z_i} \stackrel{?}{=} R_i \cdot Y_i^{\lambda_i \cdot c}\) 成立是否（为什么它会成立呢？这是因为 \(z_i\) 可以看作是把 \(\lambda_i \cdot s_i\) 当作完整私钥所对应的签名数据，这时完整公钥是 \(g^{\lambda_i \cdot s_i} = Y_i^{\lambda_i}\) ，验证 \(g^{z_i} \stackrel{?}{=} R_i \cdot Y_i^{\lambda_i \cdot c}\) 其实就是验证一个常规的 Schnorr 签名），如果成立，则把 \(z = \sum z_i\) 作为最终的签名数据 \(z\) 。而签名数据的另一部分 \(R = \prod_{i \in S} D_i \cdot (E_i)^{\rho_i}\) ，其中 \(D_i,E_i\) 是公开数据，而 \(\rho_i\) 也可以利用公开数据算出来的，所以 \(R\) 容易算出来。

为什么 FROST 协议会产生和常规的 Schnorr 签名（参见节 2.1）相同的签名数据呢？Schnorr 签名数据分为 \(R,z\) 两部分，下面分别讨论 \(R,z\) 的正确性。

下面讨论 \(R\) 的正确性：
\[\begin{aligned} R &= g^k & \text{(这是常规 Schnorr 计算 R 的方式)}\\ &= g^{\sum_{i \in S} k_i} \\ &= g^{\sum_{i \in S} (d_i + e_i \cdot \rho_i)} \\ &= \prod_{i \in S} R_i \\ &= \prod_{i \in S} D_i \cdot (E_i)^{\rho_i} & \text{(这是 FROST Schnorr 计算 R 的方式)}\\ \end{aligned}\]

下面讨论 \(z\) 的正确性：
\[\begin{aligned} z &= k + s \cdot c & \text{(这是常规 Schnorr 计算 z 的方式)}\\ &= \sum_{i \in S} k_i + s \cdot c \\ &= \sum_{i \in S} (d_i + e_i \cdot \rho_i) + s \cdot c & \text{(假设 s = Σ λᵢ sᵢ)}\\ &= \sum_{i \in S} (d_i + e_i \cdot \rho_i) + \sum_{i\in S} \lambda_i \cdot s_i \cdot c \\ &= \sum_{i \in S} (d_i + e_i \cdot \rho_i + \lambda_i \cdot s_i \cdot c) \\ &= \sum_{i \in S} z_i & \text{(这是 FROST Schnorr 计算 z 的方式)}\\ \end{aligned}\]

在上面推导中用到了等式 \(s = \sum_{i\in S} \lambda_i \cdot s_i\) ，它是否成立呢？答案是肯定的，参考节 3.1.1 。至此，我们已经证明了 FROST 协议产生的签名数据和常规的 Schnorr 签名一样。