BLS Threshold Signature
Table of Contents
1. 简介
本文将介绍 BLS 门限签名，它比 ECDSA 门限签名要简单很多。
1.1. 标准的 BLS 签名
BLS 签名利用了 Pairing，记私钥为整数 \(k\) ，则公钥为 \(P=k \cdot G\) （这里 \(G\) 是曲线 \(G_1\) 的 Generator）；对消息 \(m\) ，将其映射到曲线 \(G_2\) 上的一个点，记为 \(H(m)\) ， 消息 \(m\) 的签名数据为 \(S=k \cdot H(m)\) 。 显然，公钥 \(P\) 是曲线 \(G_1\) 上的点，而签名数据 \(S\) 则是另一曲线 \(G_2\) 上的点。
要验证签名时，验证 \(e(P,H)=e(G,S)\) 是否成立即可（这里的 \(e\) 就是 Pairing 运算）。证明如下： \[e(P,H) = e(kG,H) = e(G, H)^k = e(G, kH) = e(G,S)\]
1.2. Lagrange 插值
在介绍 BLS 门限签名前，先介绍一下 Lagrange 插值，这是后面介绍的 BLS 门限签名的基础。
已知 \(t-1\) 次曲线 \(f(x)\) 上的 \(t\) 个点 \((x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)\) ，则这个 \(t-1\) 次曲线可由下式确定 \[\begin{aligned}f(x) = & \frac{(x-x_2)(x-x_3)\cdots(x-x_t)}{(x_1 - x_2)(x_1 - x_3)\cdots(x_1 - x_t)}y_1 + \frac{(x-x_1)(x-x_3)\cdots(x-x_t)}{(x_2 - x_1)(x_2 - x_3)\cdots(x_2 - x_t)}y_2 + \cdots \\ & + \frac{(x-x_1)(x-x_2)\cdots(x-x_{t-1})}{(x_t - x_1)(x_t - x_2)\cdots(x_t - x_{t-1})}y_t \end{aligned}\]
对于 \(x=0\) 的特殊情况，从上式可得零点函数值为 \[f(0) = \sum_{i=1}^{t} \left( \prod_{j=1,j\ne i}^t \frac{x_j}{x_j - x_i} \right) y_i\]
2. BLS 门限签名
设共有 \(n\) 个参与者，下面将介绍一个门限为 \(t\) 的 BLS 签名方案，即生成群体签名时至少需要 \(t\) 个参与者配合（小于 \(t\) 个参与者不能生成群体签名）。
这里关注的重点是签名方案，不关心它的 DKG 方案。假设采用 Shamir's Secret Sharing 方案，Trusted Dealer 把群体私钥 \(k\) 做为某个 \(t-1\) 次多项式 \(x=0\) 时的值 \(f(0)\) ，这个多项式中取 \(n\) 个点 \((x_1,k_1),\cdots, (x_n,k_n)\) ，分别发送给 \(n\) 个参与者。
任何 \(t\) 个参与者，利用 \((x_1,k_1),\cdots, (x_t,k_t)\) 可以恢复出完整私钥 \[k = \sum_{i=1}^{t} \left( \prod_{j=1, j \neq i}^{t} \frac{x_j}{x_j - x_i} \right) k_i\]
BLS 门限签名的思路： 每个参与者把 \(k_i\) 作为 BLS 私钥生成签名 \(S_i = k_i \cdot H(m)\) ，发送给其它的参与者；每个参与者收集到其它人发来的签名后，进行签名校验，一旦收集到 \(t\) 个通过校验的合法签名后，把这 \(t\) 个签名 \(S_i\) 通过 Lagrange 插值计算出对应的零点函数值，把它记为 \(S\) ， \(S\) 就是群体签名。
下面验证一下 \(S\) 确实是群体私钥 \(k\) 对应的签名 \[\begin{aligned}
S &\triangleq \sum_{i=1}^{t} \left( \prod_{j=1, j \neq i}^{t} \frac{x_j}{x_j - x_i} \right) \cdot S_i\\
&= \sum_{i=1}^{t} \left( \prod_{j=1, j \neq i}^{t} \frac{x_j}{x_j - x_i} \right) \cdot (k_i \cdot H(m)) \\
&= \left( \sum_{i=1}^{t} \left( \prod_{j=1, j \neq i}^{t} \frac{x_j}{x_j - x_i} \right) k_i \right) \cdot H(m) \\
&= k \cdot H(m) \\
\end{aligned}\]