Algorand共識協(xié)議的工作原理及優(yōu)缺點(diǎn)分析

概述

1.1 引言

Algorand 稱其突破了”公鏈不可能三角“，項(xiàng)目創(chuàng)始人是圖靈獎(jiǎng)得主、MIT CSAIL 實(shí)驗(yàn)室的 Silvio Micali 教授。Algorand 提出的共識協(xié)議是項(xiàng)目的一大亮點(diǎn)，本文主要分析 Algorand 共識協(xié)議的工作原理，并分析其優(yōu)缺點(diǎn)。

1.2 Algorand 設(shè)計(jì)的初衷

Algorand 想解決的核心問題是：去中心化網(wǎng)絡(luò)中低延時(shí)（Latency）和高置信度（Confidence）之間的矛盾［1］。

其中，延時(shí)指從發(fā)起交易到確認(rèn)交易所需要的時(shí)間；置信度指的是發(fā)出的交易不會再被更改的概率。

在比特幣網(wǎng)絡(luò)中，為了提高交易的置信度，用戶必須等待 6 個(gè)區(qū)塊確認(rèn)（約 1 個(gè)小時(shí)）的確認(rèn)延時(shí)；而如果選擇低延時(shí)，比如少于 6 個(gè)確認(rèn)，甚至是 0 確認(rèn)，則必然導(dǎo)致低置信度，增加“雙花”攻擊的可能。雙花問題是絕大多數(shù)加密數(shù)字貨幣的核心問題。比特幣中采用 PoW 共識來解決，但鏈本身仍然有分叉的可能，并且需要較長的共識達(dá)成過程和確認(rèn)時(shí)間。

同時(shí) Algorand 還想解決比特幣中 PoW 挖礦耗費(fèi)巨大資源、交易確認(rèn)時(shí)間長、易分叉、網(wǎng)絡(luò)呈中心化趨勢，可擴(kuò)展性差等問題。

1.3 Algorand 是什么？

根據(jù)官方描述，Algorand 是一個(gè)采用 permissionless 的純 PoS 共識的公鏈項(xiàng)目，結(jié)合改進(jìn)的拜占庭共識協(xié)議，可實(shí)現(xiàn)快速的交易確認(rèn)，幾乎不會分叉，并且用戶數(shù)可無限擴(kuò)展，不會影響交易確認(rèn)速度。同時(shí)兼顧“可擴(kuò)展、安全性、去中心化”這個(gè)“公鏈不可能三角”［2］。

（注：”公鏈不可能三角“的正確性和具體定義存在較多爭議［7］。在 Algorand 中：可擴(kuò)展性指在較大用戶規(guī)模下仍可實(shí)現(xiàn)較高的吞吐量［8］，安全性指的是可以對抗惡意攻擊［9］，去中心化指的是網(wǎng)絡(luò)完全開放，成為節(jié)點(diǎn)沒有任何門檻［10］。）

· 可擴(kuò)展性：Algorand 通過可驗(yàn)證隨機(jī)函數(shù)（VRF）隨機(jī)選擇區(qū)塊的生產(chǎn)者和驗(yàn)證者，一旦得知被選中，生產(chǎn)者或驗(yàn)證者只需廣播一個(gè)簡短的消息即可證明自己的身份。每產(chǎn)生一個(gè)新區(qū)塊在網(wǎng)絡(luò)中需要交換的消息不會隨著用戶數(shù)的增大而改變，，因此即使用戶規(guī)模增大，系統(tǒng)仍可保持較高的 TPS（每秒處理的交易數(shù)）。Algorand 的 TPS 是比特幣的 125 倍。

· 安全性：由于采用了上述的 VRF 隨機(jī)選取生產(chǎn)者和驗(yàn)證者，并且選取的過程完全由節(jié)點(diǎn)獨(dú)立完成，因此Algorand 網(wǎng)絡(luò)中的攻擊者無法預(yù)先得知下一個(gè)區(qū)塊生產(chǎn)者和驗(yàn)證者，從而也就無法完成攻擊。具體來說，生產(chǎn)者和驗(yàn)證者的身份只有在他們確定自己被選中并廣播對應(yīng)的證明信息時(shí)才會被披露，這時(shí)攻擊者即使立刻采取各種攻擊手段，也無法阻止關(guān)于新區(qū)塊的正確消息在網(wǎng)絡(luò)中的傳播。

· 去中心化：Algorand 中每一輪的區(qū)塊生產(chǎn)者和驗(yàn)證者都是隨機(jī)選取的，并且加入網(wǎng)絡(luò)沒有任何門檻，因此是完全去中心化的。

下面詳細(xì)介紹 Algorand 的共識協(xié)議。

lgorand 協(xié)議詳述

幾乎所有公鏈項(xiàng)目的區(qū)塊產(chǎn)生和共識的過程都可以抽象為兩個(gè)步驟：

1. 選擇出區(qū)塊生產(chǎn)者，生成新區(qū)塊

2. 其他節(jié)點(diǎn)對新區(qū)塊達(dá)成共識

以上步驟周而復(fù)始，最終形成一條“不可篡改”的區(qū)塊鏈。

整個(gè)共識過程雖然簡單，但在實(shí)際實(shí)現(xiàn)中，必須解決幾個(gè)關(guān)鍵問題：

· 如何選擇區(qū)塊生產(chǎn)者，且保證公平和不可被預(yù)測？

· 如何對新區(qū)塊達(dá)成共識？

· 如何避免分叉？

· 如何提高安全性？

· 如何擴(kuò)展到更大規(guī)模的用戶？

比特幣采用哈希函數(shù)的隨機(jī)性來確保公平，采用工作量證明（PoW）達(dá)成共識，同時(shí)能夠在一定程度上抵抗算力攻擊。然而比特幣仍然面臨上述消耗計(jì)算資源、確認(rèn)時(shí)間長、易分叉以及擴(kuò)展性差等問題。以 Qtum 為代表的采用純權(quán)益證明（PoS）共識機(jī)制的項(xiàng)目，同樣采用了哈希函數(shù)，并且不需要消耗大量的計(jì)算資源，然而仍然面臨易分叉、安全性及擴(kuò)展性的問題。

Algorand 提出了一種新的共識機(jī)制解決上述 5 個(gè)問題。

2.1 基礎(chǔ)知識

正式介紹 Algorand 共識協(xié)議之前，本文假設(shè)讀者基本了解以下名詞的含義：

· 哈希函數(shù)（Hash）

· 公鑰/私鑰

· 數(shù)字簽名

· 交易

· 區(qū)塊

· 賬本

· 共識

· 拜占庭協(xié)議（Byzantine Agreement，BA）

· 誠實(shí)節(jié)點(diǎn)

· 攻擊節(jié)點(diǎn)

· P2P 通信

如果讀者對上述概念不理解，請先搜索相關(guān)關(guān)鍵詞進(jìn)一步了解，再閱讀以下內(nèi)容。

2.2 Algorand 的基本過程

Algorand 協(xié)議可以按照時(shí)間順序劃分為不同輪次，每一輪都會達(dá)成共識并生成新區(qū)塊。其典型的通用過程如下：

1. 每一輪共識開始時(shí)，隨機(jī)選出潛在的 leaders，各自生成新區(qū)塊，對新區(qū)塊進(jìn)行簽名和廣播

2. 隨機(jī)選出驗(yàn)證組，對 leaders 廣播的新區(qū)塊進(jìn)行驗(yàn)證，達(dá)成共識后廣播確認(rèn)新區(qū)塊，進(jìn)入下一輪

接下來具體討論 Algorand 共識協(xié)議細(xì)節(jié)，本節(jié)主要參考［4］。

2.3 保證 Algorand 的隨機(jī)性：可驗(yàn)證隨機(jī)函數(shù)

Algorand 利用 VRF 來選擇區(qū)塊生產(chǎn)者和驗(yàn)證者，保證所有共識參與者都是隨機(jī)地、公平地被選出的?？沈?yàn)證隨機(jī)函數(shù)（VRF，Verifiable Random Function）是由 Micali 教授等提出的一種偽隨機(jī)函數(shù)，和普通的隨機(jī)函數(shù)一樣，對于不同輸入，其輸出也具有隨機(jī)性（嚴(yán)格來說是“偽隨機(jī)”）。其獨(dú)特之處在于調(diào)用者可以提供一個(gè)證明，表明這個(gè)隨機(jī)輸出確實(shí)由該調(diào)用者產(chǎn)生。

VRF 可以有多種實(shí)現(xiàn)方式，Micali 等人在其原始論文中提供了一種較復(fù)雜的實(shí)現(xiàn)方式［3］。Algorand 利用哈希函數(shù)和數(shù)字簽名的特性，提供了一種較為簡單的 VRF 實(shí)現(xiàn)。具體實(shí)現(xiàn)方式是調(diào)用者 i 將輸入 m 通過數(shù)字簽名和哈希函數(shù)映射為固定長度的輸出 H［SIGi（m）］，即 m -》 H［SIGi（m）］。

對于任何輸入 m，不同的調(diào)用者 i 生成的數(shù)字簽名 SIGi（m） 都是唯一的；而對于不同輸入，哈希函數(shù) H 的輸出具有隨機(jī)性，因此上述映射符合 VRF 的”隨機(jī)性“要求。同時(shí)，由于 i 的數(shù)字簽名 SIGi（m） 可通過其公鑰對其身份進(jìn)行驗(yàn)證，因此其也符合 VRF ”可驗(yàn)證“ 的特性，SIGi（m） 就是 VRF 中提到的”證明“。

這個(gè)函數(shù)特別適合在所有節(jié)點(diǎn)中隨機(jī)選擇出共識的參與者，下面具體討論。

2.3.1 隨機(jī)選出每一輪的區(qū)塊生產(chǎn)者（Leader）

每一輪共識開始時(shí)，每個(gè)節(jié)點(diǎn)都可以通過以下 VRF 獨(dú)立地驗(yàn)證自己是否是潛在的 leader：

.H［SIG（r， 1， Q（r-1））］ 《= 1 / SIZE（PK（r-k））

其中，H 是哈希運(yùn)算；SIG 是簽名運(yùn)算；r 是目前的輪次；Q（r-1） 為與 r-1 輪的種子（將在后續(xù) 2.6 節(jié)中解釋）；SIZE（PK（r-k）） 是在 r-k 輪所有符合要求的公鑰的數(shù)量（為什么是 r-k ？k 為回溯系數(shù)，也將在 2.6 節(jié)中闡述）；公式開始的 。 表示將哈希結(jié)果轉(zhuǎn)化為小數(shù)位，從而保證結(jié)果為［0，1）的某個(gè)值。

節(jié)點(diǎn)通過自己的私鑰計(jì)算上面簽名的哈希值是否符合要求，從而知道自己是否屬于候選的 leader，在此過程中無需和其他節(jié)點(diǎn)交換信息。由于哈希函數(shù)輸出的隨機(jī)性，可以認(rèn)為符合要求的候選節(jié)點(diǎn)都是隨機(jī)選出的。候選節(jié)點(diǎn)隨后可以生成新區(qū)塊，并向全網(wǎng)提供簽名證實(shí)自己的身份。如果有多個(gè)候選 leader，最終上述哈希值最小的 leader 將在后續(xù)的共識中成為本輪最終的 leader。Leader 產(chǎn)生的區(qū)塊 Br 包含了本輪的所有交易和上述的證明信息，由驗(yàn)證組成員進(jìn)行共識驗(yàn)證。

2.3.2 隨機(jī)選出每一輪每一階段的驗(yàn)證組

驗(yàn)證組成員的選擇與上述過程類似，在每一輪和每一階段（step），所有節(jié)點(diǎn)都可以獨(dú)立驗(yàn)證自己是否屬于驗(yàn)證組成員：

.H［SIG（r， s， Q（r-1））］ 《= n / SIZE（PK（r-k））

其中 s 為本輪所處的不同階段，Algorand 在每一輪的各個(gè)階段都有不同的驗(yàn)證組，從而進(jìn)一步保證安全性；n 為預(yù)期的驗(yàn)證組成員數(shù)量，可以人為設(shè)定；其他參數(shù)含義不再重復(fù)。

與候選 leader 一樣，每一階段的驗(yàn)證組成員均隨機(jī)選出，驗(yàn)證節(jié)點(diǎn)在證實(shí)自己身份后，可以開始參與共識驗(yàn)證過程，揭露自己的簽名即可證明其身份。

2.3.3 引入權(quán)益證明（Proof-of-Stake，PoS）機(jī)制

上述的隨機(jī)選擇過程沒有考慮 Token 持有者的權(quán)重，惡意節(jié)點(diǎn)可能通過大量生成有效私鑰從而有極大概率成為區(qū)塊的生產(chǎn)者和驗(yàn)證者。

Algorand 在其公布的實(shí)現(xiàn)建議中引入了名為 Honest Majority of Money （HMM）的條件假設(shè)，其基本思想來源于 PoS 共識機(jī)制，即在上述隨機(jī)選擇過程中引入代幣持有量（Stake）作為權(quán)重，持有量多的節(jié)點(diǎn)被選中的概率較高，而代幣持有者往往更傾向于保護(hù)網(wǎng)絡(luò)的安全性。具體可以表示為如下公式：

.H［SIG（r， 1， Q（r-1））］ 《= （a（i，r） / M） * （1 / SIZE（PK（r-k）））

其中，a（i，r） / M 為節(jié)點(diǎn)所持有的幣的數(shù)量占代幣總數(shù) M 的權(quán)重。其余過程與前面描述一直。

2.4 Algorand 如何對新區(qū)塊達(dá)成共識：改進(jìn)的拜占庭協(xié)議 BA*

Algorand 中驗(yàn)證者對新區(qū)塊達(dá)成共識的過程，實(shí)際上是一種改進(jìn)的拜占庭協(xié)議（Byzantine Agreement），Algorand 稱其為 BA*。

BA* 由一種改進(jìn)的二元拜占庭協(xié)議（Binary Byzantine Agreement，BBA）和分級共識協(xié)議（Graded Consensus，Protocol GC）組合而成［5］。

2.4.1 改進(jìn)的二元拜占庭協(xié)議 BBA*

Algorand 引入的 BBA* 是一個(gè)改進(jìn)的二元拜占庭協(xié)議（所謂二元，即只能達(dá)成 0 或 1 兩種共識）。BBA* 可以在誠實(shí)節(jié)點(diǎn)超過 ? 的情況下，快速達(dá)成共識。其具體過程是一個(gè) 3 步循環(huán)，循環(huán)中每一步都有 ? 的概率達(dá)成共識。

節(jié)點(diǎn)之間需要進(jìn)行 P2P 通信，假設(shè)被選中的驗(yàn)證節(jié)點(diǎn)中有 t 個(gè)惡意節(jié)點(diǎn)，驗(yàn)證組總的節(jié)點(diǎn)數(shù)為 n 》= 3t + 1，即惡意節(jié)點(diǎn)不超過 ? 。協(xié)議過程如下：

上述協(xié)議中各符號的具體含義可參考［4］。所有驗(yàn)證節(jié)點(diǎn)i都有一個(gè)初始值 bi（bi = 0 或 1），協(xié)議開始時(shí)，每個(gè)驗(yàn)證節(jié)點(diǎn)都會向其他驗(yàn)證節(jié)點(diǎn)發(fā)送各自的初始值，

協(xié)議第一步（Step 1）是歸 0 過程：

如果某驗(yàn)證節(jié)點(diǎn) i 收到 0 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ? ，輸出共識結(jié)果為 0，共識結(jié)束，不再執(zhí)行后面所有步驟

如果某驗(yàn)證節(jié)點(diǎn) i 收到 1 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ?，則該驗(yàn)證節(jié)點(diǎn)把自己的 bi 設(shè)為 1

如果收到的 0 或 1 都沒超過 ?， 則驗(yàn)證節(jié)點(diǎn)把自己的 bi 設(shè)為 0

第一步結(jié)束節(jié)點(diǎn)再次向其他節(jié)點(diǎn)發(fā)送各自的 bi

第二步（Step 2）為歸 1 過程：

如果某驗(yàn)證節(jié)點(diǎn) i 收到 1 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ? ，輸出共識結(jié)果為 1，共識結(jié)束，不再執(zhí)行后面所有步驟

如果某驗(yàn)證節(jié)點(diǎn) i 收到 0 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ?，則該驗(yàn)證節(jié)點(diǎn)把自己的 bi 設(shè)為 0

如果收到的 0 或 1 都沒超過 ?， 則驗(yàn)證節(jié)點(diǎn)把自己的 bi 設(shè)為 1

第二步結(jié)束節(jié)點(diǎn)再次向其他節(jié)點(diǎn)發(fā)送各自的 bi

第三步（Step 3）為重新設(shè)定初始值的過程：

如果某驗(yàn)證節(jié)點(diǎn) i 收到 0 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ?，設(shè)定 bi = 0

如果某驗(yàn)證節(jié)點(diǎn) i 收到 1 的總數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ?，設(shè)定 bi = 1

如果收到的 0 或 1 都沒超過 ?，則每個(gè)驗(yàn)證節(jié)點(diǎn)會對某個(gè)和本輪本階段相關(guān)的信息進(jìn)行簽名，并對簽名求哈希。bi 被設(shè)置為這些哈希值中最小哈希的最低有效位（仍然是 0 或 1）

之后返回第一步，直到達(dá)成共識

在 Algorand 中， BBA* 的結(jié)果是對是否接受某個(gè)區(qū)塊達(dá)成共識，共識結(jié)果只有接受（0）或拒絕（1）兩種情況。

2.4.2 分級共識協(xié)議 GC

上述 BBA* 只適用于二元情況，當(dāng)需要對任意值達(dá)成共識，需要引入分級共識協(xié)議，將任意值問題轉(zhuǎn)化為二元問題：

Algorand 采用的 GC 分為兩步（上圖來自 Algorand 白皮書［4］，為了和文中其他部分對應(yīng)，將兩個(gè)步驟命名為 Step 2 和 3），協(xié)議開始時(shí)，每個(gè)驗(yàn)證節(jié)點(diǎn)i各自都有一個(gè)初始值 vi（在 Algorand 中即候選的新區(qū)塊的哈希）：

第一步 （Step 2），所有驗(yàn)證節(jié)點(diǎn)將各自的 vi 發(fā)給其他所有驗(yàn)證節(jié)點(diǎn)；

第二步（Step 3），對于某個(gè)x值，當(dāng)且僅當(dāng)節(jié)點(diǎn)收到其他驗(yàn)證節(jié)點(diǎn)發(fā)來該 x 值的總次數(shù)（多次收到同一節(jié)點(diǎn)發(fā)送的x值，只算一次）超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ? 時(shí)，這個(gè)節(jié)點(diǎn)會對其它節(jié)點(diǎn)發(fā)送值 x：

經(jīng)過 GC，每個(gè)節(jié)點(diǎn)都會輸出一個(gè)值對 （vi， gi），輸出規(guī)則：

· 當(dāng)收到 x 的總次數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ? 時(shí)，設(shè)定 vi = x， gi = 2；

· 當(dāng)收到 x 的總次數(shù)超過總驗(yàn)證節(jié)點(diǎn)數(shù)的 ? 時(shí)，設(shè)定 vi = x， gi = 1；

· 否則，設(shè)定 vi = 空， gi = 0；

簡單來說，分級共識的作用是從多個(gè)可能的候選新區(qū)塊中選擇被大多數(shù)認(rèn)可的一個(gè)作為最終候選的區(qū)塊，再通過上面的 BBA* 最終達(dá)成共識。

2.4.3 BA* = GC + BBA*

改進(jìn)的拜占庭協(xié)議 BA* 結(jié)合了上述 GC 和 BBA*，先通過 GC 把任意值問題（從多個(gè)區(qū)塊中選擇一個(gè)候選）轉(zhuǎn)化為二元問題（接收或拒絕新區(qū)塊？），再利用 BBA* 達(dá)成快速二元拜占庭共識，從而可以快速對任意值達(dá)成共識，其共識過程如下［4］：

BA* 的第一步，和第二步，所有驗(yàn)證節(jié)點(diǎn) i 執(zhí)行 2.4.2 中分級共識 GC，各自得到一個(gè)關(guān)于新區(qū)塊的數(shù)值對 （vi， gi），其中 vi 為驗(yàn)證節(jié)點(diǎn) i 認(rèn)為的候選區(qū)塊哈希（有可能為空），gi = 0 或 1 或 2 。

第三步，所有驗(yàn)證節(jié)點(diǎn)根據(jù)各自的 （vi， gi） 設(shè)定 BBA* 的初始值，如果 gi = 2，則設(shè)定初始值為 0，如果 gi = 0 或 1， 則設(shè)定初始值為 1 。之后進(jìn)行 2.4.1 中的 BBA* 共識過程：

· 若共識結(jié)果為 0，則最終輸出結(jié)果為 vi（非空新區(qū)塊）

· 若共識結(jié)果為 1， 則最終輸出結(jié)果為空（即新區(qū)塊為空）

無論哪種情況，BA* 都可以在驗(yàn)證節(jié)點(diǎn)中達(dá)成共識，從而確定新區(qū)塊及其包含的交易（有可能為空區(qū)塊）。

2.5 Algorand 區(qū)塊鏈分叉的可能性

Algorand 實(shí)際采用的是經(jīng)典拜占庭共識的升級版 BA*，它和以比特幣為代表的中本聰共識的最大區(qū)別在于分叉的可能性。后者由于完全去中心化，節(jié)點(diǎn)之間無法完全通信，因此可能僅在部分節(jié)點(diǎn)間達(dá)成共識，容易發(fā)生分叉。

Algorand 可以通過設(shè)定最大可接受的錯(cuò)誤概率 F 調(diào)整分叉的概率。在 Algorand 提供的兩種實(shí)現(xiàn)中，其分叉概率分別為 10^-12 和 10^-18，在現(xiàn)實(shí)中分叉僅存在理論上的可能。為給讀者一個(gè)直觀概念，假設(shè) Algorand 每秒生成一個(gè)區(qū)塊，10^-18 的概率意味著從宇宙大爆炸至今的時(shí)間內(nèi)，只有可能發(fā)生一次分叉，可見其概率極低。

即使真的發(fā)生分叉，Algorand 仍可以從分叉中恢復(fù)：

· Algorand 遵守中本聰共識中的最長鏈法則

· 如果有多條最長鏈，則選擇包含非空區(qū)塊的最長鏈

· 如果仍相同，則可以具體根據(jù)區(qū)塊哈希值進(jìn)行排序選擇

2.6 Algorand 如何保證安全性

上述的共識算法在理想情況下可以實(shí)現(xiàn)去中心化環(huán)境下較快速的拜占庭共識，數(shù)字簽名和 VRF 本身的安全性也對系統(tǒng)安全提供了基本的保障。除此之外，Algorand 還引入了以下機(jī)制，進(jìn)一步提升安全性：

種子 Q（r）

Algorand 中的隨機(jī)性主要靠 VRF 保證，每輪隨機(jī)的選出 leader 及驗(yàn)證組。一個(gè)比較直接的想法是把上一區(qū)塊 B（r-1） 作為隨機(jī)函數(shù)的輸入。但這種方法將給惡意節(jié)點(diǎn)帶來一定的優(yōu)勢：因?yàn)閰^(qū)塊和其包含的交易高度相關(guān)，惡意節(jié)點(diǎn)可以通過調(diào)整區(qū)塊中包含的交易集，獲得多個(gè)輸出，并選擇對其最有利的交易集產(chǎn)生新區(qū)塊，從而提高自己在下一輪中成為 leader 或驗(yàn)證組的概率。

為解決這一問題，Algorand 引入了一個(gè)隨機(jī)的、不斷更新的種子參數(shù) Q（r），Q（r） 與交易集本身相互獨(dú)立，因此惡意節(jié)點(diǎn)無法通過調(diào)整交易集而獲利。

當(dāng)區(qū)塊非空時(shí)，Q（r） = H（SIG（Q（r-1），r） （其中，SIG 為 本輪 leader 的簽名）

當(dāng)區(qū)塊為空時(shí)，Q（r） = H（Q（r-1），r）

可以看出，Q（r） 在每一輪都發(fā)生變化，且與交易本身無關(guān)。可以證明，當(dāng) Q（r-1） 是隨機(jī)的，則 Q（r） 也是隨機(jī)的。因此惡意節(jié)點(diǎn)無法通過改變交易集影響下一個(gè)種子的生成。其中，Q（1）的定義沒有在相關(guān)文獻(xiàn)中找到。

回溯系數(shù) k

種子參數(shù)降低了惡意節(jié)點(diǎn)預(yù)測 leader 的可能性，但擁有多個(gè)潛在 leader 的惡意節(jié)點(diǎn)仍可以有比普通節(jié)點(diǎn)更高的概率成為下一個(gè)區(qū)塊的 leader，但這個(gè)概率會隨著區(qū)塊的變多而逐漸變小。因此，Algorand 引入了一個(gè)回溯系數(shù) k，第 r 輪的候選組只從 r-k 輪已存在的候選組中選取，惡意節(jié)點(diǎn)在 r-k 輪能夠影響第 r 輪候選組的概率極低。

一次性公鑰

上一節(jié)中提到，Algorand 從協(xié)議層面的分叉僅在理論上可能發(fā)生。在實(shí)際中，如果惡意節(jié)點(diǎn)可以挾持其他節(jié)點(diǎn)，仍可以在驗(yàn)證組被公開的瞬間，強(qiáng)制這些節(jié)點(diǎn)重新簽名新的區(qū)塊，從而產(chǎn)生短暫的分叉。Algorand 引入了一種一次性公鑰的機(jī)制，以杜絕這種可能性。

具體原理是所有節(jié)點(diǎn)在加入 Algorand 網(wǎng)絡(luò)時(shí)（即發(fā)生第一筆交易時(shí)），都生成足夠多的一次性公鑰，并公布。這些公鑰將用作后續(xù)所有輪次的簽名驗(yàn)證，并且每個(gè)公鑰只使用一次，一旦被使用后就銷毀。一次性公鑰的生成過程需要一定的時(shí)間，在 Algorand 的典型實(shí)現(xiàn)中，每個(gè)新節(jié)點(diǎn)需要約 1 小時(shí)來生成未來 10^6 輪的所有公鑰（約 180 MB 數(shù)據(jù)）。雖然這增加了節(jié)點(diǎn)加入時(shí)的門檻，但可以從根本上杜絕上述分叉攻擊：因?yàn)橐坏┖灻瓿?，公鑰即被銷毀，即使被惡意節(jié)點(diǎn)劫持，也無法再次簽名產(chǎn)生分叉。

2.7 Algorand 的可擴(kuò)展性

對于目前大多數(shù)去中心化區(qū)塊鏈，如比特幣，以太坊以及 Qtum 等，可擴(kuò)展性的主要瓶頸在于所有鏈上計(jì)算都要進(jìn)行全網(wǎng)驗(yàn)證，而達(dá)成全網(wǎng)共識往往需要一定的時(shí)間。Algorand 采用 PoS+VRF 機(jī)制進(jìn)行隨機(jī)選擇區(qū)塊生產(chǎn)者和驗(yàn)證者，無論網(wǎng)絡(luò)中有多少節(jié)點(diǎn)，每一輪都只需要在少數(shù)節(jié)點(diǎn)上進(jìn)行驗(yàn)證，大大提高了共識速度，提高可擴(kuò)展性。同時(shí)，Algorand 還采用了改進(jìn)的拜占庭共識 BA*，該協(xié)議可以減少共識節(jié)點(diǎn)之間的通信量，從而進(jìn)一步提高共識速度。

此前 Algorand 發(fā)布了其性能測試數(shù)據(jù)，結(jié)果表明，在 1000 臺 EC2 服務(wù)器（AWS 虛擬云服務(wù)器）、500，000 用戶場景下，Algorand 網(wǎng)絡(luò)確認(rèn)時(shí)間穩(wěn)定為 1 分鐘，吞吐量約為比特幣網(wǎng)絡(luò)的 125 倍。（比特幣約為 7 TPS）且吞吐量不會隨著節(jié)點(diǎn)數(shù)的變多而明顯下降［1］。

Algorand 的優(yōu)缺點(diǎn)

通過上述分析，Algorand 基本解決了第 2 節(jié)開頭提出的一系列問題：

· 通過 PoS 和可驗(yàn)證隨機(jī)函數(shù)（VRF）實(shí)現(xiàn)區(qū)塊生產(chǎn)者和驗(yàn)證者的選擇

· 通過改進(jìn)的拜占庭共識 BA* 對新產(chǎn)生的區(qū)塊達(dá)成共識

· 通過一定的參數(shù)設(shè)計(jì)，從數(shù)學(xué)上將分叉的概率降至極低值

· 引入種子參數(shù)，回溯系數(shù)以及一次性公鑰等機(jī)制進(jìn)一步增強(qiáng)安全性

· 每一輪都只進(jìn)行局部驗(yàn)證，并通過減少節(jié)點(diǎn)間通信量進(jìn)一步提升系統(tǒng)的吞吐量，提高可擴(kuò)展性

Algorand 在可擴(kuò)展性，安全性和去中心化程度三個(gè)方面達(dá)到了一個(gè)很好的均衡，但這不意味著其真的打破了所謂的”不可能三角“。

可擴(kuò)展性方面：本質(zhì)上還是通過較少的驗(yàn)證節(jié)點(diǎn)對所有交易進(jìn)行驗(yàn)證，當(dāng)網(wǎng)絡(luò)中全節(jié)點(diǎn)變多時(shí)，只能保證性能不下降太多，不是真正意義上的可擴(kuò)展。另外，每一輪驗(yàn)證節(jié)點(diǎn)之間的通信依賴于所處的網(wǎng)絡(luò)狀態(tài)，網(wǎng)絡(luò)不穩(wěn)定將導(dǎo)致共識時(shí)間變長，影響 TPS。官方稱 Algorand 在 Permissinoed 環(huán)境下將有更好的性能［4］，原因可能在于 Permissionless 環(huán)境下節(jié)點(diǎn)所處環(huán)境有太多不確定性，會在一定程度上影響可擴(kuò)展性。

安全性方面：Algorand 本質(zhì)上采用的還是拜占庭共識，惡意節(jié)點(diǎn)不能超過 ?，而比特幣可以在惡意節(jié)點(diǎn)數(shù)小于 ? 的情況下保證安全。

去中心化方面：Algorand 采用 PoS 共識和 VRF 決定區(qū)塊生產(chǎn)者和驗(yàn)證者，擁有較多代幣的節(jié)點(diǎn)在 PoS 過程中被選中的概率較高，且 Staking 獎(jiǎng)勵(lì)向大戶集中，有一定的中心化趨勢；而 VRF 選舉機(jī)制的引入讓鏈上計(jì)算只由部分節(jié)點(diǎn)進(jìn)行驗(yàn)證，損失了去中心化系統(tǒng)全網(wǎng)驗(yàn)證的特性。

此外，Algorand 的主網(wǎng)剛剛發(fā)布［6］，此前所有結(jié)果均是理想環(huán)境下的數(shù)據(jù)，且部分代碼未開源，虛擬機(jī)相關(guān)設(shè)計(jì)也暫未提及，其實(shí)現(xiàn)的復(fù)雜度、穩(wěn)定性和實(shí)際性能還有待時(shí)間的檢驗(yàn)。

總結(jié)

Algorand 通過創(chuàng)新共識協(xié)議設(shè)計(jì)，同時(shí)實(shí)現(xiàn)了較高的可擴(kuò)展性，較好的安全性和一定程度的去中心化，并且所有結(jié)論都有較為嚴(yán)格的數(shù)學(xué)證明，是一種較為創(chuàng)新和嚴(yán)謹(jǐn)?shù)墓沧R機(jī)制，目前較適用于有一定準(zhǔn)入門檻的去中心化、高吞吐量加密數(shù)字貨幣項(xiàng)目。