作者:cryptography. 编译: Cointime.com QDD
引言
比特币领域的许多文化文章都会吹嘘以下触目的话语:
Schnorr签名将改善比特币在多重签名交易中的隐私!
...然而,大多数人选择忽略使这个陈述成立的巧妙数学。这种数学并不令人费解。我们只需要对椭圆曲线密码学有基本的了解,Schnorr签名的好处很快就变得非常令人兴奋。
预备知识
让我们都了解一下:
符号 | 含义 |
G | secp256k1曲线的基点。 |
m | 我们要签名的消息(字节数组)。 |
H(x) | SHA-256哈希函数。 |
n | secp256k1曲线的阶。在曲线上有可能的有效非零点,加上“无穷远”点(也称为零点)。 |
X⬅Zn | 从模中随机采样整数。请注意,在采样时我们排除零。 |
a II b | 字节数组和的串联。 |
一般而言,大写变量如表示椭圆曲线上的点,而小写字母如表示普通自然数,称为标量。
弗兰肯斯坦登场
为了理解Schnorr签名对比特币开发者的重要性,我们需要将其与我们目前使用的ECDSA进行比较。如果您选择跳过这部分,我可以理解。
但为什么ECDSA这么糟糕呢?
首先,当签名时需要计算随机数的模乘逆,以及在验证时需要计算签名的模乘逆。糟糕。更准确地说,无聊。与其他离散数学运算相比,模乘逆运算非常慢。
此外,看看我刚才写出的步骤数量。它更像是一项手术过程,只是碰巧涉及您的私钥,而不是一个签名算法。
此外,ECDSA签名是可塑的。是一个有效的签名,但也是!这可能会对某些应用程序造成干扰,因为它们希望签名不会改变。遗留比特币P2PKH地址仍然容易受到这种影响 - 如果签名的值被反转,任何从P2PKH支出的交易的交易ID都可能会改变。
此外,ECDSA的安全性证明相当薄弱。
再者,ECDSA(及其前身DSA)最早是在九十年代初发表的,以绕过Schnorr签名的专利,该专利在2008年到期。比特币自起源区块以来一直在使用Schnorr的仿制品。现在是时候升级到品牌名了。
Schnorr签名
与ECDSA相比,Schnorr签名以其优雅的简洁性为人称道。
1. 随机采样一个随机数。
r ←Zn
2. 将基点乘以。
R=rG
3. 使用随机数点、签名公钥和消息进行哈希以得到挑战。
e=H(R II D II m)
*如果您在其他网站上阅读有关Schnorr签名的内容,可能会看到挑战计算为。比特币中使用的变体称为前缀键Schnorr,其中挑战还与签名密钥相关联。
4. 使用私钥计算签名。
s=r+ed mod n
最终签名是元组(R,s),其中是R曲线上的一个点,s是一个标量值。
验证Schnorr签名很容易。只需将上述等式的两边都乘以,并检查它们是否相等。
e=H(R II D II m)
sG=R+eD
验证者假定知道公钥D和消息m,否则他们在验证什么呢?验证与哈希一样快速,然后是两个点乘法运算和一个点加法运算。
通过简单地分解可以很容易地证明签名是有效的。
由于类似secp256k1这样的密码学安全的椭圆曲线的属性,要计算一个曲线点的离散对数是不可行的(尚未可行)。这就是为什么在不知道私钥的情况下无法伪造签名,但可以使用容易验证的。
但这些特定的等式为什么有效呢?
我无意逆向证明Schnorr的设计,但也许我至少可以指出每个步骤和每个变量在试图攻击该方案的人的角度来看都在做什么。
回顾一下Schnorr签名的定义。
请注意:
- 和都是从模集合随机采样的,即。
- 随机数在每个签名中都会改变,而私钥保持一致。
- 可以由任何知道(可能是)公共参数的人计算得出。
当签名者将私钥与挑战相乘时,这会得到另一个标量值,签名者只有在知道的情况下才能计算出这个值。例如,只知道和的人无法计算。
那么添加的目的是什么?为什么不让签名成为?因为是公开的,所以任何观察者都可以通过求逆运算计算私钥。
d=s·e-1
这就是为什么必须保持秘密且均匀随机:这些特性防止观察者能够通过签名来计算签名者的私钥。
如果观察者知道签名中使用的值,他们可以计算签名者的私钥。
s=r+ed
ed=s-r
d=e-1(s-r)
另一个常见的问题是:必须对每个签名使用不同的。如果在两个不同消息上使用相同的随机数进行签名,那么由于可以通过解一个方程组来计算签名这两个消息所使用的私钥。
有趣的是,这种对的定义指示了一些令人意外的事情。是笛卡尔坐标系上连接点和之间直线的斜率,但仅在两个签名之间重用。
相反,如果我们在创建两个签名时使用了两个不同的随机数,观察者无法在不知道和的情况下解出。因为没有可用的方程组。
如果我们使用不同的随机数来对同一消息进行签名会怎样?这会导致任何问题吗?不会,因为请记住,挑战也与随机数相关联。
e=H(R II D II m)
如果随机数改变,也会改变。即使只是将其与和相关联,攻击者仍然需要知道或来计算。
但这为什么如此酷呢?
1. Schnorr更快。
2. Schnorr比ECDSA更简单实现。
3. Schnorr签名不可塑。
4. Schnorr具有非常可靠的安全性证明。
5. Schnorr允许线性签名聚合。
我在那里加粗了第五个功能,因为这个特性对比特币未来的潜力非常重要。
聚合器还是鳄鱼?
在ECDSA中,签名聚合几乎不可能。ECDSA门限签名是可以实现的,而且很方便,但是与Schnorr的线性签名聚合相比,它们既不容易也不快。而且,如果还不够强大,Schnorr甚至可以比ECDSA更好地实现门限签名。
当我说Schnorr签名是线性的时候,这意味着Schnorr只需要简单的标量加法和乘法运算。验证也是如此:只需要点加法和点乘法来验证签名。而ECDSA则需要模乘逆来进行签名和验证。
这个听起来有点晦涩的解释可以简化为一个非常重要的事实:
对于给定消息的一组Schnorr签名的总和是在生成这些签名的公钥的总和下的有效签名。
换句话说,如果一群不同的签名者合作签署相同的消息,这些签名可以相加以产生一个聚合签名。如果还将签署者的公钥求和以获得一个聚合公钥,那么聚合签名将在聚合公钥下是有效的。
简单示例
假设您有三个具有自己的私钥和公钥对的参与方。他们每个人都会采样自己的私人随机数。
姓名 | 公钥 | 私钥 | 随机数 |
Alice | Da | da | ra |
Bob | Db | db | rb |
Carol | Dc | dc | rc |
他们都希望签署相同的消息,并且自然而然地就基点G和哈希函数H(x)达成了一致。
1. 他们各自独立地计算自己的公共随机数点。
2. 他们就一个聚合随机数点达成一致。
3. 他们就一个聚合公钥达成一致。
4. 他们将消息与这个聚合随机数点和聚合公钥一起进行哈希。
5. 他们各自计算签名的份额。
6. 他们将彼此的值发送给对方,并通过将所有值相加进行聚合。
最终的聚合签名为(R,s)。
要进行验证,回想一下签名(R,s)中的公匙D在消息m中有效,如果:
对于我们的聚合签名来说,这将成立。回想一下Alice、Bob和Carol的聚合。
我们的验证是有效的,因为通过聚合签名,我们还聚合了个体的随机数和私钥(乘以)。然后我们可以因式分解,这意味着我们将其与一个聚合私钥相乘,并添加了一个聚合的秘密随机数,尽管参与者之间从未公开他们的私钥或秘密随机数。
因此,乘以和将满足等式。
然而
如果在对抗条件下(共同签署者不信任彼此)使用此示例作为多签名协议,它将存在一个隐藏的缺陷。您能看出是什么吗?
提示:攻击向量在聚合过程中非常早。
好处
与Taproot结合使用,开发者可以将大量聚合公钥的任意组合嵌入到一个单一的调整公钥中,该公钥编码了一系列可能的花费条件,但在正常条件下看起来仍然像普通的公钥。
比特币开发者现在可以使用诸如MuSig的多签名签名方案和ROAST等门限签名协议,比以往使用ECDSA时具有更高的效率、安全性和隐私性。
现在任何给定的公钥都可以是大量子密钥、脚本、门限公钥等的聚合。
所有评论