原文鏈接：https://mp.weixin.qq.com/s/FD_zkmNcLHv440Y2oqpoag

Algorand背景介紹 (Background)

Algorand是MIT機(jī)械工程與計(jì)算機(jī)科學(xué)系SilvioMicali教授與合作者于2016年提出的一個(gè)區(qū)塊鏈協(xié)議鸦致，主要是為了解決比特幣區(qū)塊鏈采用的pow共識(shí)協(xié)議存在的算力浪費(fèi)拼窥，擴(kuò)展性弱、易分叉蹋凝、確認(rèn)時(shí)間長(zhǎng)等不足。因此SilvioMicali教授在algorand區(qū)塊鏈協(xié)議中提出了一種新的共識(shí)協(xié)議BA总棵，其目標(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ū)塊鞍爱，這個(gè)概率意味著平均每190萬(wàn)年出現(xiàn)一次分叉。
4.可拓展性好专酗。

Algorand概述 (Algorand, in aNutshell)

(一) 假想環(huán)境 (Setting)
1.在無(wú)需準(zhǔn)入(permissionless)和需要準(zhǔn)入(permissioned)環(huán)境下都能正常工作睹逃，當(dāng)然在需要準(zhǔn)入的環(huán)境下能表現(xiàn)得更好。
2.敵手能力很強(qiáng)(VeryAdversary Environments)

1. 可以立刻腐蝕(corrupt)任何他想要的用戶(user)，前提條件是：在無(wú)需準(zhǔn)入的環(huán)境中沉填，需要2/3以上的金額(money)屬于誠(chéng)實(shí)(honest)用戶疗隶；而在需要準(zhǔn)入且一人一票的環(huán)境中，需要2/3以上的誠(chéng)實(shí)用戶
2. 完全控制和完美協(xié)調(diào)已腐蝕的用戶
   3)調(diào)度已腐蝕用戶所發(fā)送的所有信息翼闹，前提條件是斑鼻，誠(chéng)實(shí)用戶發(fā)送的消息需要在一定的時(shí)間內(nèi)發(fā)送到95%以上的其他誠(chéng)實(shí)用戶，而其延遲只和消息大小有關(guān)猎荠。

(二) 主要特點(diǎn) (Main Properties)

1. 計(jì)算量為最優(yōu)坚弱，不論系統(tǒng)中存在多少用戶，每1500個(gè)用戶的計(jì)算量之和最多僅為幾秒鐘
2. 一個(gè)新的區(qū)塊在10分鐘內(nèi)被生成关摇，并且永遠(yuǎn)不會(huì)因分叉問題而被主鏈拋棄荒叶，事實(shí)上Algorand發(fā)生分叉的概率微乎其微
3. 沒有礦工，所有有投票權(quán)的用戶都有機(jī)會(huì)參與新塊的產(chǎn)生過程

(三) Algorand采用的技術(shù) (Algorand’s Techniques)

1. 一種新的拜占庭共識(shí)(BA: Byzantine Agreement)協(xié)議拒垃，即BA*停撞，這也是后文將重點(diǎn)介紹的協(xié)議
2. 采用密碼學(xué)抽簽：BA*協(xié)議中每一輪參與投票的用戶都可以證明確實(shí)是隨機(jī)選取的
3. 種子參數(shù)：選取完全無(wú)法預(yù)測(cè)的種子參數(shù)，從而保證不被敵手所影響悼瓮，上一輪的種子參數(shù)會(huì)參與下一輪投票用戶的生成
4. 秘密抽簽和秘密資格：所有參與共識(shí)投票的用戶都是秘密地得知他們的身份戈毒，投票后他們的身份被暴露，雖然敵手可以馬上腐蝕他們横堡，但是他們發(fā)送的消息已經(jīng)無(wú)法被撤回埋市，另外在消息生成后，用于簽名的一次性臨時(shí)秘鑰(后文會(huì)提到)會(huì)立刻被丟棄命贴，使得敵手在該輪無(wú)法再次生成任何合法消息
5. 用戶可替換(player-replacable)：在拜占庭協(xié)議中道宅，每個(gè)參與共識(shí)者需要投票多輪以達(dá)成共識(shí)，而在BA*中這并不可行胸蛛，因?yàn)橐坏┩镀焙笞约壕捅┞读宋垡穑瑫?huì)被敵手腐蝕。配合密碼學(xué)秘密抽簽葬项，用戶會(huì)秘密知道自己有且只有參與某特定時(shí)刻的投票的資格泞当，只要在該時(shí)刻參與投票，因?yàn)榻酉聛硗镀睓?quán)會(huì)轉(zhuǎn)移給別人民珍，這就使敵手的腐蝕失去了意義襟士。
   另外，誠(chéng)實(shí)的用戶可以是懶惰的(Lazy Honesty)嚷量。一個(gè)用戶不需要時(shí)刻在線陋桂，可以根據(jù)適當(dāng)?shù)臈l件適當(dāng)在線并參與共識(shí)即可。

Algorand的前置條件 (Preliminaries)

(一) 密碼學(xué)前置條件 (Cryptographic Primitives)

1.理想(ideal)的hash函數(shù)
給定一個(gè)hash函數(shù)H蝶溶，可以生成任意長(zhǎng)度字符串s的hash值H(s)嗜历。要求在給定H(s)的長(zhǎng)度后，能做到分布是完全均勻和獨(dú)立于s的(H as a random oracle)。在本文中秸脱，H(s)的長(zhǎng)度固定為256位比特(256-bit long)落包，事實(shí)上這個(gè)長(zhǎng)度已經(jīng)能夠抵抗碰撞(collision-resilient)，即給定兩個(gè)字符串x摊唇，ｙ咐蝇，其H(x)=H(y)的概率足夠小(根據(jù)生日悖論，發(fā)生碰撞需要的嘗試次數(shù)約為2^256/2=2¹²⁸)巷查。

2.數(shù)字簽名(Digital Signing)
數(shù)字簽名體系(digital digning scheme)包括三個(gè)高效函數(shù)：基于概率的公私鑰生成(key generator)函數(shù)G有序，簽名算法(signing algorithm)S，以及驗(yàn)證算法(verification algorithm)V岛请。
定義用戶i對(duì)消息m的簽名如下：

image

通過V可以驗(yàn)證這個(gè)簽名：

若s = sig_i(m)崇败，則V(pk_i,m, s) = YES

并且數(shù)字簽名很難被偽造盅称，即很難找到另外一個(gè)ｍ使得V(pk_i, m, s) = YES成立。作為用戶i要做的后室，就是保管好自己的私鑰sk_i缩膝，并公開其對(duì)應(yīng)的公鑰pk_i，使得其他人能夠驗(yàn)證簽名岸霹。

一般情況下是不能從簽名sig_i(m)中還原ｍ的疾层，同時(shí)需要用戶信息而找到其對(duì)應(yīng)的公鑰，所以一般情況下的“簽名”贡避，包括用戶身份信息i痛黎，消息原文ｍ，以及對(duì)應(yīng)的簽名刮吧，定義如下：

image

數(shù)字簽名應(yīng)該是唯一的湖饱，即通過數(shù)字簽名體系(G, S, V)，很難找到兩個(gè)不同的簽名s ≠ s’杀捻，使得V(pk, m, s) =V(pk, m, s’) = 1琉历。

在Algorand里，用戶使用數(shù)字簽名來：

為交易生成簽名

生成憑證(credential)水醋，用以證明自己有投票權(quán)

為消息ｍ生成簽名，這里需要使用一次性臨時(shí)秘鑰

(二) 理想的公開賬本 (The Idealized Public Ledger)

在Algorand中彪置，我們假設(shè)賬本的模型如下：

1.擁有一個(gè)初始狀態(tài)(Initial Status)拄踪，假設(shè)每個(gè)公鑰pk₁，… 拳魁，pk_j以及其對(duì)應(yīng)的金額為a₁惶桐，…，a_j，表示如下：

S⁰= (pk₁, a₁), …, (pk_j, a_j)

并且這個(gè)狀態(tài)作為系統(tǒng)公共常識(shí)(common knowledge of the system)而存在姚糊。

2.交易(Payments)贿衍，我們定義交易如下：

?= SIG_pk(pk, pk’, a’, I, H(I’))

pk和pk’分別為支付方和接收方的公鑰，在這里公開的信息為I救恨，敏感信息I’被H混淆贸辈。

3. 魔法賬本(The Magic Ledger)，這是一個(gè)無(wú)法篡改的列表肠槽，定義為：

L= PAY¹, PAY², …

每個(gè)PAY^r+1都包括了該塊中所有的交易擎淤，并且只在PAY^r之后加入，理想狀態(tài)下秸仙，一個(gè)新的塊會(huì)在固定或有限(fixed or finite)的時(shí)間內(nèi)加入賬本嘴拢。

這個(gè)賬本模型比比特幣的賬本模型更加一般化，每個(gè)公鑰相當(dāng)于一個(gè)錢包寂纪，其金額可以通過查詢當(dāng)前的狀態(tài)S^r得到席吴，而S^r是通過S⁰經(jīng)過L = PAY¹, …, PAY^r線性變換后計(jì)算得到。

(三) 基本概念和符號(hào) (Basic Notions and Notations)**

1. 公鑰捞蛋，用戶和擁有者(Keys,Users, and Owners)孝冒，一般情況下，公鑰和用戶其實(shí)是等價(jià)的襟交，而擁有者一般是表示擁有這個(gè)錢包的使用權(quán)迈倍，即擁有這個(gè)公鑰對(duì)應(yīng)的私鑰，當(dāng)一個(gè)公鑰j付款給另一個(gè)公鑰i后捣域，可以理解為用戶i加入了系統(tǒng)啼染。

2. 無(wú)需準(zhǔn)入和需要準(zhǔn)入的系統(tǒng)(Permissionlessand Permissioned Systems)，如果一個(gè)公鑰可以隨意加入系統(tǒng)焕梅，一個(gè)用戶可以擁有多個(gè)公鑰迹鹅，則這是一個(gè)無(wú)需準(zhǔn)入的系統(tǒng)，否則便是一個(gè)需要準(zhǔn)入的系統(tǒng)贞言。

3. 同速時(shí)鐘(Same-SpeedClocks)斜棚，用戶之間的時(shí)間可以不同，但是時(shí)鐘的走速必須相同该窗。

4. 輪次(Round)弟蚀，Algorand的輪次對(duì)應(yīng)于區(qū)塊鏈的塊高度的概念，我們統(tǒng)一使用上標(biāo)表示輪次酗失。在輪次r>0開始前义钉，所有公鑰的集合為PKr，而其系統(tǒng)狀態(tài)為：

image

image

是公鑰i對(duì)應(yīng)的金額规肴，在這里因?yàn)閍是一個(gè)數(shù)字捶闸，我們采用了(r)以區(qū)別于a的r次方夜畴。注意到PK^r是能夠從S^r中獲得的，而S^r中也能包括除了公鑰和金額外的其他狀態(tài)删壮√盎妫可以理解，在輪次0央碟，PK⁰和S⁰作為初始公鑰集(initial public keys)和初始狀態(tài)(initial status)税灌，是系統(tǒng)的公共常識(shí)。而在輪次r硬耍，已經(jīng)變?yōu)镻K¹垄琐，… ，PK^r和S¹经柴，… 狸窘，S^r。在輪次r坯认，系統(tǒng)從S¹遷移到S^r+1翻擒，即：

image

5. 正式交易集(OfficialPaysets)，第r輪的交易集即PAY^r是由該輪次的所有交易所組成牛哺。而通過Algorand算法選出的交易集(可能為空集)即為正式交易集陋气。用戶只有在某輪次通過正式交易集中接收了一定金額之后，才被認(rèn)為加入了系統(tǒng)引润。事實(shí)上正式交易集PAY^r是狀態(tài)S^r到狀態(tài)S^r+1的映射：

image

不難理解巩趁，一個(gè)理想的系統(tǒng)中，可以從S⁰和PAY⁰淳附，… 议慰，PAY^r獲取S^r+1。

(四) 塊和證明塊 (Blocks and Proven Blocks)

一個(gè)塊包括輪次r奴曙，該輪的正式交易集PAY^r，一個(gè)隨機(jī)種子Q^r洽糟，以及上一個(gè)塊的hash炉菲，也就是說從B⁰之后，一個(gè)傳統(tǒng)的區(qū)塊鏈大致如下所示：

image

當(dāng)一個(gè)區(qū)塊B^r附帶上憑證(certificate)坤溃，標(biāo)記為CERT^r拍霜，之后得到已經(jīng)證明的塊(proven block)

image

。如此以來薪介，魔法賬本其實(shí)是一串已證明的塊：

image

(五) 敵手模型 (The Adversarial Model)

1.  誠(chéng)實(shí)和惡意用戶(Honest and Malicious Users)沉御，誠(chéng)實(shí)用戶的行為完全符合預(yù)定規(guī)則，如執(zhí)行相應(yīng)邏輯昭灵，收發(fā)信息等等吠裆，而這里的惡意(malicious)是指任何違反預(yù)定規(guī)則的行為，即拜占庭錯(cuò)誤
   

2.  敵手(The Adversary)烂完，敵手是一個(gè)有效的算法试疙，即可以在多項(xiàng)式時(shí)間內(nèi)，可以在任何時(shí)間抠蚣，使任何用戶變?yōu)閻阂庾？酰锤?corrupt)用戶，并且可以完全控制和協(xié)調(diào)所有惡意用戶嘶窄，可以以用戶名字做出任何違反規(guī)則的行為怀跛，或是簡(jiǎn)單地選擇不收發(fā)任何消息。在用戶做出任何惡意行為前柄冲，沒人能知道他已經(jīng)被腐化了吻谋，而特定的行為能夠暴露其已經(jīng)被腐化的事實(shí)。但是這個(gè)敵手：
   

被約束在算力和密碼學(xué)的范圍內(nèi)现横，即基本不能偽造誠(chéng)實(shí)用戶的數(shù)字簽名
無(wú)法干擾誠(chéng)實(shí)節(jié)點(diǎn)之間的消息傳送漓拾。

3. 好人掌錢(HMM: Honesty Majority of Money)，我們假定一個(gè)連續(xù)的好人掌錢模型戒祠，對(duì)于一個(gè)非負(fù)整數(shù)k和一個(gè)實(shí)數(shù)h > 1/2骇两，我們認(rèn)為好人在第r-k輪掌握的錢的比例是大于h的。Algorand采用“向前看”的策略姜盈，即在第r輪參與投票的候選人低千，是從r-k輪選出來的，所以即使整個(gè)網(wǎng)絡(luò)在r-k被腐化了馏颂，其真正掌權(quán)也需要等到地r輪示血。
   

(六) 通信模型（The Communication Model）

同比特幣一樣，Algorand采用點(diǎn)對(duì)點(diǎn)緋聞通信協(xié)議來完成消息的傳播饱亮。

如果把消息的到達(dá)率(reachability)表示為ρ矾芙。模型認(rèn)為一條消息被誠(chéng)實(shí)用戶發(fā)出到超過ρ的人接收到的時(shí)間只和消息長(zhǎng)度μ ∈ Z⁺有關(guān)，定義該函數(shù)為λ_ρ,μ近上。即從時(shí)間t發(fā)出的一條大小為μ的消息剔宪，一定能在t+λ_ρ,μ之前到達(dá)比例為ρ的誠(chéng)實(shí)用戶。

Algorand面臨的是多個(gè)用戶同時(shí)發(fā)送各自消息壹无，并且還要幫助其他用戶傳遞合法消息的模型葱绒。所以函數(shù)λ被認(rèn)為和三個(gè)變量相關(guān)，到達(dá)率ρ斗锭，消息長(zhǎng)度μ ∈ Z⁺以及用戶數(shù)n地淀。模型修改為對(duì)所有的誠(chéng)實(shí)用戶n，在t時(shí)刻同時(shí)發(fā)送了各自的長(zhǎng)度為μ ∈ Z⁺的消息m₁岖是，… 帮毁，m_n实苞，則所有這些消息一定能在t+λ_n,ρ,μ之前到達(dá)比例為ρ的誠(chéng)實(shí)用戶。為了簡(jiǎn)化烈疚，后文一般情況下會(huì)使ρ＝１黔牵，并且不再提及到達(dá)率的問題。另外爷肝，敵手是可以控制任何用戶猾浦，以加速某些消息的到達(dá)時(shí)間。

Algorand實(shí)例化 (Embodiments of Algorand)
Algorand能夠在同步和異步網(wǎng)絡(luò)中工作灯抛。為了方便理解金赦，可以將其網(wǎng)絡(luò)環(huán)境假想為一個(gè)同步完全網(wǎng)絡(luò) (SC networks: synchronous complete networks)。在這樣的網(wǎng)絡(luò)環(huán)境下对嚼，假設(shè)存在一個(gè)全局時(shí)鐘夹抗，每次計(jì)時(shí)都是在整數(shù)點(diǎn)上r=1，２猪半，…兔朦。在每個(gè)偶數(shù)點(diǎn)r，網(wǎng)絡(luò)中的用戶i獨(dú)立并發(fā)地發(fā)送一個(gè)消息!](http://upload-images.jianshu.io/upload_images/3959874-1fe79fd6208bc00d?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

(消息可以為空)磨确，而在r+1的時(shí)刻沽甥，j就可以收到這個(gè)消息，j知道消息是從i處發(fā)送的乏奥。敵手可以在任何奇數(shù)時(shí)間點(diǎn)上發(fā)動(dòng)攻擊摆舟，腐化誠(chéng)實(shí)用戶拥峦，聯(lián)合惡意用戶隙轻，控制其邏輯和消息發(fā)送等行為。

(一) 目標(biāo) (Objectives)

在理想情況下粘优，共識(shí)協(xié)議的最終目的為：

1. 完全正確性(Perfect Correctness)骗炉，即所有的誠(chéng)實(shí)用戶都共識(shí)在B^r上照宝。

2. 完整性為1(Completeness 1)：以１的概率，B^r包含的交易集PAY^r句葵，是最大化的(maximal)厕鹃，也就是包含盡可能多的有效交易。

而Algorand的目標(biāo)更加現(xiàn)實(shí)乍丈，因?yàn)橛袗阂庥脩舻拇嬖诩敛辏绻僭O(shè)誠(chéng)實(shí)用戶的占比h>2/3，非正式地描述轻专，Algorand的目標(biāo)是：

• 保證以壓倒性的概率做到完全正確忆矛，并且完整性接近h。

犧牲完整性帶來的壞處是降低交易效率请垛，但正確性得以保證催训，排除了分叉的風(fēng)險(xiǎn)洽议。

(二) 出塊者和驗(yàn)證者(Leader and Verifiers)**

Algorand采用了抽簽的方式來獲知自己的身份。

對(duì)于出塊者而言漫拭，其出塊權(quán)的計(jì)算公式為：

.H(SIG_i(r,1, Q^r-1)) ≤ p

這里Q^r-1是隨機(jī)表示種子绞铃，后文會(huì)介紹其公式。.H函數(shù)表示把H函數(shù)的輸出字符串均勻地匹配到[0,1]區(qū)間之中去嫂侍。這樣以來，可以直接和概率作比較計(jì)算荚坞。在出塊時(shí)挑宠，如果誠(chéng)實(shí)用戶發(fā)現(xiàn)自己有出塊權(quán)(.H≤p)，會(huì)選擇按照最大化的原則出塊颓影，同時(shí)可能有多個(gè)用戶滿足.H≤p各淀。

驗(yàn)證者具有投票權(quán)，其計(jì)算公式為：

.H(SIG_i(r, s, Q^r-1)) ≤ p’

其中s既是步驟(step)诡挂，從第二步開始碎浇，所有的驗(yàn)證者都采用這個(gè)公式。且每一步的p’都是一樣的璃俗。如果誠(chéng)實(shí)的用戶發(fā)現(xiàn)自己有驗(yàn)證權(quán)(.H≤p’)奴璃，會(huì)在對(duì)應(yīng)的步驟投票。

(三) 塊的生成 (Glock Generation)**

輪次r的出塊者l^r不一定是誠(chéng)實(shí)的城豁，若為誠(chéng)實(shí)苟穆，則出塊形式應(yīng)為：

image

若出塊者為惡意，其出塊形式會(huì)是以下兩種之一：

image

要注意唱星，若PAY^r確實(shí)為空集雳旅，其

image

，要注意這和空集是不同的间聊，前者表示一切正常攒盈，但是后者表示出錯(cuò)了，因此輸出了默認(rèn)值哎榴。

不論那種表示形式型豁，其隨機(jī)數(shù)種子保存在第三項(xiàng)中，供用戶計(jì)算憑證所用叹话。

(四) 隨機(jī)數(shù)種子Qr和向后看參數(shù)k (The Seed Q r and the Look-Back Parameter k)**

Algorand的隨機(jī)數(shù)種子可以從上一輪的塊的第三項(xiàng)中獲取偷遗，計(jì)算公式為：

image

另外為了防止敵手控制，Algorand引入了向后看參數(shù)k驼壶，第r輪的共識(shí)參與者氏豌，需要在第r-k輪加入系統(tǒng)。

隨機(jī)數(shù)種子和向后看參數(shù)的引入都是為了增加敵手根據(jù)當(dāng)前的狀態(tài)預(yù)測(cè)將來的難度热凹，從而無(wú)法準(zhǔn)確選擇腐蝕目標(biāo)泵喘。

(五) 概念(Notations)

r ≥ 0：當(dāng)前輪次

s ≥ 1：當(dāng)前步驟泪电，其中第一步出塊，后面步全部是投票

B^r：輪次r的出塊

PK^r：在第r-1輪結(jié)束以及第r輪開始時(shí)的公鑰集合

S^r：在第r-1輪結(jié)束以及第r輪開始時(shí)的系統(tǒng)狀態(tài)

PAY^r：B^r中的交易集

l^r：輪次r的出塊者(leader)纪铺，出塊者可以選擇輪次r的交易集PAY^r

SV^r,s：輪次r相速，步驟s的驗(yàn)證者集

SV^r：輪次r的驗(yàn)證者集，SV^r = ∪_s≥1SV^r,s

MSV^r,s和MSV^r,s：誠(chéng)實(shí)用戶和惡意用戶集合鲜锚，易知MSV^r,s∪HSV^r,s= SV^r,s 以及 MSV^r,s∩HSV^r,s=?

n₁ ∈ Z^＋和n ∈ Z⁺：出塊者集和驗(yàn)證者集的成員個(gè)數(shù)的期望值突诬，注意到n₁<<n，因?yàn)橹灰诟怕噬媳ＷC出塊者集中至少有一個(gè)誠(chéng)實(shí)用戶芜繁，而驗(yàn)證者集中誠(chéng)實(shí)用戶要占多數(shù)

h ∈ (0, 1)：一個(gè)大于2/3的常數(shù)旺隙，代表誠(chéng)實(shí)用戶在系統(tǒng)中的比例，表示誠(chéng)實(shí)用戶或者在誠(chéng)實(shí)用戶手中的金額在每個(gè)PK^r中的比例至少為h

H：密碼學(xué)隨機(jī)函數(shù)

⊥：一個(gè)特殊字符串骏令，表示默認(rèn)值蔬捷，其長(zhǎng)度等于H的輸出

F ∈ (0, 1)：一個(gè)參數(shù)，用來表示允許的錯(cuò)誤概率榔袋，當(dāng)≤F時(shí)可以認(rèn)為不可能發(fā)生周拐，概率≥1-F可以認(rèn)為幾乎必然發(fā)生

p_h ∈ (0, 1)：出塊者是誠(chéng)實(shí)的概率，理想情況下等于h凰兑，在有敵手的情況下妥粟，需要分情況討論分析

k∈ Z^＋：向后看參數(shù)，第r輪的出塊者和驗(yàn)證者在第r-k輪產(chǎn)生(嚴(yán)格說來聪黎，應(yīng)為max{0, r-k}輪產(chǎn)生)罕容，即SV^r? PK^r?k

p₁ ∈ (0, 1)：在輪次r的第一輪，在r-k輪的用戶被選入出塊者集SV^r,1的概率

image

p∈ (0, 1)：在輪次r的第s輪稿饰，在r-k輪的用戶被選入出塊者集SV^r,s的概率

image

CERT^r：B^r的憑證集合锦秒，集合的憑證(即對(duì)H(B^r)的簽名)數(shù)應(yīng)該大于t_H。

image

：被證明的塊

image

：用戶i知道B<sup>r</sup>的本地時(shí)間喉镰，Algorand允許每個(gè)用戶有自己的獨(dú)立時(shí)間旅择，只要其時(shí)鐘走速相同即可

image

：每個(gè)用戶i在第r輪第s步的開始和結(jié)束時(shí)間

Λ和λ：表示執(zhí)行第一步和其他步的時(shí)間上限

(六) 參數(shù) (Parameters)**

1. 參數(shù)間的關(guān)系
   

在輪次r，投票者和候選的出塊者從集合PK^r-k中選出侣姆。選擇k使得敵手無(wú)法在輪次r-k-1以高于F的概率預(yù)測(cè)Q^r-1生真，否則的話敵手可以在r-k輪引入惡意用戶，他們可能成為第r輪的出塊者或候選者

在每輪的第一步捺宗，選取n₁使得SV^r,1不為空集

2. 重要參數(shù)的選取
   

H的輸出為256比特長(zhǎng)

h=80%柱蟀，n₁=35

Λ=1分鐘，λ=10秒鐘

3.  協(xié)議初始化蚜厉，協(xié)議在時(shí)間0长已，輪次0開始，因?yàn)闆]有B<sup>-1</sup>或CERT<sup>-1</sup>，規(guī)定B<sup>-1</sup>是一個(gè)公開的參數(shù)术瓮，在其中包括Q<sup>-1</sup>康聂，所有的用戶都在時(shí)間0知道B<sup>-1</sup>
   

BA共識(shí)*

Algorand的拜占庭共識(shí)協(xié)議BA，按順序包括出塊者(Leader)選舉胞四，分級(jí)共識(shí)(GC:Graded Consensus)協(xié)議和二元拜占庭(BBA)協(xié)議幾個(gè)步驟恬汁。這里涉及到額外幾個(gè)概念和參數(shù)。

(一) 概念 (Notations)**

1.  m∈ Z<sup>＋</sup>：BBA*中的步數(shù)辜伟，是3的倍數(shù)
   

2.  L<sup>r </sup>≤ m/3：一個(gè)隨機(jī)變量氓侧，是伯努利試驗(yàn)?zāi)芸吹剑钡膰L試次數(shù)，每次嘗試的概率為P<sub>h</sub>/2导狡，最多嘗試m/3次甘苍，所有嘗試都失敗時(shí)，L<sup>r</sup> = m/3烘豌，L<sup>r</sup>決定了需要生成B<sup>r</sup>的時(shí)間上限
   

3.  t<sub>H</sub> = 2n/3 + 1：協(xié)議需要的簽名個(gè)數(shù)
   

4.  CERT<sup>r</sup>：B<sup>r</sup>的憑證集，包含t<sub>H</sub>個(gè)第r輪的驗(yàn)證者對(duì)于H(B<sup>r</sup>)的合法簽名
   

(二) 參數(shù) (Parameters)**

1. 參數(shù)間的關(guān)系

• 對(duì)輪次r的每一步s > 1看彼，選擇n廊佩，使得以下條件必然成立

|HSV^r,s| > 2|MSV^r,s | 以及 |HSV^r,s | +4|MSV^r,s | < 2n

  h越接近1，n可以越小

• 選取m靖榕，使得L^r < m/3必然成立

2.  重要參數(shù)的選取
   

• F = 10^-12

• n ≈ 1500标锄，k = 40，m = 180

(三) 臨時(shí)秘鑰的生成 (Implementing Ephemeral Keys)**

權(quán)威機(jī)構(gòu)可以為用戶U生成秘鑰茁计，將主公鑰(PMK: public master key)公開料皇，將主私鑰私(SMK: secret master key)下交給用戶。假定共識(shí)上線為180步星压，用戶需要參與共識(shí)100萬(wàn)輪共識(shí)践剂，則用戶可以利用主私鑰生成10⁶*180個(gè)臨時(shí)私鑰，并將主私鑰銷毀娜膘。而其他人通過主公鑰以及輪次和步數(shù)信息逊脯，可以生成對(duì)應(yīng)的公鑰，以驗(yàn)證簽名竣贪。

當(dāng)然另外也可以通過公鑰默克爾樹的方式來管理秘鑰军洼，用戶提前將樹根公開，每次發(fā)消息時(shí)將公鑰和對(duì)應(yīng)路徑同時(shí)發(fā)出演怎，其他人可以確認(rèn)公鑰的真實(shí)性匕争，再用公鑰驗(yàn)證簽名。

(四) 算法實(shí)質(zhì) (Actual Protocol)**

（因公式較多爷耀，以下以圖片展示甘桑，可點(diǎn)擊圖片查閱）

image

image

[圖片上傳中...(image-89950c-1521609358967-1)]

image

(五) 協(xié)議分析 (Analysis of Algorand)**

1. 分級(jí)共識(shí)協(xié)議(GC: Graded Consensus Protocol)

其GC協(xié)議的定義如下：

若協(xié)議P中的所有用戶為公共常識(shí)，每個(gè)用戶i各自都知道任意的初始值v’_i。

我們稱P是一個(gè)(n-t)分級(jí)共識(shí)協(xié)議扇住，若n個(gè)用戶的每次行動(dòng)中春缕，至多只有t個(gè)惡意用戶，其中n ≥ 3t + 1每個(gè)誠(chéng)實(shí)用戶i停機(jī)輸出一個(gè)（值-級(jí)）對(duì)(a value-gradepair)(v_i, g_i)艘蹋，其中g(shù)_i ∈ {0, 1, 2}锄贼，他們滿足如下條件：

• 對(duì)于所有的誠(chéng)實(shí)用戶i和j，|g_i –g_j| ≤ 1

• 對(duì)于所有的誠(chéng)實(shí)用戶i和i女阀，g_i,g_j> 0 ? v_i = v_j

• 若對(duì)某一v宅荤，所有的輸入v’₁= … = v’_n = v，則對(duì)所有誠(chéng)實(shí)用戶i浸策，都有v_i = v以及g_i = 2

GC協(xié)議的二階段對(duì)應(yīng)于BA*的Step2和Step3冯键，以及拜占庭協(xié)議的prepare和commit部分,而輸出(v_i, g_i)可以理解為commit票。若存在用戶i庸汗，使得g_i = 2惫确，則其必然收到了2t + 1個(gè)對(duì)特定v的prepare票，即使其中有t個(gè)惡意用戶蚯舱，也就是說其他誠(chéng)實(shí)用戶改化，是少收到了對(duì)這個(gè)特定v的t + 1張prepare票，因此條件1成立枉昏。另外陈肛，在出票時(shí)間內(nèi)，如果發(fā)現(xiàn)上一輪的用戶給出不一致的票兄裂，則該用戶的所有投票都會(huì)被視為作廢句旱，如此以來，每個(gè)用戶只能給出一次有效票晰奖，如果兩個(gè)v_i和v_j都有g(shù)_i,g_j > 0谈撒，那在一定commit輪發(fā)出了t+1張v_i和t + 1張v_j的票，則commit用戶中有t + 1個(gè)用戶收到了2t + 1張v₁的prepare票匾南，另有t + 1個(gè)收到了2t + 1張v₂的prepare票港华，因?yàn)樽疃啻嬖趖個(gè)惡意用戶，這需要每個(gè)惡意用戶投兩張prepare票午衰，而如前述立宜，惡意用戶不能這么做，否則自己所有的票都會(huì)被視為作廢臊岸，所以2成立橙数。3顯然成立，事實(shí)上帅戒，這相當(dāng)于出塊者為誠(chéng)實(shí)的情況灯帮，由拜占庭協(xié)議可以保證所有誠(chéng)實(shí)節(jié)點(diǎn)對(duì)v達(dá)成共識(shí)崖技，而誠(chéng)實(shí)節(jié)點(diǎn)的額數(shù)量為2t + 1，則對(duì)于任何用戶i钟哥，g_i = 2迎献。

2. 二元拜占庭共識(shí)協(xié)議 (The Binary BA Protocol BBA*)

所謂二元既是共識(shí)結(jié)果為{0,1}，在BA協(xié)議中腻贰，是用戶i的證明消息的第一個(gè)參數(shù)ESIG_i(b_i)吁恍。當(dāng)BBA結(jié)束時(shí)，它是一個(gè)可靠的(n-t)-拜占庭共識(shí)協(xié)議播演，其中n ≥ 3t + 1冀瓦。事實(shí)上應(yīng)該理解為沒有共識(shí)的情況下，協(xié)議會(huì)永遠(yuǎn)循環(huán)下去写烤，雖然存在概率翼闽，但是要是永遠(yuǎn)不發(fā)生共識(shí)，在現(xiàn)實(shí)中是不可能發(fā)生的事情洲炊。

而對(duì)應(yīng)于BA*在共識(shí)過程感局，惡意節(jié)點(diǎn)會(huì)不斷搗亂，阻止誠(chéng)實(shí)節(jié)點(diǎn)在第s步達(dá)成共識(shí)(5 ≤ s ≤ m + 2)暂衡，但是每次在s – 2 ≡ 2 mod 3階段蓝厌，會(huì)有一次機(jī)會(huì)通過抽簽的方式有概率，讓誠(chéng)實(shí)用戶i對(duì)b_i達(dá)成共識(shí)古徒。而在最后的m+3階段，會(huì)選擇強(qiáng)制出空塊的方式結(jié)束此輪读恃。

3. BA

BA協(xié)議就是將出塊流程隧膘，GC協(xié)議和BBA協(xié)議串聯(lián)在一起，最后完成出塊流程寺惫。它是一個(gè)可靠的(n-t)-拜占庭共識(shí)協(xié)議疹吃，其中n ≥ 3t + 1。當(dāng)每一輪結(jié)束時(shí)西雀，都滿足：

一致性(Consisteny)：所有誠(chéng)實(shí)用戶i都在同一個(gè)v上達(dá)成共識(shí)萨驶，即vi = v

共識(shí)性(Agreement)：所有誠(chéng)實(shí)用戶i要不都發(fā)生共識(shí)，要不都不發(fā)生共識(shí)

4. 定理 (The Theorem)

算法作者通過歸納法證明了如下結(jié)論：

在任何輪次r > 0艇肴，如下屬性必然成立：

所有的誠(chéng)實(shí)用戶共識(shí)與同一個(gè)塊B^r

出塊者為誠(chéng)實(shí)的腔呜，則Br包含了交易的最大集，其達(dá)成共識(shí)的時(shí)間上限為T^r+1 ≤ T^r+ 8λ + Λ再悼。

出塊者為惡意的核畴，其對(duì)Br達(dá)成共識(shí)的時(shí)間上限為T^r+1 ≤ T^r + (6L^r + 10)λ + Λ

對(duì)于L^r，p_h = h²(1 + h – h²)冲九，出塊者為誠(chéng)實(shí)的概率至少為 p_h

事實(shí)上谤草，絕大多數(shù)情況下，BA*協(xié)議都可以快速達(dá)成共識(shí)。敵手需要掌握惡意出塊者丑孩，還要不斷調(diào)整每一輪投票者的行為冀宴，最后需要不錯(cuò)的運(yùn)氣，才能使該輪以最長(zhǎng)的時(shí)間結(jié)束出塊温学÷灾可以算得，其達(dá)到共識(shí)的期望時(shí)間為12.7λ + Λ

結(jié)論 (Conclusion)

Algorand基本解決了pow遇到的很多問題枫浙。根據(jù)論文給出的數(shù)據(jù)刨肃，其交易效率也很高，并且不會(huì)因?yàn)橛脩魯?shù)的增加和區(qū)塊的增大而增加共識(shí)時(shí)間箩帚，事實(shí)上真友，其最消耗時(shí)間的地方是在區(qū)塊的傳播上。