比特币:一种点对点(P2P)电子现金系统 译

摘要

一个纯正的 P2P 版本电子现金支持在线支付会从一方直接发送到另一方,而不需要经过一个金融机构。数字签名解决了部分问题,但是如果还是需要一个可信的第三方来防止双花(double-spend)问题,那也就失去了主要利处。我们提出了一个使用 P2P 网络解决双花问题(double-spending problem)的方案。网络时间戳(timestamps)化交易(transactions)的方法是将它们散列(hash)到基于散列的工作量证明,不断增长的链(chain)上,形成一条记录,不可修改除非重做工作量证明。最长的链不仅作为目击事件顺序的证明,而且也证明它来自 CPU 算力最大的池。只要大量 CPU 算力控制在不攻击网络的节点里,它们将会产生最长的链而且比攻击者节点算得快。网络本身要求最小的结构。消息会尽量广泛传播,而节点可以随意离开或者加入网络,通过接收最长的工作量证明的链来确认它们离开网络时发生的事情。

译者注

双花问题:即一笔钱被花了两次或者两次以上,也叫”双重支付”。

1. 简介

互联网上的商业几乎完全依赖于金融机构作为可信赖的第三方来处理电子支付。虽然该系统对大多数交易(transactions)都能很好地工作,但它仍然存在基于信任的模型固有的缺陷。完全不可逆的交易实际上是不可能的,因为金融机构无法避免调解纠纷。调解成本增加了交易(transactions)成本,限制了最小实际交易(transactions)规模,并切断了小规模临时交易的可能性,而且在无法为不可逆服务进行不可逆支付的能力丧失方面存在更大的成本。有了逆转的可能性,对信任的需求就会扩大。商家必须提防他们的客户,麻烦他们提供除必须信息外的更多信息。一定比例的欺诈被通过不可避免。这些成本和支付不确定性可以通过使用物理货币在人身上避免,但是不存在这样的机制在没有可信第三方的情况下通过通信信道进行支付。

需要的是一个基于加密证明而不是信任的电子支付系统,允许任何两个自愿的当事方在不需要信任的第三方的情况下直接进行交易。在计算上无法逆转的交易将保护卖方免受欺诈,而常规的托管机制(escrow mechanisms)可以很容易地实施,以保护买方。这篇论文提出了一种双花问题的解决方案,利用 P2P 分布式时间戳服务器生成交易(transactions)按时间顺序排列的计算证明。只要诚实节点共同控制的 CPU 算力比任何攻击者节点的合作组多,系统就是安全的。

2. 交易 Transactions

我们定义了一种数字签名链的电子硬币。每个拥有者通过对上一次交易(transaction)和下个拥有者公钥的散列(hash)做数字签名并将它们添加到硬币的末端来转让硬币。收款人通过验证签名来验证链的拥有权。

译者理解:

私钥加密,公钥解密:一般被用于数字签名。数字签名是用于防篡改和防止假冒的,因为只有一人拥有私钥。甲方通过私钥对数据进行签名,乙方通过甲方的公钥验证签名,如果成功,说明确实是甲方发来的,并且数据没有被修改。

数字签名操作:先将上一次交易(transaction)和下个拥有者公钥进行散列(hash),然后用私钥对散列进行加密生成数字签名。

验证操作:收款人使用拥有者的公钥对数字签名进行解密,验证该签名是否来自拥有者。

Transaction

当然,问题是收款人不能证实所有拥有者都没有双花(double-spend)硬币。一个常见的解决方案是引入一个可信的中央机构或造币厂(mint),检查每笔交易是否存在双花。每笔交易后,必须将硬币退回造币厂(mint)发行新硬币,只有直接从造币厂发行的硬币才能相信没有双花(double-spend)。这个解决方案的问题在于,整个货币体系的命运取决于运营造币厂(mint)的公司,每笔交易都必须通过它们,就像银行一样。

我们需要一种方式让收款人知道先前的拥有者没有签名任何更早的交易(transactions)。

译者理解: 签名任何更早的交易指没有创建多个数字签名,即没有双花

就我们的目的而言,最早的交易才是最重要的,所以我们不关心后面交易试图双花的问题。确认一笔交易不存在的唯一方法是知道所有交易。在以造币厂为基础的模型中,造币厂知道所有的交易,并决定哪些交易最先到达。要在没有可信第三方的情况下实现这一点,交易必须公开宣布[1]并且我们需要一个系统,让参与者们对他们接收的交易顺序历史达成一致。

3. 时间戳服务器 Timestamp Server

我们提出的解决方案从时间戳服务器(timestamp server)开始。时间戳服务器的工作方式是对要加时间戳的项目块(a block of items)进行散列(hash),并广泛地发布该散列(hash),例如在报纸或全球新闻组网络(Usenet)帖子中[2-5]。时间戳证明数据必须在当时存在,才能进入到散列(hash)中。每个时间戳在其散列(hash)中包括上一个时间戳,形成一个链,每个附加的时间戳加固了其前面的时间戳。

timestamp-server

4. 工作量证明 Proof-of-Work

要在 P2P 的基础上实现分布式时间戳服务器,我们需要使用类似于 Adam Back’s Hashcash[6] 的工作量证明系统,而不是报纸或全球新闻组网络(Usenet)帖子。工作量证明涉及到寻找一个值,当被散列(hashed)时,例如使用 SHA-256,这个值的散列(hash)以若干个零位(ZERO bits)开始。所需的平均工作量随着指定的零位(ZERO bits)数增加而指数级增长,可以通过执行单个散列(hash)验证。

对于我们的时间戳网络,我们实现的工作量证明是通过递增 block 中的 nonce 直到找到一个值,该值使得 block 的散列(hash)的零位数符合要求。一旦消耗 CPU 算力满足了工作量证明,block 将不能修改除非重做工作量证明。因为新的 blocks 会链接在当前 block 后面,修改当前 block 的工作将包括重做它后面的所有块。

译者理解:比特币工作量证明具体实现是以 SHA256 算法计算一个目标哈希,使得这个哈希值符合前 N 位全是 0。

proof-of-work

工作量证明还解决了大多数决定中确定代表权的问题。如果大多数基于一个 IP 地址一票,那么任何能够分配许多IP的人都可以颠覆它。工作量证明本质上是一个 CPU 一个票。大多数决定由最长的链代表,最长的链意味着投入的工作量证明最大。如果 CPU 算力的大多数由诚实节点控制,那么最诚实的链将会增长最快并超过任何与之竞争的链。为了修改过去的 block,攻击者将不得不重做该 block 以及它后面的 blocks 的工作量证明而且要追上并超过最诚实的节点们的工作速度。我们稍后会讲到速度更慢的攻击者追上的可能性会随着后续块的增加指数级下降。

为了补偿随着时间过去硬件速度的提高和运行节点的兴趣变化,工作量证明的难度由一个以平均每小时产生的块数为目标的活动平均值来确定。如果它们增加太快,难度就会增加。

5. 网络 Network

运行该网络的步骤如下:

  1. 新交易向所有节点广播。
  2. 每个节点将新交易收集到 block 中。
  3. 每个节点为它的 block 计算工作量证明。
  4. 当一个节点计算得到工作量证明后,向所有节点广播 block。
  5. 节点接收那些含有的所有交易都有效并且没被花掉的 block。
  6. 节点通过在链中创造下个 block,使用接收的 block 的散列(hash)作为 privious hash 表达它们接收了 block。

节点始终将最长的链视为正确的链,并将继续努力扩展它。如果两个节点同时广播下一个块的不同版本,则某些节点可能首先接收这一个或另一个。在这种情况下,他们会在收到的第一个分支上工作,但会保留另一个分支,以防它变得更长。当下一个工作量证明被找到时一个分支会变得更长,它们的连接将不复存在;工作在另外一个分支上的节点将切换到更长的分支上。

新交易不一定需要到达所有节点。只要他们到达很多的节点,不久就会进到 block 中。Block 广播也容忍信息丢失。如果一个节点没有接收到 block,当它接收到下一个 block 并发现丢失了 block时,就会请求这个 block。

6. 激励

按照惯例,区块中的第一笔交易(transaction)是一种特殊交易(transaction),它产生(start)了一枚新硬币归 block 创建者所有。这增加了节点支持网络的动力,并提供了一种将硬币初始分配到流通中的方法,因为没有中央授权来发行它们。稳定增加一定数量的新硬币类似于黄金开采商(gold miner)消耗资源以增加黄金的流通量。在我们的场景中,花费的是 CPU 时间和电力。

激励措施也可以由交易费用(transaction fees)提供资金。如果交易的输出值小于其输入值,则差额是交易费用,该费用加到包含交易的 block 的激励值中。一旦预定数量的硬币进入流通,激励就可以完全过渡为交易费用,并且完全没有通货膨胀。

激励措施可能有助于鼓励节点保持诚实。如果一个贪婪的攻击者能够集合比所有诚实节点更多的 CPU 算力,他将面临选择使用它窃取他的付款来欺骗别人,还是使用它产生新的硬币。他应该会发现,遵守这些规则比从其他任何人那里骗得的钱要多得多,这些规则比其他任何人加起来都更有利于他,而不是去破坏系统和他拥有的财富的有效性。

译者理解

如何理解窃取他的付款来欺骗别人?

这就是 51% 攻击(majority attack)。根据第5节的工作量证明所讲可知,当拥有超过半数的算力时,不仅可以重做当前 block 和后面的 blocks,还能在重做完后创建新 block 赶超其它节点。使得它创建的链更长而获得全网认可。相当于可以篡改他之前的付款交易。

7. 回收磁盘空间

一旦硬币中的最新交易被埋在足够的 blocks 下,已支付的交易就可以丢弃,以节省磁盘空间。为了在不破坏 block 的散列(block’s hash)的情况下实现这一点,交易(transactions)在默克尔树(Merkle Tree)[7] [2] [5]中进行散列(hashed)处理,只有根包含在block 的散列(block’s hash)中。然后可以通过砍掉树的分支来压缩旧块。内部的散列(hash)不需要存储。

reclaim-disk-space

没有交易记录(transactions)的 block header 大约为 80 字节(bytes)。如果我们假设每10分钟产生一个 block,则每年 80 字节 * 6 * 24 * 365 = 4.2 MB。截止到2008年,销售的计算机系统通常带有 2GB RAM,而摩尔定律预测当前每年会增长 1.2 GB,即使必须将 block header 保存在内存中,存储也不成问题。

8. 简化支付验证

无需运行完整的网络节点就可以验证付款。用户只需要保留最长工作量证明链的 block header 的副本,在确信自己拥有最长的链之前,可以通过查询网络节点(network nodes)来获取该副本,以及获取默克尔分支(Merkle branch),该分支将交易(transaction)链接到已加上时间戳的 block 上。他本身无法检查交易(transaction),但是通过将其链接到链中的某个位置,他可以看到有网络节点已接受该交易,并且其之后添加的 blocks 也进一步确认网络已接受该交易。

译者理解

如何理解已加上时间戳的 block(the block it’s timestamped in)?

查看第三节 Timestamp Server

payment-verification

这样,只要诚实的节点控制网络,验证就是可靠的,但如果网络被攻击者控制,验证会更容易受到攻击。虽然网络节点(network nodes)可以自己验证交易(transaction),但只要攻击者能够继续控制网络,简化的验证方法就可能被攻击者捏造的交易(transaction)所欺骗。防止这种情况发生的一种策略是,接收来自网络节点检测到无效块时发出的警报,提示用户软件下载完整的 block 和被警告的交易(transaction)以确认是否不一致。经常收到付款的企业可能仍希望运行他们自己的节点,以获得更独立的安全性和更快的验证。

9. 合并和拆分价值

尽管可以分别处理硬币,但要对转账中的每一分钱都进行单独交易就会很不方便。为了允许价值被分割和合并,交易要包含多个输入和输出。通常情况下,会有一个单笔输入来自较大的上一笔交易(transaction)或多笔较小金额的组合输入,以及最多有两笔输出:一笔用于支付,另一笔将零钱(如果有)返回给发送方。

combine-splitting-value

应该注意的是,扇出(fan out),指一个交易依赖于多个交易,而这些交易又依赖于更多交易,在这里不是问题。因为永远不需要提取交易历史记录的完整独立副本。

译者理解

fan out:直译为扇出,也意为展开

10. 隐私

传统的银行模式通过限制相关方和受信任的第三方对信息的访问来达到一定程度的隐私。公布所有交易(transactions)的必要性排除了此方法,但仍可以通过在另一个地方中断信息流通来保持隐私:通过使公钥匿名。公众可以看到有人正在向其他人汇款,但没有信息将交易(transaction)和任何人联系在一起。这类似于证券交易所发布的信息级别,在该级别上,公开了单个交易的时间和规模,即”磁带”(tape),但没有告知参与方是谁。

译者理解

公钥匿名:使得我们不知道转账的发起方和接收方
tape:磁带;听到声音,却不能确定是谁的声音。

privacy

作为一个附加防火墙,每个交易(transaction)都应该使用新的密钥对,以防止它们指向同一所有者。在多输入交易(multi-input transactions)中,某些联系仍然不可避免,因为显然它们的输入都是由同一所有者拥有的。风险在于如果密钥的所有者暴露,该密钥所有者的其他交易也会暴露。

11. 计算

考虑攻击者试图生成一条替代诚实链的链且比诚实链延长速度更快的情况。即使做到这一点,也不意味着系统会被任意更改,比如凭空创造价值或获取不属于攻击者的钱。节点不会接受无效交易(transaction)的付款,诚实节点不会接受包含它们的 block。攻击者只能尝试更改他自己的交易(transaction),偷回他最近花掉的钱。

诚实链和攻击者链之间的竞争可以描述为二项随机漫步(Binomial Random Walk)。成功事件是诚实链延长一个 block,领先优势增加 1,失败事件是攻击者链延长一个 block,差距减少 1。

攻击者追赶上给定差距的概率类似于赌徒破产问题(Gambler’s Ruin problem)。假设信用能够无限透支的赌徒从欠钱开始赌钱,可以进行无数次尝试回本。我们可以计算出他能回本的概率,或者说攻击者链赶上诚实链的概率,如下所示[8]:

p = 诚实节点产生下一个 block 的概率

q = 攻击者产生下一个 block 的概率

qz = 攻击者落后 z 个 blocks 追上的概率


$$ q_{z}= \begin{pmatrix} 1&if p \leq q\\ \left (q/p \right )^{z}&\ if p>q \end{pmatrix} $$


假设 $p > q$,随着攻击者要追赶的 blocks 数不断增加,概率会呈指数下降。如果他在早期没有追赶成功,那么随着他落后地越来越多,他的机会也会变得越来越渺茫。

现在考虑下新交易的接收者需要等待多长时间才能充分确定发送者不能更改交易。我们假设发送者是攻击者,他想让接收者相信他已经支付过一段时间,然后再在一段时间后将交易切换为支付给自己。当这种情况发生时,接收者会收到警告消息,但发送者希望这已经为时已晚。

接收者生成一个新的密钥对,并在签名前不久才将公钥给发送者。这可以防止发送者提前准备一个区块链(a chain of blocks),通过不断地为该链生成 blocks,等到他伪造的链足够超前,然后在那一刻执行交易。一旦交易被发送,不诚实的发送者就开始偷偷准备包含其另一个版本的交易的并行链。

接收者会一直等待直到交易被添加到一个 block 中并且在其之后链接了 z 个 blocks。他不知道攻击者已经取得的确切进度(重做了多少 blocks),但是假设诚实的 block 花费的时间是每个 block 的平均预期时间,那么攻击者的潜在进度(重做了多少 blocks)将是一个泊松分布(Poisson distribution),期望值为:


$$ \lambda = z\frac{q}{p} $$


泊松分布

如果某事件以固定强度 $\lambda$,随机且独立地出现,该事件在单位时间内出现的次数(个数)可以看成是服从泊松分布。
参考 http://episte.math.ntu.edu.tw/articles/sm/sm_16_07_1/index.html

为了得到攻击者当前仍然可以追上的概率,我们将用表示攻击者取得的各个进度的泊松密度乘以他从该点可以追上的概率:


$$\sum_{k=0}^{\infty }\frac{\lambda ^{k}e^{-\lambda }}{k!}\cdot \begin{Bmatrix} \left ( q/p \right )^{\left ( z-k \right )} & if k\leqslant z\\ 1 & if k > z \end{Bmatrix}$$


重新调整避免对分布的无穷极数求和:


$$ 1-\sum_{k=0}^{\infty }\frac{\lambda ^{k}e^{-\lambda }}{k!} \left ( 1-\left ( q/p \right )^{\left ( z-k \right )} \right ) $$


译者注

用表示攻击者取得的各个进度的泊松密度乘以他从该点可以追上的概率,这句话我翻译不一定对。

转换成 C 语言代码…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}

运行一些结果,我们可以看到概率随 z 增加呈指数下降。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012

q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006

求解 P 当小于 0.1%…

1
2
3
4
5
6
7
8
9
P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340

12. 总结

我们提出了一种不依赖信任的电子交易系统。我们从常见的数字签名硬币框架开始,该框架提供了对所有权的强大控制,但是它并不完善因为没有防止双花问题(double-spending)。为了解决这个问题,我们提出了一种使用工作量证明的 P2P 网络来记录交易的公开历史,如果诚实节点控制了大多数 CPU 算力,则对于攻击者而言,更改记录很快会变得在计算上不现实。该网络非结构化的简单性非常健壮(robust)。节点在几乎没有协调的情况下同时工作。它们不需要识别,因为消息不会被路由到任何特定的地方,只需要尽最大努力地传递。节点可以随意离开和重新加入网络,接收工作量证明链来证实它们离开时都发生了事情。它们用自己的 CPU 算力投票,通过扩展有效 blocks 来表达对有效块的接受,拒绝处理无效块来表示拒绝。任何必要的规则和激励措施都可以通过这种共识机制(consensus mechanism)来执行。

参考文献

[1] W. Dai, “b-money,” http://www.weidai.com/bmoney.txt, 1998.

[2] H. Massias, X.S. Avila, and J.-J. Quisquater, “Design of a secure timestamping service with minimal trust requirements,” In 20th Symposium on Information Theory in the Benelux, May 1999.

[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.

[4] D. Bayer, S. Haber, W.S. Stornetta, “Improving the efficiency and reliability of digital time-stamping,” In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[5] S. Haber, W.S. Stornetta, “Secure names for bit-strings,” In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.

[6] A. Back, “Hashcash - a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002.

[7] R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and
Privacy, IEEE Computer Society, pages 122-133, April 1980.

[8] W. Feller, “An introduction to probability theory and its applications,” 1957.


论文相关信息

作者 SatoShi Nakamoto

邮箱 satoshin@gmx.com

网址 www.bitcoin.org