本文作者为万向区块链、PlatON首席经济学家邹传伟。
* l0 @1 C7 F$ u6 ^7 H. \2 z* f' g4 p' u7 t" B! ]5 j% j' \  l! e
2020 年 1 月，由比特币核心开发人员 Pieter Wuille 于去年 5 月提出的 Taproot/Schnorr 软分叉升级提案已正式作为比特币改进提案（BIPs）发布，相关提案序号为 BIP 340-342。Taproot/Schnorr 升级如果获得社区支持，将是比特币自闪电网络上线后最大的技术拓展。本文查询了 BIP 340-342 相关文档 ，对 Taproot/Schnorr 升级做一个简单介绍。本文分三部分，第一部分简单介绍比特币目前的 ECDSA 签名算法，第二部分详细介绍 Schnorr 签名算法，第三部分介绍 Taproot。
  A6 ]2 R$ ~) n; }! U4 U( ?( `, G% \. p% v
一、比特币 ECDSA 签名算法
% N1 d# N' ~0 ~0 P8 u  W) ?) n1 r9 M# |; z; R* Z
比特币目前使用的 ECDSA 签名算法与建议的 Schnorr 签名算法，都属于椭圆曲线数字签名算法，它们使用的椭圆曲线都是 secp256k1。这一部分先介绍椭圆曲线 secp256k1，再介绍 ECDSA 签名算法。
3 ]/ O- W# X* q; l* y! F: ]! V% {4 V6 r- S% s, s* U  b
（一）椭圆曲线 secp256k1# o7 ?' h6 S- `
" J! k3 F0 N" G: M( [7 B

: K$ ?& R  L3 }2 I
( j. l2 k, `0 c, e  k9 V5 q（二） ECDSA 签名算法8 E9 ?* k6 |( p. }+ @6 V. ~
; V  O* s/ K5 w0 m5 e; ^2 k0 X; I
注： G 坐标为 （79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8）， 阶等于 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141， 均采用 16 进制表达。
2 F' [) q/ B+ N9 g
! }$ Q5 M4 i& S4 H5 T二、Schnorr 签名算法& S5 D5 o4 D, G' L+ n* F
; y) [( U. B: F: O" V& p3 k
这一部分先介绍 Schnorr 签名算法主要特点，再分步骤介绍 Schnorr 签名算法及批验证，最后介绍基于 Schnorr 签名的多重签名算法。  [+ |" p+ i* g6 v3 A) ^
# Q0 z" E3 v+ V3 f, k# D
（一）主要特点Schnorr 签名算法与 ECDSA 签名算法使用同样的椭圆曲线 secp256k1 和哈希函数 SHA256，所以在这个层面它们具有同样的安全性。Schnorr 签名算法主要有以下优点。
0 A: L+ ?7 T, ^; _9 r9 y! _$ `) [/ U4 W% e- Z1 |0 Q: c1 z& O
第一，Schnorr 签名算法有可证明安全性。在假设椭圆曲线离散对数问题难度的随机寓言（Random Oracle）模型，以及假设原像抗性（Preimage Resistance）和次原像抗性（Second Preimage Resistance）的通用群模型下，Schnorr 签名算法具备选择消息攻击下的强不可伪造性（Strong Unforgeability under Chosen Message Attack，SUF-CMA）。换言之，如果不知道 Schnorr 签名的私钥，即使有针对任意消息的有效 Schnorr 签名，也没法推导出其他有效 Schnorr 签名。而 ECDSA 签名算法的可证明安全性则依赖于更强的假设。- w' ^( c/ P9 t
; H. @+ I" R/ v# ?2 @0 [! v
第二，Schnorr 签名算法具有不可延展性（Non-malleability）。签名延展性的含义是，第三方在不知道私钥的情况下，能将针对某一公钥和消息的有效签名，改造成针对该公钥和信息的另一个有效签名。ECDSA 签名算法则有内在的可延展性，这是 BIP 62 和 BIP 146 针对的问题。5 b% R. v: i2 y9 w# k

9 r# B( ~6 A9 `) S第三，Schnorr 签名算法是线性的，使得多个合作方能生成对他们的公钥之和也有效的签名。这一特点对多重签名、批验证（Batch Verification）等应用非常重要，既能提高效率，也有助于保护隐私。而在 ECDSA 签名算法下，如无额外的见证数据，批验证相对逐个验证并无效率提升。
: l+ L  ~5 L, _! P8 V
0 ]) w4 B6 ^$ N8 U最后，Schnorr 签名算法因为使用同样的椭圆曲线 secp256k1 和哈希函数 SHA256，能兼容目前的比特币公私钥生成机制。$ F& L/ C1 O3 [7 b6 J
  c) m( n9 a% l
（二） Schnorr 签名算法
9 {8 r/ m( l: R$ |
/ v8 w( k: P$ s9 u! ?5 A! P6 F公私钥生成0 S. U- D0 ]1 Q
2 y( Q. ~# L7 z3 |
签名生成0 T8 ?" O1 j+ s' ^* ]* U% M
+ m/ s5 F3 e( u- ]5 n
签名验证$ W% i+ g7 M# M. b/ u; {; x: B

/ A9 t0 R$ }# A1 J批验证
% I. ~' R) r+ P! |0 C
; `; O$ H+ d% a- u, k
2 @: P3 R7 ?# c. K. `: C" g4 K# Z3 \
（三） Schnorr 签名算法与多重签名5 G, `8 D3 c; e4 L2 V

. Z; s- v2 O$ S3 R2 ]密钥生成, U9 @! d8 a7 b
6 [7 [. @& V* L/ S. R
签名生成
5 O+ u! D* J0 h3 n* L" k- T# U! h! o1 A6 U
签名验证
8 l2 k: }0 G, r
) W: a2 S- }4 z9 E) Y9 n. l三、Taproot 升级# Z1 a' e0 Z" V" q

, ]  {0 I7 F9 {) c) z3 z9 r4 |1 |Taproot 升级可以视为默克抽象语言树（Merkelized Abstract Syntax Tree，简称 MAST）的一个应用，而 MAST 又与支付到脚本哈希（Pay-to-Script-Hash，简称 P2SH）有关。因此，这部分依次介绍 P2SH、MAST 和 Taproot。# Z, X0 R8 {, G+ k7 K
( N+ C5 {8 ~# v# w. I+ {
（一） P2SHP2SH 是 2012 年推出的一类新型交易，使复杂脚本的使用与直接向比特币地址支付一样简单。在 P2SH 中，复杂的锁定脚本被其哈希值所取代，称为兑换脚本（Redeem Script）。当随后出现的一笔交易试图花费这个 UTXO 时，必须包含与哈希值匹配的脚本，同时解锁脚本。P2SH 的主要优点包括：一是在交易输出中，复杂脚本由哈希值取代，使得交易代码变短。二是将构建脚本的负担转移至接收方，而非发送方。三是隐私保护性更好。理论上，除了接收方，任何其他方都可以不知道兑换脚本中包含的支出条件。比如，在多重交易中，发送方可以不知道与多重签名地址有关的公钥；只在接收方支出资金时，才披露公钥。但 P2SH 也存在不足：一是所有可能的支出条件最终都必须被披露，包括那些实际上没有被触发的支出条件。二是在有多个可能的支出条件时，P2SH 将变得繁复，会增加计算和验证的工作量。
7 a) ?! z9 j" v5 ~' Q, ?( |& E  c
（二） MASTMAST 使用默克树来加密复杂的锁定脚本（图 3），其叶子是一系列相互不重叠的脚本（比如，多重签名或时间锁）。要支出时，只需披露相关脚本以及从该脚本通向默克树根的路径。比如，在图 3 中，要使用 script 1，只需披露 script 1、script 2 以及 hash 3 即可。
* }( i" a2 ]/ |, ?* Q& k3 M
% U: B9 _* q& u& e 2 J3 i) W3 t% n$ X% {' S4 O7 _7 ~

4 D- |. o% U( ~1 DMAST 的主要优点包括：一是支持复杂的支出条件。二是不用披露未被执行的脚本或未被触发的支出条件，提供更好的隐私保护。三是压缩交易大小。随着脚本数量的增加，非 MAST 交易大小是线性增长，而 MAST 交易大小是对数增长（图 4）。( L- P0 u8 w4 r+ \5 S/ P: B
" V  }, i$ O% S% T: G3 X

  n# M7 \$ U3 `  [/ Y3 a9 g
/ m7 M6 g/ G" U1 D0 m（三） Taproot但 P2SH 与常见的支付到公钥哈希（Pay-to-Public-Key-Hash，P2PKH）在表现上不一样，仍然有隐私保护问题。有没有可能让 P2SH 和 P2PKH 在链上看起来一样？这就是 Taproot 要解决的问题。4 P  P9 A0 R4 k9 e* h5 i, y$ A

! D4 Q" g9 M) ]+ M; x涉及有限数量签名者的脚本，可以分解成两部分：第一部分是多重签名，所有签名者都同意某一支出结果，称为「协作式支出」；第二部分称为「非协作式支出」，可以有非常复杂的脚本结构。这两部分是「或」的关系。比如，在图 3 中，Script 3 是一个 2-of-2 型多重签名，需要 Alice 和 Bob 两人都签名才有效，是「协作式支出」；Script 1 和 2 是「非协作式支出」。