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{array}{rl}{\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{array}$$ 从而可知 ${\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{array}{rl}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{array}$$

FROST 签名第二轮操作：Signature Aggregator 选择 $\alpha (t\le \alpha \le n)$ 个参与者，记这个 $\alpha$ 个参与者所拥有的私钥分片对应的 $x$ 轴坐标的集合为 $S$ ，Signature Aggregator 把收集来的 $D_i,E_i$ 组成一个列表 $B={⟨(i,D_i,E_i)⟩}_{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{array}{rlr}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{array}$$

下面讨论 $z$ 的正确性：
$$\begin{array}{rlr}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{array}$$

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