丁香五月天婷婷久久婷婷色综合91|国产传媒自偷自拍|久久影院亚洲精品|国产欧美VA天堂国产美女自慰视屏|免费黄色av网站|婷婷丁香五月激情四射|日韩AV一区二区中文字幕在线观看|亚洲欧美日本性爱|日日噜噜噜夜夜噜噜噜|中文Av日韩一区二区

您正在使用IE低版瀏覽器,為了您的雷峰網(wǎng)賬號安全和更好的產品體驗,強烈建議使用更快更安全的瀏覽器
此為臨時鏈接,僅用于文章預覽,將在時失效
金融科技 正文
發(fā)私信給溫曉樺
發(fā)送

0

圖靈獎得主Sivio Micali的Algorand區(qū)塊鏈協(xié)議簡介

本文作者: 溫曉樺 2018-02-19 17:31
導語:本月,圖靈獎得主、MIT教授Sivio Micali籌資開發(fā)Algorand區(qū)塊鏈協(xié)議。Algorand代表了區(qū)塊鏈底層技術發(fā)展的一個方向。

雷鋒網(wǎng)AI金融評論按:本文作者鄒傳偉,經(jīng)濟學博士,哈佛梅森學者,南湖金服合伙人、南湖互聯(lián)網(wǎng)金融學院常務副院長。曾獲首屆(2014年度)孫冶方金融創(chuàng)新獎。

2018年2月,圖靈獎得主、MIT教授Sivio Micali募集400萬美元開發(fā)Algorand區(qū)塊鏈協(xié)議一事受到了國內外媒體的普遍關注。2017年春天,筆者有幸在MIT選修了Micali教授和MIT媒體實驗室數(shù)字貨幣計劃負責人Neha Narula合開的《共享公共賬本》(Shared Public Ledger)課程。這門課主要就是講解Algorand。Algorand的目標是建立一個低能耗、高速度、民主化、可拓展性好而且?guī)缀醪粫霈F(xiàn)分叉的分布式賬本。Algorand沒有引入激勵機制或發(fā)行數(shù)字加密貨幣。

Algorand代表了區(qū)塊鏈底層技術發(fā)展的一個重要方向。本文對Algorand做一個簡單介紹,分享給國內讀者。Algorand涉及非常復雜的數(shù)學,筆者力圖用最少的數(shù)學介紹Algorand最核心的想法(涉及數(shù)學的主要是本文第三、四節(jié),略過不讀不會影響對文章大意的理解)。對Algorand感興趣的讀者可以閱讀關于Algorand的工作論文(不是白皮書,最新版工作論文于2017年5月發(fā)布,下載地址是https://arxiv.org/abs/1607.01341)。本文不構成對Algorand的商業(yè)評論。當然,筆者衷心祝愿Micali教授能取得成功。

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

Algorand是MIT機械工程與計算機科學系Silvio Micali教授與合作者(主要是紐約大學石溪分校陳靜副教授)于2016年提出的一個區(qū)塊鏈協(xié)議。Micali教授為意大利裔美國人,1982年獲加州大學伯克利分校計算機科學博士,1983年起在MIT任教。他的研究領域包括密碼學、零知識(zero knowledge)、偽隨機數(shù)生成、安全協(xié)議(secure protocol)和機制設計。

Micali教授1993年獲哥德爾獎(由歐洲理論計算機學會EATCS與美國計算機學會基礎理論專業(yè)組織ACM SIGACT于1993年共同設立,頒發(fā)給理論計算機領域最杰出的學術論文),2004年獲密碼學領域的RSA獎(RSA是三位發(fā)明公鑰-私鑰密碼系統(tǒng)的科學家Rivest、Shamir和Adleman的姓氏縮寫),2012年獲圖靈獎(由計算機協(xié)會ACM于1966年設立,獎勵給對計算機事業(yè)作出重要貢獻的個人,有“計算機界諾貝爾獎”之稱)。

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

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

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

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

第四,比特幣區(qū)塊鏈系統(tǒng)的可拓展性比較差。比如,一個比特幣區(qū)塊的大小為1M,大約能容納2000筆左右交易,因為平均每10分鐘產生一個區(qū)塊,比特幣最高支持每秒鐘6筆交易;相比而言,Paypal平均每秒鐘能支持193筆交易,Visa平均每秒鐘能支持1667筆交易[ http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/ ]。從這個意義上講,比特幣是人類歷史上投入產出比最低的社會和技術試驗之一。對可拓展性問題,比特幣閃電網(wǎng)絡是目前很受關注的一個解決方案。

鑒于比特幣區(qū)塊鏈系統(tǒng)的上述缺陷,Algorand的目標是:

  • 1.能耗低,不管系統(tǒng)中有多用戶,大約每1500名用戶中只有1名會被系統(tǒng)挑中執(zhí)行長達幾秒鐘的計算。

  • 2.民主化,不會出現(xiàn)類似比特幣區(qū)塊鏈系統(tǒng)的“礦工”群體。

  • 3.出現(xiàn)分叉的概率低于一兆分之一(即10-18)。假設Algorand中平均每分鐘產生一個區(qū)塊(后文會給出有關測試數(shù)據(jù)),這個概率意味著平均每190萬年出現(xiàn)一次分叉。

  • 4.可拓展性好。

二、Algorand的基本設置

(一)用戶和交易特征

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

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

對惡意用戶,Algorand假設他們由一個“敵對者”(adversary)控制?!皵硨φ摺蹦馨l(fā)起強大攻擊,包括:

  • “敵對者”可以在任何時候瞬間地腐化任何他選中的用戶,使其成為惡意用戶(哪怕該用戶之前是誠實用戶)。

  • “敵對者”完全控制并且完美協(xié)調所有惡意用戶??梢岳斫鉃?,惡意用戶的行為(包括發(fā)送和接收消息)完全由“敵對者”代理。

  • “敵對者”控制所有信息發(fā)送,但必須滿足一點:誠實用戶發(fā)出的消息能在一定時間內(該時間只與信息的存儲大小有關)抵達95%的誠實用戶。然而,“敵對者”幾乎不可能偽造誠實用戶的電子簽名或者干涉誠實用戶之間的通訊。

(二)區(qū)塊鏈結構

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

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

(三)網(wǎng)絡通訊

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

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

(四)共識機制

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

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

(五)密碼抽簽(cryptographic sortition)

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

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

接著,每個用戶使用自己的私鑰運行系統(tǒng)公布的隨機算法,得到自己的憑證(credential)。憑證值滿足一定條件的用戶就是這一輪的“驗證者”(verifiers)。“驗證者”組裝一個新區(qū)塊并連同自己的憑證一起對外發(fā)出。其中,在第一個子步驟中憑證值最?。ò醋值浞矫媾判颍娤拢┑哪莻€“驗證者”的地位比較特殊,稱為“領導者”。

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

從上述過程可以看出,

  • 第一,“驗證者”在秘密情況下獲知自己被選中,但他們只有公布憑證才能證明自己的“驗證者”資格。盡管“敵對者”可以瞬間腐化身份公開的“驗證者”,但已不能篡改或撤回他們已經(jīng)對外發(fā)出的消息。

  • 第二,所有“驗證者”公布自己的憑證并進行比較后,才能確定誰是“領導者”,也就是“領導者”可以視為由公共選舉產生。

  • 第三,隨機算法的性質決定了,事先很難判斷誰將被選為“驗證者”。因此,“驗證者”的選擇過程很難被操縱或預測。

  • 第四,盡管“敵對者”有可能事先安插一些交易來影響當前公共賬本,但因為“種子”參數(shù)的存在,他仍然不可能通過影響“驗證者”(特別是其中的“領導者”)的選擇來攻擊Algorand。接下來,對密碼抽簽和拜占庭協(xié)議BA★做一個相對技術化的介紹。

三、Algorand的密碼抽簽

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

(一)“驗證者”和“領導者”的選擇

假設在第r輪(可以理解為產生第r個區(qū)塊的時間段)開始時,“種子”參數(shù)為Qr-1(表現(xiàn)為一個由0和1組成的長度為256的字符串),PKr-k是第r-k輪結束后系統(tǒng)中活躍的用戶/公鑰(活躍的標志是至少參與過一筆交易)的集合,其中k被稱為回溯參數(shù)或安全參數(shù)。Qr-1和PKr-k屬于公共知識(common knowledge)。

憑證的定義。對每一個PKr-k中的用戶i,他使用自己的私鑰對“種子”參數(shù)Qr-1進行電子簽名后(用函數(shù)SIGi來表示)并輸入哈希函數(shù)(用函數(shù)H:來表示),得到自己的憑證H(SIGi(r,1,Qr-1))(函數(shù)SIGi有多個輸入?yún)?shù)時,表示將這些參數(shù)簡單串聯(lián)后再進行電子簽名,下同)。哈希函數(shù)的性質決定了:

  1. 憑證是一個近乎隨機的、由0和1組成的長度為256的字符串,并且不同用戶的憑證幾乎不可能相同;


  2. 由憑證構建的2進制小數(shù)0.H(SIGi(r,1,Qr-1))(也就是將憑證字符串寫到小數(shù)點后)在0和1之間均勻分布。

  • “潛在領導者”的選擇。對0和1之間的一個數(shù),0.H(SIGi(r,1,Qr-1))≤p發(fā)生的概率為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使用自己的私鑰對“種子”參數(shù)Qr-1進行電子簽名后并輸入哈希函數(shù),得到自己的憑證H(SIGi(r,1,Qr-1))。對0和1之間的一個數(shù)pr,滿足0.H(SIGi(r,1,Qr-1))≤pr的用戶就構成這一步的“驗證者”。

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

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

  • Qr=H(SIGlr(Qr-1,r)),如果Br不是空區(qū)塊

    =H(Qr-1,r),如果Br是空區(qū)塊

哈希函數(shù)的性質決定了,Qr和Qr-1之間的關系近乎隨機的。回溯參數(shù)或安全參數(shù)k則保證了,“敵對者”在第r-k-1輪幾乎不可能預測到Qr-1;否則,他將在第r-k輪引入惡意用戶(也就是進入PKr-k),從而能影響第r輪“領導者”和“驗證者”的選擇。

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

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

以下為敘述方便,假設:

  • 1.系統(tǒng)處在第r輪;

  • 2.每一個子步驟都選出n名“驗證者”,其中惡意“驗證者”不超過t,并且n≥3t+1(也就是誠實“驗證者”占比在2/3以上)。另外,引入計數(shù)函數(shù)#si(v)表示在第s步,“驗證者”i收到的消息v的次數(shù)(來自同一發(fā)送人的只能算1次)。

(一)分級共識協(xié)議

步驟1.1:運行密碼抽簽程序,選出“領導者”lr和這一步的“驗證者”。用vi表示“驗證者”i收到的并且他認識是來自“領導者”lr的候選區(qū)塊。

有3個原因使得vir不一定等于“領導者”lr構建的候選區(qū)塊:

  • 第一,“驗證者”i辨認“領導者”的方法是從他收到的所有“驗證者”憑證中找出按字典排序最小者。但因為網(wǎng)絡通訊原因,“領導者”lr發(fā)出的信息可能沒有到達“驗證者”i處。

  • 第二,“領導者”lr可能被“敵對者”腐化,對不同“驗證者”發(fā)出不同的候選區(qū)塊。

  • 第三,“驗證者”i本身可能是惡意的。

步驟1.2:“驗證者”i將vi發(fā)給其他用戶(這對其他“驗證者”都適用,下同)。

步驟1.3:當且僅當“驗證者”i在步驟1.2中收到的某一個的x次數(shù)超過了2t+1次(即#2i(x)≥2t+1),他將x發(fā)給其他用戶。

輸出:“驗證者”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教授證明了,分級共識協(xié)議的輸出{(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。

因此,分級共識協(xié)議的輸出{(vi,gi):i=1,2,L……n}存在兩種可能的情形。

  • 情形一:如果存在誠實“驗證者”i,使得,gi=2,那么對任意其他“驗證者”j,必有gj≥1,vj=vi。此時所有誠實“驗證者”輸出的候選區(qū)塊是一樣的。當然,如果一開始的“驗證者”收到的候選區(qū)塊都是v,那么最后一批“驗證者”輸出的也將都是v。

  • 情形二:對所有的誠實“驗證者”i,gi≤1,并且他們輸出的候選區(qū)塊不一定相同。

(二)二元拜占庭協(xié)議

首先,基于分級共識協(xié)議的輸出{(vi,gi):i=1,2,K……n}對每個誠實“驗證者”賦值:如果gi=2,那么bi=0;否則bi=1,。這些bi就是二元拜占庭協(xié)議的輸入。對應著前面的討論,此處也存在兩種情形:

  • 情形一:存在誠實“驗證者”i,使得bi=0。

  • 情形二:對所有誠實“驗證者”i,均有bi=1。

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

步驟2.1:“驗證者”i發(fā)出bi。

如果#1i(0)≥2t+1,那么“驗證者”i設定bi=0,輸出outi=0,并停止執(zhí)行協(xié)議(也可以認為他以后將一直發(fā)出bi=0);

如果#1i(1)≥2t+1,那么“驗證者”i設定bi=1;

否則,“驗證者”i設定bi=0。

步驟2.2:“驗證者”i發(fā)出bi。

如果#2i(1)≥2t+1,那么“驗證者”i設定bi=1,輸出outi=1,并停止執(zhí)行協(xié)議(也可以認為他以后將一直發(fā)出bi=1);

如果#2i(0)≥2t+1,那么“驗證者”i設定bi=0;

否則,“驗證者”i設定bi=1。

步驟2.3:“驗證者”i發(fā)出bi和SIGi(Qr-1,rj)。

如果#3i(0)≥2t+1,那么“驗證者”i設定bi=0;

如果#3i(1)≥2t+1,那么“驗證者”i設定bi=1;

否則,用Si表示所有給“驗證者”i發(fā)送消息的其他“驗證者”集合,定義圖靈獎得主Sivio Micali的Algorand區(qū)塊鏈協(xié)議簡介(lsb表示一個數(shù)的二進制表述中的最右邊位置上的數(shù)字),“驗證者”i設定bi=c,并且ri的計數(shù)往上調1位。鑒于哈希函數(shù)的性質,這實際上是將bi隨機地、不被操縱地賦值為0或1。

回到步驟2.1,Micali教授證明了,在二元拜占庭協(xié)議中,每個誠實“驗證者”i能以概率1停止并輸出outi∈{0,1},并且:

  • (共識性)存在outi∈{0,1},使得對任意誠實“驗證者”i,均有outi=out;

  • (一致性)如果存在b∈{0,1},使得對任意誠實“驗證者”i,均有bi=b,那么out=b。

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

BA★的輸出:對誠實“驗證者”i,如果二元拜占庭協(xié)議的輸出outi=0,則輸出vi(即分級共識協(xié)議的輸出);否則,輸出空區(qū)塊?。

Micali教授證明了,BA★滿足拜占庭協(xié)議的要求:

  • 1. (共識性)最后一批誠實“驗證者”輸出的區(qū)塊是相同的;

  • 2. (一致性)如果一開始的“驗證者”收到的候選區(qū)塊都是v,那么BA★的最終輸出也是v。

五、Algorand的測試情況

MIT計算機科學和人工智能實驗室對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分鐘內確認交易,而且確認交易的時間隨著用戶數(shù)量的增加,變化不大。

圖靈獎得主Sivio Micali的Algorand區(qū)塊鏈協(xié)議簡介

第二,將用戶數(shù)固定在5萬,測試不同區(qū)塊大小對通量(throughput,可以用產生一個區(qū)塊的平均耗時來衡量)的影響??梢钥闯?,區(qū)塊越大,構建區(qū)塊的耗時越長,但對拜占庭協(xié)議BA★的運行時間影響不大。

圖靈獎得主Sivio Micali的Algorand區(qū)塊鏈協(xié)議簡介

參考資料:
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)版權文章,未經(jīng)授權禁止轉載。詳情見轉載須知。

分享:
相關文章
最新文章
請?zhí)顚懮暾埲速Y料
姓名
電話
郵箱
微信號
作品鏈接
個人簡介
為了您的賬戶安全,請驗證郵箱
您的郵箱還未驗證,完成可獲20積分喲!
請驗證您的郵箱
立即驗證
完善賬號信息
您的賬號已經(jīng)綁定,現(xiàn)在您可以設置密碼以方便用郵箱登錄
立即設置 以后再說