最近在执迷于区块链,既然学习区块链如果不好好拜读一下其,祖师爷比特币白皮书,自然是有些缘木求鱼,于是仔细看了英文原版 顺便有了这篇翻译。

中本聪
satoshin@gmx.com
www.bitcoin.org

概要. 一个纯粹的点对点电子现金系统,线上支付可以直接从发送方发送到接收方,而不通过任何金融机构。虽然,数字签名可以提供部分解决方案,但是如果仍然需要信任一个第三方来防止双重支付, 便失去了最主要的好处。我们提出了一种方案,使用点对点网络,来解决双重支付问题。该网络会对交易进行哈希运算,将其添加到一个基于哈希工作证明的链上,并打上时间戳;该链会不断延长,生成的记录无法更改,除非重做工作证明(proof-of-work)。最长的链,不仅是已经共同见证的事件顺序的证明,也是来自最大CPU算力池的共识。只要网络中的大多数CPU算力是被诚实节点(没有协作攻击网络)控制着,这些诚实节点就会生成最长的链,并超越攻击者。该网络本身需要有最精简的结构。信息的广播也要基于最有效的方式,节点可以离线,并在将来加入时接受最长的那条工作证明链作为他们离开时发生事件的证明。

1. 介绍

互联网上的商业几乎完全依赖金融机构作为可信的第三方来处理电子支付。虽然这个系统对于大多数交易来说运行良好,但它仍然有基于信任模型的固有弱点——完全不可逆的交易实际上是不可能,因为金融机构无法避免仲裁争议。仲裁的花费增加了交易成本,限制了最小实际交易的规模,并切断了小额交易的可能性。对于不可逆服务失去进行不可逆支付的能力是一个更大的损失。交易有了被撤销的可能性,对信任的需求会无处不在——商家必须对他们的客户保持警惕,要求他们提供更多的信息,而不是本来需要的。一定比例的欺诈被认为是不可避免的。这些成本和支付的不确定性,在人们使用实物货币时是可以避免的,但对于通过通信信道来完成支付,目前还没有任何机制可以排除第三方信任实体。

现在需要的是一个基于加密证明而不是基于信任的电子支付系统,可以让任何有意愿的双方直接进行交易,且不需要一个信任的第三方。在计算上不可逆的交易,将保护卖家免受欺诈,而常规的托管机制可以很容易实现,以保护买家。在这份白皮书中,我们提出了一种解决双重支付问题的方法,使用一个点对点分布式时间戳服务器来生成基于算力的证明,证明按照时间排列的交易。只要诚实节点共同控制的CPU算力多于攻击节点共同控制的,该系统就是安全的。

2. 交易

我们使用一条数字签名链来定义一枚电子货币。每个拥有者将这枚货币传递给下一位拥有者的方式是: 对上一笔交易和下一位拥有者的公匙做哈希运算,取得一个哈希值,并对其做数字签名,然后将这些内容添加到这枚货币(数字签名链)的末尾。收款人可以通过验证该签名来确认自己是这枚货币(链)的最新所有者。

image.png

这里存在的问题是,最新的拥有者无法验证,之前的拥有者有没有进行过双重支付。常见的做法是引入一个信任的中心化权威机构,或者铸币厂来检查每笔交易是否存在双重支付。每笔交易后,这枚货币必须返回铸币厂,铸币厂会发行一枚新的货币,只有由该铸币厂直接发行的货币才会被相信没有双重支付。这种方案的问题在于,整个货币系统的命运完全依赖于运营铸币厂的公司,例如银行。

这里的铸币厂的概念,我认为可以理解为银行或者支付宝之类的金融机构,支付宝中的余额理解为货币,一块钱代表一枚货币,以购买5元苹果为例,当我们点击支付按钮,支付宝官方会从购买方回收5枚货币,买方余额减5, 然后支付宝官方会向收款方发行5枚新的货币,因为收款方信任支付宝,所以相信接收到的5枚货币没有双重支付问题。

我们需要一种方式,能够让收款方知道,上一个拥有者没有签名过更早的交易。我们的目的是,只让最早的那笔交易作数,这样我们不需要关心之后的双重支付尝试。确认一笔交易是否存在过的唯一方式是,知晓所有交易。在铸币厂模型中,铸币厂知晓所有交易,并且决定哪笔交易最先到达。在排除第三方信任实体的情况下,要实现这一点,交易必须被公开发布,而且我们需要这样一个系统:系统中的参与者要对接收到的交易历史的顺序达成一个统一版本。

3. 时间戳服务器

我们提出的这个解决方案从一种时间戳服务器开始。时间戳服务器会生成一个区块的哈希值,每个区块由多个需要被打上时间戳的数据项组成,然后将该哈希值广播出去,就像在报纸或新闻组帖子中[2-5]。时间戳能够证明,这些数据当时是存在的,否则无法得到该哈希值。每个时间戳会将上一个时间戳包含在其哈希中,形成一条链,后边的时间戳进一步加强了前面时间戳的可信度。
image.png

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

为了实现一个基于点对点的分布式时间戳服务器,我们需要使用一个工作量证明系统,类似于Adam Back提出的Hashcash[6],而不是报纸或新闻组贴那样。工作量证明的内容是: 搜索一个值,对该值进行哈希运算后,例如通过SHA-256运算后,其哈希值要满足是以数位0开始。根据要求的0的位数,需要的平均工作量呈指数级增长,而验证只需执行一次哈希。对于我们的时间戳网络,实现工作量证明的方式是:在区块中添加一个随机值,不断递增该随机值,直到其满足条件——该区块的哈希值中0的位数满足指定要求。一旦消耗一定的CPU算力后,满足了工作量证明,那么除非重做工作量证明,否则无法修改该区块。由于后面的区块是链接到该区块的后边,要修改该区块需要重做它后边所有区块的工作量证明。

image.png

工作量证明也解决了多数决议中投票方式的问题。如果多数是按一个IP一票的方式,那么它将能够被拥有大量IP地址的人破坏。工作量证明本质上是一个CPU一票。最长的那条链代表了多数决议,因为最多的工作量证明算力投入到了这条链上。如果大多数CPU算力是被诚实节点控制着,诚实链就会增长的最快,并且超过任何其他竞争链。要想修改过去的某个区块,攻击者必须重做这个区块以及这个区块后面所有区块的工作量证明,然后赶上并超过诚实节点的工作量。我们后面会展示,随着后续节点的添加,一个算力较慢的攻击者赶上诚实链的概率呈指数级递减。

为了应对硬件速度的不断提升,以及随着时间推移运行节点数的动态变化,工作量证明的的难度指数,通过移动平均线根据每小时平均生成区块数来调整。如果生成区块太快,难度指数会增加。

5. 网络

运行该网络的步骤如下:

  1. 新交易广播到所有节点。
  2. 每个节点将新交易收集到一个区块。
  3. 每个节点为其区块寻找工作量证明。
  4. 一旦某个节点找到了工作量证明,就向所有节点广播该区块。
  5. 如果该区块中的所有交易都是有效的,而且还没有被花费,节点会接受该区块。
  6. 节点在链中创建下一个区块时,使用接受区块的哈希值作为其“上一个”哈希时,表明节点已接受该区块。

节点总是认准最长的那条链是正确的那个,并持续向这条链添加新区块。如果两个节点同时广播下一个区块,而这两个区块是不同的版本,很有可能节点接收到这两个区块的顺序会不一致。在这种情况下节点会在接收到的第一个区块上工作,但是也会保存另一个分支以防止它将来变的更长。当下一个工作量证明被找到时,这种不相上下的状态会被打破,因为其中一个分支会变得更长;在另一个分支上工作的节点会切回到更长的这条分支上继续工作。

新交易不是一定要广播到所有节点。只要广播到一些节点,他们很快就会被打包到一个区块。区块的广播对于信息的丢失也有容错能力。如果一个节点没有收到某个区块,在接收到下一个区块时会发现它丢失了一个,然后会去请求丢失的区块。

6. 激励

按照约定,区块中的第一笔交易比较特殊——它会创建一枚新货币,由该区块的创建者持有。这给节点提供了一种激励机制,以支持该网络,并且提供了一种发行货币进入流通的方法,因为这里没有中央权威机构来发行它们。稳定增加固定数量的新货币,类似于金矿旷工消耗资源来挖掘黄金,让黄金进入流通。在我们这里,消耗的是CPU时间和电力。

也可以通过交易费来激励节点。如果交易的输出值少于其输入值,之间的差值作为交易费,被添加到包含该交易的区块的激励中。一旦预定量的货币都进入了流通,激励可以完全转移到交易费,可以完全杜绝通货膨胀。

激励也会有助于让节点保持诚实。如果一个贪婪的攻击者能够网罗比所有诚实节点更多的CPU算力,他有两种选择,使用这些算力进行欺诈把自己花出去的钱偷回来,或者使用这些算力生成新货币。他应该能够发现按照规则行事更划算,这些规则能够让他获得比所有其他人加起来还要多的新货币,而不是去破坏系统让他自己的财富也化为乌有。

7. 回收磁盘空间

一旦一枚货币的最新一笔交易,发生在足够多的区块之前,这笔交易之前的交易可以被丢弃,以节省磁盘空间。为了在不破坏区块的哈希值的情况下实现这一点,交易将被哈希进一个Merkle树中[7][2][5],只有该哈希树的根会被包含在该区块的哈希中。然后早期的区块,可以通过剪掉树枝的方式来压缩大小。树中的内部哈希不需要被保存。
image.png

一个不包含交易的区块头大约是80个字节。如果我们假设10分钟生成一个区块,80 bytes * 6 * 24 * 365 = 4.2MB 每年。截止2008年大多数在售的计算机配有 2GB 内存,根据摩尔定律预测内存每年增加 1.2GB ,所以即使一定要将区块头必须保存在内存中,存储也不会是一个问题。

8. 支付验证的简化

即使不运行一个完整的网络节点也是可以验证支付的。用户只需保存最长工作量证明链的一份副本,它可以通过向网络节点查询以确认拥有了最长的链,并获取一个Merkle树,该树连接了要查询的交易与给该交易打时间戳的区块。他不能自己验证该交易,但是可以验证该交易已经链接到了最长链的某个位置,说明一个网络节点已经接受了这笔交易,其后添加的区块会进一步确认该网络已经接受了它。

image.png

同样的,只要诚实节点控制着网络,这种简化验证就是可靠的,但是如果网络被攻击者控制着,简化验证就会变得比较脆弱。虽然网络节点可以验证他们自己的交易,但只要攻击者持续控制网络,这种简化方式就可能被攻击者的伪造交易欺骗。一种对策是,接受来自其他网络节点检测到无效区块时发出的警告,并在客户端软件上弹出通知,要求下载整个区块,以确认交易的一致性。那些高频接受支付的商家,应该仍然希望运行自己的节点,以确保更独立的安全性和更快速的交易确认。

9. 合并和分割交易额

尽管分别单独处理每个货币是可行的,但为每分货币设置一笔交易太过笨拙。为了交易额的分割和合并,交易包含多个输入和输出。通常输入是上个交易产生的,单个大额输入,或者多个小数额输入的组合,输出最多有两个:一个是支付,另一个是找零如果有的话退还给发送方。

image.png

值得注意的是,扇出——一笔交易依赖于数笔交易;这数笔交易又依赖于更多交易,在这里不是问题。因为从来没有必要去提取一笔交易的完整独立的历史副本。

10. 隐私

传统的银行模型通过限制访问,交易者和信任第三方的信息,来实现一定程度的隐私保护。要公开发布所有交易记录,就不能使用这种方法,但是通过在另一个位置阻断信息流,还是可以实现隐私保护的目的,方式就是: 保持公钥匿名。公众可以看到某人正在将一定数量货币发送给另一个人,但是无法将该笔交易关联到现实中的任何人。这和证券交易所发布的信息级别类似,每笔交易的时间和交易量,即行情是公开的,但不会显示交易双方是谁。

image.png

为每一笔交易生成一对新密匙,可以作为一道额外防火墙,以防止关联到同一个拥有者。由于多输入交易的存在,有些关联仍然不可避免,多输入交易必然暴露其多个输入是属于同一个所有者。风险在于,如果一个公钥的所有者暴露了,通过关联,属于该所有者的其他交易也会暴露。

11. 计算

设想这样一个场景,某个攻击者正在试图生成一条比诚实链更长的替代链。即使他成功了,也不能对系统随意更改,例如,不能凭空创造价值,或拿走不属于他的货币。节点不会接受无效的交易作为支付,诚实节点也绝不会接受包含无效交易的区块。攻击者只能尝试修改他自己的某一笔交易,来取回他已经花出去的货币。

诚实链与攻击者链之间的竞争可以用二项随机漫步(Binomial Random Walk)来描述。成功事件是诚实节点被延长一个区块,两条链的差距加 1,失败事件是攻击者的链延长一个区块,两条链的差距减 1。

攻击者从某一落后位置赶上诚实链的概率类似于赌徒破产问题(Gamble's Ruin Problem)。假设,一个拿着无限筹码的赌徒,从某个亏空时刻开始,允许他赌无限次,目标是填补上已有的亏空。我们能算出他最终能填补亏空的概率,也就是攻击者能够赶上诚实链的概率[8],如下:

image.png

我们假设 p > q,随着攻击者需要赶上的区块数增加,概率将呈指数下降。由于形势对他不利,如果他没有在早期幸运地快速赶上,他落得越远,赶上的机会就越渺茫。

我们现在考虑一笔新交易的收款人要等多久才能确保付款人不能再改变这个交易。我们假设付款人是一个攻击者,想让收款者暂时相信他已经付款,一段时间后将这笔钱再转回给自己,这时收款人会收到警告,但付款人希望这时已为时已晚。

在签名前不久,收款人生成一个新密钥对,并将公钥给付款人。这能防止付款人提前通过持续工作,并有很好的运气下准备一条足够领先的区块链,然后在这时执行交易。一旦交易被发出,不诚实的付款人开始秘密地在一条包含了他的替换版交易的平行链上工作。

收款人等到此笔交易被打包进区块,并已经有z个区块随后被加入。他并不知道攻击者的工作进展究竟如何,但是可以假定诚实区块在每个区块生成过程中耗费的平均时间;攻击者的潜在进展符合泊松分布,其期望值为:
image.png

为计算攻击者现在仍然能赶上的概率,我们给每个他可能达到的进度的泊松密度乘以他在那个进度能赶上诚实链的概率:

image.png

变换以避免对分布的无限尾部求和...

image.png

转为为C语言代码:

#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的增加指数级下降:

image.png

若 P 小于 0.1% ...

image.png

12. 总结

我们提出了一个不依赖于信任的电子交易系统。我们从普通的电子签名货币框架开始,虽然它提供了健壮的所有权控制,由于无法避免双重支付,所以不够完善。为了解决这个问题,我们提出了一个使用工作量证明机制的点对点网络,来记录公开的交易历史,只要诚实节点控制着大多数CPU算力,攻击者不可能通过算力对交易历史记录更改。该网络因其结构简洁而健壮。节点只需很少的协调就能同时工作。他们不需要被认证,因为信息不会被发送到任何指定位置,只需被尽力传播。节点可以随时离开和重新加入网络,只需接受最长的工作量证明链作为它们离开时发生事件的证据。它们通过它们的 CPU 算力投票,通过不断为链添加新的有效区块、拒绝无效区块,来表示它们对有效交易的接受与否。任何必要的规则和奖励都可以通过这个共识机制来强制实施。

参考文献

[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.

Q.E.D.