0
| 本文作者： 溫曉樺 | 2018-02-19 17:31 |
雷鋒網(wǎng)AI金融評(píng)論按：本文作者鄒傳偉，經(jīng)濟(jì)學(xué)博士，哈佛梅森學(xué)者，南湖金服合伙人、南湖互聯(lián)網(wǎng)金融學(xué)院常務(wù)副院長(zhǎng)。曾獲首屆（2014年度）孫冶方金融創(chuàng)新獎(jiǎng)。
2018年2月，圖靈獎(jiǎng)得主、MIT教授Sivio Micali募集400萬美元開發(fā)Algorand區(qū)塊鏈協(xié)議一事受到了國內(nèi)外媒體的普遍關(guān)注。2017年春天，筆者有幸在MIT選修了Micali教授和MIT媒體實(shí)驗(yàn)室數(shù)字貨幣計(jì)劃負(fù)責(zé)人Neha Narula合開的《共享公共賬本》（Shared Public Ledger）課程。這門課主要就是講解Algorand。Algorand的目標(biāo)是建立一個(gè)低能耗、高速度、民主化、可拓展性好而且?guī)缀醪粫?huì)出現(xiàn)分叉的分布式賬本。Algorand沒有引入激勵(lì)機(jī)制或發(fā)行數(shù)字加密貨幣。
Algorand代表了區(qū)塊鏈底層技術(shù)發(fā)展的一個(gè)重要方向。本文對(duì)Algorand做一個(gè)簡(jiǎn)單介紹，分享給國內(nèi)讀者。Algorand涉及非常復(fù)雜的數(shù)學(xué)，筆者力圖用最少的數(shù)學(xué)介紹Algorand最核心的想法（涉及數(shù)學(xué)的主要是本文第三、四節(jié)，略過不讀不會(huì)影響對(duì)文章大意的理解）。對(duì)Algorand感興趣的讀者可以閱讀關(guān)于Algorand的工作論文（不是白皮書，最新版工作論文于2017年5月發(fā)布，下載地址是https://arxiv.org/abs/1607.01341）。本文不構(gòu)成對(duì)Algorand的商業(yè)評(píng)論。當(dāng)然，筆者衷心祝愿Micali教授能取得成功。
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)行1.18*1022次哈希運(yùn)算?？紤]到哈希函數(shù)作為隨機(jī)預(yù)言（random oracle）的性質(zhì)，比特幣區(qū)塊的產(chǎn)生過程，相當(dāng)于擲一個(gè)有1.18*1022面的骰子，直到擲出某一特定的面為止。比特幣區(qū)塊鏈系統(tǒng)一年的耗電量，與秘魯全國一年的耗電量相當(dāng)，而且還在快速增長(zhǎng)中。這些巨量計(jì)算和耗電，除了產(chǎn)生比特幣區(qū)塊以外，對(duì)人類社會(huì)幾乎沒有任何價(jià)值。
第二，比特幣區(qū)塊鏈系統(tǒng)要長(zhǎng)期存續(xù)，要求50%以上的計(jì)算資源掌握在誠實(shí)用戶的手中。否則，惡意用戶在力量占優(yōu)時(shí)可能篡改區(qū)塊鏈。但隨著市場(chǎng)演變（中本聰應(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ù)陌灼鳾 Nakomoto, Satoshi, 2009, “Bitcoin: A Peer-to-Peer Electronic Cash System”. ]，當(dāng)一筆交易被記入一個(gè)區(qū)塊并接入?yún)^(qū)塊鏈后，需要再等6個(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ū)塊，比特幣最高支持每秒鐘6筆交易；相比而言，Paypal平均每秒鐘能支持193筆交易，Visa平均每秒鐘能支持1667筆交易[ http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/ ]。從這個(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í)行長(zhǎng)達(dá)幾秒鐘的計(jì)算。
2.民主化，不會(huì)出現(xiàn)類似比特幣區(qū)塊鏈系統(tǒng)的“礦工”群體。
3.出現(xiàn)分叉的概率低于一兆分之一（即10-18）。假設(shè)Algorand中平均每分鐘產(chǎn)生一個(gè)區(qū)塊（后文會(huì)給出有關(guān)測(cè)試數(shù)據(jù)），這個(gè)概率意味著平均每190萬年出現(xiàn)一次分叉。
4.可拓展性好。
Algorand是一個(gè)公有鏈系統(tǒng)。用戶（或者節(jié)點(diǎn)）加入Algorand不需要事先申請(qǐng)，可以隨時(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)大攻擊，包括：
“敵對(duì)者”可以在任何時(shí)候瞬間地腐化任何他選中的用戶，使其成為惡意用戶（哪怕該用戶之前是誠實(shí)用戶）。
“敵對(duì)者”完全控制并且完美協(xié)調(diào)所有惡意用戶?？梢岳斫鉃?，惡意用戶的行為（包括發(fā)送和接收消息）完全由“敵對(duì)者”代理。
“敵對(duì)者”控制所有信息發(fā)送，但必須滿足一點(diǎn)：誠實(shí)用戶發(fā)出的消息能在一定時(shí)間內(nèi)（該時(shí)間只與信息的存儲(chǔ)大小有關(guān)）抵達(dá)95%的誠實(shí)用戶。然而，“敵對(duì)者”幾乎不可能偽造誠實(shí)用戶的電子簽名或者干涉誠實(shí)用戶之間的通訊。
在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ì)。
與比特幣區(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)過λ長(zhǎng)時(shí)間后，至少被超過ρ的誠實(shí)用戶接收。
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è)子步驟的參與者可以完全不一樣，而且每一批參與者都無法確定下一批參與者是誰，從而無法串謀。
密碼抽簽是Algorand的關(guān)鍵創(chuàng)新，也是其得名的由來，其要點(diǎn)如下。首先，Algorand創(chuàng)建并不斷更新一個(gè)獨(dú)立參數(shù)，稱為“種子”。“種子”參數(shù)不僅不可能被“敵對(duì)者”預(yù)測(cè)，也不能被其操縱。
其次，在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ù)測(cè)。
第四，盡管“敵對(duì)者”有可能事先安插一些交易來影響當(dāng)前公共賬本，但因?yàn)椤胺N子”參數(shù)的存在，他仍然不可能通過影響“驗(yàn)證者”（特別是其中的“領(lǐng)導(dǎo)者”）的選擇來攻擊Algorand。接下來，對(duì)密碼抽簽和拜占庭協(xié)議BA★做一個(gè)相對(duì)技術(shù)化的介紹。
密碼抽簽按兩條線索執(zhí)行：一是選出“驗(yàn)證者”和“領(lǐng)導(dǎo)者”；二是創(chuàng)建并不斷完善“種子”參數(shù)。
假設(shè)在第r輪（可以理解為產(chǎn)生第r個(gè)區(qū)塊的時(shí)間段）開始時(shí)，“種子”參數(shù)為Qr-1（表現(xiàn)為一個(gè)由0和1組成的長(zhǎng)度為256的字符串），PKr-k是第r-k輪結(jié)束后系統(tǒng)中活躍的用戶/公鑰（活躍的標(biāo)志是至少參與過一筆交易）的集合，其中k被稱為回溯參數(shù)或安全參數(shù)。Qr-1和PKr-k屬于公共知識(shí)（common knowledge）。
憑證的定義。對(duì)每一個(gè)PKr-k中的用戶i，他使用自己的私鑰對(duì)“種子”參數(shù)Qr-1進(jìn)行電子簽名后（用函數(shù)SIGi來表示）并輸入哈希函數(shù)（用函數(shù)H:來表示），得到自己的憑證H(SIGi(r,1,Qr-1))(函數(shù)SIGi有多個(gè)輸入?yún)?shù)時(shí)，表示將這些參數(shù)簡(jiǎn)單串聯(lián)后再進(jìn)行電子簽名，下同）。哈希函數(shù)的性質(zhì)決定了：
憑證是一個(gè)近乎隨機(jī)的、由0和1組成的長(zhǎng)度為256的字符串，并且不同用戶的憑證幾乎不可能相同；
由憑證構(gòu)建的2進(jìn)制小數(shù)0.H(SIGi(r,1,Qr-1))（也就是將憑證字符串寫到小數(shù)點(diǎn)后）在0和1之間均勻分布。
“潛在領(lǐng)導(dǎo)者”的選擇。對(duì)0和1之間的一個(gè)數(shù)，0.H(SIGi(r,1,Qr-1))≤p發(fā)生的概率為p，稱所有滿足此條件的用戶為“潛在領(lǐng)導(dǎo)者”（也是這一步的“驗(yàn)證者”）。p使得以1-10-18的概率，在所有“潛在領(lǐng)導(dǎo)者”中，至少有一個(gè)是誠實(shí)的。
“領(lǐng)導(dǎo)者”的選擇。在所有“潛在領(lǐng)導(dǎo)者”中，存在一個(gè)用戶lr，其憑證按字典排序最小。也就是，對(duì)所有0.H(SIGi(r,1,Qr-1))≤p的用戶i，均有H(SIGlr(r,1,Qr-1))≤H(SIGi(r,1,Qr-1))。用戶lr就是第r輪的“領(lǐng)導(dǎo)者”。
“驗(yàn)證者”的選擇。第r輪第s步（s>1）的“驗(yàn)證者”的產(chǎn)生程序與上文類似。在這一步中，每一個(gè)PKr-k中的用戶i使用自己的私鑰對(duì)“種子”參數(shù)Qr-1進(jìn)行電子簽名后并輸入哈希函數(shù)，得到自己的憑證H(SIGi(r,1,Qr-1))。對(duì)0和1之間的一個(gè)數(shù)pr，滿足0.H(SIGi(r,1,Qr-1))≤pr的用戶就構(gòu)成這一步的“驗(yàn)證者”。
用Br表示第輪結(jié)束后，拜占庭協(xié)議BA★輸出的區(qū)塊。如果Algorand在第輪受到了“敵對(duì)者”攻擊，Br可能是空的，也就是不含有任何真實(shí)交易記錄（用符號(hào)來表示）。比如，“敵對(duì)者”可能腐化了這一輪的“領(lǐng)導(dǎo)者”，使其將兩個(gè)不同的候選區(qū)塊發(fā)給誠實(shí)的“驗(yàn)證者”。考慮到這個(gè)情況，“種子”參數(shù)的更新過程是：
Qr=H(SIGlr(Qr-1，r)),如果Br不是空區(qū)塊
=H(Qr-1，r）,如果Br是空區(qū)塊
哈希函數(shù)的性質(zhì)決定了，Qr和Qr-1之間的關(guān)系近乎隨機(jī)的?；厮輩?shù)或安全參數(shù)k則保證了，“敵對(duì)者”在第r-k-1輪幾乎不可能預(yù)測(cè)到Qr-1；否則，他將在第r-k輪引入惡意用戶（也就是進(jìn)入PKr-k），從而能影響第r輪“領(lǐng)導(dǎo)者”和“驗(yàn)證者”的選擇。
拜占庭協(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)處在第r輪；
2.每一個(gè)子步驟都選出n名“驗(yàn)證者”，其中惡意“驗(yàn)證者”不超過t，并且n≥3t+1（也就是誠實(shí)“驗(yàn)證者”占比在2/3以上）。另外，引入計(jì)數(shù)函數(shù)#si(v)表示在第s步，“驗(yàn)證者”i收到的消息v的次數(shù)（來自同一發(fā)送人的只能算1次）。
步驟1.1：運(yùn)行密碼抽簽程序，選出“領(lǐng)導(dǎo)者”lr和這一步的“驗(yàn)證者”。用vi表示“驗(yàn)證者”i收到的并且他認(rèn)識(shí)是來自“領(lǐng)導(dǎo)者”lr的候選區(qū)塊。
有3個(gè)原因使得vir不一定等于“領(lǐng)導(dǎo)者”lr構(gòu)建的候選區(qū)塊：
第一，“驗(yàn)證者”i辨認(rèn)“領(lǐng)導(dǎo)者”的方法是從他收到的所有“驗(yàn)證者”憑證中找出按字典排序最小者。但因?yàn)榫W(wǎng)絡(luò)通訊原因，“領(lǐng)導(dǎo)者”lr發(fā)出的信息可能沒有到達(dá)“驗(yàn)證者”i處。
第二，“領(lǐng)導(dǎo)者”lr可能被“敵對(duì)者”腐化，對(duì)不同“驗(yàn)證者”發(fā)出不同的候選區(qū)塊。
第三，“驗(yàn)證者”i本身可能是惡意的。
步驟1.2：“驗(yàn)證者”i將vi發(fā)給其他用戶（這對(duì)其他“驗(yàn)證者”都適用，下同）。
步驟1.3：當(dāng)且僅當(dāng)“驗(yàn)證者”i在步驟1.2中收到的某一個(gè)的x次數(shù)超過了2t+1次（即#2i(x)≥2t+1），他將x發(fā)給其他用戶。
輸出：“驗(yàn)證者”i按以下規(guī)則輸出(vI,gi)：
如果存在x使得#3i(x)≥2t+1，則vi=x,gi=2；
如果x存在使得#3i(x)≥t+1，則vi=x,gi=1；
否則vi=?，gi=1，其中?代表空區(qū)塊。
Micali教授證明了，分級(jí)共識(shí)協(xié)議的輸出{(vi,gi):i=1,2,L……n}滿足下列性質(zhì)：
對(duì)任意誠實(shí)“驗(yàn)證者”i和j，|gi-gj|≤1；
對(duì)任意誠實(shí)“驗(yàn)證者”i和j，如果gi,gj>0，那么必有vi=vj；
如果存在v使得有v'1=v'2=K……=v'n=v，那么對(duì)所有的誠實(shí)“驗(yàn)證者”i，均有vi=v,gi=2。
因此，分級(jí)共識(shí)協(xié)議的輸出{(vi,gi):i=1,2,L……n}存在兩種可能的情形。
情形一：如果存在誠實(shí)“驗(yàn)證者”i，使得,gi=2，那么對(duì)任意其他“驗(yàn)證者”j，必有g(shù)j≥1,vj=vi。此時(shí)所有誠實(shí)“驗(yàn)證者”輸出的候選區(qū)塊是一樣的。當(dāng)然，如果一開始的“驗(yàn)證者”收到的候選區(qū)塊都是v，那么最后一批“驗(yàn)證者”輸出的也將都是v。
情形二：對(duì)所有的誠實(shí)“驗(yàn)證者”i，gi≤1，并且他們輸出的候選區(qū)塊不一定相同。
首先，基于分級(jí)共識(shí)協(xié)議的輸出{(vi,gi):i=1,2,K……n}對(duì)每個(gè)誠實(shí)“驗(yàn)證者”賦值：如果gi=2，那么bi=0；否則bi=1，。這些bi就是二元拜占庭協(xié)議的輸入。對(duì)應(yīng)著前面的討論，此處也存在兩種情形：
情形一：存在誠實(shí)“驗(yàn)證者”i，使得bi=0。
情形二：對(duì)所有誠實(shí)“驗(yàn)證者”i，均有bi=1。
二元拜占庭協(xié)議可能經(jīng)過多次循環(huán)，用計(jì)數(shù)器ri表示“驗(yàn)證者”i經(jīng)歷的循環(huán)的次數(shù)。開始時(shí)，ri賦值為0。
步驟2.1：“驗(yàn)證者”i發(fā)出bi。
如果#1i(0)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=0，輸出outi=0，并停止執(zhí)行協(xié)議（也可以認(rèn)為他以后將一直發(fā)出bi=0）；
如果#1i(1)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=1；
否則，“驗(yàn)證者”i設(shè)定bi=0。
步驟2.2：“驗(yàn)證者”i發(fā)出bi。
如果#2i(1)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=1，輸出outi=1，并停止執(zhí)行協(xié)議（也可以認(rèn)為他以后將一直發(fā)出bi=1）；
如果#2i(0)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=0；
否則，“驗(yàn)證者”i設(shè)定bi=1。
步驟2.3：“驗(yàn)證者”i發(fā)出bi和SIGi(Qr-1,rj)。
如果#3i(0)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=0；
如果#3i(1)≥2t+1，那么“驗(yàn)證者”i設(shè)定bi=1；
否則，用Si表示所有給“驗(yàn)證者”i發(fā)送消息的其他“驗(yàn)證者”集合，定義
（lsb表示一個(gè)數(shù)的二進(jìn)制表述中的最右邊位置上的數(shù)字），“驗(yàn)證者”i設(shè)定bi=c，并且ri的計(jì)數(shù)往上調(diào)1位。鑒于哈希函數(shù)的性質(zhì)，這實(shí)際上是將bi隨機(jī)地、不被操縱地賦值為0或1。
回到步驟2.1，Micali教授證明了，在二元拜占庭協(xié)議中，每個(gè)誠實(shí)“驗(yàn)證者”i能以概率1停止并輸出outi∈{0,1}，并且：
（共識(shí)性）存在outi∈{0,1}，使得對(duì)任意誠實(shí)“驗(yàn)證者”i，均有outi=out；
（一致性）如果存在b∈{0,1}，使得對(duì)任意誠實(shí)“驗(yàn)證者”i，均有bi=b，那么out=b。
BA★的輸出：對(duì)誠實(shí)“驗(yàn)證者”i，如果二元拜占庭協(xié)議的輸出outi=0，則輸出vi（即分級(jí)共識(shí)協(xié)議的輸出）；否則，輸出空區(qū)塊?。
Micali教授證明了，BA★滿足拜占庭協(xié)議的要求：
1. （共識(shí)性）最后一批誠實(shí)“驗(yàn)證者”輸出的區(qū)塊是相同的；
2. （一致性）如果一開始的“驗(yàn)證者”收到的候選區(qū)塊都是v，那么BA★的最終輸出也是v。
MIT計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室對(duì)Algorand進(jìn)行了模擬測(cè)試[Gilad, Yossi, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich, 2017, “Algorand: Scaling Byzantine Agreements for Cryptocurrencies”. 本節(jié)引用的圖均來自這篇文章。]。他們的測(cè)試在亞馬遜云上進(jìn)行，使用了1000臺(tái)EC2虛擬機(jī)，發(fā)現(xiàn)：
第一，Algorand能在1分鐘內(nèi)確認(rèn)交易，而且確認(rèn)交易的時(shí)間隨著用戶數(shù)量的增加，變化不大。
第二，將用戶數(shù)固定在5萬，測(cè)試不同區(qū)塊大小對(duì)通量（throughput，可以用產(chǎn)生一個(gè)區(qū)塊的平均耗時(shí)來衡量）的影響?？梢钥闯?，區(qū)塊越大，構(gòu)建區(qū)塊的耗時(shí)越長(zhǎng)，但對(duì)拜占庭協(xié)議BA★的運(yùn)行時(shí)間影響不大。
參考資料：
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/
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
