比特币算法演进简史：Schnorr签名算法和聚合签名

当我们研究比特币ECDSA椭圆曲线签名算法时，会发现多重签名交易验证过程非常繁琐。你有没有想过，一个交易中的所有签名和公钥都合并为一个签名和公钥，无法追溯，简单快捷？

1980 年代，德国密码学家克劳斯-彼得·施诺尔给出了答案。以他命名的 Schnorr 签名算法可以构建更高效、更私密的区块链系统，一直备受区块链开发者的关注。2018年7月，比特币开发者Pieter Wuille编写了bip-schnorr[2]，提出将比特币的签名算法改为schnorr方案。虽然 Schnorr 和 ECDSA 都是使用 secp236k1[3] 曲线的椭圆曲线加密算法，但与 Schnorr 相比，ECDSA 有一些不足之处：

1. 证明安全性：在随机预言机模型中很容易证明 Schnorr 签名的安全性，ECDSA 没有这样的证明。

2. 不可延展：ECDSA 签名是可延展的，不知道私钥的第三方可以将给定公钥和消息的现有有效签名更改为相同私钥和消息的另一个有效签名，这个问题是直到 SegWit 被激活才修复。这个问题在 BIP62[4] 和 BIP66[5] 中有讨论。如果使用 Schnorr 签名，则可以避免类似的情况 [6]。

3. 线性：Schnorr 签名是线性的很重要。使用 Schnorr 签名的各方可以为其各自的密钥生成签名聚合。基于此特性，可以构建更高效、更私有的区块链系统。

schnorr签名算法与ECDSA相比，除了没有标准化外，几乎没有缺点。而且由于两种算法都基于相同的椭圆曲线，签名的整体升级成本也非常低。

什么是 Schnorr 签名？

在密码学中，Schnorr 签名是由 Schnorr 签名算法产生的数字签名。它是一种以简单和高效而著称的数字签名方案，其安全性基于某些离散对数问题的难处理性。[7] Schnorr原理描述如下：

下面的数字用小写字母表示，例如：a = 42。我们还将使用椭圆曲线上的一些点。这些点是成对的满足椭圆曲线方程的大数。我们将使用大写字母来表示这些点，例如：A = (4, 68)。可以对椭圆曲线上的点进行一些代数运算。可以将上面的两个点相加得到一个近似值随机的第三个点，表示为：C = A + B。一个点可以与自身相加多次：D = C + C + C。当我们说一个点与自身相加多次时，我们称之为“乘法”取一个数”：D = 3 * C。显然，如果我们将一个点A与自身相加多次（或乘以一个大数）然后得到一个点B，如果我们只知道原始点A和结果B点，计算这个大数乘以A是相当困难的。这里的“难”是指如果我们要计算这个“大数”，不能简单地将B除以A，只能不断猜测一个值x，计算出是否x * A 等于 B。因此，如果 x 的值非常大，甚至大于宇宙中所有原子数的总和，那么猜测 x 的值将花费非常长的时间。有人拿着正确的 x，计算 x * A 非常快。这种不对称性将作为我们讨论的前提。所以如果 x 的值非常大，甚至大于宇宙中所有原子数的总和，那么猜测 x 的值将花费非常长的时间。有人拿着正确的 x，计算 x * A 非常快。这种不对称性将作为我们讨论的前提。所以如果 x 的值非常大，甚至大于宇宙中所有原子数的总和，那么猜测 x 的值将花费非常长的时间。有人拿着正确的 x，计算 x * A 非常快。这种不对称性将作为我们讨论的前提。

Alice 持有私钥 x，然后选择一个随机数 r，以椭圆曲线上的原点 G，计算 R := r * G，公钥 X := x * G，使用散列函数得到一个随机数验证数字 e := Hash(R, X, message)，然后计算 s := e * x + r。

Alice 将点 R、X、消息和点值 s 发送给 Bob，Bob 验证 s * G 等于 R + e * X 。事实上，不仅鲍勃，世界上任何人都可以单独验证这个证明。一旦 s * G = R + e * X 被验证，就可以证明 Alice 持有私钥 x 并生成有效签名：(s, e)。

最终，如果要根据该证明创建签名，Alice 需要自定义散列函数来散列她签名的消息。在这种情况下，需要确定为一条消息计算的签名，并且不能重复用于另一条消息。

这种定制可以简单地通过散列 R ， X 和签名信息来完成：

e := 哈希（R，X，消息）

一个好的散列函数会在一个字符发生变化的情况下返回完全不同的散列值，这使得计算 s 的值成为一项不可能完成的任务

Schnorr签名协议的简明描述如下：

设置：

x := 随机数（又名私钥）

G := 共同点

X := x * G （又名公钥）

符号：

r := 随机数（又名随机数）

R := r * G （又名承诺）

e := 哈希（R，X，消息）（又名挑战）

s := r + e * x （又名响应）

return (R, X, s, message) ((s, e) aka signature)

核实：

接收（R，X，s，消息）

e := 哈希（R，X，消息）

S1 := R + e * X

S2 := 小号 * G

如果 S1 满足 S2比特币算法详解，则返回 OK

在此基础上，开发者可以在未来添加更复杂的概念，例如聚合签名。聚合签名的优点是交易中涉及的所有输入只需一个组合签名即可完成，大大减少了数据处理量，使网络更快、更高效。

什么是聚合签名？

聚合签名是各方使用 Schnorr 签名生成的各自密钥上的签名聚合。它可以将多重签名交易的每个参与者的公钥和签名组合成一个公钥和签名。整个合并过程是无形的。，合并前的信息不能从合并后的公钥和签名中推导出来，验证时只需要验证一次。目前，Mimblewimble 已经使用 Schnorr 签名算法实现了签名聚合。

在使用ECDSA进行多重签名的情况下，如果一共N个私钥已经签名，那么验证时需要对N个签名中的每一个进行验证。由于 Schnorr 签名算法的线性特性，在同样的情况下比特币算法详解，N 个私钥的签名可以“聚合”成一个签名，其原理如下：

由于椭圆曲线上的点能够满足乘法结合律，对于椭圆曲线上的两点X、Y以及对应的标量（私钥）x、y和原点G，则：

X + Y = x * G + y * G = (x + y) * G

对于 ECDSA 签名算法，验证 n 个签名需要 n 次模运算和 2 * n 次点乘。对于 Schnorr 签名，我们可以添加验证方程：

S1 = sum(s)(i) = s1 * G + s2 * G + … + sn * G = (s1 + s2 + … + sn) * G

S2 = sum(R + e*X)(i) = (R1 + e1 * X1) + (R2 + e2 * X2) + ... + (Rn + en * Xn) = sum( R1, R2, ..., Rn) + (e1 * X1 + e2 * X2 + ... + en * Xn)

此时，验证Schnorr签名算法生成的多重签名时，只需要2n次加法运算和n+1次点乘运算即可。由于加法运算占用的资源极低，两种多重签名验证方式的资源消耗可以大致比较如下：ECDSA是一个模加两个点积，Schnorr是一个点积的资源消耗。显而易见的结论是，使用 Schnorr 签名算法消耗的资源更少。

对于上述多重签名情况，使用 Schnorr 签名算法进行聚合签名可以提供以下额外好处：

· 性能：可以大大降低验证签名的成本。Schonrr 签名算法的优势是显而易见的。对于多签交易，需要多次验证，而聚合签名只需验证一次，从而提高了节点对该交易的验证速度。

交易量：由于多个签名聚合为一个签名，可以大大减少多个签名的大小，并且可以显着减少网络传输所消耗的带宽和节点的存储空间

隐私：使用 Schnorr 聚合签名可以提高链上数据的隐私性。对于验证者来说，聚合签名看起来和普通的 Schnorr 签名没什么区别，无法区分交易是普通交易还是多重签名交易，参与交易的用户的公钥和签名会不被暴露。出来

在创建基于 Schnorr 聚合签名的多重签名方案时，为了保证多重签名看起来像一个单密钥签名，并使传统的验证方法有效，并保证整个过程只需要线性子-签名聚合，该方案需要满足以下特征：

1. 在普通公钥模型中被证明是安全的

2. 满足 Schnorr 方程，因此生成的签名可以写为公钥组合的函数

3. 允许签名者在交互式聚合签名 (IAS) 上进行协作

4. 允许非交互式聚合签名（NAS），任何人都可以进行聚合

5. 允许每个签名者签署相同的消息

6. 允许每个签名者签署他们自己的消息

目前有许多基于 Schnorr 的聚合签名方案的实现。Blockstream给出的最终方案是MuSig。MuSig的实现方式和具体原理的区别可以参考[8][9]。

使用聚合签名

7 月 10 日，Qtum 链基金会宣布实现 QTUM-BEAM 原子交换（Atomic Swap），允许在两条独立链上进行原子跨链交易。（链接：Qtum量子链实现QTUM-BEAM原子交换，支持私有跨链交易|附详细实验步骤）

通过聚合签名，可以安全简单地实现原子交换。聚合签名本质上是签名的偏移量。一旦与真实签名相结合，就可以计算出用于签名的私钥。可以在不暴露任何信息的情况下验证聚合签名的可信度。聚合签名可以保证原子交换的原子性和双方的安全。

通过聚合签名执行原子交换的简明过程如下 [10]：

1. Alice 和 Bob 将加密货币存入两个地址，每个地址都已签名

2. Alice 的私钥是一次性的，因为她需要将它发送给 Bob

3. Alice 给 Bob 一个聚合签名，需要 Bob 确认

4. 当 Alice 广播她的签名以证明她的加密货币持有量时，Bob 有足够的信息来计算 Alice 的私钥并获得她的加密货币持有量

5. Bob 签署交易以将加密货币发送给 Alice

6. Alice 用另一半私钥对收到的加密交易进行签名并广播

7. Bob 得到所有的私钥并收到 Alice 持有的加密货币，Alice 也会得到 Bob 的货币

介绍 Schnorr 和聚合签名的影响

优势：

保存数据：签名聚合在区块链上提供数据压缩

隐私：除了交易结算，没有任何关于无脚本智能合约的记录在区块链上（签名聚合过程发生在链下）

多重性：可以在单笔交易结算中在两方之间转移多种资产（跨链原子互换）

隐式可扩展性：区块链的可扩展性是通过将多个交易压缩为单个结算交易来实现的。在满足所有先决条件之前，不会广播交易

· 无脚本脚本与聚合签名相结合，比标准智能合约具有更好的可扩展性。由于合约执行发生在链下，通过将此执行结果推送给关心它的人，公共计算资源可以减轻存储合约数据和执行条件的负担。非公开合同也可以提供更好的隐私。合同的细节只有参与者才能知道。对于其他人来说，交易与普通交易没有什么不同

坏处：

Maxwell 等人的工作。[11] 指出，满足密钥聚合的 Schnorr 多重签名的简单实现是不安全的。在普通的公钥模型中，例如使用 BN Schnorr 的签名方案，需要通过放弃密钥聚合的属性来获得安全性。他们提出了一种新的基于 Schnorr 的多重签名模型，称为 MuSig，在具有适当安全性的公共公钥模型中使用密钥聚合。它具有与标准 Schnorr 签名相同的密钥和签名大小。对于单个“聚合”公钥，它可以以与标准 Schnorr 签名相同的方式进行验证（根据签名者各自的公钥计算证明）。

引用

1.

2.

3.

4.

5.

6. 提交公钥的限制是它消除了恢复公钥或根据短公钥哈希验证签名的能力。这些结构通常与批量验证不兼容。

7.

8.

9.

10.

11.

关键词： Schnorr 签名 比特币聚合签名

Topfundclub.com 人气：218

本内容来自网络公开内容，非区块链原创内容，如转载请注明出处：/archives/28581