Algorand共識演算法

可驗證隨機函數VRF與Algorand的共識算法

Published in

CryptoCow

15 min readJan 6, 2019

共識機制一直是區塊鏈領域最重要的議題之一，從比特幣的PoW開始，不斷的有人在改進現有的共識機制，目標無非是為了讓區塊鏈效能繼續優化，並且在速度、安全性以及去中心化三者之間達成平衡。

其中PoS(Proof of Stake)並不是一個新的觀念，其核心思想就是利用持有貨幣的數量而非運算資源來分配使用者在區塊鏈上的權力，持有貨幣越多者越有機會生產區塊。但實際實作的方法中也存在諸多挑戰，例如如何公正選出委員會(Committee)或是下一個區塊產生者(Leader)等等。比較有名的PoS模型有Snow White(NXT)、Ouroboros Praos(Cardano)、還有Algorand等等，今天就來介紹一下相對較新的Algorand演算法。

Algorand: A Pure PoS Consensus Protocol

提出Algorand演算法的是一位圖靈獎的得主Silvio Micali，可以在網路上許多他介紹Algorand的影片中發現，他十分堅持相較於其他現有的實踐方法，Algorand實現的PoS是真正公平的Pure Proof of Stake。因為在他的設計中，貨幣的持有者不需要把某數量的貨幣抵押出去(會有一段時間不能使用)，或是代理(delegate)給其他人來參與PoS共識機制，而是只要自己錢包裡面擁有balance就可以一同參與這個共識機制。

除了這個看似能防止中心化的設計之外，Algorand真正創新的突破在於結合VRF(Verifiable Random Function)的Leader以及Committee抽籤( cryptographic sortition)、防止重要節點遭到惡意使用者攻擊的Participant Replacement機制、以及他們快速在Committee中形成共識的拜占庭共識演算法BA*，以下就來一一介紹。

Verifiable Random Function(VRF)

在Algorand中最重要的一個機制就是引入了VRF — Verifiable Random Function，中文是可驗證隨機函數。簡單的說，VRF能夠由私鑰(SK)以及訊息(X)產生一組可驗證的偽隨機(pseudorandom)亂數Y以及証明⍴。任何人都可以透過Verify函數來檢驗這個隨機字串是否真的是該公鑰對應私鑰持有者，依照規定使用Evaluate函數所產生，而不是自己亂掰的。更詳細一點的VRF三個函示描述如下(from this post)：

Keygen(r) → (VK, SK). On a random input, the key generation algorithm produces a verification key VK and a secret key SK pair.
Evaluate(SK, X) → (Y, ⍴). The evaluation algorithm takes as input the secret key SK, a message X and produces a pseudorandom output string Y and a proof ⍴.
Verify(VK, X, Y, ⍴) → 0/1. The verification algorithm takes as input the verification key VK, the message X, the output Y, and the proof ⍴. It outputs 1 if and only if it verifies that Y is the output produced by the evaluation algorithm on inputs SK and X.

為什麼我們需要這麼一個大家自己產生，卻又要可以被驗證的隨機字串產生器呢？這是因為在Algorand的拜占庭演算法中，雖然也存在著每一輪不同的區塊生產者(稱為Leader)以及驗證委員會(Committee, Verifiers)，但並不是用「公開選舉」的方式來選的，而是透過每個使用者自己對獎的方式來看看自己是不是下一輪的Leader。他們稱之為Cryptographic Sortition，這背後的邏輯便是仰賴VRF的原理。

Cryptographic Sortition

無論是在何種BFT的共識機制中，都是由Leader以及Committee來完成區塊的發布以及共識決議。例如EOS的dPoS BFT是固定21個BP輪流擔任Leader以及投票者、Zilliqa透過PoW加入Committee進行PBFT共識算法。這些比較直觀的拜占庭共識演算法都有一個共同特徵，就是大家都可以看到下一個區塊的Leader是誰，以及負責協議共識的Committee是誰。這造成了一個可能的風險，就是這些區塊生產者以及Committee成員容易成為DDOS或是賄賂的目標。

Algorand為了解決這種潛在的風險，利用VRF來掩蓋Leader Selection的步驟。可以想像成：一般的BFT在每一輪開始時公平公開選出Leader以及Committee，Algorand則是像在每一輪開始時公布中獎號碼，每個使用者都可以自己拿自己的票根對獎，中獎的人即可成為下一輪的Leader(或是Committee Verifier)，但在中獎者自己表明身分前，沒有人知道誰中獎，也就是沒有人能預測下一輪的Leader以及Committee。當然中獎與否並不是口說無憑，中獎者需要出示中獎証明，而這個証明是大家都可以驗證的，這正是我們剛剛說到的VRF。

在每一個新區塊要產生前，每一個使用者都可以透過Sortition()函示，由自己的私鑰配合新一輪的開獎訊息(上述的X)，一起通過VRF中的Evaluate()函示輸出一組偽隨機字串，若剛好幸運符合某些規定，則有資格成為Leader或是委員會的成員(機率與持有貨幣成正比)。若發現自己是Leader，該使用者就會準備好要發布的區塊，附上自己確實中獎的Proof一起廣播出去。同理，後面會提到的共識過程中，每一個需要Committee決議投票的步驟開始前，每一個節點也都先對獎看看自己是否幸運被抽中進入委員會，是的話就把自己的投票(或是其他要協議的值)隨著Proof一起廣播出去。

Sortition()函示，其中return的 π為proof，j為weight，即一個使用者可能被**選中多次**(想像一共要隨機選出1000人的committee, 而一位用者擁有全網20%的貨幣，那他當然應該被選中很多次，因此該使用者在Committee中將會有較高的權重)

細心的你可能會注意到，這種自己在家對獎的模式讓很多人同時成為Leader呢？答案是會的，可能會有多個節點都符合條件成為Leader，但最後大家可以規定簡單的經過hash來排序，決定出Prioroty最高的那個leader，並只幫忙廣播它的區塊。

Participant Replacement

上述的設計對安全性有很大的幫助，由於沒有人能預測參與下一輪共識的成員，所以惡意節點無法事前鎖定要攻擊的對象。當一個惡意節點知道某人是這一輪的Leader時，代表這個訊息已經散布到網路之中，該Leader想要廣播的區塊已經讓網路上的其他節點知道，因此已經可以「功臣身退」，現在才要攻擊它一切都太晚了。同理，在後面所有的共識過程中，在每一個成員廣播出自己決議的同時，投出那一票的瞬間，他們就已經達成了自己此步驟身為委員會成員的義務，而下一個步驟中，又會有新的委員會出現，生生不息的繼續完成每一輪的共識。

這就是所謂的Participant Replacement，每一個共識步驟(每個round的每個step)的決議成員都不同且彼此獨立，使得惡意使用者無法有效率的攻擊這個網路。

小結一下VRF部分，Algorand在每一個區塊leader的產生到共識的每一個決議步驟，都不是事先選擇好，而是當下發現自己有權利參與的節點，在參與共識的同時附上Proof來廣播。這不同於一些BFT模型是節點廣播區塊之後等待某些已知使用者回復簽章，而是Locally收集網路上的各種簽章投票，在幫助gossiping的同時自己運行自己的共識演算法。接著，我們就來看看核心的共識是如何達成的。

BA - Byzantine Agreement

BA*

下圖是整個BA Procedure的pseudocode。Algorand所使用的BA演算法一共分為兩個階段，在第一個階段稱為Reduction，一共會經歷兩個步驟(steps)，把共識問題簡化為二選一選擇題：同意一個Block Hash或是Empty Block Hash。第二個階段則是輸出共識的結果，可能是一個Block Hash代表大家同意該區塊，也有可能是Empty Block。

BA* 還會Output這個共識結果屬於Final或是Tentative，Final代表BA確定與足夠多人達成共識，該區塊不可能被反駁或是為Fork；而Tentative代表可能因為Partition或是網路異步，有其他節點們對另一個Block達成Tentative Consensus。

以下我們就來分層組裝這個BA裡面的運作模式。

Voting

從最簡單的voting開始。以下的pseudocode描述了在每一輪(round)的每一個步驟(step)，一個使用者都要使用剛剛介紹得Sortition()函示來檢驗自己是否有權(以及多少權重)參與共識的投票。

如果 j>0 表示自己有權參與此步驟的共識協議，因此會把自己同意的value透過Gossiping的方式廣播出去。

Counting Votes

這裡的T與τ分別為兩個參數，T代表了該步驟需要多少比例的委員投票，τ則表示該步驟所選出的委員數量。所以T × τ 就是某個值要在這個步驟達成共識所需的總投票數。一旦有某個值value所得票數超過T × τ，CountVotes就會回傳該value。

Reduction

如上面所說，Reduction()是BA*的第一階段，透過兩個步驟將共識問題簡化到要嘛選hblock，要嘛選empty_hash的二選一選擇題。

第一個步驟中，這個Committee member會投票自己原先支持的hblock，並且等著接收其他成員的投票，看看是否有某個block hash的得票數超過threshold( T · τ )。有的話就在第二步中投票給該hash，若是沒有收到任何hash超過threshold，則投給empty_hash。

Binary BA

接著我們來看BA*的第二階段，也就是BinaryBA。這個函示會回傳一個Consensus，也就是一個新區塊的共識結果。由於上一步中Reduction()已經確保了最多只會有一個不為empty_hash的famous block hash，接著就只要在這個最有名的block_hash與empty_hash之間做出選擇。大致的邏輯跟前面類似，投票之後便透過CountVotes()來等待該步驟的投票結果。

可以看到程序中在自己達成consensus之後，會繼續廣播往後三個step對該值(r)的投票訊息(看到step < s < step+3的迴圈)。這是為了讓其他可能處於不同step的誠實節點，也能收到我對於這個block_hash或empty_hash的投票。否則若是大家異步，很有可能一部分的誠實節點在step 1收集到足夠的投票達成共識，但是剩餘的節點在step1沒有成功收集票數，而已經進行到step2 或之後，因此一直無法收集足夠的票數。

Strong Synchrony & Weak Synchrony

而在Weak Synchrony的情況下，可能發生不同誠實節點取得不同Consensus的情況。例如一個節點A在step1就收集了block_hash足夠的投票，但其他所有誠實節點都沒有收集到足夠的票數，因此進行到下一個step並且再次TIMEOUT，所以大家都改投empty_string，因此其他節點在比較後面的步驟中對empty_string達成共識。

這種事情是一般BFT中不常見的，因為通常不會容許一個節點對兩個不同的value簽名。但由於Algorand的投票是有階段性的，一個節點可能在不同的階段發出不同的投票，因此會發生這種看似荒謬的事件。在這種情況下，所有節點都是誠實的但卻沒有達到完全一致的協議，所以Algorand才需要設計FINAL 以及 TENTATIVE來描述一個consensus的狀態。

若是在Strong Synchrony的情況下，大部分的使用者會在step 1 就達成共識，投票給相同的block_hash，這時他們會再進行標記為FINAL的Committee Vote，其他節點若是在BA*最後階段收到足夠多的Final Vote，就會標記這次達成決議的區塊為FINAL，即可以保證其Finality。

反之在剛剛介紹的Weak Synchrony中，由於只有少數人- 節點A在第一輪達成共識，進行CommitteeVote(FINAL, block_hash)，最終BA*無法收集足夠的Final votes，因此會標記該block為TENTATIVE。Tentative翻成中文就是暫時、猶豫的，也就是告訴我們對於該區塊的Finality無法保證，我們必須等到網路回復正常(Strong Synchrony)，並看到這個block之後出現下一個FINAL Block時，才能確保一切不可能被回溯。

這全部合起來就是Algorand的BA共識演算法，對每個區塊的共識，會在這個區塊在網路中廣播的同時就一邊進行。除了這個快速的共識演算法外，Algorand也設計了從Partition中恢復的Recovery機制，使的節點明顯確定網路Partition發生時，可以直接進入Recovery模式等待網路復原，再一起重新同步。不必像個傻B一樣一直做白工。

Committee Size

在Algorand的設計當中每次投票的過程都由不同的Committee負責，很明顯的，要求Committee越龐大代表了越公平、安全，卻勢必會提高溝通造成的延遲。Algorand在他們的實作中選擇把出事機率控制在5*10^-9 以下，由下圖中可以看到，假設80%節點是誠實的，Committee需要2000個成員才夠大。