乾貨：論權益和共識
編者按：本文來自以太坊愛好者（ID：ethfans），Odaily經授權轉載。
以太坊愛好者（ID：ethfans）https://download.wpsoftware.net/bitcoin/old-pos.pdf找到。
以太坊愛好者（ID：ethfans）
，Odaily經授權轉載。
以太坊愛好者（ID：ethfans）
找到。
1. 引言
，Odaily經授權轉載。
以太坊愛好者（ID：ethfans）
找到。
以太坊愛好者（ID：ethfans）
，Odaily經授權轉載。
注：本文檔已於2015 年3 月進行了大量修改。舊版本可以在
找到。
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.1 匿名世界裡的鑑別（authentication）
密碼學數字簽名機制的運作原理如下。簽名方生成“簽名” 和“驗證” 密鑰對（s，v），並將v 連同其姓名一起發佈在某個公共渠道上。該簽名方可以根據給定消息m 生成簽名σ，任何人都可以驗證σ 的有效性。也就是說，將v，m 和σ 輸入驗證算法，如果簽名是有效的，總是會輸出1。
為了安全起見，傳統數字簽名必須具備抗偽造性，即，任何計算能力有限的攻擊者偽造簽名的概率都微乎其微。具體而言，“偽造” 指的是（攻擊者）能在下列遊戲中勝出：
簽名者將驗證密鑰v 交給攻擊者。 攻擊者將消息m_i 發送給簽名者，並收到這些消息的有效簽名σ_i。攻擊者可以多次重複該操作。
可以看出，驗證算法使用驗證密鑰v 來驗證簽名，並通過這種方式來驗證簽名者的“身份”。由於任何人都可以創建密鑰對，若想簽名具有價值，必須通過公共記錄將驗證密鑰與簽名者的真實身份聯繫起來。如果出現失信行為（簽署無效歷史），失信方會被問責。
3.2 為DMMS 定義安全性 就DMMS 而言，所有參與方都是平等的；無法通過讓“敵手” 僅擁有不完全知識（incomplete knowledge）來獲得安全性。因此，我們使用以下三部分定義了DMMS。這些部分都不同於傳統簽名的密鑰生成算法： 使用代價函數c 來追踪算法的執行並輸出“代價（cost）” t ∈ ，其中是某個“代價域”。該函數必須是線性的，因為連續運行兩個算法的成本是它們各自成本的總和。
確定性算法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 的執行代價）。
比特幣挖礦採用的是基於哈希函數的工作量證明算法hashcash [Bac02]。這是一種使用隨機數神諭模型（random oracle model）的DMMS [BR93]。作為一種計算模型，隨機神諭是指，該模型把哈希函數當成一個“隨機數神諭” ，或者說真隨機函數3，其輸出都是純然隨機的，而且只有通過該函數才能計算出來。
雖然隨機數神諭模型的使用引起了很多爭議[Gre11]，但是有力的實證證據證實了它可以用來保障安全性。下文中，H 指的是輸入可多達256 位的哈希函數，它被當成是一個隨機數神諭。
比特幣的DMMS 如下：
代價函數給出執行中調用隨機數神諭的次數。
AttemptSign 將消息m 作為輸入，並輸出隨機數σ ∈ {0,1} 256。
代價函數也可以用來衡量創建簽名所需的時間，因為每單位時間只能消耗一定量的能源，除非你去製造黑洞（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 足夠大這個概率就小到可以忽略不計了。
（這裡的論證是很弱的，因為只考慮到了一個攻擊者要連續不斷地勝出，沒有考慮到出塊難度會調整；難度的調整會使得攻擊者在重新製造舊區塊時速度可以比網絡製造新區塊更快。筆者在這裡主張，沒有任何根據地主張，這些都不是嚴肅的問題，只是乏味的問題。）
3.6 不使用DMMS 的共識
是否一定要使用DMMS 才能打造分佈式的共識機制呢？到目前為止這還是一個開放問題。筆者的猜測是“不是”。更具體一點來說，簡單改變比特幣協議，用“優惠券” 來獎勵那些以更低難度挖出未來區塊的礦工[BDC+14, 章節6.1] 不太可能破壞共識機制，但這種模式顯然不符合我們上述的DMMS 定義。
4. 權益證明
有了比特幣的共識機製作為基礎，我們來分析一下當前最流行的替代方案，權益證明（Proof of Stake）。 PoS 的描述見[Poe14b]：
有了現代密碼學之後，“ '信息' 本身即是物理上真實且具有價值的東西” 這一觀念便擺脫了哲學系的教室，進入到真實的商業世界。我們都非常熟悉安全的通信所支撐的經濟活動：談判意見、合同、交易、買單和命令，都能發到互聯網公網上而無需擔心偽造和攔截。我們也都清楚，如果秘密數據遺失或被盜會帶來什麼樣的經濟後果。到了2009 年1 月，密碼學貨幣誕生[Nak09]，有價信息的概念就變得更加具體。你可以在公開的通信媒介中持有和交換一種同質化（fungible）的價值儲存物，僅僅只需使用密碼學方法（無需物理的安全設施）來防止欺詐和盜竊。人們不僅可以說“這把加密密鑰值1 萬美元，因為假使它暴露，我們就會損失這麼多金錢”，還可以說“這把密鑰值1 萬美元，但裡面的價值是可以分拆的，你可以拆出20 美元發給別人，自己留著剩餘的部分”。有這些背景知識，權益證明其實很好理解。一個權益證明就是一個對所有權的密碼學證明。在密碼學貨幣中，權益證明不僅能夠證明一筆貨幣的所有權，還可以證明這筆錢滿足一些特徵（比如，這筆錢是被鎖定的、無法花用的，直到某些條件被滿足才會解鎖）。具體來說，證明資金鎖定在一種稀缺且實驗性的密碼學貨幣上，可以視作證明了其人對該項目的成功有濃厚的興趣。用戶可以用提供鎖定的權益來證明自己對項目的持續存在（及可持續發展）有興趣。
也就是說，權益證明是這樣一種觀念：我們可以使用密碼學證明，而不是像朗道爾極限（Landauer limit）這樣的物理學理論，來證明某些計算是非常昂貴的。
4.1 權益證明vs DMMS
使用“純粹的權益證明” 來生成對一種密碼學貨幣的歷史的共識，這種思路其實是預設了：有可能創造出一種近似DMMS 的簽名方案7，其代價函數度量的是該種幣本身的數量。這在原理上聽起來很簡單，我們再次引用[Poe14b]:
在一個足夠有表現力（sufficiently expressive）的賬本上，貨幣的持有者可以鎖定他們的貨幣一段時間，以租借在密碼學上可驗證的“權益（stake）”。需要推進共識歷史時，每一個權益持有者都為延伸的內容（區塊）簽名，而不是為這些內容附加工作量證明。出於實踐上的方便，一般來說，每次出塊都會隨機選出權益持有者中的一小部分，來負責出塊；而且，要讓區塊獲得合法性（validity），也只需要這個小團隊中的大多數同意就行。這些被選中的權益持有者可以獲得獎勵，而且一段時間後，只要他們願意，就能解鎖自己的權益。這裡的觀念是，與其讓控制歷史的經濟代價高不可攀，權益持有者們有激勵對每一個區塊達成一致，因為（a）他們都是隨機挑選出來的，不太可能相互勾結；（ b）即使他們可能相互勾結，也不想搞崩整個系統（例如，簽署相互衝突的歷史就會導致這個結果）；（c）他們資本有限，無法造成巨大的破壞。因為上述理由，下一個被隨機選出的權益持有者團體可能只會選擇在一個他們認為可靠的歷史上出塊。
注7：權益證明方案並不總被嘗試設計成無過程性的（progress-free，亦即無論你此前做了什麼，都不會影響你下一次嘗試的成功率），所以並不都能成為正確的或者安全的DMMS。但是，其根本宗旨仍然是“讓製造歷史非常昂貴，並獎勵那些參與正確歷史的人”，所以我們繼續以成本這個視角來觀察。
該文已經稍微把事情複雜化了：在真實的權益證明系統中，往往只需要一個簽名者認可，而不需要絕大部分的認可。
這裡的問題是，要想恰到好處地定義出一種能夠度量（以某種貨幣的形式）鎖定權益數量的代價函數，先得有這種貨幣的共識歷史。如果只能達到“存在某段歷史，其中這些幣都是鎖定在一起的” 的程度，則雖然最終的DMMS 可能定義得很清楚，但其代價函數不再是度量稀缺的東西，而本文3.5 節的結論也就都不成立了。
當然，稀缺可以通過懲罰那些簽署多個歷史的權益持有者來塑造。舉個例子，如果系統使用Schnorr 或者ECDSA 簽名方案，且權益持有者在簽名時僅能選擇一個特定的nonce，則他們要簽署多個歷史時，就必然會用到同樣的(key, nonce)對來簽發兩條消息，而這會使得他人能用幾何求解出他們的私鑰。但是，這樣的設計還是不能阻止權益持有者們“研磨（grinding）” 區塊（不斷嘗試不同的區塊），僅發布那個能使他們在下一個區塊繼續擔任出塊者的區塊8，這樣不斷重複就能完全掌控整個區塊鏈。這就是“權益研磨” 攻擊的一個例子。下文我們可以看到，權益研磨只是一個更普遍問題的一個特例而已。
總的來說，一次性簽名方案可以防止權益持有者發布相互衝突的歷史（前提是攻擊者對自己會丟的幣估價更高，而不能從自己導致的混亂中得到更多），但一次性簽名無法防止權益持有者偷偷地製造相互衝突的歷史。
注8: 注意，隨機數必須由區塊鏈本身來決定，因為它就是大家要共識的唯一對象。所以PoS 礦工可以用權益研磨來扭曲系統。使用多個區塊或者久遠的區塊來決定隨機數並不能解決這個問題，無論哪一種方案，都有某一方能夠操縱它。
4.2 零成本的模擬（Costless Simulation）
如果每個人都能便宜地創建歷史，那系統就會崩潰。鎖定權益的用意正在於，讓“便宜創建歷史” 的權限僅對那些願意長期持有這種貨幣的人開放，而且可以假設，對這些人來說，這個系統意義重大，以至於不可能去攻擊它。但是，因為沒有全局時間（對那些新加入網絡的人，也沒有全局歷史），那就根本沒有辦法把“最近” 才開始持幣的人與“一直” 持幣的人區分開來。對一個權益證明系統來說，在歷史中的任何一個時間點，都有一組簽名密鑰可以轉讓貨幣、鎖定和解鎖權益、簽名區塊。可以假設，在真實世界裡的某一刻，系統創建出一個新區塊的時候，在這一刻，一些密鑰對應著所有權。但是，真實世界的時間會繼續流轉，而這個區塊會變成靜態之物，所有與它相關的簽名密鑰也會一起變成靜態的。
4.4 其他考量
我再說一遍：在真實的時間裡，區塊鏈會變得越來越長，權益會解鎖，幣會被用來交換別的產品和服務，而那些密鑰，即使誤用會導致持有者損失價值，也會變得毫無意義。但對於一個不可更改的區塊鏈來說，區塊的密鑰的含義（meaning）永遠不能發生改變。
