中本聰比特幣論文(下)

中本聰論文 比特幣:一個點對點的電子現金系統(Bitcoin: A Peer-to-Peer Electronic Cash System) (下)

譯者: Paul Chao的私房菜 趙尚威
1.文採意譯
2.圖取自 http://nakamotoinstitute.org/bitcoin
3.轉載譯文請註明出處，謝謝。

七、回收磁碟空間

當一個比特幣的最後交易紀錄已經被埋進夠多區塊裡面以後，之前的花費性交易紀錄就可以刪除以節省硬碟空間。為了讓這個不破壞區塊的哈希(hash)值，交易紀錄會用Merkle Tree來做哈希值，而且只有Merkle Tree的根值會被包含進區塊的哈希值中，舊的區塊可以把Merkle Tree的分支支解掉以壓縮空間，而中介性的哈希值不需要儲存。

沒有交易紀錄的區塊頭會是80 bytes, 如果我們假設每個區塊的產生是10分鐘，一年產生80 bytes * 6 * 24 * 365 = 4.2MB。依照2008年電腦系統銷售以2GB RAM為標配，摩爾定律預測當前的增幅是每年1.2GB，依此來看即使區塊頭必須被保留在記憶體裡，存儲都不應該是一個問題。

八、簡化付款驗證

在不運行完整網路節點的情況下來驗證付款是可能的。 用戶只需要保留在最長工作量證明的那一條鏈中所有區塊頭的副本，這個可以透過查詢比特幣網路上的節點直到確認這是最長條的鏈，以及取得已經加入時間戳記的區塊中連於交易的Merkle Tree的分支。他或許沒辦法自己檢查交易紀錄，但是透過鏈連到區塊鏈中的一處，他可以看到網路上某個節點接受了他的連結，而且在確認網路接受以後會持續有區塊加入。

因此，只要誠實的節點控制網路，驗證是可靠的，但是如果網路被攻擊者過度攻擊，還是會有漏洞。當網絡節點可以自己驗證交易的時候，這個簡化的方法可能會被攻擊者捏造的交易資料愚弄，而攻擊者可以繼續擴大攻擊整個網絡。防止這種情況的策略是在網路節點檢測到無效區塊時可以接收警報，提示用戶的軟件需要自己去下載完整的區塊以及遭警示的交易紀錄，以確認是否不一致。 頻繁收款的企業可能還是會想運行自己的節點以獲得更獨立的安全性以及更快的驗證。

九、組合和分割價值

雖然可以單獨一個一個來處理銅板，但為了每一分錢單獨去建立一筆交易是很不方便的。 為了讓價值可以被分割和合併，交易會包含多個輸入以及輸出。 輸入通常會是單筆從先前交易來的較大面額、或是多筆較小面額，但輸出最多是兩筆：一個用於付款，一個返回發送者返回更改（若有需要）。

值得一提的是，一筆交易取決於其他幾筆交易，而這些其他的幾筆交易又依賴更多其他的交易，這種扇出狀況（fan-out）在這裡不會是個問題。 因為我們從來沒有必要去提取一整個歷史交易紀錄的獨立副本。

十、隱私

傳統的銀行模式會對參與各方以及信任的第三方，保持信息存取的限制來實現一定程度的隱私，比特幣公開公布所有交易紀錄的必要性已經排除這種方法的可能，但透過把信息流打斷仍可以保持隱私：也就是讓保持公鑰匿名。公眾可以看到某人對某人發送金額，但沒有資訊能把這個交易跟任何人扯上關聯。這某種程度類似於證券交易，雖然交易時間和個別交易量被公開了，“紀錄磁帶”被公開了，但沒有告訴大家這些人到底是誰。

在這裡額外做個防火牆，每次交易都應該使用一組新的密鑰，使得擁有者的資訊不會曝光。某些連接仍不可避免會有多重輸入交易，必然表示這些輸入是由同一人擁有。這個風險在於如果所有者一個密鑰曝光，屬於這個人的其他交易也會隨著鏈接而曝光。

十一、計算

我們設想一個攻擊者試圖要快速產生另一條替代鏈，比誠實鏈的速度更快的場景。即便如此，它也不會讓系統開放到會任意變化，比如說憑空創造出價值來、或是攻擊者可以拿到不屬於自己的錢。節點是不會接受無效的交易成為真正付款，誠實的節點也永遠不會接受這樣包含這樣交易的區塊。攻擊者只可能改變自己發出的一筆交易來收回最近所花的錢。
誠實鏈和攻擊者鏈之間的競爭可以表徵為二項隨機漫步（Binomial Random Walk）。誠實的鏈條延伸了一個區塊，遞增1，增加了引導力，成為成功的事件、而攻擊者的鏈延伸了一個塊，減少了1，增加了差距，成為失敗的事件。
攻擊者從給定的差距可以趕上的機率，類似於賭徒破產問題（Gambler's Ruin problem）的機率。假設有一個無限信貸的賭徒從赤字開始，並且可以有無限次的嘗試去達成盈虧平衡。我們可以算出他有機會達到盈虧平衡的機率，也就是攻擊者的鏈可以追上誠實鏈的機率，如下[8]：
$$\large p = \small 誠實節點找到下一個區塊的機率$$ $$\large q = \small 攻擊者發現下一個區塊的機率$$ $$\large q_z = \small 攻擊者從後面的z個區塊追趕上來的機率$$ $$\large q_z = \begin{Bmatrix} 1 & \textit{if}\; p \leq q\\ (q/p)^z & \textit{if}\; p > q \end{Bmatrix}$$

若我們假設 p > q，機率是隨著攻擊者需要趕上的區塊數量增加而呈指數下降。對他來說，如果他不夠幸運，沒有早早開始的話，他的機會就會顯著地進一步變的更小。

我們現在要思考一個新交易的收件人到底需要等待多長時間才能夠確定發件人不能再更改交易。我們假設發件人就是攻擊者，他想讓收信人相信他已經付款了一段時間，一會兒之後轉過來把款轉回給自己。當發生這種情況時，收件人會被示警，但發件人會希望收件人發現的時候已經來不及了。

收件人產生一組新的密鑰對，並在簽章不久前才向發送者傳遞公鑰，這樣就可以防止發件人提前去準備一條區塊鏈，防止他幸運地遠在前面就開始進行偽造，然後執行交易那一刻能完成。一旦交易發送出去，不誠實的發件人開始在秘密兩條平行鏈上面工作，其中一條包含他的偽造版本。收件人一直等待，等到交易路已經被加到區塊裡了，並且z區塊已經被鏈接在後，他不知道攻擊者確切的進度，而是以為誠實區塊產生區塊本身就會有平均預期時間，而且假設攻擊者的潛在進度的期望值是呈帕松分佈(Poisson Distribution)：

$$\large \lambda = z \frac qp$$ 為了取得攻擊者還能趕得上的機率，我們將每個進度的數量乘以帕松密度，亦即他從那一個點可以趕上的可能性：
$$\large \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \begin{Bmatrix} (q/p)^{(z-k)} & \textit{if}\;k\leq z\\ 1 & \textit{if} \; k > z \end{Bmatrix}$$ 重新排列以避免加到分佈的無限尾部...
$$\large 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left ( 1-(q/p)^{(z-k)} \right )$$ 轉化成C的代碼:

#include 

執行產生一些結果之後，我們可以看到概率隨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

十二、結論

我們提出了一個不依靠信任的電子交易系統。我們在一開始提出了現在一般的數位簽章的貨幣框架，這種框架提供強大的所有控制權，但卻沒有辦法防止雙重支出，不夠完整。為了解決這個問題，我們提出了使用工作量證明的點對點網路來記錄歷史性的公共交易，如果誠實節點掌握多數的計算能力，這種方式可以很快就讓攻擊者的計算攻擊成為不切實際。這個網路在它的非結構簡單性裡是很強韌的，節點可以立即一起執行，不需要大量的協調工作。節點不需要被識別，因為訊息是不會經過任何特定的點，只需盡最大努力(best effort)傳遞。節點可以任意離開或重新加入網路，加入時可以信任地接受工作量證明鏈，得到它們不在時所發生的資訊。他們根據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. ↩