比特币 —— 点对点电子现金系统

摘要：纯粹的点对点电子现金需要能让人们在网络上直接进行支付，而无需经过任务金融机构。数字签名提供了一部分的解决办法，但是主要问题是我们仍然需要可信任的第三方机构来防止双花问题。在这篇文章中，我们提出了一个点对点网络的解决方案来应对双花问题。该网络会将时间戳和交易进行哈希计算，并将其放入一条不断增长的、基于工作量证明的链中，除非重新进行工作量计算，否则所有的记录都不能被修改。最长的那条链不止作为所有事件的见证者，同时证明其拥有最大的CPU算力。只要网络中占大多数的CPU算力不合作对网络进行攻击，它们就会生成最长的那条链并且超过攻击者。网络自身会保持结构最小化。消息通过广播传递，但不保证一定传达，只会在N次内尽可能尝试。节点可以随时进入与退出网络，并会接受在它们不在的那段时间里产生的最长链。

1. 介绍

因特网上的商业模式几乎都需要一个金融机构扮演可信赖的第三方机构来处理电子支付。尽管这个系统运行良好，能处理绝大多数交易，但其内在仍然是软弱的信任模式。完全不可逆的交易不可能真正存在，因为金融机构不可能避免调解争端。这种调解产生的成本提高了交易的成本，限制了实际最小交易的额度并且扼杀了可能的小额支付，这种可逆的交易还造成了非常多的损失。因为交易有逆转的可能性，所以才会有越来越广泛的对信任的需求。商人必须谨慎地对待他们的客户，不断地“烦”他们已获取更多的信息，以防止客户买到了他们不想要的（然后客户就发起“逆转”交易，退货 —— 这将对商人造成损失）。一定比例的欺诈不可避免。这种损失能够通过使用实际的现金通过线下支付解决，但是目前不存在网络通信中实现不需要第三方的支付机制。

我们真正需要的电子支付系统不是基于信任的，而是基于密码学的，让两个乐意交易的个体直接进行支付，而不是还要通过一个第三方机构。虚拟的、基于计算的交易可以保护卖家防止被骗，而普通的交易凭证机制又能保护买家。在这篇论文中，我们提出了一个针对双花问题的解决方案，对所有交易使用点对点分布式时间戳服务器来生成一个可计算的证明，证明其顺序。

2. 交易

我们定义一个电子货币就是一串电子签名。货币的拥有者如果要转移这枚货币（转账）的话，需要对前一笔交易和下一位拥有者的公钥进行哈希计算并将结果添加到货币的末尾，收款人可以通过验证签名以确认货币归属。

此时问题出现了，收款人虽然可以确认这枚货币是否是付款人所拥有，但无法确认付款人是否将这枚货币转给了两个人！这就是双花问题，也称双重支付问题。常见的解决方式就是找第三方中心机构，在其机构里保留着该用户的交易流水，从而可以通过检查每笔交易以防止双花问题。在每笔交易后，货币必须返还给铸币厂，然后发行一枚新币，并且新币直接有铸币厂发行，于是不用担心双花问题。这个解决方案的问题就是我们把整个货币系统的命运都交到了运行铸币厂的公司手上，并且每笔交易都不得不通过它们才能达成，比如大家熟知的银行。

我们需要一种既能让收款人确认、但又不需要前一个拥有者去给之前的交易签名的方式。为了这个目的，第一笔交易是最重要的，所以不需要关注后续交易的双花问题。确定交易缺失的唯一方法就是拥有所有的交易历史。在铸币厂基础模型中，铸币厂需要知道所有的交易，并且能决定哪一笔第一个到达。为了实现不需要承担信任的机构，交易历史必须被公开宣布。收款人需要证明在收到每一笔交易的这个时间点时，大多数节点承认其实第一个到达。

3. 时间戳服务器

为解决这个问题，我们首先需要一个时间戳服务器。时间戳服务器通过对以区块形式存在的一组数据进行随机散列而加上时间戳。同时，将此散列值进行广播。就像是报纸或世界性新闻组织中的文章一样。显然，该时间戳能够证实特定数据必然在某特定时间是存在的，因为只有在该时刻数据存在，才能够获取相应的随机散列值。每个时间戳应当将前一个时间戳纳入其随机散列值中，每一个随后的时间戳都对之前的一个时间戳进行增强(reinforcing)，这样就形成了一个链条（Chain）。

4. PoW（工作量证明）

为了在点对点基础上实现分布式时间戳服务，我们需要使用和 Adam Back 的哈希现金相似的工作量证明系统（PoW），像新闻报纸那样工作显然是不够的。工作量证明需要在散列时扫描到一个特定的散列值，比如在SHA-256下，散列值以一定个数的0开头。随着0的个数的上升，所需要的工作量也随呈指数级增长，但是验证结果只需要1次散列运算。

为了我们的时间戳网络，我们在区块中增加一个随机数，并需使此区块的散列值包含需要个数的0。只要CPU耗费的工作量能够满足工作量证明机制，那么除非重做所有工作，否则区块将不能被改变。而且区块是一个连着一个的，改变一个区块中的信息就还需要重新完成后面所有区块的工作量。

同时，工作量证明机制也解决了谁是大多数代表的问题。如果大多数是靠一个IP地址一票来决定的话，那么可以分配大量IP地址的节点将破坏公平。工作量证明机制的本质是一个CPU一票。大多数是最长链代表的，因为最长链有最大的工作量。如果大部分的CPU算力是诚实节点，那么，最诚实的链将增长的更快并且能超过任何竞争者的链。如果要修改一个过去的区块，攻击者将不得不重做这个区块的工作量证明及其之后所有区块的工作量证明，而且还需要赶上和超过诚实节点所做的工作。我们将在之后证明，如果一个较慢的攻击者试图赶上随后的区块，其成功率将呈指数锐减。

还有一个问题就是，硬件的运算速度在高速增长，节点参与网络的程度则有所不同。为了解决这个问题，工作量证明的难度(the proof-of-work difficulty)将采用移动平均目标的方法来确定，即令难度指向令每小时生成区块的速度为某一个预定的平均数。如果区块生成的速度过快，那么难度就会提高。

5. 网络

比特币网络的运行步骤：

  1. 新交易广播到所有节点
  2. 每个节点都把新交易加入到区块
  3. 每个节点都为自己的区块做工作量证明
  4. 当一个节点完成了工作量证明后，将此证明广播给所有节点
  5. 当所有的交易都在区块里并且没有花费时，此区块将被节点接受
  6. 节点通过在链中创建下一个块来表达它们对块的接受，使用接受的块的哈希值作为新块的前一个哈希值

节点总是将最长链作为正确的链，并继续延长最长链。如果两个节点同时广播了两个下一个区块的不同的版本，有些节点可能首先接收到一个的区块或另一个的区块。这个时候，它们就会在先到的区块上工作，同时保存另一个到分支中。当下一个工作量证明到来时，一条分支会变得更长，这时候节点们就将切换到更长的分支上。

新交易的广播不一定要广播给所有节点。只要已经到达了许多节点，不久就会进入一个块。块广播也容忍消息的丢失，如果一个节点没有收到一个块，那么当新区块来时会意识到有块已丢失，会去请求这个块。

6. 激励

按照惯例，块中的第一个交易是块创建者拥有的新比特币的特殊交易。这让节点有更大的动力来支持网络，并且提供了货币发行与流通的方式，没有任何中央节点有权力发行货币。不断增加的新硬币数量就像淘金者为了增加流通中的黄金而消耗资源一样。在我们的例子中，消耗的是CPU时间和电能。

这种激励还可以通过交易费用来实现。如果一个交易的输出值小于它的输入值，那么差额就是交易费用，它被添加到包含交易的块的激励值中。一旦预定数量的硬币进入流通，这种激励机制就可以完全过渡到交易费用，完全不受通货膨胀的影响。

这种激励有助于节点保持诚实。如果一个贪婪的攻击者拥有比所有诚实的节点更多的CPU能力，他将选择使用这些资源来偷回他的付款以欺骗他人，或者使用这些资源来生成新的硬币。他会发现，遵守规则比破坏制度和自己财富的有效性更有利可图，因为这些规则有利于他获得比其他人加起来还要多的新硬币。

7. 磁盘空间回收

一旦币中的最新交易被掩埋在足够多的块下，就可以丢弃之前的交易，以节省磁盘空间。为了在不破坏块哈希的情况下促进这一点，事务被散列在Merkle树[7][2][5]中，只有根包含在块的哈希中。旧区块可以通过砍掉树枝来压实。内部散列不需要存储。

没有交易的块头大约是80字节。假设每10分钟生成一个块，那么每年 80字节* 6 * 24 * 365 = 4.2MB。在2008年，计算机系统的内存通常为2GB，而摩尔定律预测当前每年增长1.2GB，因此存储应该不是问题，即使块头必须保存在内存中。

8. 简单支付验证（SPV）

可以在不运行完整网络节点的情况下验证支付。用户只需要保留最长链的区块头的副本，通过查询网络节点直到确信自己拥有最长链，并且可以将交易链接到其时间戳所在的块的Merkle分支上。节点不能自己检查交易，但是通过将交易链接到链中某个位置，它可以看到有网络节点已经接受了交易，并且在在进一步确认网络已经接受交易后将其添加入块。

因此，只要是诚实的节点控制网络，验证就是可靠的，但是如果网络被攻击者控制，验证就容易受到攻击。虽然网络节点可以自己验证事务，但只要攻击者继续控制网络，简化的方法就会被攻击者伪造的事务所欺骗。防范这种情况的一种策略是，当网络节点检测到无效的块时，接收来自它们的警报，提示用户的软件下载完整的块，并提醒事务确认不一致。经常收到付款的企业可能仍然希望运行自己的节点，以获得更独立的安全性和更快的验证。

9. 货币组合与分割

虽然单独处理一个币是可能的，但对转帐的每一分钱单独进行交易是很笨拙的。为了允许值被分割和组合，交易包含多个输入和输出。通常情况下，一个较大的前一个交易的单个输入或多个较小金额组合的输入，最多有两个输出:一个用于支付，一个找零返回给(如果有的话)给发送方。

需要注意的是，当一个交易依赖于多个交易，而这些交易依赖于更多交易时，在这里不是问题。不需要提取交易历史的完整独立副本。

10. 隐私

传统的银行模式通过限制相关方和受信任的第三方对信息的访问来达到一定程度的隐私。公开宣布所有交易的必要性排除了这种方法，但隐私仍然可以通过在另一个地方中断信息流来维护:保持公钥匿名。公众可以看到某人正在向其他人转账，但是没有将交易链接到任何人的信息。这类似于证券交易所发布的信息水平，在证券交易所，个人交易的时间和规模(即“磁带”)是公开的，但不告诉当事人是谁。

作为额外的防火墙，每个交易都应该使用一个新的密钥对，以防止它们链接到公共所有者。对于多输入交易，一些链接仍然是不可避免的，这必然表明它们的输入属于同一所有者。风险在于，如果某个密钥的所有者被披露，链接可能会显示属于同一所有者的其他交易。

11. 计算

我们考虑一下攻击者试图以比诚实链更快的速度生成替代链的场景。即使攻击者实现了这一点，也不会让系统面临任意的变化，比如凭空创造价值，或者从攻击者那里拿钱。节点不会接受无效的支付交易，诚实的节点不会接受包含它们的块。攻击者只能试图改变自己的一笔交易，以收回他最近花的钱。

诚实链和攻击链之间的竞争可以描述为二项分布事件。成功事件是诚实链扩展了一个block，增加了+1，失败事件是攻击者的链扩展了一个block，减少了-1的差距。

攻击者弥补给定赤字的概率类似于赌徒破产问题。假设一个拥有无限信用额度的赌徒从亏损开始，为了达到盈亏平衡，可能会进行无数次尝试。我们可以计算他达到盈亏平衡的概率，或者攻击者赶上诚实链条的概率，如下[8]所示:

  • p = 一个诚实的节点找到下一个块的概率
  • q = 攻击者找到下一个块的概率
  • qz = 攻击者从后面z块追上来的概率

根据我们的假设，p > q，随着攻击者必须跟上的块的数量的增加，概率呈指数级下降。在他的不利条件下，如果他没有在一开始就幸运地向前冲，他的机会就会变得微乎其微。

现在，我们考虑新交易的接收者需要等待多长时间，才能充分确定发送方不能更改交易。我们假设发送者是一个攻击者，他想让接收者相信他付了他一段时间的钱，然后在一段时间后将钱还给他自己。当这种情况发生时，接收方会收到警报，但发送方希望为时已晚。

接收方生成一个新的密钥对，并在签名前不久将公钥提供给发送方。这可以防止发送者提前准备一个块链，方法是不断地处理它，直到他足够幸运地提前完成，然后在那一刻执行事务。一旦事务被发送，不诚实的发送者就开始秘密地在包含他的交易的另一个版本的并行链上工作。

接收方等待，直到事务被添加到一个块，z块在它之后被链接。他不知道攻击者所取得的确切进度，但是假设诚实块使用每个块的平均预期时间，攻击者的潜在进度将是具有期望值的泊松分布:

\(\lambda=z\frac{q}{p}\)



为了得到攻击者现在仍能赶上的概率，我们将每一个他可能取得的进展的泊松密度乘以他从那一点赶上的概率:

为了得到攻击者现在仍能赶上的概率，我们用他能赶上的概率乘以泊松密度...

转化成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指数下降。

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

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. 结论

我们建议建立一个不依赖信托的电子交易系统。我们从数字签名创建货币的常规框架开始，它提供了对所有权的强大控制，但如果没有防止双重支付的方法，它就不完整。为了解决这个问题，我们提出了一个点对点网络，它使用工作量证明记录交易的公开历史，如果诚实的节点控制了大部分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.