2008-10-31 Bitcoin: A Peer-to-Peer Electronic Cash System

2008-10-31 Bitcoin: A Peer-to-Peer Electronic Cash System


Abstract. A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone.
摘要：一种纯粹点对点（peer-to-peer）的电子现金版本，将允许在线支付在双方之间直接发送，而无需通过金融机构。数字签名提供了部分解决方案，但如果仍需要一个受信任的第三方来防止“双重支付（double-spending）”，那么其主要优势就会丧失。我们提出一种利用点对点网络来解决双重支付问题的方案。该网络通过将交易哈希进一条持续增长的、基于哈希的工作量证明（proof-of-work）链来为交易加上时间戳，从而形成一份记录；除非重新完成相应的工作量证明，否则该记录无法被篡改。最长链不仅证明了所见事件的发生顺序，也证明它来自最大的 CPU 算力池。只要多数 CPU 算力由不与攻击网络的节点控制，它们就会生成最长链并在速度上超过攻击者。网络本身只需要最小的结构。消息以“尽力而为（best effort）”方式广播，节点可以随时离开并重新加入网络；它们把最长的工作量证明链当作自己离线期间发生情况的证明。
Idea
Bitcoin的关键假设。

1. Introduction

引言

Commerce on the Internet has come to rely almost exclusively on financial institutions serving as trusted third parties to process electronic payments. While the system works well enough for most transactions, it still suffers from the inherent weaknesses of the trust based model. Completely non-reversible transactions are not really possible, since financial institutions cannot avoid mediating disputes. The cost of mediation increases transaction costs, limiting the minimum practical transaction size and cutting off the possibility for small casual transactions, and there is a broader cost in the loss of ability to make non-reversible payments for non-reversible services. With the possibility of reversal, the need for trust spreads. Merchants must be wary of their customers, hassling them for more information than they would otherwise need. A certain percentage of fraud is accepted as unavoidable. These costs and payment uncertainties can be avoided in person by using physical currency, but no mechanism exists to make payments over a communications channel without a trusted party.
互联网商业几乎完全依赖金融机构充当受信任的第三方来处理电子支付。虽然这一系统对大多数交易而言“够用”，但它仍然受制于信任模型的内在弱点。完全不可逆的交易并不真正可行，因为金融机构无法避免介入纠纷调解。调解成本抬高了交易成本，限制了可行的最小交易规模，切断了“小额、随意交易”的可能性；同时，还带来更广泛的成本：对于不可逆的服务，失去了进行不可逆支付的能力。由于存在撤销（reversal）的可能，信任需求会扩散。商家必须提防客户，为了降低风险而索取本不需要的更多信息。一定比例的欺诈被视为不可避免。面对面交易时，使用实物货币可以避免这些成本与支付不确定性；但在通信渠道上，没有受信任第三方就无法完成支付的机制仍然不存在。

What is needed is an electronic payment system based on cryptographic proof instead of trust, allowing any two willing parties to transact directly with each other without the need for a trusted third party. Transactions that are computationally impractical to reverse would protect sellers from fraud, and routine escrow mechanisms could easily be implemented to protect buyers. In this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions. The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.
我们需要一种基于“密码学证明（cryptographic proof）”而非“信任”的电子支付系统，使任何两方只要愿意，就能在无需受信任第三方的情况下彼此直接交易。那些在计算上几乎不可能被逆转的交易能够保护卖家免受欺诈，而常规的托管（escrow）机制也可以很容易实现，用以保护买家。在本文中，我们提出一种方案：使用点对点的分布式时间戳服务器来生成关于交易时间顺序的计算证明，从而解决双重支付问题。只要诚实节点合计控制的 CPU 算力超过任何一个相互协作的攻击者节点群体，系统就是安全的。

2. Transactions

交易

We define an electronic coin as a chain of digital signatures. Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin. A payee can verify the signatures to verify the chain of ownership.
我们将一枚电子货币（electronic coin）定义为一条数字签名链。每一位所有者通过对“前一笔交易的哈希”与“下一位所有者的公钥”进行数字签名，并把这些内容附加到该货币链的末端，从而将货币转移给下一位所有者。收款方可以通过验证签名来验证所有权链条。
The problem of course is the payee can't verify that one of the owners did not double-spend the coin. A common solution is to introduce a trusted central authority, or mint, that checks every transaction for double spending. After each transaction, the coin must be returned to the mint to issue a new coin, and only coins issued directly from the mint are trusted not to be double-spent. The problem with this solution is that the fate of the entire money system depends on the company running the mint, with every transaction having to go through them, just like a bank.
问题当然在于：收款方（payee）无法验证某位所有者是否没有对同一枚币进行双重支付（double-spend）。一个常见的解决方案是引入一个受信任的中央权威（central authority），或称铸币机构（mint），由它检查每笔交易是否发生双重支付。每次交易之后，这枚币必须交回铸币机构以发行一枚新币；并且只有直接由铸币机构发行的币，才被信任不会被双重支付。这个方案的问题在于：整个货币系统的命运取决于运营铸币机构的那家公司，而且每笔交易都必须经过它——就像银行一样。

We need a way for the payee to know that the previous owners did not sign any earlier transactions. For our purposes, the earliest transaction is the one that counts, so we don't care about later attempts to double-spend. The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first. To accomplish this without a trusted party, transactions must be publicly announced1, and we need a system for participants to agree on a single history of the order in which they were received. The payee needs proof that at the time of each transaction, the majority of nodes agreed it was the first received.
我们需要一种方式，让收款方确信：之前的所有者没有签署任何更早的交易。对我们的目的而言，最早的那笔交易才算数，因此我们不关心之后的双重支付尝试。确认“某笔交易不存在”的唯一办法，是对所有交易都“知情”。在铸币机构模型中，铸币机构知道全部交易，并决定哪一笔最先到达。要在没有受信任第三方的情况下做到这一点，交易必须被公开发布（publicly announced）¹，并且我们需要一个系统，使参与者能够就“收到交易的先后顺序”达成一个单一历史（single history）。收款方需要证据证明：在每次交易发生时，多数节点都同意该交易是“最先收到”的那笔。

3. Timestamp Server

时间戳服务器

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post2 3 4 5. The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
我们提出的解决方案从一个时间戳服务器（timestamp server）开始。时间戳服务器的工作方式是：对一组需要加时间戳的条目做哈希（hash），然后把这个哈希广泛发布出去，例如刊登在报纸上或发布到 Usenet 帖子中²³⁴⁵。时间戳证明了这些数据在当时必然已经存在——否则不可能被纳入该哈希。每一个时间戳在其哈希中包含前一个时间戳，从而形成一条链；而每新增一个时间戳，都会对之前的时间戳起到“加固”的作用。

4. Proof-of-Work

工作量证明

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash6, rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash.
为了以点对点（peer-to-peer）的方式实现一个分布式时间戳服务器，我们需要使用一种类似于 Adam Back 的 Hashcash⁶ 的工作量证明（proof-of-work）系统，而不是依赖报纸或 Usenet 帖子。工作量证明的过程是：扫描（scanning）寻找某个数值，使得对其进行哈希（例如用 SHA-256）后，得到的哈希值以若干个零比特（zero bits）开头。所需的平均工作量随“要求的零比特数量”呈指数增长，但验证却只需要执行一次哈希即可。

For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.
对于我们的时间戳网络，我们通过在区块（block）中递增一个随机数（nonce），直到找到某个值使得该区块的哈希满足所要求的零比特条件，从而实现工作量证明。一旦耗费 CPU 努力使其满足工作量证明，该区块就无法在不重做这份工作量的情况下被更改。随着后续区块以链式方式连接在其后，想要篡改该区块所需的工作量就不仅包括重做它本身，还包括重做其后的所有区块。
The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added.
工作量证明（proof-of-work）也解决了“多数决策中代表权（representation）如何确定”的问题。如果多数是按“一 IP 地址一票（one-IP-address-one-vote）”来计算，那么任何能分配大量 IP 的人都可以颠覆它。工作量证明本质上是“一 CPU 一票（one-CPU-one-vote）”。多数决策由最长链（longest chain）来代表，因为最长链投入了最多的工作量证明努力（greatest proof-of-work effort）。如果多数 CPU 算力由诚实节点控制，诚实链将增长得最快，并超过任何竞争链。要修改过去的一个区块（past block），攻击者必须重做该区块以及其后所有区块的工作量证明，然后再追赶并超过诚实节点所完成的工作量。我们稍后将展示：随着后续区块不断增加，一个较慢攻击者追赶成功的概率会以指数方式下降（diminishes exponentially）。

To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they're generated too fast, the difficulty increases.
为了补偿硬件速度提升以及节点运行兴趣随时间变化所带来的影响，工作量证明难度（difficulty）通过一个移动平均（moving average）来决定，其目标是把“每小时平均产生的区块数量”稳定在一个水平上。如果区块生成得太快，难度就会提高。

5. Network

网络

The steps to run the network are as follows:
运行网络的步骤如下：

1)New transactions are broadcast to all nodes.
新的交易会广播（broadcast）给所有节点。

2)Each node collects new transactions into a block.
每个节点把新的交易收集进一个区块（block）。

3)Each node works on finding a difficult proof-of-work for its block.
每个节点开始为自己的区块寻找一个“困难的”工作量证明（difficult proof-of-work）。

4)When a node finds a proof-of-work, it broadcasts the block to all nodes.
当某个节点找到工作量证明后，它把该区块广播给所有节点。

5)Nodes accept the block only if all transactions in it are valid and not already spent.
节点只有在确认区块内所有交易都有效（valid）且尚未被花费（not already spent）时，才接受该区块。

6)Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.
节点通过继续创建链上的下一个区块来表达自己对该区块的接受：把被接受区块的哈希作为“前一区块哈希（previous hash）”来使用。

Nodes always consider the longest chain to be the correct one and will keep working on extending it. If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proof-of-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.
节点始终把最长链视为正确链（correct one），并持续工作以扩展它。如果两个节点同时广播了下一个区块的不同版本，一些节点可能先收到其中一个。在这种情况下，它们先在自己最先收到的那个分支上继续工作，但会保存另一个分支，以防它后来变得更长。下一次工作量证明被找到、某个分支变得更长时，平局就被打破；此前在另一分支上工作的节点将切换到较长的那条链。

New transaction broadcasts do not necessarily need to reach all nodes. As long as they reach many nodes, they will get into a block before long. Block broadcasts are also tolerant of dropped messages. If a node does not receive a block, it will request it when it receives the next block and realizes it missed one.
新的交易广播不一定必须到达所有节点。只要它们到达足够多的节点，就会在不久后被打包进某个区块。区块广播同样能容忍消息丢失（dropped messages）。如果某个节点没有收到某个区块，它会在收到下一个区块、意识到自己漏掉一个时，发起请求来补齐。

6. Incentive

激励机制

By convention, the first transaction in a block is a special transaction that starts a new coin owned by the creator of the block. This adds an incentive for nodes to support the network, and provides a way to initially distribute coins into circulation, since there is no central authority to issue them. The steady addition of a constant of amount of new coins is analogous to gold miners expending resources to add gold to circulation. In our case, it is CPU time and electricity that is expended.
按惯例，一个区块中的第一笔交易是一种特殊交易：它会创建一枚由该区块创建者（creator of the block）拥有的新币。这为节点支持网络提供了激励（incentive），并且在没有中央权威发行货币的情况下，提供了一种把货币最初分发到流通中的方式。持续、稳定地增加一恒定数量的新币，类似于黄金矿工耗费资源把黄金加入流通。只不过在我们的场景里，被耗费的是 CPU 时间与电力。

The incentive can also be funded with transaction fees. If the output value of a transaction is less than its input value, the difference is a transaction fee that is added to the incentive value of the block containing the transaction. Once a predetermined number of coins have entered circulation, the incentive can transition entirely to transaction fees and be completely inflation free.
激励也可以由交易费（transaction fees）来资助。如果一笔交易的输出价值（output value）小于其输入价值（input value），两者之差就是交易费；该费用会被加到“包含这笔交易的区块”的激励价值中。一旦预定数量的货币进入流通，激励就可以完全过渡为交易费，从而实现彻底的“零通胀（inflation free）”。

The incentive may help encourage nodes to stay honest. If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.
激励机制也可能有助于促使节点保持诚实。如果一个贪婪的攻击者（greedy attacker）能够聚集比所有诚实节点更高的 CPU 算力，那么他必须在两种用途之间做选择：要么用这些算力通过“把自己支付出去的钱偷回来”来欺诈他人（stealing back his payments），要么用这些算力来生成新币。他理应发现：遵守规则更有利可图——因为规则会让他获得比其他所有人合计更多的新币——相比之下，破坏系统会削弱体系本身以及他自己财富的有效性（validity of his own wealth）。

7. Reclaiming Disk Space

回收磁盘空间

Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block's hash, transactions are hashed in a Merkle Tree257, with only the root included in the block's hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored.
一旦一枚币的最新交易（latest transaction）被足够多的区块“埋深”（buried），它之前那些已经花费掉的交易（spent transactions）就可以被丢弃，以节省磁盘空间。为了在不破坏区块哈希（block's hash）的情况下做到这一点，交易会被哈希进一棵 Merkle Tree²⁵⁷，并且只有根（root）被包含在区块哈希中。这样，旧区块就可以通过“截断树枝（stubbing off branches）”来压缩（compacted）。内部哈希（interior hashes）无需被存储。

A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory.
一个不含交易的区块头（block header）大约是 80 字节。假设区块每 10 分钟生成一次，那么 80 字节 × 6 × 24 × 365 = 4.2MB/年。鉴于截至 2008 年，计算机系统通常配备 2GB 的 RAM，且 Moore's Law 预测当前每年约增长 1.2GB，即使区块头必须常驻内存，存储也不应成为问题。

8. Simplified Payment Verification

简化支付验证

It is possible to verify payments without running a full network node. A user only needs to keep a copy of the block headers of the longest proof-of-work chain, which he can get by querying network nodes until he's convinced he has the longest chain, and obtain the Merkle branch linking the transaction to the block it's timestamped in. He can't check the transaction for himself, but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confirm the network has accepted it.
无需运行完整网络节点也可以验证支付。用户只需要保存“最长工作量证明链（longest proof-of-work chain）”的区块头副本；他可以通过向多个网络节点查询，直到确信自己拿到的是最长链。随后，再获取把该笔交易与其被时间戳记录的区块相连接的 Merkle 分支（Merkle branch）。他无法自行验证交易本身是否有效，但通过把交易定位到链上的某个位置，他就能确认某个网络节点已经接受了它，而在其后不断追加的区块会进一步确认网络对该交易的接受。
As such, the verification is reliable as long as honest nodes control the network, but is more vulnerable if the network is overpowered by an attacker. While network nodes can verify transactions for themselves, the simplified method can be fooled by an attacker's fabricated transactions for as long as the attacker can continue to overpower the network. One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency. Businesses that receive frequent payments will probably still want to run their own nodes for more independent security and quicker verification.
因此，只要诚实节点控制着网络，这种验证就是可靠的；但如果网络算力被攻击者压制，它就更脆弱。网络节点可以自行验证交易，而这种简化方法在攻击者能够持续压制网络的期间，可能被攻击者伪造的交易所欺骗。一种防护策略是：当网络节点检测到无效区块（invalid block）时，向用户发出警报，促使用户的软件下载完整区块与被警报标记的交易，以核实不一致之处。那些频繁收款的企业，出于更独立的安全性与更快的验证需求，可能仍然希望运行自己的节点。

9. Combining and Splitting Value

价值的合并与拆分

Although it would be possible to handle coins individually, it would be unwieldy to make a separate transaction for every cent in a transfer. To allow value to be split and combined, transactions contain multiple inputs and outputs. Normally there will be either a single input from a larger previous transaction or multiple inputs combining smaller amounts, and at most two outputs: one for the payment, and one returning the change, if any, back to the sender.
虽然可以逐枚处理货币（coins），但如果一次转账中的每一分钱都要单独做一笔交易，那将非常笨重。为了允许价值被拆分与合并，交易（transactions）包含多个输入（inputs）与输出（outputs）。通常要么是来自一笔更大先前交易的单一输入，要么是把多个较小金额合并起来的多个输入；输出最多两项：一项用于支付，另一项（若存在找零）把找零返还给付款方（sender）。

It should be noted that fan-out, where a transaction depends on several transactions, and those transactions depend on many more, is not a problem here. There is never the need to extract a complete standalone copy of a transaction's history.
需要指出的是，这里的“扇出（fan-out）”并不是问题：即一笔交易依赖于多笔交易，而这些交易又依赖于更多交易。系统从不需要抽取一份“完整、可独立存在”的交易历史副本（complete standalone copy of a transaction's history）。

10. Privacy

隐私

The traditional banking model achieves a level of privacy by limiting access to information to the parties involved and the trusted third party. The necessity to announce all transactions publicly precludes this method, but privacy can still be maintained by breaking the flow of information in another place: by keeping public keys anonymous. The public can see that someone is sending an amount to someone else, but without information linking the transaction to anyone. This is similar to the level of information released by stock exchanges, where the time and size of individual trades, the "tape", is made public, but without telling who the parties were.
传统银行模型通过限制信息访问范围（只让交易双方与受信任第三方可见）来实现一定程度的隐私。必须公开宣布所有交易这一要求，使得这种方法无法使用；但隐私仍可通过在另一个位置“打断信息流”来维持：保持公钥（public keys）的匿名性。公众能看到“有人给另一个人转了一笔金额”，但缺乏把交易与具体身份关联起来的信息。这类似于证券交易所发布的信息水平：单笔交易的时间与规模（the "tape"）是公开的，但不会披露交易双方是谁。
As an additional firewall, a new key pair should be used for each transaction to keep them from being linked to a common owner. Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner. The risk is that if the owner of a key is revealed, linking could reveal other transactions that belonged to the same owner.
作为额外的防火墙，每笔交易都应使用一个新的密钥对（key pair），以避免被关联到同一所有者。对于多输入交易（multi-input transactions），仍不可避免会出现一定程度的关联，因为它必然揭示这些输入属于同一所有者。风险在于：一旦某个密钥的所有者身份被揭示，关联关系可能进一步暴露该所有者的其他交易。

11. Calculations

计算

We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain. Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes are not going to accept an invalid transaction as payment, and honest nodes will never accept a block containing them. An attacker can only try to change one of his own transactions to take back money he recently spent.
我们考虑这样一种情形：攻击者试图比诚实链更快地产生一条替代链（alternate chain）。即便攻击者做到了这一点，也并不会让系统对任意篡改敞开大门，例如凭空创造价值（creating value out of thin air）或拿走从未属于攻击者的钱。节点不会接受无效交易（invalid transaction）作为支付，而诚实节点永远不会接受包含无效交易的区块。攻击者唯一能尝试做的，是修改他自己最近的一笔交易，把他刚花出去的钱拿回来。

The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The success event is the honest chain being extended by one block, increasing its lead by +1, and the failure event is the attacker's chain being extended by one block, reducing the gap by -1.
诚实链与攻击者链之间的竞赛可以刻画为一个二项随机游走（Binomial Random Walk）。所谓“成功事件”是诚实链被扩展一个区块，使其领先优势增加 +1；所谓“失败事件”是攻击者链被扩展一个区块，使差距减少 -1。

The probability of an attacker catching up from a given deficit is analogous to a Gambler's Ruin problem. Suppose a gambler with unlimited credit starts at a deficit and plays potentially an infinite number of trials to try to reach breakeven. We can calculate the probability he ever reaches breakeven, or that an attacker ever catches up with the honest chain, as follows8:
攻击者从某个既定落后程度追赶成功的概率，类似于“赌徒破产（Gambler's Ruin）”问题。设想一个拥有无限信用额度的赌徒从落后状态开始，进行可能无限次的试验以试图回到盈亏平衡点。我们可以计算他最终回到盈亏平衡点的概率——也就是攻击者最终追上诚实链的概率——如下⁸：

p = probability an honest node finds the next block
p = 诚实节点找到下一个区块的概率

q = probability the attacker finds the next block
q = 攻击者找到下一个区块的概率

q z = probability the attacker will ever catch up from z blocks behind
q^z = 攻击者从落后 z 个区块起最终追上的概率

Given our assumption that 'p > q', the probability drops exponentially as the number of blocks the attacker has to catch up with increases. With the odds against him, if he doesn't make a lucky lunge forward early on, his chances become vanishingly small as he falls further behind.
在我们假设 p > q 的前提下，随着攻击者需要追赶的区块数增加，这个概率会以指数方式下降（drops exponentially）。在胜算不利的情况下，如果他不能在早期凭运气实现一次“幸运突进（lucky lunge）”，那么随着落后加深，他的成功机会会变得极其渺小（vanishingly small）。

We now consider how long the recipient of a new transaction needs to wait before being sufficiently certain the sender can't change the transaction. We assume the sender is an attacker who wants to make the recipient believe he paid him for a while, then switch it to pay back to himself after some time has passed. The receiver will be alerted when that happens, but the sender hopes it will be too late.
接下来我们考虑：一笔新交易的收款方需要等待多长时间，才能足够确信付款方无法更改该交易。我们假设付款方是攻击者：他想让收款方在一段时间内相信“钱已经付出去了”，随后在时间过去后把交易切换（switch）为“把钱付回给自己”。这种情况发生时收款方会收到警报，但攻击者希望那时已经“为时已晚”。

The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment. Once the transaction is sent, the dishonest sender starts working in secret on a parallel chain containing an alternate version of his transaction.
收款方在签名前不久生成一个新的密钥对（key pair），并把公钥（public key）给付款方。这阻止付款方提前准备一条领先链：例如，他事先持续挖矿，直到运气好到足够领先，然后在那一刻执行交易。交易一旦发送，不诚实的付款方就会秘密启动一条并行链（parallel chain），其中包含其交易的一个替代版本（alternate version）。

The recipient waits until the transaction has been added to a block and 'z' blocks have been linked after it. He doesn't know the exact amount of progress the attacker has made, but assuming the honest blocks took the average expected time per block, the attacker's potential progress will be a Poisson distribution with expected value:
收款方会等待：交易被加入一个区块，并且其后又链接了 z 个区块。收款方不知道攻击者具体取得了多少进展，但在假设诚实链区块生成时间等于“每区块的平均期望时间”的前提下，攻击者的潜在进展可视为服从参数为期望值的泊松分布（Poisson distribution），其期望值为：
To get the probability the attacker could still catch up now, we multiply the Poisson density for each amount of progress he could have made by the probability he could catch up from that point:
为了得到“攻击者此刻仍能追上”的概率，我们把攻击者可能取得的每一种进展幅度对应的泊松密度（Poisson density），乘以他从该进展状态出发仍能追上的概率，然后把这些乘积加总：
Rearranging to avoid summing the infinite tail of the distribution...
通过重新整理（rearranging），以避免对分布的无穷尾部（infinite tail）进行求和……
Converting to C code...
将其转换为 C 代码……
  1. #include <math.h>
  2. double AttackerSuccessProbability(double q, int z)
  3. {
  4. double p = 1.0 - q;
  5. double lambda = z * (q / p);
  6. double sum = 1.0;
  7. int i, k;
  8. for (k = 0; k <= z; k++)
  9. {
  10. double poisson = exp(-lambda);
  11. for (i = 1; i <= k; i++)
  12. poisson *= lambda / i;
  13. sum -= poisson * (1 - pow(q / p, z - k));
  14. }
  15. return sum;
  16. }
Running some results, we can see the probability drop off exponentially with 'z'.
跑出一些结果后，我们可以看到：随着 z 增大，概率呈指数级下降（drop off exponentially）。
  1.    q=0.1
  2.    z=0    P=1.0000000
  3.    z=1    P=0.2045873
  4.    z=2    P=0.0509779
  5.    z=3    P=0.0131722
  6.    z=4    P=0.0034552
  7.    z=5    P=0.0009137
  8.    z=6    P=0.0002428
  9.    z=7    P=0.0000647
  10.    z=8    P=0.0000173
  11.    z=9    P=0.0000046
  12.    z=10   P=0.0000012
  13.    
  14.    q=0.3
  15.    z=0    P=1.0000000
  16.    z=5    P=0.1773523
  17.    z=10   P=0.0416605
  18.    z=15   P=0.0101008
  19.    z=20   P=0.0024804
  20.    z=25   P=0.0006132
  21.    z=30   P=0.0001522
  22.    z=35   P=0.0000379
  23.    z=40   P=0.0000095
  24.    z=45   P=0.0000024
  25.    z=50   P=0.0000006
Solving for P less than 0.1%...
求解使 P 小于 0.1%（0.001）的 z 值……
  1.    P < 0.001
  2.    q=0.10   z=5
  3.    q=0.15   z=8
  4.    q=0.20   z=11
  5.    q=0.25   z=15
  6.    q=0.30   z=24
  7.    q=0.35   z=41
  8.    q=0.40   z=89
  9.    q=0.45   z=340

12. Conclusion

结论

We have proposed a system for electronic transactions without relying on trust. We started with the usual framework of coins made from digital signatures, which provides strong control of ownership, but is incomplete without a way to prevent double-spending. To solve this, we proposed a peer-to-peer network using proof-of-work to record a public history of transactions that quickly becomes computationally impractical for an attacker to change if honest nodes control a majority of CPU power. The network is robust in its unstructured simplicity. Nodes work all at once with little coordination. They do not need to be identified, since messages are not routed to any particular place and only need to be delivered on a best effort basis. Nodes can leave and rejoin the network at will, accepting the proof-of-work chain as proof of what happened while they were gone. They vote with their CPU power, expressing their acceptance of valid blocks by working on extending them and rejecting invalid blocks by refusing to work on them. Any needed rules and incentives can be enforced with this consensus mechanism.
我们提出了一种不依赖信任（trust）的电子交易系统。我们从常见框架出发：用数字签名（digital signatures）构造的“币”，它能对所有权提供强有力的控制，但如果没有防止双重支付（double-spending）的方法，这个框架仍是不完整的。为了解决这一点，我们提出了一个使用工作量证明（proof-of-work）的点对点网络，用以记录一份公开的交易历史；只要诚实节点控制了多数 CPU 算力，这份历史就会迅速变得在计算上难以被攻击者篡改。该网络的优势在于其“无结构的简洁性（unstructured simplicity）”所带来的稳健性。节点几乎无需协作就能同时工作。它们不需要被识别，因为消息不会被路由到任何特定地点，只需要以“尽力而为（best effort）”方式送达即可。节点可以随时离开并重新加入网络，并把工作量证明链（proof-of-work chain）当作自己离线期间发生情况的证明。它们用 CPU 算力投票：通过继续扩展有效区块（valid blocks）来表达接受；通过拒绝在无效区块（invalid blocks）上工作来表达拒绝。任何所需的规则与激励，都可以通过这一共识机制来执行。

References

[1]b-money Dai Wei (1998-11-01) http://www.weidai.com/bmoney.txt. 

[2]Design of a secure timestamping service with minimal trust requirements Henri Massias, Xavier Serret-Avila, Jean-Jacques Quisquater 20th Symposium on Information Theory in the Benelux (1999-05) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6228. 

[3]How to time-stamp a digital document Stuart Haber, W.Scott Stornetta Journal of Cryptology (1991) https://doi.org/cwwxd4 DOI: 10.1007/bf00196791. 

[4]Improving the Efficiency and Reliability of Digital Time-Stamping Dave Bayer, Stuart Haber, W. Scott Stornetta Sequences II (1993) https://doi.org/bn4rpx DOI: 10.1007/978-1-4613-9323-8_24. 

[5]Secure names for bit-strings Stuart Haber, W. Scott Stornetta Proceedings of the 4th ACM conference on Computer and communications security - CCS ’97(1997) https://doi.org/dtnrf6 DOI: 10.1145/266420.266430. 

[6]Hashcash - A Denial of Service Counter-Measure Adam Back (2002-08-01) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8. 

[7]Protocols for Public Key Cryptosystems Ralph C. Merkle 1980 IEEE Symposium on Security and Privacy (1980-04) https://doi.org/bmvbd6 DOI: 10.1109/sp.1980.10006. 

[8]An Introduction to Probability Theory and its Applications William Feller John Wiley & Sons (1957) https://archive.org/details/AnIntroductionToProbabilityTheoryAndItsApplicationsVolume1. 

    热门主题

    BRK
    PGR
    CB
    AXP
    COF
    AAPL
    GOOG
    MSFT
    AMZN
    NVDA
    TSLA
    TCEHY
    IBKR
    STZ
    OXY
    CNOOC
    UNH
    Warren Buffett
    Steve Jobs
    Ideas
    I.C.S
    MOOM Picks

      • Recent Articles

      • 2008-10-31 Bitcoin: A Peer-to-Peer Electronic Cash System

        Refer To：《Bitcoin: A Peer-to-Peer Electronic Cash System》。 Abstract. A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital ...

      • I.C.S.21.006.Account.Bitcoin

        加密货币已经是整个金融系统的重要组成部分。 1、加密算法 加密技术是Bitcoin能够成立的基础，分私钥/公钥，从私钥算公钥很容易，从公钥反推私钥在计算上不可行。Bitcoin利用密钥巨大的数据集代替账号，随机生成几十亿个账号也不可能有重复的可能性，全世界所有人可以共享同一个账本。 以自托管钱包为例，钱包在本地生成一个随机数私钥 k（256-bit），再由私钥推导出 公钥 K = k·G（椭圆曲线运算），再由公钥派生出 地址（address，不同链规则不同：BTC 是 ...

      • 1996-03-01 Warren Buffett.Helzberg

        Refer To：《1996-03-01 Warren Buffett's Letters to Berkshire Shareholders》。 Helzberg's Diamond Shops Helzberg 钻石连锁店 A few years back, management consultants popularized a technique called "management by walking around" (MBWA). At Berkshire, we've ...

      • 2010-05-26 Warren Buffett.Investment, Speculation, Gambling

        Refer To：《2010-05-26 Warren Buffett.Investment, Speculation, Gambling》。 WARREN BUFFETT: It’s a question of being, it’s the ability to inject enormous amounts of leverage into a system where leverage is dangerous. And without people fully appreciating ...

      • 1997-02-28 Warren Buffett.USAir

        Refer To：《1997-02-28 Warren Buffett's Letters to Berkshire Shareholders》。 USAir When Richard Branson, the wealthy owner of Virgin Atlantic Airways, was asked how to become a millionaire, he had a quick answer: “There’s really nothing to it. Start as ...