比特币Schnorr签名提案BIP-340与源代码分析
将于2021年11月正式激活的Taproot更新被视为比特币数年来“最雄心勃勃的升级”，甚至是“目前为止比特币协议升级提议中最具重要性的一次”，被誉为“Segwit后的最大技术更新”。
Taproot 升级包含了Schnorr签名(BIP 340)、Taproot (BIP 341) 和Tapscript (BIP 342) 三个部分
本文结合BIP-340提案及其Python参考实现分析了在比特币系统中使用Schnorr签名的相关内容。
1secp256k1椭圆曲线上的Schnorr签名
本节简介BIP-340提案内容，此提案为
secp256k1椭圆曲线上的Schnorr签名建立标准。https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
Schnorr签名相比于目前使用的ECDSA签名有如下优点（而且目前没有发现缺点）：
可证明安全：Schnorr签名在ECDLP假设下在ROM中证明是SUF-CMA安全的；或在ECDLP假设以及哈希抗原象和和抗第二原象假设下在GGM中证明是SUF-CMA安全的。反之，关于ECDSA所有已知的最好结果都依赖更强的假设。 非延展性：延展性的意思是一个没有私钥的第三方可以把已知的一个有效签名修改为另一个对同样公钥和消息的有效签名。ECDSA签名本质上是延展的，而SUF-CMA安全意味着Schnorr签名是非延展的。 线性性：Schnorr签名的线性性允许多个参与方很容易的生成对所有人公钥的和的有效签名，而ECDSA签名没有简单的方法实现。
Schnorr签名的良好性质使其支持如下重要扩展应用，如多重签名/门限签名/盲签名/Adaptor签名等等。
设计原则
Schnorr签名变体
对于消息，公钥，椭圆曲线基点，Schnorr签名包括一个椭圆曲线点，整数和。其满足 和。Schnorr签名具有如下两种变体：
：验证方程 ：验证方程
变体1避免了编码所引入的计算复杂度，并可以提供更短的签名（对的编码是32字节，而哈希值可以更短，16字节的足够提供128比特SUF-CMA安全。）（但是更短的哈希值更容易发生碰撞，会降低多方签名场景下的安全性。）
变体2由于在哈希输入内部没有椭圆曲线操作，所以支持批量验证，可以使得验证性能获得巨大提升。
提案选择，由于要避开短哈希的脆弱性，以及支持批量验证。
密钥前缀
使用如上验证方程会出现相关密钥攻击，敌手可以把对公钥的签名转换为对于同样消息但对公钥（私钥为）的签名。这种攻击会使得使用BIP32的未加强导出密钥方法以及其他依赖对已知密钥添加加法项的方法（比如Taproot）的签名不安全。
为了防止这种攻击，在挑战哈希的输入中加入公钥作为前缀
除了防止相关密钥攻击，密钥前缀在一些多用户场景方案（比如MuSig多重签名）的证明中也具有重要作用。
编码,
对椭圆曲线点进行编码有很多种方法，为了优先考虑紧凑性，采用如下编码方法：
只编码坐标，导致32字节的公钥和64字节的签名
隐式坐标
每一个有效的坐标都对应于两个可能的坐标，为了兼容性的考虑，采用如下隐式选择坐标的方法：
隐式选择为偶数的坐标
带标签哈希
通过给哈希数据添加SHA256(tag) || SHA256(tag)前缀的方式将标签包括进来。
最终方案
综上，最终方案的公钥为曲线上坐标是偶数的点的坐标， 签名是，是的坐标，其坐标为偶数，验证方程为：
提案细节与Python 参考实现分析
https://github.com/bitcoin/bips/blob/master/bip-0340/reference.py
椭圆曲线 secp256k1相关参数设置请参见标准：https://www.secg.org/sec2-v2.pdf
插播一句，Python作为最广泛普及且具有良好可读性的语言，能用几乎是plain English的语言把事情说清楚，真心希望以后的所有标准草案以及论文能提供Python参考实现或原型实现：）
主要签名方案实现为如下三个函数（去掉了所有异常检测代码）：
pubkey_gen(seckey)schnorr_sign(msg, seckey, aux_rand)schnorr_verify(msg, pubkey, sig)
公钥生成
输入：私钥, 一个新鲜均匀随机生成的32字节数组 输出：公钥，32字节
def pubkey_gen(seckey: bytes) -> bytes:
d0 = int_from_bytes(seckey)
P = point_mul(G, d0)
return bytes_from_point(P)
注意这里使用 bytes_from_point编码时只使用了的坐标，因此公钥是32字节。
签名生成
输入：3个32字节数组，私钥，消息，辅助随机数据
def schnorr_sign(msg: bytes, seckey: bytes, aux_rand: bytes) -> bytes:
d0 = int_from_bytes(seckey)
P = point_mul(G, d0)
d = d0 if has_even_y(P) else n - d0
t = xor_bytes(bytes_from_int(d), tagged_hash("BIP0340/aux", aux_rand))
k0 = int_from_bytes(tagged_hash("BIP0340/nonce", t + bytes_from_point(P) + msg)) % n
R = point_mul(G, k0)
k = n - k0 if not has_even_y(R) else k0
e = int_from_bytes(tagged_hash("BIP0340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n
sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n)
return sig
必须注意如下细节（主要为了防止侧信道攻击）： Let be the byte-wise xor of bytes() and Let
签名验证
def schnorr_verify(msg: bytes, pubkey: bytes, sig: bytes) -> bool:
P = lift_x(pubkey)
r = int_from_bytes(sig[0:32])
s = int_from_bytes(sig[32:64])
e = int_from_bytes(tagged_hash("BIP0340/challenge", sig[0:32] + pubkey + msg)) % n
R = point_add(point_mul(G, s), point_mul(P, n - e))
if (R is None) or (not has_even_y(R)) or (x(R) != r):
return False
return True
其中 lift_x函数通过坐标算出坐标从而恢复椭圆曲线点。
签名批量验证
批量验证算法标准定义如下，并没有给出Python参考实现：
：
生成 个在范围 中的随机整数 . For : ; 如果 ，输出失败。
注：关于批量验证为什么能加速验证过程请参见这篇文章： https://suredbits.com/schnorr-applications-batch-verification/
2libsecp256k1库中的Schnorr签名源代码
比特币的所有开源代码都在Bitcoin Core这个库（https://github.com/bitcoin/bitcoin )里，libsecp256k1是集成于其中的一个子库（https://github.com/bitcoin-core/secp256k1） ，对secp256k1椭圆曲线上的操作进行了优化的C语言实现。其原本是支持目前比特币在使用的ECDSA签名的，近期也已经将兼容BIP-340的代码作为可选模组整合其中（0.21.0版本之后），静待2021年11月通过软分叉来激活。其原理和上述Python参考实现一致，但是多了为代码产业级可用的额外考量，感兴趣的朋友可以参考阅读。
库中关于Schnorr签名的代码主要文件路径为：
include/secp256k1_schnorrsig.hsrc/modules/schnorrsig/main_impl.hsrc/bench_schnorrsig.c
主要的相关函数为：
secp256k1_schnorrsig_signsecp256k1_schnorrsig_sign_customsecp256k1_schnorrsig_verify