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=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