深度解析Algorand共識協議

概述1.1 引言Algorand 稱其突破了”公鏈不可能三角“，專案創始人是圖靈獎得主、MIT CSAIL 實驗室的 Silvio Micali 教授。Algorand 提出的共識協議是專案的一大亮點，本文主要分析 Algorand 共識協議的工作原理，並分析其優缺點。1.2 Algorand 設計的初衷Algorand 想解決的核心問題是：去中心化網路中低延時（Latency）和高置信度（Confidence）之間的矛盾[1]。其中，延時指從發起交易到確認交易所需要的時間；置信度指的是發出的交易不會再被更改的概率。

在比特幣網路中，為了提高交易的置信度，使用者必須等待 6 個區塊確認（約 1 個小時）的確認延時；而如果選擇低延時，比如少於 6 個確認，甚至是 0 確認，則必然導致低置信度，增加“雙花”攻擊的可能。雙花問題是絕大多數加密數字貨幣的核心問題。比特幣中採用 PoW 共識來解決，但鏈本身仍然有分叉的可能，並且需要較長的共識達成過程和確認時間。同時 Algorand 還想解決比特幣中 PoW 挖礦耗費巨大資源、交易確認時間長、易分叉、網路呈中心化趨勢，可擴充套件性差等問題。1.3 Algorand 是什麼？根據官方描述，Algorand 是一個採用 permissionless 的純 PoS 共識的公鏈專案，結合改進的拜占庭共識協議，可實現快速的交易確認，幾乎不會分叉，並且使用者數可無限擴充套件，不會影響交易確認速度。同時兼顧“可擴充套件、安全性、去中心化”這個“公鏈不可能三角”[2]。（注：”公鏈不可能三角“的正確性和具體定義存在較多爭議[7]。在 Algorand 中：可擴充套件性指在較大使用者規模下仍可實現較高的吞吐量[8]，安全性指的是可以對抗惡意攻擊[9]，去中心化指的是網路完全開放，成為節點沒有任何門檻[10]。）· 可擴充套件性：Algorand 透過可驗證隨機函式（VRF）隨機選擇區塊的生產者和驗證者，一旦得知被選中，生產者或驗證者只需廣播一個簡短的訊息即可證明自己的身份。每產生一個新區塊在網路中需要交換的訊息不會隨著使用者數的增大而改變，，因此即使使用者規模增大，系統仍可保持較高的 TPS（每秒處理的交易數）。Algorand 的 TPS 是比特幣的 125 倍。

· 安全性：由於採用了上述的 VRF 隨機選取生產者和驗證者，並且選取的過程完全由節點獨立完成，因此Algorand 網路中的攻擊者無法預先得知下一個區塊生產者和驗證者，從而也就無法完成攻擊。具體來說，生產者和驗證者的身份只有在他們確定自己被選中並廣播對應的證明資訊時才會被披露，這時攻擊者即使立刻採取各種攻擊手段，也無法阻止關於新區塊的正確訊息在網路中的傳播。· 去中心化：Algorand 中每一輪的區塊生產者和驗證者都是隨機選取的，並且加入網路沒有任何門檻，因此是完全去中心化的。下面詳細介紹 Algorand 的共識協議。lgorand 協議詳述幾乎所有公鏈專案的區塊產生和共識的過程都可以抽象為兩個步驟：1. 選擇出區塊生產者，生成新區塊

2. 其他節點對新區塊達成共識以上步驟週而復始，最終形成一條“不可篡改”的區塊鏈。整個共識過程雖然簡單，但在實際實現中，必須解決幾個關鍵問題：· 如何選擇區塊生產者，且保證公平和不可被預測？· 如何對新區塊達成共識？· 如何避免分叉？

· 如何提高安全性？· 如何擴充套件到更大規模的使用者？比特幣採用雜湊函式的隨機性來確保公平，採用工作量證明（PoW）達成共識，同時能夠在一定程度上抵抗算力攻擊。然而比特幣仍然面臨上述消耗計算資源、確認時間長、易分叉以及擴充套件性差等問題。以 Qtum 為代表的採用純權益證明（PoS）共識機制的專案，同樣採用了雜湊函式，並且不需要消耗大量的計算資源，然而仍然面臨易分叉、安全性及擴充套件性的問題。Algorand 提出了一種新的共識機制解決上述 5 個問題。2.1 基礎知識正式介紹 Algorand 共識協議之前，本文假設讀者基本瞭解以下名詞的含義：

· 雜湊函式（Hash）· 公鑰/私鑰· 數字簽名· 交易· 區塊· 賬本

· 共識· 拜占庭協議（Byzantine Agreement，BA）· 誠實節點· 攻擊節點· P2P 通訊如果讀者對上述概念不理解，請先搜尋相關關鍵詞進一步瞭解，再閱讀以下內容。

2.2 Algorand 的基本過程Algorand 協議可以按照時間順序劃分為不同輪次，每一輪都會達成共識並生成新區塊。其典型的通用過程如下：1. 每一輪共識開始時，隨機選出潛在的 leaders，各自生成新區塊，對新區塊進行簽名和廣播2. 隨機選出驗證組，對 leaders 廣播的新區塊進行驗證，達成共識後廣播確認新區塊，進入下一輪接下來具體討論 Algorand 共識協議細節，本節主要參考[4]。2.3 保證 Algorand 的隨機性：可驗證隨機函式

Algorand 利用 VRF 來選擇區塊生產者和驗證者，保證所有共識參與者都是隨機地、公平地被選出的。可驗證隨機函式（VRF，Verifiable Random Function）是由 Micali 教授等提出的一種偽隨機函式，和普通的隨機函式一樣，對於不同輸入，其輸出也具有隨機性（嚴格來說是“偽隨機”）。其獨特之處在於呼叫者可以提供一個證明，表明這個隨機輸出確實由該呼叫者產生。VRF 可以有多種實現方式，Micali 等人在其原始論文中提供了一種較複雜的實現方式[3]。Algorand 利用雜湊函式和數字簽名的特性，提供了一種較為簡單的 VRF 實現。具體實現方式是呼叫者 i 將輸入 m 透過數字簽名和雜湊函式對映為固定長度的輸出 H[SIGi(m)],即 m -> H[SIGi(m)]。對於任何輸入 m，不同的呼叫者 i 生成的數字簽名 SIGi(m) 都是唯一的；而對於不同輸入，雜湊函式 H 的輸出具有隨機性，因此上述對映符合 VRF 的”隨機性“要求。同時，由於 i 的數字簽名 SIGi(m) 可透過其公鑰對其身份進行驗證，因此其也符合 VRF ”可驗證“ 的特性，SIGi(m) 就是 VRF 中提到的”證明“。這個函式特別適合在所有節點中隨機選擇出共識的參與者，下面具體討論。2.3.1 隨機選出每一輪的區塊生產者（Leader）每一輪共識開始時，每個節點都可以透過以下 VRF 獨立地驗證自己是否是潛在的 leader：

.H[SIG(r, 1, Q(r-1))] <= 1 / SIZE(PK(r-k))其中，H 是雜湊運算；SIG 是簽名運算；r 是目前的輪次；Q(r-1) 為與 r-1 輪的種子（將在後續 2.6 節中解釋）；SIZE(PK(r-k)) 是在 r-k 輪所有符合要求的公鑰的數量（為什麼是 r-k ？k 為回溯係數，也將在 2.6 節中闡述）；公式開始的 . 表示將雜湊結果轉化為小數位，從而保證結果為[0,1)的某個值。節點透過自己的私鑰計算上面簽名的雜湊值是否符合要求，從而知道自己是否屬於候選的 leader，在此過程中無需和其他節點交換資訊。由於雜湊函式輸出的隨機性，可以認為符合要求的候選節點都是隨機選出的。候選節點隨後可以生成新區塊，並向全網提供簽名證實自己的身份。如果有多個候選 leader，最終上述雜湊值最小的 leader 將在後續的共識中成為本輪最終的 leader。Leader 產生的區塊 Br 包含了本輪的所有交易和上述的證明資訊，由驗證組成員進行共識驗證。2.3.2 隨機選出每一輪每一階段的驗證組驗證組成員的選擇與上述過程類似，在每一輪和每一階段（step），所有節點都可以獨立驗證自己是否屬於驗證組成員：.H[SIG(r, s, Q(r-1))] <= n / SIZE(PK(r-k))

其中 s 為本輪所處的不同階段，Algorand 在每一輪的各個階段都有不同的驗證組，從而進一步保證安全性；n 為預期的驗證組成員數量，可以人為設定；其他引數含義不再重複。與候選 leader 一樣，每一階段的驗證組成員均隨機選出，驗證節點在證實自己身份後，可以開始參與共識驗證過程，揭露自己的簽名即可證明其身份。2.3.3 引入權益證明（Proof-of-Stake，PoS）機制上述的隨機選擇過程沒有考慮 Token 持有者的權重，惡意節點可能透過大量生成有效私鑰從而有極大概率成為區塊的生產者和驗證者。Algorand 在其公佈的實現建議中引入了名為 Honest Majority of Money （HMM）的條件假設，其基本思想來源於 PoS 共識機制，即在上述隨機選擇過程中引入代幣持有量（Stake）作為權重，持有量多的節點被選中的概率較高，而代幣持有者往往更傾向於保護網路的安全性。具體可以表示為如下公式：.H[SIG(r, 1, Q(r-1))] <= (a(i,r) / M) * (1 / SIZE(PK(r-k)))

其中，a(i,r) / M 為節點所持有的幣的數量佔代幣總數 M 的權重。其餘過程與前面描述一直。2.4 Algorand 如何對新區塊達成共識：改進的拜占庭協議 BA*Algorand 中驗證者對新區塊達成共識的過程，實際上是一種改進的拜占庭協議（Byzantine Agreement），Algorand 稱其為 BA*。BA* 由一種改進的二元拜占庭協議（Binary Byzantine Agreement，BBA）和分級共識協議（Graded Consensus，Protocol GC）組合而成[5]。2.4.1 改進的二元拜占庭協議 BBA*Algorand 引入的 BBA* 是一個改進的二元拜占庭協議（所謂二元，即只能達成 0 或 1 兩種共識）。BBA* 可以在誠實節點超過 ⅔ 的情況下，快速達成共識。其具體過程是一個 3 步迴圈，迴圈中每一步都有 ⅓ 的概率達成共識。

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

上述協議中各符號的具體含義可參考[4]。所有驗證節點i都有一個初始值 bi（bi = 0 或 1），協議開始時，每個驗證節點都會向其他驗證節點傳送各自的初始值，

協議第一步（Step 1）是歸 0 過程：

如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ⅔ ，輸出共識結果為 0，共識結束，不再執行後面所有步驟
如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ⅔，則該驗證節點把自己的 bi 設為 1
如果收到的 0 或 1 都沒超過 ⅔，則驗證節點把自己的 bi 設為 0
第一步結束節點再次向其他節點傳送各自的 bi

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

如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ⅔ ，輸出共識結果為 1，共識結束，不再執行後面所有步驟
如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ⅔，則該驗證節點把自己的 bi 設為 0
如果收到的 0 或 1 都沒超過 ⅔，則驗證節點把自己的 bi 設為 1
第二步結束節點再次向其他節點傳送各自的 bi

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

如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ⅔，設定 bi = 0
如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ⅔，設定 bi = 1
如果收到的 0 或 1 都沒超過 ⅔，則每個驗證節點會對某個和本輪本階段相關的資訊進行簽名，並對簽名求雜湊。bi 被設定為這些雜湊值中最小雜湊的最低有效位（仍然是 0 或 1）
之後返回第一步，直到達成共識

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

2.4.2 分級共識協議 GC

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

Algorand 採用的 GC 分為兩步（上圖來自 Algorand 白皮書[4]，為了和文中其他部分對應，將兩個步驟命名為 Step 2 和 3），協議開始時，每個驗證節點i各自都有一個初始值 vi（在 Algorand 中即候選的新區塊的雜湊）：

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

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

經過 GC，每個節點都會輸出一個值對 (vi, gi)，輸出規則：

· 當收到 x 的總次數超過總驗證節點數的 ⅔ 時，設定 vi = x， gi = 2；
· 當收到 x 的總次數超過總驗證節點數的 ⅓ 時，設定 vi = x， gi = 1；
· 否則，設定 vi = 空， gi = 0；

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

2.4.3 BA* = GC + BBA*

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

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

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

· 若共識結果為 0，則最終輸出結果為 vi（非空新區塊）
· 若共識結果為 1，則最終輸出結果為空（即新區塊為空）

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

2.5 Algorand 區塊鏈分叉的可能性

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

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

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

· Algorand 遵守中本聰共識中的最長鏈法則
· 如果有多條最長鏈，則選擇包含非空區塊的最長鏈
· 如果仍相同，則可以具體根據區塊雜湊值進行排序選擇

2.6 Algorand 如何保證安全性

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

種子 Q(r)

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

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

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

當區塊為空時，Q(r) = H(Q(r-1),r)

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

回溯係數 k

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

一次性公鑰

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

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

2.7 Algorand 的可擴充套件性

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

此前 Algorand 釋出了其效能測試資料，結果表明，在 1000 臺 EC2 伺服器（AWS 虛擬雲伺服器）、500,000 使用者場景下，Algorand 網路確認時間穩定為 1 分鐘，吞吐量約為比特幣網路的 125 倍。（比特幣約為 7 TPS）且吞吐量不會隨著節點數的變多而明顯下降[1]。

Algorand 的優缺點

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

· 透過 PoS 和可驗證隨機函式（VRF）實現區塊生產者和驗證者的選擇
· 透過改進的拜占庭共識 BA* 對新產生的區塊達成共識
· 透過一定的引數設計，從數學上將分叉的概率降至極低值
· 引入種子引數，回溯係數以及一次性公鑰等機制進一步增強安全性
· 每一輪都只進行區域性驗證，並透過減少節點間通訊量進一步提升系統的吞吐量，提高可擴充套件性

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

可擴充套件性方面：本質上還是透過較少的驗證節點對所有交易進行驗證，當網路中全節點變多時，只能保證效能不下降太多，不是真正意義上的可擴充套件。另外，每一輪驗證節點之間的通訊依賴於所處的網路狀態，網路不穩定將導致共識時間變長，影響 TPS。官方稱 Algorand 在 Permissinoed 環境下將有更好的效能[4]，原因可能在於 Permissionless 環境下節點所處環境有太多不確定性，會在一定程度上影響可擴充套件性。

安全性方面：Algorand 本質上採用的還是拜占庭共識，惡意節點不能超過 ⅓，而比特幣可以在惡意節點數小於 ½ 的情況下保證安全。

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

此外，Algorand 的主網剛剛釋出[6]，此前所有結果均是理想環境下的資料，且部分程式碼未開源，虛擬機器相關設計也暫未提及，其實現的複雜度、穩定性和實際效能還有待時間的檢驗。

總結

Algorand 透過創新共識協議設計，同時實現了較高的可擴充套件性，較好的安全性和一定程度的去中心化，並且所有結論都有較為嚴格的數學證明，是一種較為創新和嚴謹的共識機制，目前較適用於有一定準入門檻的去中心化、高吞吐量加密數字貨幣專案。

參考文獻
[1]https://algorandcom.cdn.prismic.io/algorandcom%2Fa26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf
[2]https://www.algorand.com/what-we-do/technology/core-blockchain-innovation
[3] S. Micali, M. Rabin and S. Vadhan. Verifiable Random Functions. 40th Foundations of Computer Science (FOCS), New York, Oct 1999.
[4]https://algorandcom.cdn.prismic.io/algorandcom%2Fece77f38-75b3-44de-bc7f-805f0e53a8d9_theoretical.pdf
[5]https://algorandcom.cdn.prismic.io/algorandcom%2F218ddd09-8d6f-42f7-9db9-5cfbc0aedbe5_algorand_agreement.pdf
[6]https://www.algorand.com/resources/blog/the-borderless-economy-is-here
[7] https://www.odaily.com/post/5134308
[8] https://www.algorand.com/what-we-do/technology/scalability/
[9] https://www.algorand.com/what-we-do/technology/security/
[10]https://www.algorand.com/what-we-do/technology/permissionless-blockchain/

深度解析Algorand共識協議

推荐阅读

近期文章

新手教程

1什麼是區塊鏈？區塊鏈能做什麼？

2區塊鏈是如何運作的？

3區塊鏈和比特幣的關係？

4比特幣有什麼價值？

5如何購買比特幣？