可驗證隨機函數VRF之Algorand演算法

DFINITY的閾值接力結構與可驗證隨機函數（VRF）密切相關，VRF演算法作為一種基於密碼學的新型共識模型被提出，最大的優勢是快速共識、抗攻擊能力、極低算力需求（較高的經濟性），業界已問世的解決方案有圖靈獎得主Micali提出的Algorand演算法和DFINITY中基於BLS的演算法。這一篇將對Algorand演算法做一個解析。

作者：叢宏雷

Algorand論文地址

Algorand設計考慮

演算法假設：

1. 網路中誠實節點的數目始終佔優。

2. 節點可以自由地隨時加入網路，而不需要申請。

網路中每個節點通過一個公鑰地址（同時也是錢包地址）表示，對於新加入的節點地址，只有被網路中其他節點轉賬成功（即錢包餘額大於0）後，才可以參與到網路中的區塊共識。

3. 攻擊者也是動態變化的（誠實節點隨時可能變為攻擊者）。

網路假設：

網路消息傳播時間上限：固定時間內完成對固定比例的用戶的網路傳播。

比如，比特幣：1KB消息，在1秒鐘內完成全網95%的傳播，而1MB消息需要1.5分鐘完成全網95%的傳播。

Algorand的性質

l 可控制的分叉風險，（足夠小概率的分叉可能性，）

l 需要很少的計算量

l 鏈上生成一個塊的延遲近似於在網路中完成區塊廣播的延遲

l 不要求網路節點7x24在線 （Lazy Honesty）

Algorand演算法

leader的選擇

可能的攻擊：

1. 儘管可以通過對上一個區塊的哈希計算來確定構建下一個區塊的leader節點和verifier set節點，但是由於哈希函數自身的性質，攻擊節點只需要在區塊中添加一些微小的改動就可以很大影響下一個區塊的leader節點的選擇，從而破壞leader／verifier的隨機性。為保證完全隨機，在區塊中引入block quantity，Qr（r為第r個塊）一個區塊的Qr值只有在當前區塊的leader在整個網路中被揭曉時才能最終確認，從而使攻擊者無法事先攻擊。

2. 即使leader／verifier的選擇是完全隨機的，攻擊者也有可能在leader／verifier被揭曉的同時，馬上攻擊這些節點，從而控制leader/verifier。為解決這個問題，採用的方案是設計多個潛在的leader，並且每個潛在leader都獨立完成區塊的構建，然後每個潛在leader都將自己的認證信息，構建的區塊一起發送到網路中，通過共識演算法選定真正的leader。由於在真正leader的身份在被揭曉之前，網路已經完成了區塊數據的廣播，即使攻擊者攻陷了真正的leader也無法改變區塊的數據。

3. 演算法中，區塊生成都需要經過若干步驟，如果在演算法執行過程中verifier節點被攻擊，比如網路被斷開，可能造成演算法無法持續執行下去，從而造成整個區塊無法確認，整個網路被停滯。而且，也無法要求每個節點都7x24在線，始終為整個網路進行服務。因此設計演算法支持player-replaceable，從而使任何節點都可以隨時被其他節點接管。

具體演算法：

輸入參數：（r, Qr-1）：其中r為第r輪（第r個區塊），Qr-1為上一個區塊的Qr值

判斷節點是potential leader的條件：

H（Sig（r, 1, Qr-1）） <= 1 / size(PKr-k)

size(PKr-k)為第r-k輪中網路中參與區塊共識的公鑰個數（也就是錢包的數目）

所有potential leader中哈希值最小的為真正的leader

verifier的選擇

定義回看參數k，概率p

輸入參數：（r, s, Qr-1）: 其中r為第r輪，s為第s步，Qr-1為上一輪的Q值

判斷方法：對於i，如果 H（Sig(r, s, Qr-1)）< p，則i為verifier

Qr的計算

如果leader_r存在而且在給定的時間內發布了對應的credential：

Qr = H(Sigleader_r(Qr-1), r-1)，即首先用leader對於Qr-1的簽名，再對簽名和r-1計算哈希

否則: Qr = H(Qr-1, r-1)，即對Qr-1和r-1計算哈希

一次性密鑰

節點密鑰只用於以下用途：

1. 網路支付

2. 生成本節點的認證證書（credential）

3. 認證一次性密鑰

對於節點在網路中發送的每個消息，採用一次性密鑰進行簽名。因此攻擊者無法盜取消息密鑰對網路消息進行改寫。

m次Binary BA

m次Binary BA演算法所有節點，執行m步下列消息傳播，在每一步：

1. 每個節點發送比特b和簽名Sigi(r, s)給網路中所有節點（包括自身）

2. 每個節點收集網路中廣播的消息

3. 判定：

a) 如果＃s(0) >= 2t + 1，則設定 b = 0

b) 如果＃s(1) >= 2t + 1，則設定 b = 1

c) 否則設定b為所有接收到消息的節點的消息簽名的最小哈希值lsb

b = lsb(min H(Sigi(s)))

通過以上演算法可以證明，拜占庭環境（n，t）配置下，如果 n>= 3t + 1，達成共識的概率 >= m

也就是說，在每一步開始達成共識的概率至少為

Algorand實現

演算法參數選擇：

n t : 每個驗證組中存在的攻擊節點最大數目，即BFT演算法中的f

n k：回看參數，在r－k輪共識時有效的網路節點才能參與到此輪共識

n p：每個驗證組中節點占共識演算法所有參與節點的比重，控制驗證節點組的大小

n r：網路傳播時間界限內消息在網路中的reachability, r(n – t)

n A：區塊數據的傳播延遲

n ?：哈希數據的傳播延遲

整個共識演算法分為3+m步，每一步都定義嚴格的時間界限。

第一步：為潛在leader向網路傳播備選區塊，所需時間依賴於區塊數據大小，定義時間界限為A

後續步驟都只包含共識區塊的哈希值，定義每一步的時間界限為?

每一輪共識演算法所需要的嚴格時間界限為：T = A + (m+2) ?

1. 潛在leader生成備選區塊

如果一個節點判斷自己為潛在leader，執行以下操作

1. 搜集待執行的事務，構建一個儘可能大的區塊，組成PAYi,

2. 構造備選區塊Bi, r = (r,

3. 生成一個一次性密鑰對，對H(Bi,r)進行簽名

4. 銷毀密鑰對的私鑰

5. 向網路廣播消息mi,(r, 1) : 第i個節點，在第r輪的第1個step中發出的消息

a) 節點的leader credential ＝ Sigleader_r(r, 1, Qr-1)

b) 一次性公鑰

c) 添加一次性公鑰後的COMi(r)

d) 備選區塊Bi,r

e) 一次性密鑰對備選區塊的簽名

2. 第二驗證組驗證備選區塊

如果一個節點判斷自己為(r, 2)的驗證組，執行以下操作：

1. 等待給定時間（系統配置時間A）完成對備選區塊的收集

2. 驗證消息的正確性

3. 計算所有備選leader的credential的哈希，選擇最小的哈希值為實際leader

4. 驗證實際leader發送過來的區塊內容的有效性，否則設置區塊為空塊，得到實際區塊B

5. 生成一個一次性密鑰對，對H(B)進行簽名

6. 銷毀密鑰對的私鑰

7. 向網路廣播消息mi,(r, 2)

a) 當前驗證節點的verifier credential =

b) 一次性公鑰

c) 添加一次性公鑰後的commitment COMi(r)

d) 實際區塊的哈希值

e) 一次性密鑰對實際區塊哈希值的簽名

f) 實際leader所發消息的（a, b, c, e）項內容

3. 第三驗證組收集驗證結果

如果一個節點判斷自己為(r, 3)驗證組，執行以下操作

1. 等待系統給定時間（A+?），收集第二驗證組的驗證結果

2. 如果存在>=2t+1個驗證節點對某個區塊的完成驗證，則執行如下操作

a) 生成一個一次性密鑰對，對對應區塊的哈希進行簽名

b) 銷毀密鑰對的私鑰

c) 向網路廣播消息mi,(r, 3)

i. 當前驗證節點的verifier credential

ii. 一次性公鑰

iii. 添加最新一次性公鑰後的commitment，COMi(r)

iv. 一次性密鑰對實際區塊哈希值的簽名

4. 第四驗證組進行0/1投票

如果一個節點判斷自己為(r, 4)驗證組，執行以下操作

1. 等待系統給定時間，收集之前驗證組的驗證結果

2. 計算分級共識

a) 如果存在 >= 2t+1個驗證節點對某個區塊完成驗證，v = x, g = 2

b) 如果存在 >= t+1個驗證節點對某個區塊完成驗證，v = x, g = 1

c) 否則 g ＝

3. 如果 g = 2，設定 b = 0，否則設定 b = 1

4. 生成一次性密鑰對，對b進行簽名，然後銷毀私鑰

5. 向網路發送消息 mi,(r, 4)

a) 當前驗證節點的verifier credential

b) 一次性公鑰

c) 添加最新一次性公鑰後的commitment，COMi(r)

d) 一次性密鑰對b的簽名

5. 後續(5 - 2+m)驗證組持續投票

此步驟為循環執行，直至達成共識。如果共識，執行步驟6.

如果一個節點判斷自己為(r, s)驗證組，執行以下操作

1. 等待系統給定時間，收集之前驗證組的投票結果

2. 計算分級共識

a) 如果存在 >= 2t+1個節點投票為0，b = 0

b) 如果存在 >= 2t+1個節點投票為1，b = 1

c) 否則設定b為

3. 生成一次性密鑰對，對b進行簽名，然後銷毀私鑰

4. 向網路發送消息 mi,(r, s)

a) 當前驗證節點的verifier credential

b) 一次性公鑰

c) 添加最新一次性公鑰後的commitment，COMi(r)

d) 一次性密鑰對b的簽名

6. 完成區塊簽名

1. 等待系統給定時間，收集投票結果

2. 如果超過2t+1個節點投票為0，選定B為實際leader所提供的區塊，否則設定B為空塊

3. 生成一次性密鑰對，對H(B)進行簽名，並銷毀私鑰

4. 向網路發送消息mi,(r, s)

a) 當前驗證節點的verifier credential

b) 一次性公鑰

c) 添加最新一次性公鑰後的commitment，COMi(r)

d) 一次性密鑰對H(B)的簽名

至此完成共識：

Br = B

CERTr = { mr, 3+m }