頭條楓林網作者簡介：鄒傳偉，經濟學博士，哈佛梅森學者，南湖金服合夥人、南湖互聯網金融學院常務副院長。 曾獲首屆（2014年度）孫冶方金融創新獎。
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是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月底，每產生一個比特幣區塊，需要運行 
第二，比特幣區塊鏈系統要長期存續，要求50%以上的計算資源掌握在誠實用戶的手中。 否則，惡意用戶在力量佔優時可能篡改區塊鏈。 但隨著市場演變（中本聰應該沒有預見到這種情況），比特幣區塊鏈系統中的計算資源集中在少數幾個“礦池”中。 這就構成了一個潛在的不穩定因素。 “礦池”的存在也使比特幣區塊鏈系統偏離了其早期宣稱的民主特徵，形成了“礦工”和普通使用者這樣不同階層的使用者。 從比特幣歷史上關於擴容的討論以及多次分叉不難看出，比特幣區塊鏈系統已經形成了中心化程度很高的社區結構。
第三，比特幣區塊鏈系統容易出現分叉。 根據中本聰的白皮書[ Nakomoto, Satoshi, 2009, “Bitcoin: A Peer-to-Peer Electronic Cash System”. ]，當一筆交易被記入一個區塊並接入區塊鏈後，要等該筆交易所在區塊後面再接上5個區塊，才能比較肯定這筆交易進入比特幣的公共賬本 ，而非在某一個分叉上。 因為比特幣區塊鏈系統平均每10分鐘才能產生一個區塊，一筆交易從被記入區塊到被確認需要1個小時左右時間。
第四，比特幣區塊鏈系統的可拓展性比較差。 比如，一個比特幣區塊的大小為1M，大約能容納2000筆左右交易，因為平均每10分鐘產生一個區塊，比特幣平均每秒鐘能支持3-4筆交易；相比而言，Paypal 平均每秒鐘能支持193筆交易，Visa平均每秒鐘能支持1667筆交易 [ http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/ ] 。 從這個意義上講，比特幣是人類歷史上投入產出比最低的社會和技術試驗之一。 對可拓展性問題，比特幣閃電網絡是目前很受關注的一個解決方案。
鑑於比特幣區塊鏈系統的上述缺陷，Algorand的目標是：1.能耗低，不管系統中有多用戶，大約每1500名用戶中只有1名會被系統挑中執行長達幾秒鐘的 計算。 2.民主化，不會出現類似比特幣區塊鏈系統的“礦工”群體。 3.出現分叉的概率低於一兆分之一（即 
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★每次循環的每一個子步驟的參與者可以完全不一樣，而且每一批參與者都無法確定下一批參與者是誰，從而無法串謀。
密碼抽籤是Algorand的關鍵創新，也是其得名的由來，其要點如下。 首先，Algorand創建並不斷更新一個獨立參數，稱為“種子”。 “種子”參數不僅不可能被“敵對者”預測，也不能被其操縱。
其次，在BA★每次循環中，Algorand基於當前 “種子”參數構建並公佈一個隨機算法（也被稱為“可驗證的隨機函數”或verifiable random functions，見下文）。 該隨機算法中的一個關鍵參數是用戶的私鑰，這個私鑰只有用戶本人才知道。
接著，每個用戶使用自己的私鑰運行系統公佈的隨機算法，得到自己的憑證（credential）。 憑證值滿足一定條件的用戶就是這一輪的“驗證者”（verifiers）。 “驗證者”組裝一個新區塊並連同自己的憑證一起對外發出。 其中，在第一個子步驟中憑證值最小（按字典方面排序，見下）的那個“驗證者”的地位比較特殊，稱為“領導者”。
最後，所有“驗證者”基於“領導者”組裝的新區塊運行拜贊庭協議BA★。 在BA★的每次循環中的每一個子步驟中，被選中的“驗證者”都是不同的。 這樣能有效防止驗證權力集中在某些用戶手中，避免“敵對者”通過腐化這些用戶來攻擊區塊鏈。
從上述過程可以看出，第一，“驗證者”在秘密情況下獲知自己被選中，但他們只有公佈憑證才能證明自己的“驗證者”資格。 儘管“敵對者”可以瞬間腐化身份公開的“驗證者”，但已不能篡改或撤回他們已經對外發出的消息。 第二，所有“驗證者”公佈自己的憑證並進行比較後，才能確定誰是“領導者”，也就是“領導者”可以視為由公共選舉產生。 第三，隨機算法的性質決定了，事先很難判斷誰將被選為“驗證者”。 因此，“驗證者”的選擇過程很難被操縱或預測。 第四，儘管“敵對者”有可能事先安插一些交易來影響當前公共賬本，但因為“種子”參數的存在，他仍然不可能通過影響“驗證者”（特別是其中的“領導者”）的 選擇來攻擊Algorand。 接下來，對密碼抽籤和拜贊庭協議BA★做一個相對技術化的介紹。
密碼抽籤按兩條線索執行：一是選出“驗證者”和“領導者”；二是創建並不斷完善“種子”參數。
“驗證者”和“領導者”的選擇
假設在第 
哈希函數的性質決定了：1.憑證是一個近乎隨機的、由0和1組成的長度為256的字符串，並且不同用戶的憑證幾乎不可能相同；2.由憑證構建的2進制小數 
用戶 
用 
哈希函數的性質決定了， 
拜贊庭協議BA★相當於一個兩階段的投票機制。 第一階段，“驗證者”對其收到的候選區塊（為控制通訊成本，實際上用的是候選區塊的哈希摘要）運行分級共識協議（graded consensus）,選出“驗證者” 共識最多的候選區塊。 第二階段，“驗證者”對第一階段選出的候選區塊，運行二元拜贊庭協議（binary Byzantine Agreement），即要么接受它，要么接受空區塊。 需要強調的，在每一階段中的每一個子步驟，Algorand可能使用完全不同的“驗證者”。
以下為敘述方便，假設：1.系統處在第 
步驟1.1 ： 運行密碼抽籤程序，選出“領導者” 
有3個原因使得
步驟1.2： “驗證者”
步驟1.3： 當且僅當“驗證者” 
輸出 ：“驗證者” 
如果存在 
如果存在 
否則， 
Micali教授證明了，分級共識協議的輸出 
對任意誠實“驗證者” 
對任意誠實“驗證者” 
如果存在 
因此，分級共識協議的輸出 
首先，基於分級共識協議的輸出 
二元拜贊庭協議可能經過多次循環，用計數器 
步驟2.1： “驗證者” 
如果 
如果 
否則，“驗證者”
步驟2.2 ： “驗證者” 
如果 
如果 
否則，“驗證者”
步驟2.3 ： “驗證者” 
如果 
如果 
否則，用 
（共識性）存在 
（一致性）如果存在 
BA★的輸出：對誠實“驗證者” 
MIT計算機科學和人工智能實驗室對Algorand進行了模擬測試 [ Gilad, Yossi, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich, 2017, “Algorand: Scaling Byzantine Agreements for Cryptocurrencies”. 本節引用的圖均來自這篇文章。 ] 。 他們的測試在亞馬遜雲上進行，使用了1000台EC2虛擬機，發現：
第一，Algorand能在1分鐘內確認交易，而且確認交易的時間隨著用戶數量的增加，變化不大。
第二，將用戶數固定在5萬，測試不同區塊大小對通量（throughput，可以用產生一個區塊的平均耗時來衡量）的影響。 可以看出，區塊越大，構建區塊的耗時越長，但對拜贊庭協議BA★的運行時間影響不大。
推薦
—
知識星球
從技術、商品、貨幣等角度聊區塊鏈與數字貨幣。 歡迎各路英豪加入待字閨中區塊鏈知識星球。 目前已經近200人加入，後面一些關於數字貨幣和區塊鏈隨想就在這裡與大家展開討論。 大家不要錯過。
往期推薦：