Schnorr

Schnorr 签名基于有限域椭圆曲线, 与 ECDSA 类似, 但是 Schnorr 相对于 ECDSA 来说, 更快速, 并且可以实现多签聚合。

假设有通信双方 A 和 B, 已知椭圆曲线 $E_p(a, b)$ 、基点 $G$、 $G$ 的阶 $n$，要签名的消息 $m$。

A 生成自己的公钥和私钥，即从 $\{1,\cdots,n-1\}$ 随机选择一个数 $k_A$ 作为私钥，公钥 $H_A=k_AG$

A 签名过程如下:

• 在$\{1,\cdots,n-1\}$ 中选择一个数 $k$
• 计算点 $R$ 的坐标: $R = kG$
• 将要签名的消息 $m$、公钥 $H_A$、$R$ 的 $x$ 坐标组合进行哈希运算, 得到 $e=\mathrm{Hash}(R_x \ || \ H_A|| \ m) \mod n$
• 计算 $s = k + e \cdot k_A \mod n$

最终签名结果是 $(R_x, s)$

已知要签名的消息 $m$ 、签名数据 $(R_x, s)$、A 的公钥 $H_A$, B 验证过程如下:

• 计算哈希值 $e = \mathrm{Hash}(R_x \ || \ H_A|| \ m)$。
• 验证等式: $sG = R_x + eH_A$ 是否成立。

证明:

当 $k + e \cdot k_A$ 结果等于 $s$ 时, 则说明签名有效。

Schnorr 另一个重要的特征是聚合签名。聚合签名用于将多个签名数据聚合成一个签名数据, 从而减少总签名数据的大小, 降低交易费用。

聚合签名的过程如下:

• 对于每一个签名的参与者使用同一种椭圆曲线和基点 $G$, 生成各自的私钥 $k_m$ 和公钥 $P_i$。

• 每个参与者选择不同的随机数 $k_i$, 并计算对应的 $R_i = k_iG$

• 与单签不同的, 聚合签名计算 $e$ 时需要每一个签名参与者的公钥聚合, 以及 $R_i$ 聚合。公钥和 $R_i$ 都是有限域椭圆曲线上的点。聚合最简单的方式是点加: 将 $P_i$ 依次相加得到聚合公钥点 $P_{agg} = \sum P_i$, 将 $R_i$ 依次相加得到聚合点 $R_{agg} = \sum R_i$

• 计算哈希值 $e = \mathrm{Hash}(R_{agg} \ || \ P_{agg}|| \ m)$

• 每个签名的参与者使用各自的私钥 $k_m$ 以及 选择的随机 $k_i$ 计算各自的 $s_i = k_i + e \cdot k_m \mod n$

• 计算聚合签名 $s_{agg} = \sum s_i \mod n$, 这里的加法是算术加法。

• 最终的聚合签名是 $(R_{agg}, s_{agg})$

验证聚合签名时, 只需验证等式 $s_{agg}G = R_{agg} + eP_{agg}$ 是否成立。