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

Algorand背景介紹 (Background)

Algorand是MIT機械工程與計算機科學(xué)系SilvioMicali教授與合作者于2016年提出的一個區(qū)塊鏈協(xié)議，主要是為了解決比特幣區(qū)塊鏈采用的pow共識協(xié)議存在的算力浪費，擴展性弱、易分叉、確認時間長等不足。因此SilvioMicali教授在algorand區(qū)塊鏈協(xié)議中提出了一種新的共識協(xié)議BA，其目標(biāo)是：
1.能耗低，不管系統(tǒng)中有多用戶，大約每1500名用戶中只有1名會被系統(tǒng)挑中執(zhí)行長達幾秒鐘的計算。
2.民主化，不會出現(xiàn)類似比特幣區(qū)塊鏈系統(tǒng)的“礦工”群體。
3.出現(xiàn)分叉的概率低于一兆分之一（即10-18）。假設(shè)Algorand中平均每分鐘產(chǎn)生一個區(qū)塊，這個概率意味著平均每190萬年出現(xiàn)一次分叉。
4.可拓展性好。

Algorand概述 (Algorand, in aNutshell)

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

可以立刻腐蝕(corrupt)任何他想要的用戶(user)，前提條件是：在無需準(zhǔn)入的環(huán)境中，需要2/3以上的金額(money)屬于誠實(honest)用戶；而在需要準(zhǔn)入且一人一票的環(huán)境中，需要2/3以上的誠實用戶

完全控制和完美協(xié)調(diào)已腐蝕的用戶
3)調(diào)度已腐蝕用戶所發(fā)送的所有信息，前提條件是，誠實用戶發(fā)送的消息需要在一定的時間內(nèi)發(fā)送到95%以上的其他誠實用戶，而其延遲只和消息大小有關(guān)。

(二) 主要特點 (Main Properties)

計算量為最優(yōu)，不論系統(tǒng)中存在多少用戶，每1500個用戶的計算量之和最多僅為幾秒鐘

一個新的區(qū)塊在10分鐘內(nèi)被生成，并且永遠不會因分叉問題而被主鏈拋棄，事實上Algorand發(fā)生分叉的概率微乎其微

沒有礦工，所有有投票權(quán)的用戶都有機會參與新塊的產(chǎn)生過程

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

一種新的拜占庭共識(BA: Byzantine Agreement)協(xié)議，即BA*，這也是后文將重點介紹的協(xié)議

采用密碼學(xué)抽簽：BA*協(xié)議中每一輪參與投票的用戶都可以證明確實是隨機選取的

種子參數(shù)：選取完全無法預(yù)測的種子參數(shù)，從而保證不被敵手所影響，上一輪的種子參數(shù)會參與下一輪投票用戶的生成

秘密抽簽和秘密資格：所有參與共識投票的用戶都是秘密地得知他們的身份，投票后他們的身份被暴露，雖然敵手可以馬上腐蝕他們，但是他們發(fā)送的消息已經(jīng)無法被撤回，另外在消息生成后，用于簽名的一次性臨時秘鑰(后文會提到)會立刻被丟棄，使得敵手在該輪無法再次生成任何合法消息

用戶可替換(player-replacable)：在拜占庭協(xié)議中，每個參與共識者需要投票多輪以達成共識，而在BA*中這并不可行，因為一旦投票后自己就暴露了，會被敵手腐蝕。配合密碼學(xué)秘密抽簽，用戶會秘密知道自己有且只有參與某特定時刻的投票的資格，只要在該時刻參與投票，因為接下來投票權(quán)會轉(zhuǎn)移給別人，這就使敵手的腐蝕失去了意義。
另外，誠實的用戶可以是懶惰的(Lazy Honesty)。一個用戶不需要時刻在線，可以根據(jù)適當(dāng)?shù)臈l件適當(dāng)在線并參與共識即可。

Algorand的前置條件 (Preliminaries)

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

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

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

image
其中pk_i和sk_i為用戶i的公鑰和私鑰。這里使用H(m)是利用了其能夠抵抗碰撞的特性。

通過V可以驗證這個簽名：

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

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

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

image

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

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

為交易生成簽名

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

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

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

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

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

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

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

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

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

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

魔法賬本(The Magic Ledger)，這是一個無法篡改的列表，定義為：

L= PAY¹, PAY², …

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

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

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

公鑰，用戶和擁有者(Keys,Users, and Owners)，一般情況下，公鑰和用戶其實是等價的，而擁有者一般是表示擁有這個錢包的使用權(quán)，即擁有這個公鑰對應(yīng)的私鑰，當(dāng)一個公鑰j付款給另一個公鑰i后，可以理解為用戶i加入了系統(tǒng)。

無需準(zhǔn)入和需要準(zhǔn)入的系統(tǒng)(Permissionlessand Permissioned Systems)，如果一個公鑰可以隨意加入系統(tǒng)，一個用戶可以擁有多個公鑰，則這是一個無需準(zhǔn)入的系統(tǒng)，否則便是一個需要準(zhǔn)入的系統(tǒng)。

同速時鐘(Same-SpeedClocks)，用戶之間的時間可以不同，但是時鐘的走速必須相同。

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

image

注意其中image

是公鑰i對應(yīng)的金額，在這里因為a是一個數(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)的公共常識。而在輪次r，已經(jīng)變?yōu)镻K¹，… ，PK^r和S¹，… ，S^r。在輪次r，系統(tǒng)從S¹遷移到S^r+1，即：

image

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

image

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

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

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

image

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

image

。如此以來，魔法賬本其實是一串已證明的塊：

image

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

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

敵手(The Adversary)，敵手是一個有效的算法，即可以在多項式時間內(nèi)，可以在任何時間，使任何用戶變?yōu)閻阂?#xff0c;即腐化(corrupt)用戶，并且可以完全控制和協(xié)調(diào)所有惡意用戶，可以以用戶名字做出任何違反規(guī)則的行為，或是簡單地選擇不收發(fā)任何消息。在用戶做出任何惡意行為前，沒人能知道他已經(jīng)被腐化了，而特定的行為能夠暴露其已經(jīng)被腐化的事實。但是這個敵手：

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

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

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

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

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

Algorand面臨的是多個用戶同時發(fā)送各自消息，并且還要幫助其他用戶傳遞合法消息的模型。所以函數(shù)λ被認為和三個變量相關(guān)，到達率ρ，消息長度μ ∈ Z⁺以及用戶數(shù)n。模型修改為對所有的誠實用戶n，在t時刻同時發(fā)送了各自的長度為μ ∈ Z⁺的消息m₁，… ，m_n，則所有這些消息一定能在t+λ_n,ρ,μ之前到達比例為ρ的誠實用戶。為了簡化，后文一般情況下會使ρ＝１，并且不再提及到達率的問題。另外，敵手是可以控制任何用戶，以加速某些消息的到達時間。

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

(消息可以為空)，而在r+1的時刻，j就可以收到這個消息，j知道消息是從i處發(fā)送的。敵手可以在任何奇數(shù)時間點上發(fā)動攻擊，腐化誠實用戶，聯(lián)合惡意用戶，控制其邏輯和消息發(fā)送等行為。

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

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

完全正確性(Perfect Correctness)，即所有的誠實用戶都共識在B^r上。

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

而Algorand的目標(biāo)更加現(xiàn)實，因為有惡意用戶的存在，如果假設(shè)誠實用戶的占比h>2/3，非正式地描述，Algorand的目標(biāo)是：

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

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

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

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

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

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

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

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

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

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

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

輪次r的出塊者l^r不一定是誠實的，若為誠實，則出塊形式應(yīng)為：

image

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

image

要注意，若PAY^r確實為空集，其

image

，要注意這和空集是不同的，前者表示一切正常，但是后者表示出錯了，因此輸出了默認值。

不論那種表示形式，其隨機數(shù)種子保存在第三項中，供用戶計算憑證所用。

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

Algorand的隨機數(shù)種子可以從上一輪的塊的第三項中獲取，計算公式為：

image

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

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

(五) 概念(Notations)

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

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

B^r：輪次r的出塊

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

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

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

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

SV^r,s：輪次r，步驟s的驗證者集

SV^r：輪次r的驗證者集，SV^r = ∪_s≥1SV^r,s

MSV^r,s和MSV^r,s：誠實用戶和惡意用戶集合，易知MSV^r,s∪HSV^r,s= SV^r,s 以及 MSV^r,s∩HSV^r,s=?

n₁ ∈ Z^＋和n ∈ Z⁺：出塊者集和驗證者集的成員個數(shù)的期望值，注意到n₁<<n，因為只要在概率上保證出塊者集中至少有一個誠實用戶，而驗證者集中誠實用戶要占多數(shù)

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

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

⊥：一個特殊字符串，表示默認值，其長度等于H的輸出

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

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

k∈ Z^＋：向后看參數(shù)，第r輪的出塊者和驗證者在第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的憑證集合，集合的憑證(即對H(B^r)的簽名)數(shù)應(yīng)該大于t_H。

image：被證明的塊 image：用戶i知道B^r的本地時間，Algorand允許每個用戶有自己的獨立時間，只要其時鐘走速相同即可 image：每個用戶i在第r輪第s步的開始和結(jié)束時間

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

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

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

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

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

重要參數(shù)的選取

H的輸出為256比特長

h=80%，n₁=35

Λ=1分鐘，λ=10秒鐘

協(xié)議初始化，協(xié)議在時間0，輪次0開始，因為沒有B^-1或CERT^-1，規(guī)定B^-1是一個公開的參數(shù)，在其中包括Q^-1，所有的用戶都在時間0知道B^-1

BA共識*

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

(一) 概念 (Notations)**

m∈ Z^＋：BBA*中的步數(shù)，是3的倍數(shù)

L^r≤ m/3：一個隨機變量，是伯努利試驗?zāi)芸吹?#xff11;的嘗試次數(shù)，每次嘗試的概率為P_h/2，最多嘗試m/3次，所有嘗試都失敗時，L^r = m/3，L^r決定了需要生成B^r的時間上限

t_H = 2n/3 + 1：協(xié)議需要的簽名個數(shù)

CERT^r：B^r的憑證集，包含t_H個第r輪的驗證者對于H(B^r)的合法簽名

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

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

• 對輪次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必然成立

重要參數(shù)的選取

• F = 10^-12

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

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

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

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

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

（因公式較多，以下以圖片展示，可點擊圖片查閱）

imageimage

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

image

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

分級共識協(xié)議(GC: Graded Consensus Protocol)

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

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

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

• 對于所有的誠實用戶i和j，|g_i –g_j| ≤ 1

• 對于所有的誠實用戶i和i，g_i,g_j> 0 ? v_i = v_j

• 若對某一v，所有的輸入v’₁= … = v’_n = v，則對所有誠實用戶i，都有v_i = v以及g_i = 2

GC協(xié)議的二階段對應(yīng)于BA*的Step2和Step3，以及拜占庭協(xié)議的prepare和commit部分,而輸出(v_i, g_i)可以理解為commit票。若存在用戶i，使得g_i = 2，則其必然收到了2t + 1個對特定v的prepare票，即使其中有t個惡意用戶，也就是說其他誠實用戶，是少收到了對這個特定v的t + 1張prepare票，因此條件1成立。另外，在出票時間內(nèi)，如果發(fā)現(xiàn)上一輪的用戶給出不一致的票，則該用戶的所有投票都會被視為作廢，如此以來，每個用戶只能給出一次有效票，如果兩個v_i和v_j都有g(shù)_i,g_j > 0，那在一定commit輪發(fā)出了t+1張v_i和t + 1張v_j的票，則commit用戶中有t + 1個用戶收到了2t + 1張v₁的prepare票，另有t + 1個收到了2t + 1張v₂的prepare票，因為最多存在t個惡意用戶，這需要每個惡意用戶投兩張prepare票，而如前述，惡意用戶不能這么做，否則自己所有的票都會被視為作廢，所以2成立。3顯然成立，事實上，這相當(dāng)于出塊者為誠實的情況，由拜占庭協(xié)議可以保證所有誠實節(jié)點對v達成共識，而誠實節(jié)點的額數(shù)量為2t + 1，則對于任何用戶i，g_i = 2。

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

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

而對應(yīng)于BA*在共識過程，惡意節(jié)點會不斷搗亂，阻止誠實節(jié)點在第s步達成共識(5 ≤ s ≤ m + 2)，但是每次在s – 2 ≡ 2 mod 3階段，會有一次機會通過抽簽的方式有概率，讓誠實用戶i對b_i達成共識。而在最后的m+3階段，會選擇強制出空塊的方式結(jié)束此輪。

BA

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

一致性(Consisteny)：所有誠實用戶i都在同一個v上達成共識，即vi = v

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

定理 (The Theorem)

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

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

所有的誠實用戶共識與同一個塊B^r

出塊者為誠實的，則Br包含了交易的最大集，其達成共識的時間上限為T^r+1 ≤ T^r+ 8λ + Λ。

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

對于L^r，p_h = h²(1 + h – h²)，出塊者為誠實的概率至少為 p_h

事實上，絕大多數(shù)情況下，BA*協(xié)議都可以快速達成共識。敵手需要掌握惡意出塊者，還要不斷調(diào)整每一輪投票者的行為，最后需要不錯的運氣，才能使該輪以最長的時間結(jié)束出塊。可以算得，其達到共識的期望時間為12.7λ + Λ

結(jié)論 (Conclusion)

Algorand基本解決了pow遇到的很多問題。根據(jù)論文給出的數(shù)據(jù)，其交易效率也很高，并且不會因為用戶數(shù)的增加和區(qū)塊的增大而增加共識時間，事實上，其最消耗時間的地方是在區(qū)塊的傳播上。

作者：vdes
鏈接：https://www.jianshu.com/p/c1f73f2eafac
來源：簡書
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

總結(jié)

以上是生活随笔為你收集整理的Algorand协议详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。