1. ECDSA

ECDSA，全称为Elliptic curve Digital Signature Algorithm，采用Elliptic curve cryptography来实现的数字签名算法。

目前Bitcoin采用的是ECDSA签名方案。

公私钥对$(pk,P)$(pk,P)，其中公钥$P=pk\times G$P=pk×G，$G$G为所选椭圆曲线的base point。（elliptic curve base point: a point on the curve that generates a subgroup of large prime order $n$n。 $n\times G=\mathcal{O}$n×G=O, $\mathcal{O}$O is the identity element。）

1.1 ECDSA签名

ECDSA对消息$m$m的签名流程为：

• 1）计算消息$m$m的hash值：$e=hash(m)$e=hash(m)。（hash函数可为SHA-2，输出转换为数值。）
• 2）若group order $n$n的bit length为$L_n$Ln​，则取$e$e值最左侧的$L_n$Ln​ bits赋值给$z$z。（注意，$z$z值可以比$n$n大，但bit length不能比$n$n的长。）
• 3）选择随机数$k\in_R [1,n-1]$k∈R​[1,n−1]。（注意，不信任一般的随机数生成器，因为不好的RNG有太多的failures和vulnerabilities，可采用RFC6979 根据$pk$pk和$m$m来计算deterministic $k$k。）（如：2013年8月，安卓Bitcoin钱包因使用了错误的随机数生成器，引起私钥泄露，导致资金损失；2010年12月，索尼PS3游戏机因错误的使用了静态而不是随机的$k$k值，导致其ECDSA私钥泄露。）
• 4）计算curve point $(x_1,y_1)=k\times G$(x1​,y1​)=k×G。
• 5）计算$r=x_1\mod n$r=x1​modn，若$r=0$r=0，则跳转继续执行步骤3）。
• 6）计算$s=(z+r\cdot pk)/k \mod n$s=(z+r⋅pk)/kmodn，若$r=0$r=0，则跳转继续执行步骤3）。
• 7）最终的签名为$(r,s)$(r,s)。（注意，$(r,-s\mod n)$(r,−smodn)也为有效签名。）

整个ECDSA签名流程中，要求：

• $k$k值应为secret。
• 不同的签名应选择不同的$k$k值，否则会泄露私钥$pk$pk。
  

1.2 ECDSA验签

对收到的签名$(r,s)$(r,s)，采用公钥$P$P进行验签的流程为：

• 1）验证公钥$P$P不等于identity element $\mathcal{O}$O，且为其坐标为valid。
• 2）验证公钥$P$P lies on the curve。
• 3）验证公钥$P$P的order为$n$n，即$n\times P=\mathcal{O}$n×P=O。
• 4）验证签名$(r,s)$(r,s)有效，即满足$r\in [1,n-1],s\in [1,n-1]$r∈[1,n−1],s∈[1,n−1]。
• 5）计算消息$m$m的hash值，所采用的hash函数应与签名时一致。$e=hash(m)$e=hash(m)。
• 6）取$e$e的最左侧$L_n$Ln​ bits赋值给$z$z。
• 7）计算$u_1=z/s\mod n,u_2=r/s\mod n$u1​=z/smodn,u2​=r/smodn。
• 8）计算curve point $(x_1,y_1)=u_1\times G+u_2\times P$(x1​,y1​)=u1​×G+u2​×P。若$(x_1,y_1)=\mathcal{O}$(x1​,y1​)=O，则签名无效。
• 9）若$r\equiv x_1(\mod n)$r≡x1​(modn)成立，则签名有效，否则签名无效。

注意，以上ECDSA验签算法可做如下改进：

• 只计算一次$1/s\mod n$1/smodn。
• 使用Shamir’s trick，a sum of two scalar multiplication $u_1\times G+u_2\times P$u1​×G+u2​×P can be calculated faster than two scalar multiplications done independently。（参考2014年论文《The Double-Base Number System in Elliptic Curve Cryptograhy》）

ECDSA总的签名和验签流程可以如下图示意：

1.3 ECDSA的public key recovery

ECDSA也支持public key recovery算法，前提是提前知道签名方的公钥或者公钥hash值，否则有可能恢复出错误的公钥信息。

1.4 ECDSA的弊端

Bitcoin中采用ECDSA的弊端主要有：

• 1）ECDSA的验签过程中，需要进行求倒数和scalar multiplication运算，这些运算操作都是computationally heavy的。
  在Bitcoin中，每个节点都需要验证所有的交易，当你广播一条交易时，数以千记的计算机都需要验证你的签名。因此，Making verification process simpler will be very beneficial even if signing process is harder。

• 2）每个节点需要分别验证每个签名。对于m-of-n multisig transaction，节点甚至需要对同一签名进行多次验证。如具有7-of-11 multisig input的transaction，将包含7个签名，同时需要网络中的每个节点验证7到11个签名信息。同时，这样的transaction将占据区块中大量的空间，需要pay larger fees for that。

2. Schnorr signature

2.1 Schnorr签名、验签

Schnorr signature与ECDSA比，仅有轻微的差异：

• ECDSA的签名信息$(r,s)$(r,s)为2个scalar，而Schnorr的签名信息$(R,s)$(R,s)为1个point $R$R和1个scalar $s$s。$R=k\times G$R=k×G为a random point on elliptic curve。
• Shnorr签名中的$s$s计算方式不同，$s=k+hash(P,R,m)\cdot pk$s=k+hash(P,R,m)⋅pk，其中$pk$pk为私钥，$P=pk\times G$P=pk×G为公钥，$m$m为待签名消息。
• Schnorr的验签过程，验证$s\times G=R+hash(P,R,m)\times P$s×G=R+hash(P,R,m)×P是否成立。

Schnorr的签名验签总体流程示意图如下：

2.1 Schnorr signature的优势

Schnorr signature验签过程中使用的方程式$s\times G=R+hash(P,R,m)\times P$s×G=R+hash(P,R,m)×P为线性的。因此有一些很好的特性。如：

2.1.1 Schnorr signature支持 batch validation

在Bitcoin中，需要首先验证区块内的所有签名均有效，若其中某一签名无效，不用关心具体是哪一个，直接拒绝整个区块。
若采用ECDSA，需要对每个签名都分别进行验证，若区块内有1000个签名，则需要进行1000次倒数运算和2000次point multiplication运算，总的有大约3000次heavy operations。
若采用Schnorr signature，则仅需将所有的验签方式累加一块进行验证，可节约计算资源。若区块内有1000个签名，仅需验证：
$(s_1+s_2+\cdots+s_{1000})\times G=(R_1+\cdots+R_{1000})+(hash(P_1,R_1,m_1)\times P_1+\cdots+(hash(P_{1000}+R_{1000}+m_{1000}))\times P_{1000})$(s1​+s2​+⋯+s1000​)×G=(R1​+⋯+R1000​)+(hash(P1​,R1​,m1​)×P1​+⋯+(hash(P1000​+R1000​+m1000​))×P1000​)
对应有一些point additions（几乎可忽略相应的计算开销）和1001次point multiplication，相对于ECDSA方案验签速度几乎提升了3倍。相当于对one heavy operation per signature。

总体示意如下图所示：

2.1.2 Schnorr signature支持Key aggregation

为保证比特币安全，用户通常会有至少2个不同的私钥用于控制其所拥有的比特币。如1个私钥用于笔记本上的热钱包，1个私钥用于硬件钱包或者冷钱包。当某一个私钥泄露了，要求仍然可以控制比特币账户的安全。

目前采用的方案是使用2-of-2 multisig script，即要求在交易中包含2个不同的签名。

采用Schnorr signature，使用2个私钥$(pk_1,pk_2)$(pk1​,pk2​)生成shared public key $P=P_1+P_2=pk_1\times G+pk_2\times G$P=P1​+P2​=pk1​×G+pk2​×G。生成随机数$(k_1,k_2)$(k1​,k2​)，对应的随机point $(R_1=k_1\times G,R_2=k_2\times G)$(R1​=k1​×G,R2​=k2​×G)。$R=R_1+R_2$R=R1​+R2​计算通用$hash(P,R,m)$hash(P,R,m)，计算$s_1=k_1+hash(hash,R,m)\cdot pk_1, s_2=k_2+hash(hash,R,m)\cdot pk_2$s1​=k1​+hash(hash,R,m)⋅pk1​,s2​=k2​+hash(hash,R,m)⋅pk2​。基于shared public key $P=P_1+P_2=pk_1\times G+pk_2\times G$P=P1​+P2​=pk1​×G+pk2​×G生成的shared signature为：$(R,s)=(R_1+R_2,s_1+s_2)$(R,s)=(R1​+R2​,s1​+s2​)。这种签名方案存在的问题是要求私钥方相互间能够 interact。

参考资料：

[1] https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[2] Stepan medium博客 How Schnorr signatures may improve Bitcoin
[3] Stepan medium博客BLS signatures: better than Schnorr
[4] Stepan medium博客 ECDSA is not that bad: two-party signing without Schnorr or BLS