注：本文檔已於2015 年3 月進行了大量修改。舊版本可以在https://download.wpsoftware.net/bitcoin/old-pos.pdf 找到。
1. 引言
2009 年，中本聰創造了比特幣[Nak09]。比特幣是一種互聯網貨幣系統，可以實現點對點的數字代幣轉賬。為確保所有人就代幣所有權達成共識，中本聰採用了一種可由所有網絡參與者復制並驗證的公共賬本。為了避免單點故障，該賬本採用一種動態成員多方簽名（dynamic membership multiparty signature，DMMS）[BCD+14] 機制來證實（authenticated），即，在每次“心跳” 時對整個賬本歷史執行一次高成本計算（但是驗證成本很低）。
不同於傳統的數字簽名，DMMS 中沒有“可偽造性” 的概念（there is no notion of “forgeability” for a DMMS）。每個DMMS 的創建成本都很高（在比特幣中，需要消耗高昂的電力成本），並且，這種行為可以得到賬本上增發的新貨幣作為獎勵。由於這些新代幣必須得到其他人的認可才有用，參與者會受到激勵來共同擴展“真正的賬本”，而非自行創建賬本 1。 （譯者註：此處的“認可” 一詞原文為“recognize”，也就是說它的原意可能並沒有那麼多“社會共識” 的暗示，其本身可以有嚴格的技術含義：如果你沒有收到一個區塊，你就不會認可由這個區塊發行的貨幣。）
由於比特幣的DMMS 在計算和熱力學[Poe14a] 方面成本非常高，人們已經提出了其它更為經濟環保的方案。最常被提議的方案是PoS（權益證明），它是一種低成本的分佈式共識機制。正如Andrew Poelstra [Poe14b] 在2014 年所言，PoS 是不可行的，但還是湧現出各種形式的PoS 方案。與此同時，各種論壇上經常有人聲稱Poelstra 的論點是“虛假” 或“錯誤” 的，儘管他們從來沒有提出任何有說服力的反例或錯誤。此外，也有人給出了中肯的意見，認為Poelstra 的這篇論文寫得晦澀枯燥。由此可見，這篇論文還有許多不足之處。雖然Poelstra 沒有發現他的前作有任何不准確之處，但是他準備藉此機會進一步地正式闡述他的論點。
相比Poelstra 撰寫論文時，人們對比特幣共識的科學認識已經有了巨大進步[MLJ14, BMC+15] 。
本文旨在更新Poelstra 的論文，闡明比特幣所解決的問題，PoS 背後的設計原理，以及PoS 之類的機制無法在比特幣的信任模型中產生分佈式共識的原因。
注1: 為了確保所有參與者都可以看到“真正的賬本”，我們需要一個同步網絡：所有（有效）數據都能在一定的時間長度λ 內到達所有參與者，而且網絡心跳時間比λ 長得多。如果沒有同步網絡，分佈式共識的難度會大得多。 （經常被人引用的一個結論是，使用確定性算法是不可能實現分佈式共識的[FLP85]；但使用概率算法就可以很容易避免這一問題，因此在共識系統的設計難度上沒有很多討論。本文檔的舊版本錯誤地引用了這一結論，以為這一點使得所有分佈式共識機制在異步網絡中都不可能達成共識，感謝Dominic Williams 指出了這一點。）
2. 分佈式共識
在討論比特幣對於分佈式共識問題的解決方案之前，我們首先要理解這個問題的本質。分佈式共識（比特幣系統所使用的術語）是一種彼此之間缺乏信任的參與方之間達成的共識（即，全局一致global agreement）。這些參與方都是匿名的，而且在系統建立時並不一定存在。正如Poelstra 在其論文中所解釋的那樣：
就密碼學貨幣而言，僅在交易的時間順序上達成分佈式共識就足夠了，即，就“第一個轉移特定資金的交易達成共識”。這樣可以確保整個網絡都認可新的資金所有者。
之所以需要達成這種共識，是為了防止 重複花費 問題（double-spending）。在所有去中心化數字貨幣機制中，都有可能出現付款方將同一筆資金發送給兩個不同的人的情況，而且這兩筆交易看起來都是有效的。因此，收款方需要能夠確保沒有發生衝突，或者在有衝突的情況下，網絡會認可其交易為正確版本。就交易順序達成分佈式共識可以實現這一目的：在發生衝突的情況下，每個人都認可第一筆交易是有效的，其餘交易是無效的。
（數字貨幣的其它問題，如權限和防偽，相對來說比較容易，可以通過傳統密碼學解決。）
重點是，我們應該意識到，儘管分佈式共識是個難題，但是普通共識更加容易，經過了更深入的研究，而且使用受信任且可識別的簽名方可以將效率提高數万億倍。因此，（即使是在有限條件下）引入了受信任方的密碼學貨幣都應該考慮的一點是，其新型信任模型是不是能幫助降低達成共識的難度。對更高效的、具備受信任方的共識機制感興趣的讀者可以研究一下。
3. 動態成員多方簽名（Dynamic Membership Multiparty Signatures）
比特幣的賬本是公開可用的，比特幣網絡中的所有參與者都可以驗證賬本上每筆交易的有效性。然而，由於賬本在根本上屬於歷史記錄，密碼學無法辨別真偽，必須要有人來證明賬本，而且其他人必須相信這個人不會簽署錯誤的歷史。
最早的數字現金系統都由單個非匿名者簽署所有交易[Cha83]。然而，這樣不僅為系統引入了單點故障風險，而且可以讓簽署方（以及任何可以通過權力或武力來脅迫該簽署方的人）審查交易或發起重複花費。雖然我們可以採用盲簽名（具體參見[Cha83]）來防止審查制度，但是無法防範單點故障和重複花費問題。多方簽名或許有可以解決後面兩個問題，但是所有簽名方難以同時遭到脅迫與所有簽名方必須得到所有參與者的信任這兩個要求是相互衝突的。非匿名性也意味著，特定攻擊者總能持續攻擊系統。
比特幣的解決方案是完全去掉固定且可識別的簽名者。比特幣的賬本由一組被稱為礦工的簽名者驗證，他們不向其它參與者公開自己的身份，或許還可以零成本進入或退出系統。礦工通過叫做“挖礦” 的過程來生成簽名。在挖礦過程中，他們會共同為連續的、由交易數據組成的區塊生成 工作量證明 [Bac02]。
在本節中，我們將解釋挖礦是如何運作以及如何提供驗證的。
3.1 匿名世界裡的鑑別（authentication）
密碼學數字簽名機制的運作原理如下。簽名方生成“簽名” 和“驗證” 密鑰對（s，v），並將v 連同其姓名一起發佈在某個公共渠道上。該簽名方可以根據給定消息m 生成簽名σ，任何人都可以驗證σ 的有效性。也就是說，將v，m 和σ 輸入驗證算法，如果簽名是有效的，總是會輸出1。
為了安全起見，傳統數字簽名必須具備抗偽造性，即，任何計算能力有限的攻擊者偽造簽名的概率都微乎其微。具體而言，“偽造” 指的是（攻擊者）能在下列遊戲中勝出：
簽名者將驗證密鑰v 交給攻擊者。攻擊者將消息m_i 發送給簽名者，並收到這些消息的有效簽名σ_i。攻擊者可以多次重複該操作。攻擊者生成一個新的消息m 連同一個基於m 的有效簽名σ。
這種安全性被稱為 選擇明文攻擊下的不可偽造性（existential unforgeability under chosen-message attack），是密碼學文獻中的常見標準。
【在多方簽名機制中，每個簽名者都有一個驗證密鑰。只有簽名者（或者說簽名密鑰）的“可採信子集” 生成的簽名才有效。在定義安全性時，上述遊戲經過了修改，允許攻擊者請求（並獲取）簽名密鑰，只要該攻擊者獲得的密鑰無法組成“可採信子集” 即可。 】
可以看出，驗證算法使用驗證密鑰v 來驗證簽名，並通過這種方式來驗證簽名者的“身份”。由於任何人都可以創建密鑰對，若想簽名具有價值，必須通過公共記錄將驗證密鑰與簽名者的真實身份聯繫起來。如果出現失信行為（簽署無效歷史），失信方會被問責。
這樣來看，身份鑑別並不適用於簽名者匿名且不固定的系統。事實上，我們還不清楚“身份鑑別” 在這類系統中能發揮什麼作用！如果任何人都能以匿名方式生成簽名，就無法區分誠實的簽名和不誠實的簽名、真實的歷史和虛假的歷史。那麼上述安全性定義就喪失了意義，因為攻擊者可以自由加入簽名者集，並“偽造簽名”2。
為了解決這一問題，比特幣採用了另一種安全模型。在該模型中，所有參與者都平等，但是他們會在經濟激勵下保持誠實。在下一部分，我們將介紹該安全模型。
注2: 正如我們在第四部分所見，如果是密碼學貨幣，匿名參與方就有可能鎖定保證金，並通過某種機制在無需確認任何人的身份的情況下，懲罰失信行為者。這實際上就是權益證明。然而，密碼學貨幣離不開共識，因此“如果是密碼學貨幣” 這個前提導致我們在這裡無法使用權益證明，否則就會陷入循環推理。我們會在下一部分解決這個問題。
3.2 為DMMS 定義安全性
就DMMS 而言，所有參與方都是平等的；無法通過讓“敵手” 僅擁有不完全知識（incomplete knowledge）來獲得安全性。因此，我們使用以下三部分定義了DMMS。這些部分都不同於傳統簽名的密鑰生成算法：
使用代價函數c 來追踪算法的執行並輸出“代價（cost）” t ∈ ，其中 是某個“代價域”。該函數必須是線性的，因為連續運行兩個算法的成本是它們各自成本的總和。隨機化算法AttemptSign 將消息m 作為輸入，輸入簽名σ。輸入任何消息m，該算法的代價都應該是1。確定性算法Verify 將消息m、簽名σ 和目標代價T 作為輸入，輸出0 或1。
當且僅當Verify(m, T, AttempSign(m)) = 1 對所有屬於的T 都有1/T 的概率成立，則我們說該DMMS 是正確的（correct），這個概率是由AtemptSign 算法來保證的；當且僅當任意多項式算法實現Verify(m, T, A (m)) = 1 的概率都不超過1−(1−1/T)t，則我們說這樣的DMMS 是安全的（ secure）（其中t 是算法A 的執行代價）。
換言之，安全的DMMS 指的是沒有比重複執行AttemptSign 更好的簽名算法（從創建驗證簽名的意義上來說）。
我們簡要論證了我們的安全性定義。為了實現動態成員集合，我們不能讓參與成本過於昂貴，也不能讓已有簽名者通過顯而易見的手段或經濟因素排斥新加入的簽名者。這就意味著，簽名過程應該是“可分割的”，既不需要也不激勵簽名者之間進行任何通信。也就是說，花兩倍長的時間運行一個簽名算法應該與在同樣的兩個硬件上並行運行該簽名算法的成功概率一樣高。在極端情況下，這意味著最好的簽名算法應該由對單一基礎步驟的重複、獨立執行來組成，這是由定義推導出來的。
3.3 挖礦機製作為一種DMMS
比特幣挖礦採用的是基於哈希函數的工作量證明算法hashcash [Bac02]。這是一種使用隨機數神諭模型（random oracle model）的DMMS [BR93]。作為一種計算模型，隨機神諭是指，該模型把哈希函數當成一個“隨機數神諭” ，或者說真隨機函數3，其輸出都是純然隨機的，而且只有通過該函數才能計算出來。
雖然隨機數神諭模型的使用引起了很多爭議[Gre11]，但是有力的實證證據證實了它可以用來保障安全性。下文中，H 指的是輸入可多達256 位的哈希函數，它被當成是一個隨機數神諭。
比特幣的DMMS 如下：
代價函數給出執行中調用隨機數神諭的次數。 AttemptSign 將消息m 作為輸入，並輸出隨機數σ ∈ {0,1} 256。 Verify 將簽名σ 、消息m 和目標T 作為輸入。僅當H(m || σ) < 2256/T 時，輸出1。
不難看出，在隨機數神諭模型中，沒有比重複運行哈希函數更好的創建有效簽名的方法。
注3：該模型是完全不現實的，因為真正的隨機函數，from, say, 512 bits to 256 bits，平均需要2512·256 位來表示，已經超過了目前已知的表達極限。
3.4 沒有世界時間
請注意，在上一部分，我們將哈希函數調用的數量作為我們的代價函數，它與計算次數大致成正比，而計算次數又與散熱量大致成正比。最後，散熱量與創建這些簽名的經濟和環境成本大致成正比。
一個顯而易見的問題是，我們是否可以採用“成本更低” 的代價函數？尤其是，為什麼我們不能直接使用時鐘時間？為什麼我們使用DMMS 對區塊進行簽名來創建區塊鏈，而非直接按照時間順序對交易進行排序來解決共識衝突？
答案是，分佈式系統中缺少明確定義的時鐘時間。網絡延遲限制了信息的傳播速度。根據狹義相對論可知，如果是幾乎同時發生的事件，不同的觀察者無法就其時間順序達成共識。
如果只是這個問題，那麼要求每筆交易之間間隔幾秒鐘即可（如果相互衝突的交易之間間隔太短，這兩個交易都會被拒絕；但是等到每筆交易完成幾秒鐘後，所有參與方就能確保不會發生這種情況）。但是，實際情況會更加糟糕，原因有兩點：
“網絡延遲” 在惡意環境中無法得到限制。攻擊者或能使用拒絕服務攻擊（denial-of-service measures）來任意降低系統速度，並通過其它方式對網絡進行物理分區。用相對論來說，這意味著無論將等待時間設為多久，都無法確保參與者不會與網絡中的其他參與者類空分離（spacelike separated）。新加入網絡或最近離線的用戶需要訪問歷史數據。但是，沒有辦法可以事後驗證交易發生的順序，因此在出現交易衝突的情況下，用戶無法保證他們收到的交易是先發生的。
3.5 來自DMMS 的共識
既然我們已經了解了DMMS，並解釋了為什麼比特幣的hashcash 是一個安全的算法，接著來思考如何通過DMMS 實現分佈式共識。
我們的主張是，通過DMMS 實現分佈式共識是有可能的。
我們首先需要通過我們的代價函數（單調函數）來衡量（a）某種無法一次為多個消息創建簽名的稀缺資源，和（b）創建簽名所需的平均時間。 （為了實現去中心化，這種稀缺資源可能需要被永久消耗，就像在比特幣系統中那樣，讓挖礦的邊際成本在資本成本中占主導。Poelstra 支持這一觀點[Poe14a]，但是John Tromp 並不認同[Tro14]。）
以比特幣為例，我們的代價函數的定義是“哈希函數調用的次數”。我們主張，該函數實際上用來衡量計算簽名所需消耗的能源，並且得到了Landauer limit 的論證[Lan61]。從物理學上來說，所謂的能源，就是任意不可逆的位操作所需消耗的最低熱量。通過計算sha256 計算中涉及的不可逆位操作的數量，（至少從原則上來說）我們可以為創建一個比特幣DMMS 所需消耗的能源量設定下限。
代價函數也可以用來衡量創建簽名所需的時間，因為每單位時間只能消耗一定量的能源，除非你去製造黑洞（black hole）（即，不讓簽名乃至任何信息以可用的形式提取出來）。當然了，在現實生活中，比特幣礦工不會在接近黑洞極限的情況下操作，而且所需時間取決於挖礦硬件的速度。隨著挖礦硬件的改進，以及同時在線的硬件數量增多，創建DMMS 所需的時間減少。在比特幣中，目標代價會根據這一情況進行調整，將創建每個簽名所需的時間保持在10 分鐘左右 4。
注4：鑑於3.4 中提到的無世界時間，讀者可能會想知道如何準確調整時間。實際上，時間戳是由礦工插入區塊的，而且確實沒有任何方法可以防止礦工弄虛作假。比特幣可以抵禦不實時間戳導致的較小目標偏離，並且也禁止了目標（譯者註：即難度）過快地發生變化。因此，想要製造大幅的目標偏離是非常昂貴的，而且有可能遭到不配合的礦工的阻撓。關於更多討論，請參閱[Poe14c, Section 6.3]。
那麼，有了一個可以通過代價函數來衡量稀缺資源的安全DMMS，我們該如何獲得共識歷史？首先，我們假設網絡是同步的，因此（絕大部分）參與者可以在一定時間λ 內獲得所有有效數據。我們將交易歷史分割成一系列區塊，其中每個區塊都包含一系列交易，以及前一個區塊的密碼學承諾（commitment） 5。每個有效區塊必須擁有一個已經設定好目標的DMMS，且目標使得創建區塊所需的時間比λ 長的多（這樣一來，在同一個共識歷史上工作的礦工都知道哪個區塊是最新的，而且區塊創建者也不會因為優先知道最新區塊而佔據很大優勢）。需要明確的是，每個DMMS 的目標代價是由系統規則定義的，不由礦工決定。
注5：承諾（commitment）是一種密碼學對象，由某個秘密數據計算得出，但是不會洩漏該數據，因此該數據在事後無法修改。抗碰撞哈希函數就是一例：給定數據x，你可以先發布H(x)（H 是哈希函數），之後再公開x。驗證者可以使用公開的值計算H(x)，來確認這個值是否與原始值相同。
網絡參與者的運作方式是：首先考慮以同一個創世塊（已硬編碼到系統中）開頭的所有有效區塊分支。 （由於每個區塊都包含前一個區塊的承諾，結果會形成以創世塊為根的有向非循環圖，這些區塊分支就是圖中的路徑。）然後計算每個區塊上的DMMS 的目標成本總和得出每條區塊分支的重量。最重的區塊分支會被視為“真實的” 歷史。
在創建區塊時，礦工根據自己的意願選擇交易，並加入一個特殊的“獎勵交易” 用來將其它交易的費用以及網絡定義的補貼分配給自己，再加上（他所認為的正統鏈上的）最新區塊的承諾，然後計算DMMS。如果另一名礦工創建並發布了一個區塊，礦工就會相應地更新他們的“真實歷史上的最新區塊”，並在自己所挖的區塊中改變承諾以適配這種變化。計算出一個DMMS 之後，他們會把這個完成的區塊公佈到網絡中。
我們主張這樣就能形成一個共識的歷史，是說整個網絡會漸進地對到底哪些區塊是真實歷史的一部分（而哪些不是）達成共識，而且不一致只會發生在最近的歷史中。具體的論述可見Miller 和La Viola Jr. [MLJ14]（我們這篇文章中可度量耗能程度DMMS， 在那篇文章中的表述是“moderately-hard puzzles”），但我們這裡附上一個不那麼正式的論證。
因為網絡是同步的，區塊傳輸的時間大大短於區塊生產的時間，所以所有參與者都能迅速認識到最重的歷史。
我們還進一步認為，網絡中的大部分參與者都會參與生產能延伸真實歷史的DMMS。一個優雅且正確的理由是由Vitalik Buterin 提出的[But15]：因為“獎勵交易” 當且僅當其區塊屬於真實歷史才會被大家接受，所以對每一個礦工來說，納什均衡就是服從絕大多數6。
注6：也是在同一篇文章裡，Buterin 說：“要是你已經厭煩了PoS 的反對者老是跟你引用Andrew Poelstra 寫的這篇文章（即[Poe 14b]），請盡情鏈上本文，作為還擊。” 不太清楚他這麼說是什麼意思；自始至終，無論在哪兒，他都沒能駁倒本文的主張：除了消耗一種系統外的資源，沒有別的產生共識的辦法。
要想改變“真實歷史”，攻擊者必須產生另一個權重更大（即目標開銷更大）的歷史（這樣的另類歷史版本可以定義為從當前的歷史最新頂端向後回溯N 個區塊處產生的一個分叉）。他具有的資源比正在延伸真實歷史的礦工團體要少，因為那個礦工團體才是多數。所以，他在網絡中能勝出的概率是小於1 的（因為在任意給定時間段裡，網絡中延伸真實歷史的嘗試次數都多過他延伸自己的另類歷史的嘗試），而且，要想讓自己的歷史超過真實歷史，他還必須勝出N 次以上。如果勝出一次的概率是P < 1，那他勝出N 次的概率就是PN，N 足夠大這個概率就小到可以忽略不計了。
（這裡的論證是很弱的，因為只考慮到了一個攻擊者要連續不斷地勝出，沒有考慮到出塊難度會調整；難度的調整會使得攻擊者在重新製造舊區塊時速度可以比網絡製造新區塊更快。筆者在這裡主張，沒有任何根據地主張，這些都不是嚴肅的問題，只是乏味的問題。）
（未完）
原文鏈接:
https://download.wpsoftware.net/bitcoin/pos.pdf
作者: Andrew Poelstra
翻譯&校對: 閔敏& 阿劍
