概述

1.1 引言

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

1.2 Algorand 設計的初衷

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

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

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

同時 Algorand 還想解決比特幣中 PoW 挖礦耗費巨大資源、交易確認時間長、易分叉、網絡呈中心化趨勢，可擴展性差等問題。

1.3 Algorand 是什么？

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

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

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

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

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

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

lgorand 協(xié)議詳述

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

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

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

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

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

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

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

· 如何避免分叉？

· 如何提高安全性？

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

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

Algorand 提出了一種新的共識機制解決上述 5 個問題。

2.1 基礎知識

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

· 哈希函數（Hash）

· 公鑰/私鑰

· 數字簽名

· 交易

· 區(qū)塊

· 賬本

· 共識

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

· 誠實節(jié)點

· 攻擊節(jié)點

· P2P 通信

如果讀者對上述概念不理解，請先搜索相關關鍵詞進一步了解，再閱讀以下內容。

2.2 Algorand 的基本過程

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

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

2. 隨機選出驗證組，對 leaders 廣播的新區(qū)塊進行驗證，達成共識后廣播確認新區(qū)塊，進入下一輪

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

2.3 保證 Algorand 的隨機性：可驗證隨機函數

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

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

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

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

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

每一輪共識開始時，每個節(jié)點都可以通過以下 VRF 獨立地驗證自己是否是潛在的 leader：

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

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

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

2.3.2 隨機選出每一輪每一階段的驗證組

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

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

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

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

2.3.3 引入權益證明（Proof-of-Stake，PoS）機制

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

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

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

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

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

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

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

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

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

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

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

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

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

如果某驗證節(jié)點 i 收到 1 的總數超過總驗證節(jié)點數的 ?，則該驗證節(jié)點把自己的 bi 設為 1

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

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

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

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

如果某驗證節(jié)點 i 收到 0 的總數超過總驗證節(jié)點數的 ?，則該驗證節(jié)點把自己的 bi 設為 0

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

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

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

如果某驗證節(jié)點 i 收到 0 的總數超過總驗證節(jié)點數的 ?，設定 bi = 0

如果某驗證節(jié)點 i 收到 1 的總數超過總驗證節(jié)點數的 ?，設定 bi = 1

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

之后返回第一步，直到達成共識

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

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

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

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

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

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

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

· 當收到 x 的總次數超過總驗證節(jié)點數的 ? 時，設定 vi = x， gi = 2；

· 當收到 x 的總次數超過總驗證節(jié)點數的 ? 時，設定 vi = x， gi = 1；

· 否則，設定 vi = 空， gi = 0；

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

2.4.3 BA* = GC + BBA*

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

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

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

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

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

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

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

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

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

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

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

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

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

2.6 Algorand 如何保證安全性

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

種子 Q（r）

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

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

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

當區(qū)塊為空時，Q（r） = H（Q（r-1），r）

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

回溯系數 k

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

一次性公鑰

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

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

2.7 Algorand 的可擴展性

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

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

Algorand 的優(yōu)缺點

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

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

· 通過改進的拜占庭共識 BA* 對新產生的區(qū)塊達成共識

· 通過一定的參數設計，從數學上將分叉的概率降至極低值

· 引入種子參數，回溯系數以及一次性公鑰等機制進一步增強安全性

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

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

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

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

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

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

總結

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