一、Algorand的發(fā)展背景

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

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

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

第二，比特幣區(qū)塊鏈系統(tǒng)要長期存續(xù)，要求50%以上的計算資源掌握在誠實用戶的手中。否則，惡意用戶在力量占優(yōu)時可能篡改區(qū)塊鏈。但隨著市場演變（中本聰應(yīng)該沒有預(yù)見到這種情況），比特幣區(qū)塊鏈系統(tǒng)中的計算資源集中在少數(shù)幾個“礦池”中。這就構(gòu)成了一個潛在的不穩(wěn)定因素。“礦池”的存在也使比特幣區(qū)塊鏈系統(tǒng)偏離了其早期宣稱的民主特征，形成了“礦工”和普通使用者這樣不同階層的使用者。從比特幣歷史上關(guān)于擴容的討論以及多次分叉不難看出，比特幣區(qū)塊鏈系統(tǒng)已經(jīng)形成了中心化程度很高的社區(qū)結(jié)構(gòu)。

第三，比特幣區(qū)塊鏈系統(tǒng)容易出現(xiàn)分叉。根據(jù)中本聰?shù)陌灼跱akomoto， Satoshi， 2009， “Bitcoin： A Peer-to-Peer Electronic Cash System”。］，當(dāng)一筆交易被記入一個區(qū)塊并接入?yún)^(qū)塊鏈后，要等該筆交易所在區(qū)塊后面再接上5個區(qū)塊，才能比較肯定這筆交易進入比特幣的公共賬本，而非在某一個分叉上。因為比特幣區(qū)塊鏈系統(tǒng)平均每10分鐘才能產(chǎn)生一個區(qū)塊，一筆交易從被記入?yún)^(qū)塊到被確認需要1個小時左右時間。

第四，比特幣區(qū)塊鏈系統(tǒng)的可拓展性比較差。比如，一個比特幣區(qū)塊的大小為1M，大約能容納2000筆左右交易，因為平均每10分鐘產(chǎn)生一個區(qū)塊，比特幣平均每秒鐘能支持3-4筆交易；相比而言，Paypal平均每秒鐘能支持193筆交易，Visa平均每秒鐘能支持1667筆交易。從這個意義上講，比特幣是人類歷史上投入產(chǎn)出比最低的社會和技術(shù)試驗之一。對可拓展性問題，比特幣閃電網(wǎng)絡(luò)是目前很受關(guān)注的一個解決方案。

鑒于比特幣區(qū)塊鏈系統(tǒng)的上述缺陷，Algorand的目標(biāo)是：1.能耗低，不管系統(tǒng)中有多用戶，大約每1500名用戶中只有1名會被系統(tǒng)挑中執(zhí)行長達幾秒鐘的計算。2.民主化，不會出現(xiàn)類似比特幣區(qū)塊鏈系統(tǒng)的“礦工”群體。3.出現(xiàn)分叉的概率低于一兆分之一（即）。假設(shè)Algorand中平均每分鐘產(chǎn)生一個區(qū)塊（后文會給出有關(guān)測試數(shù)據(jù)），這個概率意味著平均每190萬年出現(xiàn)一次分叉。4.可拓展性好。

二、Algorand的基本設(shè)置

用戶和交易特征

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

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

對惡意用戶，Algorand假設(shè)他們由一個“敵對者”（adversary）控制。“敵對者”能發(fā)起強大攻擊，包括：1.“敵對者”可以在任何時候瞬間地腐化任何他選中的用戶，使其成為惡意用戶（哪怕該用戶之前是誠實用戶）。2.“敵對者”完全控制并且完美協(xié)調(diào)所有惡意用戶。可以理解為，惡意用戶的行為（包括發(fā)送和接收消息）完全由“敵對者”代理。3.“敵對者”控制所有信息發(fā)送，但必須滿足一點：誠實用戶發(fā)出的消息能在一定時間內(nèi)（該時間只與信息的存儲大小有關(guān)）抵達95%的誠實用戶。然而，“敵對者”幾乎不可能偽造誠實用戶的電子簽名或者干涉誠實用戶之間的通訊。

區(qū)塊鏈結(jié)構(gòu)

在Algorand中，與交易有關(guān)的信息均存儲在一系列區(qū)塊中。每個區(qū)塊主要包括：1.從上一個區(qū)塊以來的交易信息；2.一個哈希指針，相當(dāng)于對所有前序區(qū)塊所含信息的一個摘要或濃縮；3.當(dāng)期“領(lǐng)導(dǎo)者”電子簽名后的“種子”參數(shù)（細節(jié)見后文）。這樣，這一系列區(qū)塊通過這些哈希指針連接在一起，構(gòu)成了區(qū)塊鏈。如果某一區(qū)塊的信息被“敵對者”篡改，其與后序區(qū)塊中保存的哈希指針就會出現(xiàn)不匹配。這就使得區(qū)塊鏈難以被篡改。

Algorand的上述設(shè)計與比特幣區(qū)塊鏈系統(tǒng)基本相同，但存在一個關(guān)鍵差別。目前，Algorand是一個單純的分布式賬本協(xié)議，沒有引入激勵機制，沒有發(fā)行類似比特幣的數(shù)字加密貨幣。Algorand中交易所用的貨幣是外生給定的（可以是任何法定貨幣或數(shù)字加密貨幣），交易只影響貨幣在不同用戶之間的分配。而在比特幣區(qū)塊鏈系統(tǒng)中，“礦工”構(gòu)建了被公共賬本接受的區(qū)塊后，就會得到系統(tǒng)給予的一定數(shù)量的比特幣作為獎勵。

網(wǎng)絡(luò)通訊

與比特幣區(qū)塊鏈系統(tǒng)一樣，Algorand假設(shè)用戶之間的通訊采取“點對點傳言”模式（peer-to-peer gossip）：當(dāng)某一用戶傳播一條消息后，第一次收到這條消息的用戶隨機并且獨立地選擇他的一些“鄰居”，并將消息傳給“鄰居”們。當(dāng)沒有用戶是第一次收到這條消息時，這條消息的傳播就終止了。

Algorand對網(wǎng)絡(luò)通訊的要求是：對任意大于95%的可及性參數(shù)（reachability）ρ和消息的存儲大小參數(shù)μ，總存在一個時間參數(shù)λ（λ只與ρ和μ有關(guān)），使得一個誠實用戶發(fā)出的存儲大小為μ的消息，在經(jīng)過λ長時間后，至少被超過ρ的誠實用戶接收。

共識機制

Algorand中，用戶（不是全部用戶，僅指被系統(tǒng)隨機挑中作為“驗證者”的用戶，詳見下文）通過一個拜贊庭協(xié)議（由Micali教授開發(fā)，稱為BA★）對新區(qū)塊達成共識。BA★執(zhí)行起來非常快。大致言之，BA★每次循環(huán)有3個子步驟，在每次循環(huán)后均有1/3以上的概率能達成共識。一旦“驗證者”對某一個新區(qū)塊達成共識，超過一半的“驗證者”再用自己的私鑰對該區(qū)塊進行電子簽名（相當(dāng)于認證），該區(qū)塊就開始在Algorand網(wǎng)絡(luò)中傳播。

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

密碼抽簽（cryptographic sortition）

密碼抽簽是Algorand的關(guān)鍵創(chuàng)新，也是其得名的由來，其要點如下。首先，Algorand創(chuàng)建并不斷更新一個獨立參數(shù)，稱為“種子”。“種子”參數(shù)不僅不可能被“敵對者”預(yù)測，也不能被其操縱。

其次，在BA★每次循環(huán)中，Algorand基于當(dāng)前 “種子”參數(shù)構(gòu)建并公布一個隨機算法（也被稱為“可驗證的隨機函數(shù)”或verifiable random functions，見下文）。該隨機算法中的一個關(guān)鍵參數(shù)是用戶的私鑰，這個私鑰只有用戶本人才知道。

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

最后，所有“驗證者”基于“領(lǐng)導(dǎo)者”組裝的新區(qū)塊運行拜贊庭協(xié)議BA★。在BA★的每次循環(huán)中的每一個子步驟中，被選中的“驗證者”都是不同的。這樣能有效防止驗證權(quán)力集中在某些用戶手中，避免“敵對者”通過腐化這些用戶來攻擊區(qū)塊鏈。

從上述過程可以看出，第一，“驗證者”在秘密情況下獲知自己被選中，但他們只有公布憑證才能證明自己的“驗證者”資格。盡管“敵對者”可以瞬間腐化身份公開的“驗證者”，但已不能篡改或撤回他們已經(jīng)對外發(fā)出的消息。第二，所有“驗證者”公布自己的憑證并進行比較后，才能確定誰是“領(lǐng)導(dǎo)者”，也就是“領(lǐng)導(dǎo)者”可以視為由公共選舉產(chǎn)生。第三，隨機算法的性質(zhì)決定了，事先很難判斷誰將被選為“驗證者”。因此，“驗證者”的選擇過程很難被操縱或預(yù)測。第四，盡管“敵對者”有可能事先安插一些交易來影響當(dāng)前公共賬本，但因為“種子”參數(shù)的存在，他仍然不可能通過影響“驗證者”（特別是其中的“領(lǐng)導(dǎo)者”）的選擇來攻擊Algorand。接下來，對密碼抽簽和拜贊庭協(xié)議BA★做一個相對技術(shù)化的介紹。

三、Algorand的密碼抽簽

密碼抽簽按兩條線索執(zhí)行：一是選出“驗證者”和“領(lǐng)導(dǎo)者”；二是創(chuàng)建并不斷完善“種子”參數(shù)。

“驗證者”和“領(lǐng)導(dǎo)者”的選擇

假設(shè)在第輪（可以理解為產(chǎn)生第個區(qū)塊的時間段）開始時，“種子”參數(shù)為（表現(xiàn)為一個由0和1組成的長度為256的字符串），是第輪結(jié)束后系統(tǒng)中活躍的用戶/公鑰（活躍的標(biāo)志是至少參與過一筆交易）的集合，其中被稱為回溯參數(shù)或安全參數(shù)。和屬于公共知識（common knowledge）。憑證的定義。對每一個中的用戶，他使用自己的私鑰對“種子”參數(shù)進行電子簽名后（用函數(shù)來表示）并輸入哈希函數(shù)（用函數(shù)來表示），得到自己的憑證（函數(shù)有多個輸入?yún)?shù)時，表示將這些參數(shù)簡單串聯(lián)后再進行電子簽名，下同）。

哈希函數(shù)的性質(zhì)決定了：1.憑證是一個近乎隨機的、由0和1組成的長度為256的字符串，并且不同用戶的憑證幾乎不可能相同；2.由憑證構(gòu)建的2進制小數(shù)（也就是將憑證字符串寫到小數(shù)點后）在0和1之間均勻分布。“潛在領(lǐng)導(dǎo)者”的選擇。對0和1之間的一個數(shù)，發(fā)生的概率為，稱所有滿足此條件的用戶為“潛在領(lǐng)導(dǎo)者”（也是這一步的“驗證者”）。使得以的概率，在所有“潛在領(lǐng)導(dǎo)者”中，至少有一個是誠實的。“領(lǐng)導(dǎo)者”的選擇。在所有“潛在領(lǐng)導(dǎo)者”中，存在一個用戶，其憑證按字典排序最小。也就是，對所有的用戶，均有。

用戶就是第輪的“領(lǐng)導(dǎo)者”。“驗證者”的選擇。第輪第步（）的“驗證者”的產(chǎn)生程序與上文類似。在這一步中，每一個中的用戶使用自己的私鑰對“種子”參數(shù)進行電子簽名后并輸入哈希函數(shù)，得到自己的憑證。對0和1之間的一個數(shù)，滿足的用戶就構(gòu)成這一步的“驗證者”。

“種子”參數(shù)的更新

用表示第輪結(jié)束后，拜贊庭協(xié)議BA★輸出的區(qū)塊。如果Algorand在第輪受到了“敵對者”攻擊，可能是空的，也就是不含有任何真實交易記錄（用符號來表示）。比如，“敵對者”可能腐化了這一輪的“領(lǐng)導(dǎo)者”，使其將兩個不同的候選區(qū)塊發(fā)給誠實的“驗證者”。考慮到這個情況，“種子”參數(shù)的更新過程是：

哈希函數(shù)的性質(zhì)決定了，和之間的關(guān)系近乎隨機的。回溯參數(shù)或安全參數(shù)則保證了，“敵對者”在第輪幾乎不可能預(yù)測到；否則，他將在第輪引入惡意用戶（也就是進入），從而能影響第輪“領(lǐng)導(dǎo)者”和“驗證者”的選擇。

四、Algorand的拜贊庭協(xié)議BA★

拜贊庭協(xié)議BA★相當(dāng)于一個兩階段的投票機制。第一階段，“驗證者”對其收到的候選區(qū)塊（為控制通訊成本，實際上用的是候選區(qū)塊的哈希摘要）運行分級共識協(xié)議（graded consensus），選出“驗證者”共識最多的候選區(qū)塊。第二階段，“驗證者”對第一階段選出的候選區(qū)塊，運行二元拜贊庭協(xié)議（binary Byzantine Agreement），即要么接受它，要么接受空區(qū)塊。需要強調(diào)的，在每一階段中的每一個子步驟，Algorand可能使用完全不同的“驗證者”。

以下為敘述方便，假設(shè)：1.系統(tǒng)處在第輪；2.每一個子步驟都選出名“驗證者”，其中惡意“驗證者”不超過，并且（也就是誠實“驗證者”占比在2/3以上）。另外，引入計數(shù)函數(shù)表示在第步，“驗證者”收到的消息的次數(shù)（來自同一發(fā)送人的只能算1次）。

分級共識協(xié)議

步驟1.1：運行密碼抽簽程序，選出“領(lǐng)導(dǎo)者”和這一步的“驗證者”。用表示“驗證者”收到的并且他認識是來自“領(lǐng)導(dǎo)者”的候選區(qū)塊。

有3個原因使得不一定等于“領(lǐng)導(dǎo)者”構(gòu)建的候選區(qū)塊。第一，“驗證者”辨認“領(lǐng)導(dǎo)者”的方法是從他收到的所有“驗證者”憑證中找出按字典排序最小者。但因為網(wǎng)絡(luò)通訊原因，“領(lǐng)導(dǎo)者”發(fā)出的信息可能沒有到達“驗證者”處。第二，“領(lǐng)導(dǎo)者”可能被“敵對者”腐化，對不同“驗證者”發(fā)出不同的候選區(qū)塊。第三，“驗證者”本身可能是惡意的。

步驟1.2：“驗證者”將發(fā)給其他用戶（這對其他“驗證者”都適用，下同）。

步驟1.3：當(dāng)且僅當(dāng)“驗證者”在步驟1.2中收到的某一個的次數(shù)超過了次（即），他將發(fā)給其他用戶。

輸出：“驗證者”按以下規(guī)則輸出：

如果存在使得，則；

如果存在使得，則；

否則，，其中代表空區(qū)塊。

Micali教授證明了，分級共識協(xié)議的輸出滿足下列性質(zhì)：

對任意誠實“驗證者”和，；

對任意誠實“驗證者”和，如果，那么必有；

如果存在使得，那么對所有的誠實“驗證者”，均有。

因此，分級共識協(xié)議的輸出存在兩種可能的情形。情形一：如果存在誠實“驗證者”，使得，那么對任意其他“驗證者”，必有。此時所有誠實“驗證者”輸出的候選區(qū)塊是一樣的。當(dāng)然，如果一開始的“驗證者”收到的候選區(qū)塊都是，那么最后一批“驗證者”輸出的也將都是。情形二：對所有的誠實“驗證者”，，并且他們輸出的候選區(qū)塊不一定相同。

二元拜贊庭協(xié)議

首先，基于分級共識協(xié)議的輸出對每個誠實“驗證者”賦值：如果，那么；否則，。這些就是二元拜贊庭協(xié)議的輸入。對應(yīng)著前面的討論，此處也存在兩種情形。情形一：存在誠實“驗證者”，使得。情形二：對所有誠實“驗證者”，均有。

二元拜贊庭協(xié)議可能經(jīng)過多次循環(huán)，用計數(shù)器表示“驗證者”經(jīng)歷的循環(huán)的次數(shù)。開始時，賦值為0。

步驟2.1：“驗證者”發(fā)出。

如果，那么“驗證者”設(shè)定，輸出，并停止執(zhí)行協(xié)議（也可以認為他以后將一直發(fā)出）；

如果，那么“驗證者”設(shè)定；

否則，“驗證者”設(shè)定。

步驟2.2：“驗證者”發(fā)出。

如果，那么“驗證者”設(shè)定，輸出，并停止執(zhí)行協(xié)議（也可以認為他以后將一直發(fā)出）；

如果，那么“驗證者”設(shè)定；

否則，“驗證者”設(shè)定。

步驟2.3：“驗證者”發(fā)出和。

如果，那么“驗證者”設(shè)定；

如果，那么“驗證者”設(shè)定；

否則，用表示所有給“驗證者”發(fā)送消息的其他“驗證者”集合，定義（表示一個數(shù)的二進制表述中的最右邊位置上的數(shù)字），“驗證者”設(shè)定，并且的計數(shù)往上調(diào)1位。鑒于哈希函數(shù)的性質(zhì)，這實際上是將隨機地、不被操縱地賦值為0或1。回到步驟2.1Micali教授證明了，在二元拜贊庭協(xié)議中，每個誠實“驗證者”能以概率1停止并輸出，并且：

（共識性）存在，使得對任意誠實“驗證者”，均有；

（一致性）如果存在，使得對任意誠實“驗證者”，均有，那么。

拜贊庭協(xié)議BA★的輸出

BA★的輸出：對誠實“驗證者”，如果二元拜贊庭協(xié)議的輸出，則輸出（即分級共識協(xié)議的輸出）；否則，輸出空區(qū)塊。Micali教授證明了，BA★滿足拜贊庭協(xié)議的要求：1. （共識性）最后一批誠實“驗證者”輸出的區(qū)塊是相同的；2. （一致性）如果一開始的“驗證者”收到的候選區(qū)塊都是，那么BA★的最終輸出也是。

五、Algorand的測試情況

MIT計算機科學(xué)和人工智能實驗室對Algorand進行了模擬測試［Gilad， Yossi， Rotem Hemo， Silvio Micali， Georgios Vlachos， and Nickolai Zeldovich， 2017， “Algorand： Scaling Byzantine Agreements for Cryptocurrencies”。 本節(jié)引用的圖均來自這篇文章。］。他們的測試在亞馬遜云上進行，使用了1000臺EC2虛擬機，發(fā)現(xiàn)：

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

第二，將用戶數(shù)固定在5萬，測試不同區(qū)塊大小對通量（throughput，可以用產(chǎn)生一個區(qū)塊的平均耗時來衡量）的影響。可以看出，區(qū)塊越大，構(gòu)建區(qū)塊的耗時越長，但對拜贊庭協(xié)議BA★的運行時間影響不大。