"比特币 - 点对点电子现金系统"

Satoshi Nakamoto
[email protected]
www.bitcoin.org

摘要 (Abstract)

一种纯粹的点对点电子现金版本将允许在线支付直接从一方发送到另一方，无需通过金融机构。数字签名提供了部分解决方案，但如果仍然需要一个可信的第三方来防止双重支付，主要优势将会丧失。我们提出了一种利用点对点网络解决双重支付问题的方案。该网络通过将交易的哈希值记录在一个持续的基于哈希的工作量证明链中来为交易添加时间戳，形成一个无法在不重新进行工作量证明的情况下被修改的记录。最长的链不仅作为所见事件序列的证明，还证明它来自最大的 CPU 算力集。只要大多数 CPU 算力由不合作攻击网络的节点控制，它们将生成最长的链并超越攻击者。网络本身需要最小的结构。消息以尽力而为的方式广播，节点可以随意离开和重新加入网络，接受最长的工作量证明链作为它们离开期间发生事情的证明。

引言 (Introduction)

互联网商务几乎完全依赖金融机构作为可信的第三方来处理电子支付。尽管该系统对于大多数交易来说运作得相当顺利，但它仍然存在基于信任模型的固有弱点。完全不可逆的交易实际上是不可能的，因为金融机构无法避免调解争议。调解的成本增加了交易成本，限制了实际可行的最小交易规模，并切断了小额随意交易的可能性，同时在无法进行不可逆支付以获取不可逆服务方面也带来了更广泛的成本。由于存在逆转的可能性，信任的需求扩散开来。商家必须警惕他们的客户，要求提供比实际需要更多的信息。一定比例的欺诈被视为不可避免。这些成本和支付的不确定性可以通过使用实体货币在面对面交易中避免，但在没有可信第三方的情况下，通过通信渠道进行支付的机制尚不存在。

所需要的是一个基于加密证明而非信任的电子支付系统，允许任何两个愿意的方直接相互交易，而无需可信的第三方。计算上不可能逆转的交易将保护卖家免受欺诈，而常规的托管机制也可以轻松实施以保护买家。在本文中，我们提出了一种利用点对点分布式时间戳服务器解决双重支付问题的方案，以生成交易时间顺序的计算证明。只要诚实节点集体控制的 CPU 算力超过任何合作攻击者节点组，该系统就是安全的。

交易 (Transactions)

我们将电子货币定义为一系列数字签名。每个所有者通过数字签名前一笔交易的哈希值和下一个所有者的公钥，并将这些添加到货币末尾，从而将货币转移给下一个所有者。收款人可以验证这些签名以验证所有权链。

Transaction: 交易
Owner [N]’s Public Key: 所有者 [N] 的公钥
Hash: 哈希
Owner [N]’s Signature: 所有者 [N] 的电子签名
Owner [N]’s Private Key: 所有者 [N] 的私钥

当然，问题在于收款人无法验证某个所有者是否没有双重支付该货币。一个常见的解决方案是引入一个可信的中央权威机构，或造币厂，来检查每笔交易是否存在双重支付。在每笔交易之后，货币必须返回造币厂以发行新货币，只有直接由造币厂发行的货币才被信任不会被双重支付。这一解决方案的问题在于整个货币系统的命运依赖于运行造币厂的公司，所有交易都必须通过他们，就像银行一样。

我们需要一种方式让收款人知道之前的所有者没有签署任何早期交易。就我们的目的而言，最早的交易才是有效的，因此我们不关心后来的双重支付尝试。确认某笔交易不存在的唯一方法是了解所有交易。在基于造币厂的模型中，造币厂了解所有交易并决定哪些先到达。为了在没有可信第三方的情况下实现这一点，交易必须公开宣布^[1]，并且我们需要一个系统让参与者就收到交易的顺序达成单一的历史记录。收款人需要证明在每笔交易发生时，大多数节点都同意这是第一笔收到的交易。

时间戳服务器 (Timestamp Server)

我们提出的解决方案始于一个时间戳服务器。时间戳服务器的工作方式是对一组需要时间戳的项目进行哈希，并广泛发布该哈希，例如在报纸或 Usenet 帖子中^[2-5]。时间戳证明数据在当时必须存在，显然，才能进入哈希。每个时间戳在其哈希中包含前一个时间戳，形成一个链，每一个额外的时间戳都在强化之前的时间戳。

Hash: 哈希
Block: 区块
Item: 项目

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

为了在点对点基础上实现一个分布式时间戳服务器，我们需要使用类似于 Adam Back 的 Hashcash ^[6]的工作量证明系统，而不是依赖报纸或 Usenet 帖子。工作量证明涉及扫描一个值，当使用 SHA-256 等哈希函数进行哈希时，哈希值以若干个零位开头。所需的平均工作量随着所需零位数的增加而呈指数增长，并且可以通过执行一个哈希操作来验证。对于我们的时间戳网络，我们通过在区块中递增一个 nonce，直到找到一个使区块哈希满足所需零位的值来实现工作量证明。一旦 CPU 的努力被用来满足工作量证明，区块就无法在不重新进行工作的情况下被更改。随着后续区块的链接，改变该区块的工作将包括重新处理所有后续区块。

Block: 区块
Prev Hash: 前一区块哈希
Nonce: 随机数
Tx (Transaction): 交易

工作量证明还解决了在多数决策中确定代表性的问题。如果多数基于一 IP 地址一票的原则，任何能够分配多个 IP 的人都可能破坏它。工作量证明本质上是一个 CPU 一票。多数决策由最长链代表，最长链投入了最多的工作量证明。如果大多数 CPU 能力由诚实节点控制，诚实链将增长得最快，并超越任何竞争链。要修改过去的一个区块，攻击者必须重新进行该区块及其后所有区块的工作量证明，然后赶上并超过诚实节点的工作量。我们稍后将展示，随着后续区块的增加，攻击者赶上的概率会呈指数级下降。

为了补偿硬件速度的提高和随着时间推移运行节点的兴趣变化，工作量证明的难度通过一个移动平均值来确定，目标是每小时生成的平均区块数量。如果生成速度过快，难度将增加。

网络 (Network)

运行网络的步骤如下：

1. 新的交易被广播到所有节点。
2. 每个节点将新的交易收集到一个区块中。
3. 每个节点致力于为其区块找到一个困难的工作量证明。
4. 当一个节点找到工作量证明时，它会将该区块广播给所有节点。
5. 节点仅在区块中的所有交易都是有效且未被花费的情况下接受该区块。
6. 节点通过致力于创建链中的下一个区块来表达对该区块的接受，使用已接受区块的哈希作为前一个哈希。

节点总是认为最长的链是正确的，并将继续致力于扩展它。如果两个节点同时广播下一个区块的不同版本，某些节点可能会先收到其中一个。在这种情况下，它们会处理收到的第一个区块，但会保存另一个分支以防其变得更长。平局将在找到下一个工作量证明并且一个分支变得更长时被打破；原本在另一个分支上工作的节点将切换到更长的分支。

新的交易广播不一定需要到达所有节点。只要它们到达足够多的节点，就会很快被包含在一个区块中。区块广播也能容忍消息丢失。如果一个节点没有收到某个区块，当它收到下一个区块并意识到缺少一个时，它会请求该区块。

激励机制 (Incentive)

按照惯例，一个区块中的第一笔交易是一笔特殊的交易，创建一个由区块创建者拥有的新币。这为节点支持网络提供了激励，并提供了一种将币最初分发到流通中的方式，因为没有中央权威机构来发行它们。持续增加固定数量的新币类似于金矿工消耗资源将黄金添加到流通中。在我们的情况下，消耗的是 CPU 时间和电力。

激励机制也可以通过交易费来资助。如果一笔交易的输出价值小于其输入价值，差额就是交易费，加入包含该交易的区块的激励值中。一旦预定数量的币进入流通，激励机制可以完全转向交易费，并完全避免通货膨胀。

激励机制可能有助于鼓励节点保持诚实。如果一个贪婪的攻击者能够集结比所有诚实节点更多的 CPU 能力，他将不得不在使用这些能力来通过盗回支付进行欺诈，或用于生成新币之间做出选择。他应该发现，按照规则行事更有利可图，这些规则使他获得比所有其他人加起来更多的新币，而不是破坏系统和自己财富的有效性。

回收磁盘空间 (Reclaiming Disk Space)

一旦一枚硬币中的最新交易被足够多的区块掩埋，之前的已花费交易就可以被丢弃以节省磁盘空间。为了在不破坏区块哈希的情况下实现这一点，交易被哈希到一个默克尔树中^[7][2][5]，并且只有根节点包含在区块的哈希中。然后，旧区块可以通过截断树的分支来压缩。内部的哈希不需要被存储。

Block: 区块
Block Header (Block Hash): 区块头（区块哈希）
Prev Hash: 前一区块哈希
Nonce: 随机数
Root Hash: 根哈希
Hash[N]: 哈希[N]
Tx[N] (Transaction[N]): 交易[N]
Transactions Hashed in a Merkle Tree: 在默克尔树中哈希的交易
After Pruning Tx0-2 from the Block: 从区块中修剪交易0-2之后

一个没有交易的区块头大约为 80 字节。如果我们假设每 10 分钟生成一个区块，80 字节 _ 6 _ 24 * 365 = 4.2MB 每年。考虑到截至 2008 年，计算机系统通常配备 2GB 的内存，并且摩尔定律预测当前每年增长 1.2GB，即使区块头必须保留在内存中，存储也不应成为问题。

简化支付验证 (Simplified Payment Verification)

无需运行完整的网络节点即可验证支付。用户只需要保存最长工作量证明链的区块头副本，这可以通过查询网络节点直到他确信自己拥有最长的链，并获取将交易链接到其时间戳所在区块的默克尔分支。他无法自行检查交易，但通过将其链接到链中的某个位置，他可以看到网络节点已接受该交易，随后添加的区块进一步确认网络已接受该交易。

Longest Proof-of-Work Chain: 最长工作量证明链
Block Header (Block Hash): 区块头（区块哈希）
Prev Hash: 前一区块哈希
Nonce: 随机数
Merkle Root: 默克尔根
Hash[N]: 哈希[N]
Tx[N] (Transaction[N]): 交易[N]
Merkle Branch for Tx3: 交易3的默克尔分支

因此，只要诚实节点控制网络，验证是可靠的，但如果网络被攻击者压倒，则更容易受到攻击。虽然网络节点可以自行验证交易，但简化的方法可能会被攻击者伪造的交易欺骗，只要攻击者能够继续压制网络。保护这一点的一种策略是，当网络节点检测到无效区块时接受其警报，促使用户的软件下载完整区块和警报交易以确认不一致性。频繁接收付款的企业可能仍然希望运行自己的节点，以获得更独立的安全性和更快速的验证。

合并与拆分价值 (Combining and Splitting Value)

虽然可以单独处理每个硬币，但为转账中的每一分钱进行单独交易将会非常繁琐。为了允许价值的拆分与合并，交易包含多个输入和输出。通常会有来自较大前一个交易的单一输入或组合较小金额的多个输入，最多有两个输出：一个用于支付，另一个用于将找零（如果有）返回给发送者。

Transaction: 交易
In: 入金
Out: 出金

需要注意的是，扇出（fan-out），即一笔交易依赖于多笔交易，而这些交易又依赖于更多交易，在这里并不是问题。永远不需要提取一份交易历史的完整独立副本。

隐私 (Privacy)

传统的银行模式通过限制信息访问仅限于相关方和可信的第三方，达到了某种程度的隐私。必须公开宣布所有交易使得这种方法无法实施，但仍然可以通过在另一个地方打断信息流来保持隐私：保持公钥的匿名性。公众可以看到有人向其他人发送了某个金额，但没有将交易与任何人联系起来的信息。这类似于证券交易所发布的信息水平，其中个别交易的时间和规模，即“成交记录”，被公开，但不透露交易各方的身份。

Traditional Privacy Model: 传统隐私模型
New Privacy Model: 新的隐私模型
Identities: 身份
Transactions: 交易
Trusted Third Party: 可信第三方
Counterparty: 交易对手
Public: 公众

作为额外的防火墙，每笔交易都应使用新的密钥对，以防止它们被链接到同一所有者。然而，对于多输入交易来说，某种程度的链接仍然是不可避免的，因为这些交易必然会揭示其输入是由同一所有者拥有的。风险在于，如果一个密钥的所有者被揭示，链接可能会暴露属于同一所有者的其他交易。

计算 (Calculation)

我们考虑攻击者试图生成一条比诚实链更快的备用链的情景。即使实现了这一点，也不会使系统开放于任意更改，例如凭空创造价值或获取从未属于攻击者的钱。节点不会接受无效的交易作为支付，诚实的节点也永远不会接受包含这些交易的区块。攻击者只能尝试更改他自己的某笔交易以取回他最近花费的钱。

诚实链与攻击者链之间的竞争可以被描述为一个二项式随机游走。成功事件是诚实链延长一个区块，增加其领先优势+1，失败事件是攻击者的链延长一个区块，减少差距-1。

攻击者从给定的差距中赶上的概率类似于赌博者破产问题。假设一个拥有无限信用的赌徒从一个亏损开始，并进行可能无限次的试验以试图达到收支平衡。我们可以如下计算他是否有可能达到收支平衡，或攻击者是否有可能赶上诚实链的概率[8]：

p = 诚实节点找到下一个区块的概率 q = 攻击者找到下一个区块的概率 q_z = 攻击者从落后 z 个区块的情况下赶上的概率

鉴于我们假设 p>q，随着攻击者需要赶上的区块数量增加，概率呈指数下降。由于赔率对他不利，如果他在早期没有幸运地迅速前进，随着他进一步落后，他的机会将变得微乎其微。

现在我们考虑新交易的接收者需要等待多长时间，才能充分确定发送者无法更改交易。我们假设发送者是一个攻击者，他希望让接收者相信他已经支付了一段时间，然后在一段时间后将支付切换回自己。接收者在这种情况发生时会收到警报，但发送者希望那时已经太迟了。

接收者在签名前不久生成一个新的密钥对并将公钥提供给发送者。这防止发送者通过持续工作提前准备好一条区块链，直到他足够幸运地超前，然后在那一刻执行交易。一旦交易被发送，不诚实的发送者就会秘密地在一条包含其交易替代版本的平行链上工作。

接收者等待直到交易被添加到一个区块中，并且在其后链接了 z 个区块。他不知道攻击者已经取得了多少进展，但假设诚实区块每个区块所需的时间是平均预期的，攻击者的潜在进展将遵循一个泊松分布，期望值为：

为了得到攻击者现在仍然可能赶上的概率，我们将他可能取得的每一进度量的泊松密度与他从那一点赶上的概率相乘：

重新排列以避免对分布的无限尾部进行求和...

转换为 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

结论 (Conclusion)

我们提出了一个无需依赖信任的电子交易系统。我们从通常的由数字签名构成的货币框架开始，这提供了强有力的所有权控制，但如果没有防止双重支付的方法，这一系统是不完整的。为了解决这个问题，我们提出了一个使用工作量证明的点对点网络来记录公开的交易历史，如果诚实节点控制了大多数 CPU 算力，这一历史记录对攻击者来说很快就会在计算上变得不可更改。网络在其无结构的简单性中具有鲁棒性。节点同时工作，协调很少。它们不需要被识别，因为消息不会被路由到任何特定地点，只需要尽力传递即可。节点可以随意离开和重新加入网络，接受工作量证明链作为它们离开期间发生事情的证明。它们通过其 CPU 算力投票，通过工作来扩展有效区块来表达对其的接受，并通过拒绝在无效区块上工作来拒绝它们。任何需要的规则和激励都可以通过这种共识机制来执行。

参考文献 (Reference)

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