圖靈獎得主Sivio Micali的Algorand區塊鏈協議簡介

最新 02-19

2018年2月，圖靈獎得主、MIT教授Sivio Micali募集400萬美元開發Algorand區塊鏈協議一事受到了國內外媒體的普遍關注。2017年春天，筆者有幸在MIT選修了Micali教授和MIT媒體實驗室數字貨幣計劃負責人Neha Narula合開的《共享公共賬本》（Shared Public Ledger）課程。這門課主要就是講解Algorand。Algorand的目標是建立一個低能耗、高速度、民主化、可拓展性好而且幾乎不會出現分叉的分散式賬本。Algorand沒有引入激勵機制或發行數字加密貨幣。

Algorand代表了區塊鏈底層技術發展的一個重要方向。本文對Algorand做一個簡單介紹，分享給國內讀者。Algorand涉及非常複雜的數學，筆者力圖用最少的數學介紹Algorand最核心的想法（涉及數學的主要是本文第三、四節，略過不讀不會影響對文章大意的理解）。對Algorand感興趣的讀者可以閱讀關於Algorand的工作論文（不是白皮書，最新版工作論文於2017年5月發布，下載地址是https://arxiv.org/abs/1607.01341）。本文不構成對Algorand的商業評論。當然，筆者衷心祝願Micali教授能取得成功。

一、Algorand的發展背景

Algorand是MIT機械工程與計算機科學系Silvio Micali教授與合作者（主要是紐約大學石溪分校陳靜副教授）於2016年提出的一個區塊鏈協議。Micali教授為義大利裔美國人，1982年獲加州大學伯克利分校計算機科學博士，1983年起在MIT任教。他的研究領域包括密碼學、零知識（zero knowledge）、偽隨機數生成、安全協議（secure protocol）和機制設計。Micali教授1993年獲哥德爾獎（由歐洲理論計算機學會EATCS與美國計算機學會基礎理論專業組織ACM SIGACT於1993年共同設立，頒發給理論計算機領域最傑出的學術論文），2004年獲密碼學領域的RSA獎（RSA是三位發明公鑰-私鑰密碼系統的科學家Rivest、Shamir和Adleman的姓氏縮寫），2012年獲圖靈獎（由計算機協會ACM於1966年設立，獎勵給對計算機事業作出重要貢獻的個人，有「計算機界諾貝爾獎」之稱）。

Algorand由algorithm（演算法）和random（隨機）兩個詞合成，顧名思義，就是基於隨機演算法的公共賬本協議（public ledger）。Algorand針對比特幣區塊鏈系統的幾個核心缺陷進行了改進。

第一，比特幣區塊鏈系統的工作量證明共識機制需要消耗大量計算資源和能源。根據Digiconomist網站數據，截至2018年1月底，每產生一個比特幣區塊，需要運行1.18*1022次哈希運算。考慮到哈希函數作為隨機預言（random oracle）的性質，比特幣區塊的產生過程，相當於擲一個有1.18*1022面的骰子，直到擲出某一特定的面為止。比特幣區塊鏈系統一年的耗電量，與秘魯全國一年的耗電量相當，而且還在快速增長中。這些巨量計算和耗電，除了產生比特幣區塊以外，對人類社會幾乎沒有任何價值。

第二，比特幣區塊鏈系統要長期存續，要求50%以上的計算資源掌握在誠實用戶的手中。否則，惡意用戶在力量佔優時可能篡改區塊鏈。但隨著市場演變（中本聰應該沒有預見到這種情況），比特幣區塊鏈系統中的計算資源集中在少數幾個「礦池」中。這就構成了一個潛在的不穩定因素。「礦池」的存在也使比特幣區塊鏈系統偏離了其早期宣稱的民主特徵，形成了「礦工」和普通使用者這樣不同階層的使用者。從比特幣歷史上關於擴容的討論以及多次分叉不難看出，比特幣區塊鏈系統已經形成了中心化程度很高的社區結構。

第三，比特幣區塊鏈系統容易出現分叉。根據中本聰的白皮書[ Nakomoto, Satoshi, 2009, 「Bitcoin: A Peer-to-Peer Electronic Cash System」. ]，當一筆交易被記入一個區塊並接入區塊鏈後，需要再等6個區塊才能比較肯定這筆交易進入比特幣的公共賬本，而非在某一個分叉上。因為比特幣區塊鏈系統平均每10分鐘才能產生一個區塊，一筆交易從被記入區塊到被確認需要1個小時左右時間。

第四，比特幣區塊鏈系統的可拓展性比較差。比如，一個比特幣區塊的大小為1M，大約能容納2000筆左右交易，因為平均每10分鐘產生一個區塊，比特幣最高支持每秒鐘6筆交易；相比而言，Paypal平均每秒鐘能支持193筆交易，Visa平均每秒鐘能支持1667筆交易[http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/]。從這個意義上講，比特幣是人類歷史上投入產出比最低的社會和技術試驗之一。對可拓展性問題，比特幣閃電網路是目前很受關注的一個解決方案。

鑒於比特幣區塊鏈系統的上述缺陷，Algorand的目標是：

1.能耗低，不管系統中有多用戶，大約每1500名用戶中只有1名會被系統挑中執行長達幾秒鐘的計算。

2.民主化，不會出現類似比特幣區塊鏈系統的「礦工」群體。

3.出現分叉的概率低於一兆分之一（即10-18）。假設Algorand中平均每分鐘產生一個區塊（後文會給出有關測試數據），這個概率意味著平均每190萬年出現一次分叉。

4.可拓展性好。

二、Algorand的基本設置

（一）用戶和交易特徵

Algorand是一個公有鏈系統。用戶（或者節點）加入Algorand不需要事先申請，可以隨時加入。Algorand對用戶數量也沒有任何限制。每個用戶持有多個公鑰。每個公鑰均是一個電子簽名機制的一部分，也就是有一個與之對應的私鑰。每個公鑰對應著一定數量的貨幣。每筆交易實際上是一個電子簽名，該電子簽名將一定數量的貨幣從某一個公鑰轉移給另一個公鑰，並用前一個公鑰對應的私鑰進行加密。不難看出，Algorand的這些設計，與比特幣是一樣的。

Algorand要求系統中2/3的貨幣由誠實用戶掌握。誠實用戶的含義是：其行為遵守有關指引（主要指拜占庭共識協議，見下文），並且能完美地發送和接收消息。誠實用戶以外的是惡意用戶，惡意用戶的行為可以任意偏離有關指引。

對惡意用戶，Algorand假設他們由一個「敵對者」（adversary）控制。「敵對者」能發起強大攻擊，包括：

1.「敵對者」可以在任何時候瞬間地腐化任何他選中的用戶，使其成為惡意用戶（哪怕該用戶之前是誠實用戶）。

2.「敵對者」完全控制並且完美協調所有惡意用戶。可以理解為，惡意用戶的行為（包括發送和接收消息）完全由「敵對者」代理。

3.「敵對者」控制所有信息發送，但必須滿足一點：誠實用戶發出的消息能在一定時間內（該時間只與信息的存儲大小有關）抵達95%的誠實用戶。然而，「敵對者」幾乎不可能偽造誠實用戶的電子簽名或者干涉誠實用戶之間的通訊。

（二）區塊鏈結構

在Algorand中，與交易有關的信息均存儲在一系列區塊中。每個區塊主要包括：1.從上一個區塊以來的交易信息；2.一個哈希指針，相當於對所有前序區塊所含信息的一個摘要或濃縮；3.當期「領導者」電子簽名後的「種子」參數（細節見後文）。這樣，這一系列區塊通過這些哈希指針連接在一起，構成了區塊鏈。如果某一區塊的信息被「敵對者」篡改，其與後序區塊中保存的哈希指針就會出現不匹配。這就使得區塊鏈難以被篡改。

Algorand的上述設計與比特幣區塊鏈系統基本相同，但存在一個關鍵差別。目前，Algorand是一個單純的分散式賬本協議，沒有引入激勵機制，沒有發行類似比特幣的數字加密貨幣。Algorand中交易所用的貨幣是外生給定的（可以是任何法定貨幣或數字加密貨幣），交易隻影響貨幣在不同用戶之間的分配。而在比特幣區塊鏈系統中，「礦工」構建了被公共賬本接受的區塊後，就會得到系統給予的一定數量的比特幣作為獎勵。

（三）網路通訊

與比特幣區塊鏈系統一樣，Algorand假設用戶之間的通訊採取「點對點傳言」模式（peer-to-peer gossip）：當某一用戶傳播一條消息後，第一次收到這條消息的用戶隨機並且獨立地選擇他的一些「鄰居」，並將消息傳給「鄰居」們。當沒有用戶是第一次收到這條消息時，這條消息的傳播就終止了。

Algorand對網路通訊的要求是：對任意大於95%的可及性參數（reachability）ρ和消息的存儲大小參數μ，總存在一個時間參數λ（λ只與ρ和μ有關），使得一個誠實用戶發出的存儲大小為μ的消息，在經過λ長時間後，至少被超過ρ的誠實用戶接收。

（四）共識機制

Algorand中，用戶（不是全部用戶，僅指被系統隨機挑中作為「驗證者」的用戶，詳見下文）通過一個拜占庭協議（由Micali教授開發，稱為BA★）對新區塊達成共識。BA★執行起來非常快。大致言之，BA★每次循環有3個子步驟，在每次循環後均有1/3以上的概率能達成共識。一旦「驗證者」對某一個新區塊達成共識，超過一半的「驗證者」再用自己的私鑰對該區塊進行電子簽名（相當於認證），該區塊就開始在Algorand網路中傳播。

BA★的一個重要特徵是：在點對點網路通訊下，BA★的參與者可更換（player-replaceable）。也就是，BA★每次循環的每一個子步驟均可由全新的、獨立隨機選擇的參與者來執行。在這種情況下，BA★仍能正確、有效地達成共識。假設有上百萬的用戶，BA★每次循環的每一個子步驟的參與者可以完全不一樣，而且每一批參與者都無法確定下一批參與者是誰，從而無法串謀。

（五）密碼抽籤（cryptographic sortition）

密碼抽籤是Algorand的關鍵創新，也是其得名的由來，其要點如下。首先，Algorand創建並不斷更新一個獨立參數，稱為「種子」。「種子」參數不僅不可能被「敵對者」預測，也不能被其操縱。

其次，在BA★每次循環中，Algorand基於當前「種子」參數構建並公布一個隨機演算法（也被稱為「可驗證的隨機函數」或verifiable random functions，見下文）。該隨機演算法中的一個關鍵參數是用戶的私鑰，這個私鑰只有用戶本人才知道。

接著，每個用戶使用自己的私鑰運行系統公布的隨機演算法，得到自己的憑證（credential）。憑證值滿足一定條件的用戶就是這一輪的「驗證者」（verifiers）。「驗證者」組裝一個新區塊並連同自己的憑證一起對外發出。其中，在第一個子步驟中憑證值最小（按字典方面排序，見下）的那個「驗證者」的地位比較特殊，稱為「領導者」。

最後，所有「驗證者」基於「領導者」組裝的新區塊運行拜占庭協議BA★。在BA★的每次循環中的每一個子步驟中，被選中的「驗證者」都是不同的。這樣能有效防止驗證權力集中在某些用戶手中，避免「敵對者」通過腐化這些用戶來攻擊區塊鏈。

從上述過程可以看出，第一，「驗證者」在秘密情況下獲知自己被選中，但他們只有公布憑證才能證明自己的「驗證者」資格。儘管「敵對者」可以瞬間腐化身份公開的「驗證者」，但已不能篡改或撤回他們已經對外發出的消息。

第二，所有「驗證者」公布自己的憑證並進行比較後，才能確定誰是「領導者」，也就是「領導者」可以視為由公共選舉產生。

第三，隨機演算法的性質決定了，事先很難判斷誰將被選為「驗證者」。因此，「驗證者」的選擇過程很難被操縱或預測。

第四，儘管「敵對者」有可能事先安插一些交易來影響當前公共賬本，但因為「種子」參數的存在，他仍然不可能通過影響「驗證者」（特別是其中的「領導者」）的選擇來攻擊Algorand。接下來，對密碼抽籤和拜占庭協議BA★做一個相對技術化的介紹。

三、Algorand的密碼抽籤

密碼抽籤按兩條線索執行：一是選出「驗證者」和「領導者」；二是創建並不斷完善「種子」參數。

（一）「驗證者」和「領導者」的選擇

假設在第r輪（可以理解為產生第r個區塊的時間段）開始時，「種子」參數為Qr-1（表現為一個由0和1組成的長度為256的字元串），PKr-k是第r-k輪結束後系統中活躍的用戶/公鑰（活躍的標誌是至少參與過一筆交易）的集合，其中k被稱為回溯參數或安全參數。Qr-1和PKr-k屬於公共知識（common knowledge）。

憑證的定義。對每一個PKr-k中的用戶i，他使用自己的私鑰對「種子」參數Qr-1進行電子簽名後（用函數SIGi來表示）並輸入哈希函數（用函數H來表示），得到自己的憑證H（SIGi(r,1,Qr-1))(函數SIGi有多個輸入參數時，表示將這些參數簡單串聯後再進行電子簽名，下同）。哈希函數的性質決定了：

1.憑證是一個近乎隨機的、由0和1組成的長度為256的字元串，並且不同用戶的憑證幾乎不可能相同；

2.由憑證構建的2進位小數0.H(SIGi(r,1,Qr-1))（也就是將憑證字元串寫到小數點後）在0和1之間均勻分布。

「潛在領導者」的選擇。對0和1之間的一個數p，0.H(SIGi(r,1,Qr-1))≤p發生的概率為p，稱所有滿足此條件的用戶為「潛在領導者」（也是這一步的「驗證者」）。p使得以1-10-18的概率，在所有「潛在領導者」中，至少有一個是誠實的。

「領導者」的選擇。在所有「潛在領導者」中，存在一個用戶lr，其憑證按字典排序最小。也就是，對所有0.H(SIGi(r,1,Qr-1))≤p的用戶i，均有H(SIGlr(r,1,Qr-1))≤H(SIGi(r,1,Qr-1))。用戶lr就是第r輪的「領導者」。

「驗證者」的選擇。第r輪第s步（s>1）的「驗證者」的產生程序與上文類似。在這一步中，每一個PKr-k中的用戶i使用自己的私鑰對「種子」參數Qr-1進行電子簽名後並輸入哈希函數，得到自己的憑證H(SIGi(r,1,Qr-1))。對0和1之間的一個數p，滿足0.H(SIGi(r,1,Qr-1))≤p的用戶就構成這一步的「驗證者」。

（二）「種子」參數的更新

用Br表示第輪結束後，拜占庭協議BA★輸出的區塊。如果Algorand在第輪受到了「敵對者」攻擊，Br可能是空的，也就是不含有任何真實交易記錄（用符號來表示）。比如，「敵對者」可能腐化了這一輪的「領導者」，使其將兩個不同的候選區塊發給誠實的「驗證者」。考慮到這個情況，「種子」參數的更新過程是：

Qr=H(SIGlr(Qr-1，r)),如果Br不是空區塊

Qr=H（Qr-1，r）,如果Br是空區塊

哈希函數的性質決定了，Qr和Qr-1之間的關係近乎隨機的。回溯參數或安全參數k則保證了，「敵對者」在第r-k-1輪幾乎不可能預測到Qr-1；否則，他將在第r-k輪引入惡意用戶（也就是進入PKr-k），從而能影響第r輪「領導者」和「驗證者」的選擇。

四、Algorand的拜占庭協議BA★

拜占庭協議BA★相當於一個兩階段的投票機制。第一階段，「驗證者」對其收到的候選區塊（為控制通訊成本，實際上用的是候選區塊的哈希摘要）運行分級共識協議（graded consensus）,選出「驗證者」共識最多的候選區塊。第二階段，「驗證者」對第一階段選出的候選區塊，運行二元拜占庭協議（binary Byzantine Agreement），即要麼接受它，要麼接受空區塊。需要強調的，在每一階段中的每一個子步驟，Algorand可能使用完全不同的「驗證者」。

以下為敘述方便，假設：

1.系統處在第r輪；

2.每一個子步驟都選出n名「驗證者」，其中惡意「驗證者」不超過t，並且n≥3t+1（也就是誠實「驗證者」佔比在2/3以上）。另外，引入計數函數#si(v)表示在第s步，「驗證者」i收到的消息v的次數（來自同一發送人的只能算1次）。

（一）分級共識協議

步驟1.1：運行密碼抽籤程序，選出「領導者」lr和這一步的「驗證者」。用vi表示「驗證者」i收到的並且他認識是來自「領導者」lr的候選區塊。

有3個原因使得vi不一定等於「領導者」lr構建的候選區塊。

第一，「驗證者」i辨認「領導者」的方法是從他收到的所有「驗證者」憑證中找出按字典排序最小者。但因為網路通訊原因，「領導者」lr發出的信息可能沒有到達「驗證者」i處。

第二，「領導者」lr可能被「敵對者」腐化，對不同「驗證者」發出不同的候選區塊。

第三，「驗證者」i本身可能是惡意的。

步驟1.2：「驗證者」i將vi發給其他用戶（這對其他「驗證者」都適用，下同）。

步驟1.3：當且僅當「驗證者」i在步驟1.2中收到的某一個的x次數超過了2t+1次（即#2i(x)≥2t+1），他將x發給其他用戶。

輸出：「驗證者」i按以下規則輸出(vi,gi)：

如果存在x使得#3i(x)≥2t+1，則vi=x,gi=2；

如果x存在使得#3i(x)≥t+1，則vi=x,gi=1；

否則vi=?，gi=1，其中?代表空區塊。

Micali教授證明了，分級共識協議的輸出{(vi,gi):i=1,2,……n}滿足下列性質：

對任意誠實「驗證者」i和j，丨gi-gj丨≤1；

對任意誠實「驗證者」i和j，如果gi,gj>0，那麼必有vi=vj；

如果存在v使得有v1=v2=……=vn=v，那麼對所有的誠實「驗證者」i，均有vi=v,gi=2。

因此，分級共識協議的輸出{(vi,gi):i=1,2,……n}存在兩種可能的情形。

情形一：如果存在誠實「驗證者」i，使得,gi=2，那麼對任意其他「驗證者」j，必有gj≥1,vj=vi。此時所有誠實「驗證者」輸出的候選區塊是一樣的。當然，如果一開始的「驗證者」收到的候選區塊都是v，那麼最後一批「驗證者」輸出的也將都是v。

情形二：對所有的誠實「驗證者」i，gi≤1，並且他們輸出的候選區塊不一定相同。

（二）二元拜占庭協議

首先，基於分級共識協議的輸出{(vi,gi):i=1,2,……n}對每個誠實「驗證者」賦值：如果gi=2，那麼bi=0；否則bi=1，。這些bi就是二元拜占庭協議的輸入。對應著前面的討論，此處也存在兩種情形。

情形一：存在誠實「驗證者」i，使得bi=0。

情形二：對所有誠實「驗證者」i，均有bi=1。

二元拜占庭協議可能經過多次循環，用計數器ri表示「驗證者」i經歷的循環的次數。開始時，ri賦值為0。

步驟2.1：「驗證者」i發出bi。

如果#1i(0)≥2t+1，那麼「驗證者」i設定bi=0，輸出outi=0，並停止執行協議（也可以認為他以後將一直發出bi=0）；

如果#1i(1)≥2t+1，那麼「驗證者」i設定bi=1；

否則，「驗證者」i設定bi=0。

步驟2.2：「驗證者」i發出bi。

如果#2i(1)≥2t+1，那麼「驗證者」i設定bi=1，輸出outi=1，並停止執行協議（也可以認為他以後將一直發出bi=1）；

如果#2i(0)≥2t+1，那麼「驗證者」i設定bi=0；

否則，「驗證者」i設定bi=1。

步驟2.3：「驗證者」i發出bi和SIGi(Qr-1,ri)。

如果#3i(0)≥2t+1，那麼「驗證者」i設定bi=0；

如果#3i(1)≥2t+1，那麼「驗證者」i設定bi=1；

否則，用Si表示所有給「驗證者」i發送消息的其他「驗證者」集合，定義c=lsb()（lsb表示一個數的二進位表述中的最右邊位置上的數字），「驗證者」i設定bi=c，並且ri的計數往上調1位。鑒於哈希函數的性質，這實際上是將bi隨機地、不被操縱地賦值為0或1。回到步驟2.1

Micali教授證明了，在二元拜占庭協議中，每個誠實「驗證者」i能以概率1停止並輸出outi∈，並且：

（共識性）存在outi∈，使得對任意誠實「驗證者」i，均有outi=out；

（一致性）如果存在b∈，使得對任意誠實「驗證者」i，均有bi=b，那麼out=b。

（三）拜占庭協議BA★的輸出

BA★的輸出：對誠實「驗證者」i，如果二元拜占庭協議的輸出outi=0，則輸出vi（即分級共識協議的輸出）；否則，輸出空區塊?。

Micali教授證明了，BA★滿足拜占庭協議的要求：

1. （共識性）最後一批誠實「驗證者」輸出的區塊是相同的；

2. （一致性）如果一開始的「驗證者」收到的候選區塊都是v，那麼BA★的最終輸出也是v。

五、Algorand的測試情況

MIT計算機科學和人工智慧實驗室對Algorand進行了模擬測試[ Gilad, Yossi, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich, 2017, 「Algorand: Scaling Byzantine Agreements for Cryptocurrencies」. 本節引用的圖均來自這篇文章。]。他們的測試在亞馬遜雲上進行，使用了1000台EC2虛擬機，發現：

第一，Algorand能在1分鐘內確認交易，而且確認交易的時間隨著用戶數量的增加，變化不大。