邹传伟：读懂比特币ECDSA与Schnorr签名算法以及Taproot升级

原文标题：《比特币的 Taproot / Schnorr 升级》
撰文：邹传伟，万向区块链、PlatON 首席经济学家

2020 年 1 月，由比特币核心开发人员 Pieter Wuille 于去年 5 月提出的 Taproot/Schnorr 软分叉升级提案已正式作为比特币改进提案（BIPs）发布，相关提案序号为 BIP 340-342。Taproot/Schnorr 升级如果获得社区支持，将是比特币自闪电网络上线后最大的技术拓展。本文查询了 BIP 340-342 相关文档 ，对 Taproot/Schnorr 升级做一个简单介绍。本文分三部分，第一部分简单介绍比特币目前的 ECDSA 签名算法，第二部分详细介绍 Schnorr 签名算法，第三部分介绍 Taproot。

一、比特币 ECDSA 签名算法

比特币目前使用的 ECDSA 签名算法与建议的 Schnorr 签名算法，都属于椭圆曲线数字签名算法，它们使用的椭圆曲线都是 secp256k1。这一部分先介绍椭圆曲线 secp256k1，再介绍 ECDSA 签名算法。

（一）椭圆曲线 secp256k1

图 1：椭圆曲线图示

（二） ECDSA 签名算法

注： G 坐标为
（79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8），
阶等于
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141，
均采用 16 进制表达。

二、Schnorr 签名算法

这一部分先介绍 Schnorr 签名算法主要特点，再分步骤介绍 Schnorr 签名算法及批验证，最后介绍基于 Schnorr 签名的多重签名算法。

（一）主要特点

Schnorr 签名算法与 ECDSA 签名算法使用同样的椭圆曲线 secp256k1 和哈希函数 SHA256，所以在这个层面它们具有同样的安全性。Schnorr 签名算法主要有以下优点。

第一，Schnorr 签名算法有可证明安全性。在假设椭圆曲线离散对数问题难度的随机寓言（Random Oracle）模型，以及假设原像抗性（Preimage Resistance）和次原像抗性（Second Preimage Resistance）的通用群模型下，Schnorr 签名算法具备选择消息攻击下的强不可伪造性（Strong Unforgeability under Chosen Message Attack，SUF-CMA）。换言之，如果不知道 Schnorr 签名的私钥，即使有针对任意消息的有效 Schnorr 签名，也没法推导出其他有效 Schnorr 签名。而 ECDSA 签名算法的可证明安全性则依赖于更强的假设。

第二，Schnorr 签名算法具有不可延展性（Non-malleability）。签名延展性的含义是，第三方在不知道私钥的情况下，能将针对某一公钥和消息的有效签名，改造成针对该公钥和信息的另一个有效签名。ECDSA 签名算法则有内在的可延展性，这是 BIP 62 和 BIP 146 针对的问题。

第三，Schnorr 签名算法是线性的，使得多个合作方能生成对他们的公钥之和也有效的签名。这一特点对多重签名、批验证（Batch Verification）等应用非常重要，既能提高效率，也有助于保护隐私。而在 ECDSA 签名算法下，如无额外的见证数据，批验证相对逐个验证并无效率提升。

最后，Schnorr 签名算法因为使用同样的椭圆曲线 secp256k1 和哈希函数 SHA256，能兼容目前的比特币公私钥生成机制。

（二） Schnorr 签名算法

公私钥生成

签名生成

签名验证

批验证

图 2：逐个验证签名的时间 / 批验证所需时间

（三） Schnorr 签名算法与多重签名

密钥生成

签名生成

签名验证

三、Taproot 升级

Taproot 升级可以视为默克抽象语言树（Merkelized Abstract Syntax Tree，简称 MAST）的一个应用，而 MAST 又与支付到脚本哈希（Pay-to-Script-Hash，简称 P2SH）有关。因此，这部分依次介绍 P2SH、MAST 和 Taproot。

（一） P2SH

P2SH 是 2012 年推出的一类新型交易，使复杂脚本的使用与直接向比特币地址支付一样简单。在 P2SH 中，复杂的锁定脚本被其哈希值所取代，称为兑换脚本（Redeem Script）。当随后出现的一笔交易试图花费这个 UTXO 时，必须包含与哈希值匹配的脚本，同时解锁脚本。P2SH 的主要优点包括：一是在交易输出中，复杂脚本由哈希值取代，使得交易代码变短。二是将构建脚本的负担转移至接收方，而非发送方。三是隐私保护性更好。理论上，除了接收方，任何其他方都可以不知道兑换脚本中包含的支出条件。比如，在多重交易中，发送方可以不知道与多重签名地址有关的公钥；只在接收方支出资金时，才披露公钥。但 P2SH 也存在不足：一是所有可能的支出条件最终都必须被披露，包括那些实际上没有被触发的支出条件。二是在有多个可能的支出条件时，P2SH 将变得繁复，会增加计算和验证的工作量。

（二） MAST

MAST 使用默克树来加密复杂的锁定脚本（图 3），其叶子是一系列相互不重叠的脚本（比如，多重签名或时间锁）。要支出时，只需披露相关脚本以及从该脚本通向默克树根的路径。比如，在图 3 中，要使用 script 1，只需披露 script 1、script 2 以及 hash 3 即可。

图 3：MAST，来源：https://medium.com/@listedreserve/schnorr-and-taproot-cc4fa1edc828

MAST 的主要优点包括：一是支持复杂的支出条件。二是不用披露未被执行的脚本或未被触发的支出条件，提供更好的隐私保护。三是压缩交易大小。随着脚本数量的增加，非 MAST 交易大小是线性增长，而 MAST 交易大小是对数增长（图 4）。

图 4：脚本数量与交易大小，来源：https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f

（三） Taproot

但 P2SH 与常见的支付到公钥哈希（Pay-to-Public-Key-Hash，P2PKH）在表现上不一样，仍然有隐私保护问题。有没有可能让 P2SH 和 P2PKH 在链上看起来一样？这就是 Taproot 要解决的问题。

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

图 5：Taproot，来源：https://medium.com/@listedreserve/schnorr-and-taproot-cc4fa1edc828

参考文献

1 Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille, 2018, "Simple Schnorr Multi-Signatures with Applications to Bitcoin".

本文来源：HashKey Capital Research
原文标题：邹传伟：读懂比特币ECDSA与Schnorr签名算法以及Taproot升级

—-

编译者/作者：HashKey Capital Rese

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。