# 读书笔记：签名与验证 By [Aulee](https://paragraph.com/@aulee) · 2023-03-30 --- 我对 _Programming Bitcoin_ 的第三章的后半部分——签名和验证——理解不够清楚。现结合书中这部分内容按照自己的理解来理一理逻辑线索。这个和书中所要传达的意思可能并不一致。所有错误归于我自己，与原书作者无关。 签名与验证的基本原理 ---------- ### 定义所有权 我们利用椭圆曲线来表达对某物的所有权关系。我们以椭圆曲线上的某个点`P`来代表某一物。可以理解`P`为打在某物上的不可撕毁和改变的标签。这个`P`被称为公钥，是每个人可见的。因为是二维平面上的曲线上的一个点，因此公钥`P`由横坐标和纵坐标的两个值构成。在椭圆曲线上，可以作为公钥的点必须满足一条性质，即其为曲线上一个特定的点`G`的倍数，即`eG=P`。`G`点是每个人都知道的，其坐标数值是公共知识。但是倍数`e`是私人知识。因为从`P`和`G`的数值推测出`e`的值是极为困难以至被认为是不可能的。这被称为“离散对数难题”（discrete log problem）。我们说知道`e`的值的人为`P`所代表的物的所有者。因为只有他能给出从`G`到`P`的确切的倍数，从而可以获得排他的所有权。`e`被称为私钥。 ### 验证所有权 但是难点在于，`e`的所有者既要向人们证明他知道`e`，又不能向别人直接透露`e`,否则人人都可宣誓为`P`所代表的物的所有者，使`e`失去了证明排他所有权的能力。因此他需要一种间接的机制来证明。比如他可以向人们展示，他可从某一“随机”的`R`出发，经一定倍数到达`P`，即`sR=P`。而设若`R`也是`G`的倍数，即`kG=R`，则有`skG=P`，从而证明了他知道`e=sk`。他并不向人们直接展示`k`，而代以向人们展示`R`，否则他就暴露了`e`。因此所有者所发出的签名（signature）为`(s, R)`。其他人可以由此轻松验证`sR=P`，以确认其对`e`的知识，进而对`P`所代表的物的所有权。这真是个聪明的办法！ 但是上述聪明的办法却存在一个致命的漏洞：`s`与`R`都是由签名者给出的，则`R`并不是任意给定的，而可能是以先射箭后画靶子的方式倒推出来的：`R=P/s`。此时所谓的验证就是在重复一个恒等式：`s(P/s)≡P`。为了解决这个问题，签名者转而向人们展示`sR=rP`。其中`r`为`R`的横坐标，即`R=(r, y)`。这个式子是难以随意捏造的。因为签名者通过不断调整`s`与`R`的值而恰好达到P的r倍是非常困难的，是与离散对数难题同等困难的难题。按照原书作者Jimmy Song的比喻，这相当于在射出箭之前，就在箭头镌刻了其射出后要降落的目标，从而证明了自己非凡的箭艺。在上述等式中，我们可以视等式左边的R为射出箭后实际达到的目标，而视等式右边的r为镌刻在箭头的目标。二者如能若合符节，即可视为提供了关于签名者对`e`的知识的证明(即在我们的比喻中证明了自己的箭艺)。为什么呢？因为当知道`e`时，找到`(s, R)`使得`sR=rP`是个轻松可解决的问题。我们可以选择任意的`k`以构建`R`：`kG=R`。这个`k`也是私人知识，不对外公布。同时，由于知道`e`，所以有`eG=P`。代入上面等式，有`skG=reG`。从而解得`s=re/k`。这样我们就得到了可以满足等式的签名数对`(s, R)`。但是在上述证明中我们尚待排除一种可能，即我们之所以在箭头镌刻`r`，是因为`R`这个目标是我反复练习过的，我有把握射中目标，我才将之刻上去！这样看来，我们在段首提出的漏洞并没有得到解决？！这种担心是多余的。因为，即使通过反复练习找到了符合等式的`(s, R)`数对，但反复练习的成本不仅极高，而且毫无用处，因为，尽管通过惊人成本的试错获得了对`P`所代表物品的所有权，但并不能真的进一步做什么以达成对物的支配。此时所有权就只是没有实际功用的空洞的所有权。下面说明，需要知道`e`，才能真正获得对`P`所代表的物的支配权。 ### 扩展：验证信息 至迟从17世纪英国哲学家洛克起，经济学界就已明确了对物的所有权产生自对物的支配权，即对物的消费、使用、买卖、处置等的权利。如果没有对物的支配权，则所有权就是空洞、抽象的因而是没有现实意义的。因此，对物的所有权一定要靠对物的支配权来体现。我们前面通过私钥、公钥对`(e, p)`所定义的所有权仍然是不包含支配权的空洞的所有权。现在，我们扩展`sR=rP`等式以体现对`P`所代表的物的支配。首先将上式移项，`R=r/sP`。然后在等式右侧加入新的一项，得`R=r/sP+z/sG`。其中`z`被称为签名哈希（signature hash），是对关于`P`所代表的物的一条信息的哈希值。这条信息可以是关于物的描述，或者是对物进行处置、交易的指令。对`P`所代表的物的支配权正是通过加入`z`来体现的。扩展之后，生成签名的流程是类似的。首先产生一随机的`k`，由此计算`R=kG`。然后依据上式计算`s`值：`s=(re+z)/k`。由此对外公布签名`(s, R)`。验证者使用此签名，和其他公开信息`P`和`G`，完成对等式的验证。这一验证达成了两项证明：一是证明了签名者对`P`所代表的物的所有权，二是证明了签名者（也即所有者）发出了关于物的信息`z`。这样，通过数字签名所实现的所有权关系就是包含了处置权的完整的所有权关系。注意在扩展模型里，每次签名都会随信息哈希值的不同而不同，这使得经过反复练习而能射中某一箭靶（即反复试错猜出一对能通过验证的签名）变得更不可行了。唯一的生成正确签名的途径是知道`e`。 一些技术性细节 ------- * `k`不能公开。如果`k`被公开，可以反解出私钥`e=(sk-z)/r`。 * `k`不能重复使用。如果在两次签名中使用同一`k`。则有`s_1=(re+z_1)/k, s_2=(re+z_2)/k`,由此可反解出私钥`e=(s_2z_1 - s_1z_2)/(rs_1-rs_2)`。 * 以上两条说明`k`的“随机性”非常重要。一旦`k`被猜中，私钥即被暴露。所以书中介绍了一种提供确定性的`k`的算法，`k`取决于私钥`e`和签名哈希`z`。因此每个人的每次签名都会得到不同的`k`。 * 上述所有的代数运算都是模运算（modulo arithmetic）。在模运算中任何加减乘除的运算，结果都是小于模所规定的质数的整数。比如说，求逆的运算使用到费马小定理（Fermat’s Little Theorem）：`k^(-1)=k^(n-2) % n`，所得结果仍为同一域（field）内的整数。 * 进行对整数的模运算有两个好处。首先计算机不擅长处理无穷小数。而有限小数不能构成一个域。有限小数间的乘除运算并不总是有限小数。其次只有当椭圆曲线上的点是模运算的整数时，对点的数乘才能产生出类似随机性的跳跃性，才能产生出数乘的非对称性，从而制造出可以利用的离散对数难题。 * 在比特币所使用的椭圆曲线密码体系secp256k1中，实际包含了两组模运算。一组是椭圆曲线上的点的加减运算中涉及的模运算。这组模运算的质数为`p=2^256-2^32-977`，其10进制数值为： `115792089237316195423570985008687907853269984665640564039457584007908834671663` * 另一组模运算为与椭圆曲线上的点的数乘相对应的系数的模运算。由于数乘序列`{G, 2G, 3G, 4G, …, nG}`是一个周期为`n`的有限群（finite group)。因此相应的系数运算构成一个质数为`n`的模运算。`n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141`,其10进制数值为: `115792089237316195423570985008687907852837564279074904382605163141518161494337` * 注意`n`和`p`这两个巨大的数虽然接近，但并不相同。在编程实现中，特别容易混淆两组模运算而发生错误。 参考书目 ---- Song, Jimmy. _Programming bitcoin: Learn how to program bitcoin from scratch_. O'Reilly Media, 2019. --- *Originally published on [Aulee](https://paragraph.com/@aulee/iTMsX8LyPOzG9rmMrK2F)*