Bitcoin: A Peer-to-Peer Electronic Cash System

contributed by < kinoe_T >

tags: paper

一個純對等網路實作的電子貨幣可以讓線上交易直接在付款人和收款人雙方之間進行，無需任何第三方金融機構認証。數位簽章雖然也提供了部份的解方，但如果我們依然需要一個值得信任的第三方來避免雙重支付的行為的話，其最主要的益處就會喪失。對於雙重支付問題，我們提出了一個使用對等網路的解決方案。該網路透過「將交易透過計算雜湊值的方式串接到一個基於雜湊值計算的工作量證明的鍊結上」來做時間戳章 (timestamping) ，使該交易形成一個無法被更改的記錄，唯一的更改方式是重新做一次工作量證明。其中最長的一條鍊結不僅是一連串（交易）事件的證明，也證明了這些交易是經過了最多的 CPU 運算而得來的。只要大部分的 CPU 資源並沒有聯合在一起要進行網路攻擊，那麼他們產生出來的最長鍊就會超越攻擊者的鍊結長度。該網路本身需要的基礎建設很少。只要訊息儘可能在網路上擴散，所有的節點都可以隨意離開與重返這個網路，並透過接收最長工作量證明鍊作為他們離開期間的事件證明。

1. 簡介

網路上的商業行為目前幾乎完全依靠金融機構作為可信任的第三方來進行電子支付的行為。儘管在進行大部分的交易時這套系統都沒什麼問題，但信任制度本身固有的弱點依舊造成這套系統有所不備。從根本上來看，完全不可逆的交易是不可能存在的，因為金融機構無法避免商業糾紛。而調解商業糾紛增加了交易成本、限制了交易的（在電腦系統上實作的）大小、並且讓小型的臨時交易 （casual transaction） 變得不可能。並且更廣義上來看，無法為了不可逆的服務建制一個不可逆的交易系統也是一種成本。只要交易愈是需要可以撤銷、這套信用機制就愈是不可割捨。商人們為了防範其消費者，於是向消費者索取遠多於他們所需要的用戶資訊。少數的詐欺行為依然無法避免會發生。雖然這些成本和交易的不確定性在現實生活中可以透過交易者本人經由現金進行交易來避免，但在通信交易的世界中目前依然沒有任何一套機制是不需要可信任的第三方的。
要解決這些問題，我們需要的是一套基於密碼學校驗，而非信任制度的電子交易系統，讓任意兩個合意的交易者可以直接與對方進行交易，而不需要有任何的第三方參與。只要交易記錄本身在計算上是幾乎無法竄改的，就能避免賣方進行詐欺。並且常見的第三方託管機制可以被輕易的被實作，用以保障買方的權益（這句看不懂）。在這篇論文中，我們提出了一個應付雙重支付問題的解方，透過使用對等網路的分散式時間戳記伺服器，來產生一系列按時間順序發生的交易的計算證明。只要誠實的節點控制了比合力攻擊者更多的大部份 CPU 資源，這套系統就會是安全的。

2. 交易

我們定義電子貨幣為「一條數位簽章的鍊結 (a chain of digital signatures)」。每個貨幣的擁有者都可以將自己手上的貨幣轉移到另一個人手上，透過「將前一個交易的雜湊值與要轉交的對象的公鑰一起（以自己的私鑰）做電子簽章，並將簽章附加到鍊結的尾端」的方式進行。收款人可以透過付款人的公鑰來驗證簽章的正確性，藉以確認貨幣的所有權。

但問題還是一樣啊，收款人沒辦法驗證給他錢的這個貨幣擁有者是不是已經把要給他的這筆錢花到別的地方去了。一個常見的解決方法就是引入一個可信任的第三方，或叫作鑄幣場 (mint)，來確認每一筆錢是不是都沒有被雙重支付過。在每一次的交易中，付款人需要將錢交還給鑄幣場，鑄幣場將金幣銷毀，並鑄出等值的金幣交給付款人，只有從鑄幣場出來的金幣才能確定是沒有被雙重支付過的。這個解決方法的問題在於整套金融體系的命運全都被掌握在這個營運鑄幣場的公司手上，每一筆交易都必須經由他們，就像銀行一樣。
我們需要有一個方式讓收款人確認付款人沒有將要給他的那筆錢拿去簽署在其它更早的交易上。為此，（對於每一筆要交付出去的錢，）只有最早發生的那一次交易才是算數的，後面那些嘗試做雙重支付的交易對我們來說都不重要。要確認一筆交易是不是最早的那筆，唯一的方法就是記錄所有的交易歷史。在鑄幣場模式當中，鑄幣場本來就會得知並記錄所有的交易歷史，透過這些記錄他們就能夠確定哪筆交易最早發生。但在沒有一個可信任的第三方的情況下，交易記錄就必須要公諸於世[1]，並且要有一個方式，可以讓所有參與這個系統的人對交易歷史的時間順序達成唯一的共識。收款人需要能確保當每一筆交易發生時，大多數的節點都同意這筆交易是最早的那一筆。

3. 時間戳記伺服器

我們的解決方法要從時間戳記伺服器開始說起。時間戳記伺服器的職責是「拿一個要被蓋時間戳記的物件區塊 (block of items) 做雜湊運算，並將計算所得的雜湊值廣播出去，就像在發報紙或是發 Usenet 的帖子[2-5]一樣」。很顯然，該時間戳記證明了在該時間點這些資料已經存在，要不然怎麼會產生出這條雜湊值呢。每個時間戳記的雜湊值都記錄了比他更早的時間戳記，因而形成一條鍊結，愈後面的時間戳記愈是證實了前面的時間戳記。

4. 工作量證明

為了實作一個架構在對等網路上的分散式時間戳記伺服器，我們需要一套像是 Adam Back 的 Hashcash[6] 當中用到的那種「工作量證明系統」，而不是單純只是發報紙或是發論壇帖子而已。所謂工作量證明，指的是「尋找一個特定的數字，我們稱其做 nonce。將 nonce 與要進行雜湊的資料串接在一起後，可以使生成的雜湊值（例如: SHA-256 的 16 進位字串）開頭數個位數是 0」。要找到 nonce 所需的運算量會隨著要求的 0 的數量變多而指數增長，但驗證該 nonce 是不是正確的只需要進行一次雜湊運算。
回到我們的時間戳記網路，我們實作工作量證明的方法，是透過不斷遞增一個區塊裡頭的 nonce 值，直到那個可以滿足開頭數個位數為 0 的數字被找到為止。一旦 CPU 資源被投入、正確的 nonce 值被找到後，這個區塊就不能夠再被修改了。除非你改掉他之後又再做一次一樣的流程，找到另一個新的 nonce 值。而隨著愈多的區塊被串接到這個區塊後面，由於後面的區塊會包含前面區塊的雜湊值，因此更新前面的區塊就會連帶著需要更新後面的區塊。

這套工作量證明的系統同時也解決了多數決機制中的表決問題。考慮一個多數決系統，其規則是一個 IP 一票，那麼擁有很多 IP 的人就擁有最大的話語權，他可以隨意操作表決的結果。而工作量證明實質上是一個 CPU 一票的機制。表決的結果體現在最長鍊上面，因為最長鍊是經過了最多的 CPU 計算而產生出來的。如果大部分的 CPU 資源都是被誠實節點所控制，那麼可信任的鍊結就會長的最快，比其他的分叉都還要快，因而形成最長鍊。如果有攻擊者想要竄改任意一個區塊，那麼他必須重做該區塊的工作量證明、重做該區塊後面的所有區塊的工作量證明、趕上並超越誠實節點製造區塊的速度。之後我們將會證明，計算速度不夠快的攻擊者追趕上最長鍊的機率會隨著區塊的增加而指數降低。
此外，隨著硬體計算速度與參與網路的節點日益增長，我們需要動態調整找到 nonce 值的難度（也就是前面要有幾個 0）。為了讓網路每小時平均產出固定數量的區塊，工作量證明的難度會被隨之調整。當區塊產生的太快，難度就會增加。

5. 網路

營運上述這樣一個網路時會進行以下步驟：

1. 新的交易發生時，會廣播給所有節點
2. 每個節點都會將新的交易收集起來，放進區塊裏面
3. （當區塊滿了之後，）每個節點各自尋找 nonce 值，進行工作量證明
4. 當某個節點完成了工作量證明後，他將自己手上的那個區塊廣播給所有節點知道
5. 其它收到這個區塊的節點，只會在該區塊內的所有交易都是合法（一筆錢沒被花兩次）的情況下才會接受這個區塊
6. 當節點接受這個區塊後，這個區塊等同於已經串接到鍊結上。於是節點再生出一個新的區塊，並把已接受的這個區塊當作新區塊的前一個區塊，回到第一步

所有節點都視當前的最長鍊為正確的交易記錄，要產生新區塊時會串在這個最長鍊上。如果有兩個節點同時廣播了兩個不同版本的區塊，其它節點最先收到的有可能會是任意一個版本。在這個情況下，節點們會視先拿到的版本為最長鍊的尾端並繼續在上頭工作，而晚到的那個版本則被記錄下來變成分支。當更新的區塊被挖出來之後，總有一天這兩個分支會有一條變得比較長。就算分岔時節點跑到比較短的那條去工作，在收到新的區塊後也會因為注意到另一條分支更長的而跳轉過去。
新的交易發生時，並不需要讓所有節點都收到廣播。只要有足夠多的節點收到通知，這些交易遲早都會被加進區塊裏面。而區塊的廣播也是一樣，就算有掉封包也沒關係。如果有節點沒收到特定區塊，當他收到再下一個區塊的時候自己就會發現前面有漏掉了，到時候再跟別的節點請求正確內容即可。

6. 獎勵機制

依照慣例，每個區塊的第一筆交易都是一個特別的交易，該交易無中生有了一些新的貨幣，其擁有者是創造出該區塊的人。這套機制有兩個功能：既可以獎勵協助維護網路運作的節點們，也同時發行了一些貨幣進入市場中流通（現在沒有公正的第三方來發行貨幣了）。這種「貨幣量以穩定的數量持續增加」的現象，就好像是「金礦的礦工耗費資源從礦場當中挖出黃金並拿去鑄幣」一樣。在我們的例子中，CPU 運算所耗費的時間以及電力就是我們消耗的資源。
獎勵機制也可以透過交易手續費來支付。如果一筆交易的輸出比輸入還要少，那麼其差值就可以當作交易手續費被添加到包含該交易的區塊的獎勵值上。一旦預先設定好的金幣發行量已經完全進入市場流通，獎勵值可以完全透過手續費而非創造區塊來支付，因此完全不會有通貨膨脹的問題。
這套獎勵機制或許也有助於讓節點保持誠實。如果一個貪心的攻擊者真的掌握了比所有誠實節點還要多的 CPU 資源，那麼他有兩個選擇：修改以前的交易記錄並用這些 CPU 資源去重算工作量證明，藉以從其他人手中騙取金幣；或是乖乖的創造新區塊並獲得獎勵。攻擊者應該會發現，遵守遊戲規則比較划的來，因為創造新區塊得到的金幣數量會比從其他人身上騙來的還要多，沒必要破壞規則與自己財產的合法性。

7. 回收硬碟空間

一旦某個區塊中的最後一筆（最晚發生的一筆）交易已經被足夠多的區塊給埋住了，在那之前發生過的交易就可以丟掉，以節省硬碟空間。為了避免區塊的雜湊值因修改內容而變化，我們要使用雜湊樹 (Merkle Tree)[7][2][5] 來儲存交易記錄。計算區塊雜湊值時，我們只需要把雜湊樹的根節點考慮進去就可以了。舊區塊可以透過將雜湊樹的子樹剪掉來達到壓縮體積的效果，因為雜湊樹中間的節點是沒有必要儲存的。

一個不包含任何交易訊息的區塊，光是他的標頭 (header) 部分大概只會有 80 bytes。假設每十分鐘會產生一個區塊，那麼每年也只會產生

$80B\times 6\times 24\times 365=4.2MB$ 的資料而已。至今 2008 年，大部分的家用電腦都配有 2 GB 的 RAM，且根據摩爾定律，RAM 的大小還會每年增長 1.2 GB，就算必須把所有的區塊標頭都塞在記憶體裡面其實也不成問題。

8. 簡化的交易驗證

對於單一節點來說，不需要保存所有交易記錄也可以去驗證一筆交易是否合法。使用者只需要備份一份最長鍊的區塊標頭（這串標頭可以透過不斷查詢網路上的其他節點找到），然後再獲取將這筆交易和包含他的區塊串起來的雜湊樹分支就行了。使用者自己無法驗證這筆交易，而是透過雜湊樹確認這筆交易的確存在於鍊結上，進一步推斷網路上的其它節點是接受這筆交易記錄的。如果包含該交易的區塊後面串的區塊愈多，就代表愈多的網路節點接受這筆交易。

如此一來，只要誠實的節點在網路上的佔比愈高，驗證結果就愈可信；反之如果攻擊者的稱霸了整個網路，那這套驗證機制就會愈薄弱。只要網路節點可以幫自己的交易做驗證，那麼這套簡化的驗證方法很容易被持續稱霸網路的攻擊者用造假的交易記錄蒙騙。一個對付此問題的機制是，當有節點發現了不合法的交易記錄時，讓他去向網路上的其它節點發出警告，其它節點收到警告後會自動下載完整的區塊內容，用來交叉比對那筆被警告的交易，以確保區塊的正確性。很常進行交易的商家或許會因為需要有更獨立的安全性與更快的驗證速度，而自行營運節點。

9. 合併與切分交易量

雖然技術上來說，交易中的每一筆錢都可以分開處理，但是真的對每一分要轉移的錢都執行一次交易就太笨了。這些交易金額可以被切分或是被合併起來，讓每一次的交易都包含多個輸入和輸出。通常一筆交易的輸入可以來自於一筆很大的進帳，或是來自於很多筆小進帳，然後會產生兩個輸出，一個是支付用的，一個是找零用的（找零 = 把多出來的錢支付給自己）。

這種「扇出」（每筆交易的錢都來自於多筆交易，而那多筆交易的錢又來自於更多的交易）的行為，在這裡不會給我們帶來困擾。因為我們永遠都不會有需要將歷史上所有的交易記錄都整理出來的這種需求。

10. 隱私

傳統銀行維持帳戶隱私的方式，是藉由限制使用者存取交易雙方的資訊以及可信第三方的資料達成的。但我們的網路運作機制天生就是需要將所有的交易記錄廣播給所有人知道，可想而知這種維護隱私的方式在我們這裡行不通。但這並不表示我們就無法維持帳戶隱私。如下圖所示，我們可以在資訊流上的不同地方截斷存取權——也就是不公開公鑰。網路上的大家只能夠知道有一筆錢從某人手上轉移到了另一人手上，但是卻不知道這背後參與這場交易的人是誰。這種資訊揭露的程度，就好像股票市場一樣。在股市中你能夠看到的只有某張股票在某個時間點，被以多少錢（俗稱「行情」）、多少份量交易了出去，但你並不知道股票買賣的雙方到底是誰。

若要更進一步維護隱私，則應該限制一對數位簽章金鑰只能使用一次，避免透過金鑰的值辨識出多筆交易的參與人是同一個人。但某種程度上的關聯性仍無法避免，例如在一個有多個輸入的交易當中，所有的輸入都會需要被確認是來自於同一個人手上，才能合成一筆合法的金額。而這種作法的風險在於，如果某把鑰匙的所有人被揭露了，那麼跟這個人有關的其它交易也都會跟著一起被揭露。

11. 計算

考慮以下情況：攻擊者嘗試產生出一條比誠實鍊還要更長、長的更快的另一條鍊結。就算他成功了，這也不代表整個系統就會陷入可以被隨意修改的窘境，諸如憑空創造財富，或是拿走從來不屬於攻擊者的金錢等等，都是做不到的。節點們並不會認可非法交易的支付行為，也不會接受包含這些非法交易的區塊。攻擊者只能夠嘗試修改自己曾參與過的交易，拿回自己花掉的錢而已。
這個誠實鍊和攻擊者鍊之間的長度競爭，可以視為一種二項隨機漫步。成功的事件可以定義為「誠實鍊多了一個區塊」，記做 +1；失敗的事件則定義為「攻擊者鍊多了一個區塊」，記做 -1。
要計算攻擊者從落後給定的區塊數量開始成功追趕上誠實鍊的機率，就像是在解賭徒破產問題 (Gambler's Ruin problem)一樣。 假設一個賭徒在一開始擁有無限多的籌碼，他要下去玩一場永遠不會結束的賭局，並且嘗試達到損益平衡。（這句看不懂） 要計算賭徒成功達到損益平衡，也就是攻擊者成功追趕上誠實鍊的長度的機率，我們可以列出以下式子[8]：

$p=$ 誠實結點長出下一個區塊的機率

$q=$ 攻擊者長出下一個區塊的機率

$q_z=$ 攻擊者從落後

$z$ 個區塊的情況下成功追上誠實鍊長度的機率

$$q_z=\{\begin{array}{ll}1& \text{ if }p\le q\\ (\frac{q}{p}{)}^z& \text{ if }p>q\end{array}$$

在我們的系統中，

$p>q$ 應當是成立的，因此，當攻擊者落後的區塊愈多，成功追趕上的機率就會指數降低。在攻擊者處於劣勢的情況下，他如果一開始沒有追趕上來，後來居上的機率就會小到幾乎消失了。
現在我們來思考一個問題：一筆交易的收款人大概需要等多久才能足夠確定一筆交易已經無法再被更改了呢？假設付款人是一個攻擊者，他想要先暫時先讓收款人相信自己有付款給他，過一段時間之後再讓交易無效化，使最長鏈切換到他付款給自己的那個版本上。收款人到時候會收到版本切換的通知，付款人只求到時發出通知時一切已經為時已晚。
收款人會在進行數位簽章前很短的時間內產生出一對金鑰，然後把公鑰公開給付款人。這避免了付款人事先不斷挖礦，準備好一條很長的鍊子，直到他幸運到可以超越最長鍊，然後才發動交易。一旦交易記錄被廣播了，不誠實的付款人才能開始祕密的在另一個版本鍊子挖礦，並將自己的非法交易放在那裡面。
收款者必須等到他的交易被加進區塊裏面，並且有

$z$ 個區塊接在後面之後，才能確定交易成功。他並不知道攻擊者的明確的工作進度（領先幾個區塊），但是以誠實節點產生每個區塊所需要的平均耗時來看，攻擊者可能領先的進度可以用有著以下期望值的泊松分佈來預測：

$$\lambda =z\frac{q}{p}$$

現在要計算攻擊者依然可以趕上誠實鍊的機率，我們必須計算泊松分佈的機率密度。給定他所需要追上的區塊數量，他能夠成功追上誠實鍊的機率可以表示為：

$$\begin{gathered} \sum _{k=0}^{\mathrm{\infty }}\frac{{\lambda }^k{e}^{-\lambda }}{k!}\dot{ \\ }\{\begin{array}{ll}(q/p{)}^{z-k}& \text{if }k\le z\\ 1& \text{if }k>z\end{array} \end{gathered}$$

調整成以下式子避免要計算無限長尾：

$$1-\sum _{k=0}^z\frac{{\lambda }^k{e}^{-\lambda }}{k!}(1-(\frac{q}{p}{)}^{(z-k)})$$

轉換成以下的 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\mathrm{\%}$ 時的

$q$ 與

$z$ 值：

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. 結論

我們提出了一個不需要可信第三方的電子交易系統。我們首先著眼於傳統金融貨幣的架構，在此架構中，貨幣是藉由數位簽章的方式交易的。這套系統對於貨幣的所有權有很高的掌握度，但如果沒有可以避免雙重支付的方法的話，這套系統就不完整。為了解決這個問題，我們提出了一個利用工作量證明來記錄資訊的對等網路，在網路上記載著所有交易記錄的公開資訊，並且只要誠實的節點掌握大多數的 CPU 資源，交易記錄很快地就會變得難以被攻擊者竄改。即便不需要很多的基礎建設，這座網路依然很可靠。所有節點同時都在工作，但卻不需要彼此合作。這些節點也不需要是可辨識身份的，因為訊息並沒有一定要傳遞給誰，只要儘最大限度被傳的愈遠愈好。任意節點都可以隨時離線並重返網路，只要回來時請求那條工作量證明的最長鍊，就可以得知他離開的期間發生了什麼事。節點們利用他們的 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.

其它參考資料

• Bitcoin - 開放原始碼點對點數位貨幣
• 《詳解比特幣白皮書》系列 - Master 林
• 工作量證明 PoW (Proof of Work)－算力挖礦 - 桑幣知識+
• Day13|密碼學初探(6)：Merkle Tree - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天
• 概念講解區塊鏈 - sony112502
• 區塊鏈 Blockchain – 共識機制之工作量證明 Proof-Of-Work
• Writing a tiny blockchain in JavaScript | Savjee.be