Algorand共識算法是圖靈獎獲得者Silvio Micali在2017年底提出。Michali是MIT的教授，是一位密碼學家和計算機理論學家，在偽隨機數以及零知識證明領域很有名。
Algorand共識算法的論文的下載地址：https://people.csail.mit.edu/nickolai/papers/gilad-algorand.pdf。
本文先介紹一下VRF，再介紹Algorand共識算法的流程：
1：VRF（Verifiable Random Function）可驗證隨機函數
從VRF的名字可知，VRF是隨機生成函數，而且這個函數是可驗證的。VRF函數的輸出由兩部分組成：隨機結果以及隨機證明（proof）。
VRF函數的實現一般有兩種：一種基於RSA算法，一種基於EC算法。下圖詳細解釋RSA算法的生成和驗證流程（EC算法邏輯上類似）：
OS2IP是字符串轉整數字函數，I2OSP是整數轉字符串函數，MGF是Mask Generation Function（掩碼生成函數）。從上圖可以看出，驗證數據是RSA的加密結果，驗證過程從RSA的公鑰進行解密驗證。隨機數據的生成是對驗證數據再進行Hash處理。
簡單的說，VRF提供了一個隨機數據生成方法，而且這個隨機過程和私鑰有關，並可以通過公鑰被驗證。
2：Algorand的共識過程
Algorand的共識分為兩個步驟：1）隨機選舉區塊生成者生成區塊 2）形成共識（也就是論文中的BA*算法）。
3：Algorand的隨機選舉
Algorand算法中的節點都有權重（weight），該權重和賬戶的餘額成正比。
上圖中的t是選中的賬戶餘額閥值，w=賬戶餘額/賬戶餘額閥值，也就是說w是賬戶中可以分割成多少個賬戶餘額閥值。利用多項式分佈B(k;w,p)，計算出hash對應的比例在哪個區間內，則最後選中的次數就是多少，也就是最後的j的數值。
特別說明的是，因為共識過程分為兩個步驟，所以隨機選擇也有兩種role：1）生成區塊的選擇 2）共識過程（BA*)選擇。
4：隨機選擇中的Seed
VRF函數中的Seed算法如下：
當前輪（round）的Seed是之前輪的Seed和輪數的VRF的隨機結果。SKu是選擇的生成區塊的節點的私鑰。第一輪的Seed是隨機生成的。
5：Algorand的區塊生成
每個節點在新一輪的開始，都會以“區塊生成者”的role，計算隨機選舉。選中的節點中，生成區塊並且廣播區塊信息。
6：Algorand的BA*算法
BA*算法又分為兩步階段：1）同步確定最大優先級區塊 2）是否該區塊能穩定共識。有關第一階段的過程如下圖所示：
先從節點中，隨機選舉出投票人，第一步：投票人會廣播自己認為的最大比例的區塊，第二步，投票人再次廣播它知道的最大比例的區塊。經過兩步就能確定最大比例的區塊。
有關第二階段，過程和第一階段類似，只是步數可能更多。
總結：Algorand採用了VRF函數，並結合賬戶的餘額比例，隨機確定區塊生成以及投票人角色。根據論文中的模擬數據，比特幣的POW共識換成Algorand共識後，TPS增長125倍。和DPOS+BFT相比，Algorand的安全性更強，只要超過2/3的賬戶餘額是誠實節點，Algorand即安全。
閱讀更多 比特兒大魔王 的文章
