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. 我们认为攻击者试图生成一个替代链比诚实链更快的场景。即使这样做了，它也不会使系统受到任意更改的影响，例如凭空创造价值或拿不属于攻击者的钱。节点不会接受作为支付的无效事务，并且诚实节点将永远不会接受包含它们的块。攻击者只能尝试改变他自己的交易，以收回他最近花的钱。
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. 诚实链和攻击者链之间的竞争可以被刻划为二项式随机游走。成功事件是诚实链被一个块扩展，其领先优势增加+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 follows [8]:
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.
攻击者从给定的赤字中追赶的概率类似于赌徒的破产问题。假设一个拥有无限信用的赌徒从赤字开始，为了达到收支平衡，可能要进行无数次尝试。我们可以计算他达到收支平衡的概率，或者攻击者追上诚实链条的概率，如下所示[8]：
假设p>q，随着攻击者必须追赶的块数的增加，概率呈指数下降。面对这样的机遇，如果他不早点幸运地向前冲刺，他的机会就变得渺小了，因为他落在了后面。
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. 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. 当发生这种情况时，接收器会被提醒，但发送者希望它太晚了。接收方生成新的密钥对，并在签名之前向发送方提供公钥。这防止发送者通过连续地处理它来提前准备一连串的块，直到他足够幸运地获得足够的提前，然后此时执行事务。一旦事务被发送，不诚实的发送者就开始秘密地在包含其事务的备选版本的并行链上工作。
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块之后才被链接。他不知道攻击者已经取得的确切的进展量，但是假设诚实的块占用每个块的平均预期时间，攻击者的潜在进展将是具有期望值的泊松分布：
为了得到攻击者现在仍然能够追上的概率，我们乘以泊松密度，对于他可能已经取得的每个进展量，乘以从那个点开始他可以追上的概率：
重新排列以避免对分布的无限尾求和…
设想如下场景：一个攻击者试图比诚实节点产生链条更快地制造替代性区块链。即便它达到了这一目的，但是整个系统也并非就此完全受制于攻击者的独断意志了，比方说凭空创造价值，或者掠夺本不属于攻击者的货币。这是因为节点将不会接受无效的交易，而诚实的节点永远不会接受一个包含了无效信息的区块。一个攻击者能做的，最多是更改他自己的交易信息，并试图拿回他刚刚付给别人的钱。
诚实链条和攻击者链条之间的竞赛，可以用二叉树随机漫步（Binomial Random Walk)来描述。成功事件定义为诚实链条延长了一个区块，使其领先性+1，而失败事件则是攻击者的链条被延长了一个区块，使得差距-1。
攻击者成功填补某一既定差距的可能性，可以近似地看做赌徒破产问题（Gambler’s Ruin problem）。假定一个赌徒拥有无限的透支信用，然后开始进行潜在次数为无穷的赌博，试图填补上自己的亏空。那么我们可以计算他填补上亏空的概率，也就是该攻击者赶上诚实链条，如下所示[8] ：
假定p>q，那么攻击成功的概率就因为区块数的增长而呈现指数化下降。由于概率是攻击者的敌人，如果他不能幸运且快速地获得成功，那么他获得成功的机会随着时间的流逝就变得愈发渺茫。那么我们考虑一个收款人需要等待多长时间，才能足够确信付款人已经难以更改交易了。我们假设付款人是一个支付攻击者，希望让收款人在一段时间内相信他已经付过款了，然后立即将支付的款项重新支付给自己。虽然收款人届时会发现这一点，但为时已晚。
收款人生成了新的一对密钥组合，然后只预留一个较短的时间将公钥发送给付款人。这将可以防止以下情况：付款人预先准备好一个区块链然后持续地对此区块进行运算，直到运气让他的区块链超越了诚实链条，方才立即执行支付。当此情形，只要交易一旦发出，攻击者就开始秘密地准备一条包含了该交易替代版本的平行链条。
然后收款人将等待交易出现在首个区块中，然后在等到z个区块链接其后。此时，他仍然不能确切知道攻击者已经进展了多少个区块，但是假设诚实区块将耗费平均预期时间以产生一个区块，那么攻击者的潜在进展就是一个泊松分布，分布的期望值为：
当此情形，为了计算攻击者追赶上的概率，我们将攻击者取得进展区块数量的泊松分布的概率密度，乘以在该数量下攻击者依然能够追赶上的概率。
化为如下形式，避免对无限数列求和：
写为如下C语言代码：
Converting to C code...
#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值呈指数下降。
Running some results, we can see the probability drop off exponentially with 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
Solving for P less than 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.结论-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. 我们提出了一个电子交易系统，不依赖于信任。我们从通常的数字签名硬币框架开始，它提供了对所有权的强有力控制，但是没有办法防止双重消费，它是不完整的。为了解决这个问题，我们提出了一个对等网络，它使用工作证明来记录事务的公共历史，如果诚实的节点控制大部分CPU功率，那么对于攻击者来说，这在计算上很快就变得不切实际。网络在其非结构化的简单性方面是健壮的。节点同时工作，几乎没有协调。它们不需要被标识，因为消息没有路由到任何特定的位置，并且只需要在尽力的基础上交付。节点可以随意离开和重新加入网络，接受工作链的证明作为他们离开时发生的事情的证据。他们用自己的CPU能力投票，通过扩展有效块来表达他们对有效块的接受，通过拒绝处理无效块来表示对无效块的拒绝。任何需要的规则和激励可以通过这种共识机制来实施。
我们在此提出了一种不需要信用中介的电子支付系统。我们首先讨论了通常的电子货币的电子签名原理，虽然这种系统为所有权提供了强有力的控制，但是不足以防止双重支付。为了解决这个问题，我们提出了一种采用工作量证明机制的点对点网络来记录交易的公开信息，只要诚实的节点能够控制绝大多数的CPU计算能力，就能使得攻击者事实上难以改变交易记录。该网络的强健之处在于它结构上的简洁性。节点之间的工作大部分是彼此独立的，只需要很少的协同。每个节点都不需要明确自己的身份，由于交易信息的流动路径并无任何要求，所以只需要尽其最大努力传播即可。节点可以随时离开网络，而想重新加入网络也非常容易，因为只需要补充接收离开期间的工作量证明链条即可。节点通过自己的CPU计算力进行投票，表决他们对有效区块的确认，他们不断延长有效的区块链来表达自己的确认，并拒绝在无效的区块之后延长区块以表示拒绝。本框架包含了一个P2P电子货币系统所需要的全部规则和激励措施。
参考文献-References
[1] W. Dai, "b-money," http://www.weidai.com/bmoney.txt, 1998.
《a scheme for a group of untraceable digital pseudonyms to pay each other with money and to enforce contracts amongst themselves without outside help》—《一种能够借助电子假名在群体内部相互支付并迫使个体遵守规则且不需要外界协助的电子现金机制》
[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.
《概率学理论与应用导论》
————————————————
版权声明：本文为CSDN博主「一个处女座的程序猿」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41185868/article/details/78939022
