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）控制。“敵對者”能發起強大攻擊，包括：
- “敵對者”可以在任何時候瞬間地腐化任何他選中的使用者，使其成為惡意使用者（哪怕該使用者之前是誠實使用者）。
- “敵對者”完全控制并且完美協調所有惡意使用者。可以了解為，惡意使用者的行為（包括發送和接收消息）完全由“敵對者”代理。
- “敵對者”控制所有資訊發送，但必須滿足一點：誠實使用者發出的消息能在一定時間内（該時間隻與資訊的存儲大小有關）抵達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有多個輸入參數時，表示将這些參數簡單串聯後再進行電子簽名，下同）。哈希函數的性質決定了：
- 憑證是一個近乎随機的、由0和1組成的長度為256的字元串，并且不同使用者的憑證幾乎不可能相同；
- 由憑證建構的2進制小數0.H(SIGi(r,1,Qr-1))（也就是将憑證字元串寫到小數點後）在0和1之間均勻分布。
- “潛在上司者”的選擇。對0和1之間的一個數，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之間的一個數pr，滿足0.H(SIGi(r,1,Qr-1))≤pr的使用者就構成這一步的“驗證者”。
（二）“種子”參數的更新
用Br表示第輪結束後，拜占庭協定BA★輸出的區塊。如果Algorand在第輪受到了“敵對者”攻擊，Br可能是空的，也就是不含有任何真實交易記錄（用符号來表示）。比如，“敵對者”可能腐化了這一輪的“上司者”，使其将兩個不同的候選區塊發給誠實的“驗證者”。考慮到這個情況，“種子”參數的更新過程是：
-
Qr=H(SIGlr(Qr-1，r)),如果Br不是空區塊
=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個原因使得vir不一定等于“上司者”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,L……n}滿足下列性質：
對任意誠實“驗證者”i和j，|gi-gj|≤1；
對任意誠實“驗證者”i和j，如果gi,gj>0，那麼必有vi=vj；
如果存在v使得有v'1=v'2=K……=v'n=v，那麼對所有的誠實“驗證者”i，均有vi=v,gi=2。
是以，分級共識協定的輸出{(vi,gi):i=1,2,L……n}存在兩種可能的情形。
- 情形一：如果存在誠實“驗證者”i，使得,gi=2，那麼對任意其他“驗證者”j，必有gj≥1,vj=vi。此時所有誠實“驗證者”輸出的候選區塊是一樣的。當然，如果一開始的“驗證者”收到的候選區塊都是v，那麼最後一批“驗證者”輸出的也将都是v。
- 情形二：對所有的誠實“驗證者”i，gi≤1，并且他們輸出的候選區塊不一定相同。
（二）二進制拜占庭協定
首先，基于分級共識協定的輸出{(vi,gi):i=1,2,K……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,rj)。
如果#3i(0)≥2t+1，那麼“驗證者”i設定bi=0；
如果#3i(1)≥2t+1，那麼“驗證者”i設定bi=1；
否則，用Si表示所有給“驗證者”i發送消息的其他“驗證者”集合，定義
（lsb表示一個數的二進制表述中的最右邊位置上的數字），“驗證者”i設定bi=c，并且ri的計數往上調1位。鑒于哈希函數的性質，這實際上是将bi随機地、不被操縱地指派為0或1。
回到步驟2.1，Micali教授證明了，在二進制拜占庭協定中，每個誠實“驗證者”i能以機率1停止并輸出outi∈{0,1}，并且：
- （共識性）存在outi∈{0,1}，使得對任意誠實“驗證者”i，均有outi=out；
- （一緻性）如果存在b∈{0,1}，使得對任意誠實“驗證者”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分鐘内确認交易，而且确認交易的時間随着使用者數量的增加，變化不大。
第二，将使用者數固定在5萬，測試不同區塊大小對通量（throughput，可以用産生一個區塊的平均耗時來衡量）的影響。可以看出，區塊越大，建構區塊的耗時越長，但對拜占庭協定BA★的運作時間影響不大。
參考資料：
1.Nakomoto, Satoshi, 2009, “Bitcoin: A Peer-to-Peer Electronic Cash System”
2.http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/
3.http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/
https://www.leiphone.com/news/201802/D835Yu95sY7ihrAp.html