詳解 Algorand 共識協議的工作原理及優缺點

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* 都可以在驗證節點中達成共識，從而確定新區塊及其包含的交易（有可能為空區塊）。