Schnorr签名

2021-04-15 本文已影响0人雪落无留痕

Schnorr签名由Claus Schnorr于2008年提出，区块链协议公司Blockstream的密码学家Gregory Maxwell、Pieter Wuille等人，则在2018年提出了一种名为MuSig的Schnorr签名方案。

Schnorr签名

Schnorr签名使用点 $R$ 和标量 $s$ 来生成签名， $R$ 是椭圆曲线上的一随机点： $R=k\cdot G$ ，签名第2部分为： $s = k + H(P,R,m)\cdot sk$ , 其中 $sk$ 为私钥， $P = sk\cdot G$ 为公钥， $m$ 为消息，采用下式验证签名的有效性：
$s\cdot G =R+H(P,R,m)\cdot P$

批量验证

要验证网络上的区块，要保证区块中所有交易的签名是有效的。对于ECDSA签名，每个签名必须单独验证，通过使用Schnorr签名，可以将所有的签名相加，从而节省一些算力。对于1000个签名的区块而言，需要验证：
$(s_1+s_2+\cdots+s_{1000})\cdot G = \\ (R_1+R_2+\cdots+R_{1000}) + H(P_1, R_1, m_1)\cdot P_1+\cdots + H(P_{1000}, R_{1000}, m_{1000})\cdot P_{1000}$

密钥聚合

对于比特币2-of-2多重签名，采用ECDSA需要两个单独的签名。使用Schnorr签名，可以使用一对私钥 $(sk_1, sk_2)$ , 并生成一个与共享公钥 $P=P_1+P_2=sk_1\cdot G+sk_2\cdot G$ 对应的共享签名。要生成这个签名，需要分别选择随机数 $k_1$ 和 $k_2$ ，生成随机点 $R_1 = k_1\cdot G$ , $R_2=k_2\cdot G$ ，将它们相加计算一个公共的Hash值 $H(P, R_1+R_2, m)$ , 再分别计算签名： $s_i=k_i+H(P,R,m)\cdot sk_i$ ，得到 $s_1$ 和 $s_2$ 。将得到的签名相加，使用 $(R, s) = (R_1+R_2, s_1+s_2)$ 作为共享公钥 $P$ 的签名。其它人无法确认它是否为聚合签名，因为它和普通的Schnorr签名一致。

这种构造存在三个问题：

（1）要对交易进行签名，需要进行多轮通信，计算公共的 $R$ ，再进行签名。

（2）恶意密钥攻击，若某一参与方被黑客攻击，并假装公钥为 $P_1-P_2$ , 则它可以用 $P_1$ 私钥 $sk_1$ 控制共享资金。

（3）不能使用确定性 $k$ 进行签名，对于2-2签名，若黑客获得一对有效的签名： $(R_1, s_1, R_2, s_2)$ 和 $(R_1', s_1', R_2,s_2')$ , 其中 $R_2$ 是相同的, 但 $R=R_1+R_2$ 和 $R'=R_1'+R_2$ , 可以计算出第二个私钥：
$s_2 -s_2' = (H(P,R_1+R_2,m)-H(P,R_1'+R_2,m))\cdot sk_2 \\ sk_2 = \frac{(s_2-s_2')}{H(P,R_1+R_2,m)-H(P,R_1'+R_2,m)}$
因此需要使用好的随机数生成器使用密钥聚合。

MuSig

MuSig解决了第2个问题，使得攻击者无法盗取密钥。聚合签名对应于聚合公钥，此时不将所有签名者公钥相加，而是乘以某个因子，聚合的公钥为： $P=H(L,P_1)*P_1+\cdots+H(L,P_n)*P_n$ , 此处 $L=H(P_1,\cdots, P_n)$ 为取决于所有公钥的公用数字，其非线性特性可以防止攻击者构造恶意的公钥。

为了生成签名，每个联合签名者选择一个随机数 $k_i$ , 并与其他人共享 $R_i=k_i*G$ , 再将这些随机点加在一起，得到 $R=R_1+\cdots+R_n$ ，生成签名 $s_i=k_i+H(P,R,m)\cdot H(L,P_i)\cdot sk_i$ ，生成的聚合签名为： $(R,s)=(R_1+\cdots +R_n, s_1+\cdots+s_n)$ , 验证方程为：
$s\cdot G=R+H(P,R,m)\cdot P$