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

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

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

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

第二，比特幣區(qū)塊鏈系統(tǒng)要長期存續(xù)，要求50%以上的計(jì)算資源掌握在誠實(shí)用戶的手中。否則，惡意用戶在力量占優(yōu)時(shí)可能篡改區(qū)塊鏈。但隨著市場演變（中本聰應(yīng)該沒有預(yù)見到這種情況），比特幣區(qū)塊鏈系統(tǒng)中的計(jì)算資源集中在少數(shù)幾個(gè)“礦池”中。這就構(gòu)成了一個(gè)潛在的不穩(wěn)定因素?！暗V池”的存在也使比特幣區(qū)塊鏈系統(tǒng)偏離了其早期宣稱的民主特征，形成了“礦工”和普通使用者這樣不同階層的使用者。從比特幣歷史上關(guān)于擴(kuò)容的討論以及多次分叉不難看出，比特幣區(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)一筆交易被記入一個(gè)區(qū)塊并接入?yún)^(qū)塊鏈后，要等該筆交易所在區(qū)塊后面再接上5個(gè)區(qū)塊，才能比較肯定這筆交易進(jìn)入比特幣的公共賬本，而非在某一個(gè)分叉上。因?yàn)楸忍貛艆^(qū)塊鏈系統(tǒng)平均每10分鐘才能產(chǎn)生一個(gè)區(qū)塊，一筆交易從被記入?yún)^(qū)塊到被確認(rèn)需要1個(gè)小時(shí)左右時(shí)間。

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

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

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

用戶和交易特征

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

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

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

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

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

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

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

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

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

共識(shí)機(jī)制

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

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

密碼抽簽（cryptographic sortition）

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

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

接著，每個(gè)用戶使用自己的私鑰運(yùn)行系統(tǒng)公布的隨機(jī)算法，得到自己的憑證（credential）。憑證值滿足一定條件的用戶就是這一輪的“驗(yàn)證者”（verifiers）?！膀?yàn)證者”組裝一個(gè)新區(qū)塊并連同自己的憑證一起對(duì)外發(fā)出。其中，在第一個(gè)子步驟中憑證值最?。ò醋值浞矫媾判?，見下）的那個(gè)“驗(yàn)證者”的地位比較特殊，稱為“領(lǐng)導(dǎo)者”。

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

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

三、Algorand的密碼抽簽

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

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

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

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

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

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

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

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

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

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

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

分級(jí)共識(shí)協(xié)議

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

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

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

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

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

如果存在使得，則；

如果存在使得，則；

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

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

對(duì)任意誠實(shí)“驗(yàn)證者”和，；

對(duì)任意誠實(shí)“驗(yàn)證者”和，如果，那么必有；

如果存在使得，那么對(duì)所有的誠實(shí)“驗(yàn)證者”，均有。

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

二元拜贊庭協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（共識(shí)性）存在，使得對(duì)任意誠實(shí)“驗(yàn)證者”，均有；

（一致性）如果存在，使得對(duì)任意誠實(shí)“驗(yàn)證者”，均有，那么。

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

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

五、Algorand的測試情況

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

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

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