2018年是公鏈技術爆發的一年，誕生了諸多從共識方面創新的專案。由於目前人們普遍認為存在區塊鏈“不可能三角”，這些共識往往要在效能、安全、去中心化、激勵機制中做出取捨。例如，EOS達成每秒數千次交易速度是以犧牲去中心化為前提的。然而“不可能三角”從來沒有像FLP、CAP這些分散式系統定理一樣得到嚴謹的數學證明，因此有些人認為打破“不可能三角”是有可能的。可驗證隨機函式VRF被認為是一個有前景的方向。本次為大家帶來最近熱度非常高的Algorand專案的分析。1、Algorand共識演算法簡介Algorand共識演算法是圖靈獎獲得者Silvio Micali在2017年底提出。Michali是MIT的教授，是一位密碼學家和計算機理論學家，在偽隨機數以及零知識證明領域很有名。Algorand共識演算法的論文的下載地址：https://people.csail.mit.edu/nickolai/papers/gilad-algorand.pdfAlgorand採用了VRF函式，並結合賬戶的餘額比例，隨機確定區塊生成以及投票人角色。所謂VRF（Verifiable Random Function）就是可驗證隨機函式。

隨機數對於區塊鏈技術來說很關鍵。 本質上，分散式賬本的核心問題就是隨機選擇出塊人的問題，這個隨機性要能被全網確認，並且不能被操控，也不能被預測， 否則惡意節點透過操控這個隨機數就可以操控長鏈，從而實現雙花攻擊。PoW的方案是讓大家進行算力競賽，設定一個計算雜湊的難題，誰先算出來誰贏，算力高的贏的概率高，算力低的贏的概率低，以這樣的方式保證勝出者是隨機的。投入的算力能夠體現在雜湊值上， 這樣全網能夠驗證，並選擇包含最多算力的那條鏈。惡意節點只能透過提升自己的算力來增加攻擊成功的概率。PoS的方案是選舉，大家不用浪費電力去進行算力競賽，而是文明一點，隨機選舉一個節點來出塊，並且被選中的概率和它擁有的份額相關。 如果“隨機”這一步沒有問題的話，惡意節點只能透過增加自己的份額，增加自己被選中的概率，從而增加雙花攻擊的成功概率。 這裡有一點比PoW的方案要好就是，要實現攻擊，先得成為持幣大戶，如果攻擊成功幣價大跌，攻擊者也會承受最大的損失。那麼接下來的核心問題就是，這個不能被操控不能被預測的隨機數從哪來。傳統地PoS方案嘗試從鏈上現有的資料入手，比如使用上一個區塊的雜湊值，上一個區塊的時間戳等等來作為隨機數的來源，但這些會帶來額外的安全風險。 因為區塊本身的資訊就是節點寫進去的，然後又要根據裡面的資訊來選舉後續的出塊者，存在迴圈論證的嫌疑，安全性不會太好。 這也是傳統地認為PoS方案不如PoW可靠的部分原因。Algorand提出的VRF能夠由私鑰( SK )以及訊息( X )產生一組可驗證的偽隨機 (pseudorandom) 數Y以及證明 ⍴。任何人都可以透過Verify函式來檢驗這個隨機字串是否真的是該公鑰對應私鑰持有者，依照規定使用Evaluate函式所產生，而不是自己亂掰的。更詳細一點的VRF三個函示描述如下：• 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 Yand 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。algorand就是透過隨機演算法從一群大範圍的驗證者中選取一部分驗證者執行BFT演算法(Micali教授實現的BA*演算法)，從而達到提高共識的效果。無論是在何種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。2、Algorand共識演算法缺陷(1)現實環境的隨機選擇的空間並不大。

VRF是可以提供了公平且不容易收到偽造和攻擊的委員會隨機選擇方式，但是任何隨機數的生成必須依賴大的種子集合才可以有作用，在VRF中假設80%節點是誠實的，Committee需要2000個成員才夠大，現實情況是不太可能有這麼多成員的。(2)完全沒考慮網路延遲情況。VRF Committee集合選舉時依賴數量龐大的主機通訊的，主機之間相互溝通造成的延遲，必然大大拖慢整個系統的處理速度。(3)沒考慮節點的動態加入和退出情況。Algorand的下一個區塊的釋出者是從k個區塊之前的所有參與者（在k區塊之前的某段鏈上發過交易的節點）裡選。於是，惡意節點想影響下個區塊的釋出者，他得影響k個區塊才行，當k很大的時候，這個影響也是微乎其微。於是，Algorand得到了一個無偏向的隨機數產生器。不過，這個做法有一個問題——k區塊之前的節點，有可能已經不線上了。而對於這一點，雖然Micali做出瞭解釋，但是個人覺得並不符合實際情況。(4)簽名資料龐大，造成儲存浪費並影響效能。

Algorand使用VRF來確定提案組與驗證組，這個方式充分發揮了VRF的可驗證性優勢，且後驗優勢使得Algorand的共識體系更安全。但是，Algorand進入驗證階段，採用的是一種可擴充套件的拜占庭容錯演算法，即BA*演算法，參與節點透過VRF秘密抽籤選出。這一設計使Algorand在驗證前必須等待憑證（VRF prove）到來，才能知曉參與節點。而且，由於使用了可擴充套件的拜占庭容錯演算法，使得Algorand的驗證組規模必須比較大(2000～4000人)，這將導致簽名資料異常龐大。根據我們的估算，在平均每組3000個驗證節點的規模下，每組的簽名資料長達126KB，加上其它資訊，通知資訊約300K，每塊的簽名資料可達2000*64*12=1M（共12組，每組3000人，至少2/3達成共識。ed25519簽名資料長度是64。），遠超一般門限簽名幾十個位元組，嚴重浪費儲存和容量（因每塊儲存的交易量將被佔用，不儲存簽名又會影響安全），不僅造成儲存浪費，而且更影響效能。(5)無法構建很好的激勵機制在POW中，提案者得到提案權需要預先付出算力成本，若其提案區塊有問題（交易雙花），則該提案區塊在全網其他節點驗證必將失敗，從而不但沒有鑄塊收益，還付出了算力成本。Algorand協議並沒有設計經濟激勵機制，Micali教授曾迴應”Algorand協議只需要進行平凡的計算，因此不需要激勵”。在沒有經濟激勵機制下，高效能頻寬和伺服器必然不願意參與（因為它本身要消耗費用），整個網路會遇到網路本身無法解決的困難。(6)存在潛在的安全問題網路使用者必須連續訪問其私鑰，以確定其在每一輪中的VRF狀態（即驗證者、提議者，或者兩者都不是）。

一般認為，對於那些將大量資產儲存在區塊鏈上的個人，為了防止攻擊，他們應該把私鑰以冷儲存的方式進行儲存。而持續的驗證（需要經常簽名）會需要高頻率地動用私鑰，從而增加被攻擊的風險。這顯然將導致網路中很多誠實的個體（出於安全的考慮）會避免參與驗證過程，從而造成區塊鏈缺乏活力的問題。(7)買斷問題在區塊鏈的嬰兒期，系統的通證價值通常較低，其市值也是處在相對較低的水平。Token的發行往往要經過私募-->基石-->公募 等逐步分散的過程，因此很長一段時間裡幣是集中在少數人手裡的，因此任何POS共識都面臨著EOS類似的中心化的問題。(8)沒有懲罰問題Algorand所存在的另一個問題是，沒有辦法識別“離線驗證者”並懲罰它們。因此，在沒有懲罰措施來防止無效的情況下，沒有經濟激勵就是一個問題，很多人會選擇不為共識做貢獻，因此離開這個網路。假設網路中只有10%的誠信節點在不斷地進行驗證，而其餘節點是離線的狀態，與此同時，惡意的節點選擇保持線上，那其就很容易超過線上委員會節點。這使得惡意節點更容易控制共識。總的來說，Algorand的VRF和加密抽籤後驗性給出了一個解決“三角悖論”的很好設計思想，但其在驗證環節的設計更偏單純的學術化理想化，導致其對網路流量、有效通訊資料等實際工程落地思考不夠，嚴重影響了公鏈執行效能、節點網路規模、賬本儲存容量和去中心化程度。

更多區塊鏈資訊：www.qukuaiwang.com.cn/news