【前沿演算法】Algorand、Dfinity和Thunder共識體系的技術分析
這一期，我們繼續分享共識演算法方面的相關內容。本期主題位置如下：
（獲取完整高清圖請關注"BinSTD"公眾號回覆“技術圖譜”）
在當前的區塊鏈公鏈體系中，有三大當紅專案Algorand、Dfinity和Thunder，因其創始成員來自美國著名大學教授，均以獨特的學術見解和創新的科學方法來提升區塊鏈的去中心化程度、安全性和交易效能，試圖破解區塊鏈領域中著名的“不可能三角”難題。
隨著對這三個專案的深入調查和研究，我們有了進一步的理解，特此撰文分享一些思考和見解:
（1）Algorand可能無法達到所宣稱的高效能，且其去中心化特性存在潛在問題；
（2）Dfinity和Thunder在安全性和效能上都存在較多疑點；
（3）因三者均沒有實際公開上線和工程落地，是否真正解決區塊鏈的“三元悖論”存疑。
此外，值得關注的是，這三個專案都沒有公開相應的Token激勵機制，我們認為會制約參與者的積極性，進而影響其公鏈的生態發展和實用價值。同時，其容量的限制和網路通訊的低效，都會制約其規模應用和實際使用的落地。
1. Algorand共識體系分析
Algorand是一個基於隨機演算法的公有鏈專案, 由MIT著名的密碼學專家、圖靈獎獲得者Micali教授及其團隊提出，其動機是為了解決區塊鏈中由去中心化、安全性以及交易效能三個方面所組成的“不可能三角”難題。該問題也被稱為“三元悖論” ，一般認為在現有區塊鏈技術中這三個方面無法同時滿足，最多隻能滿足其中兩個要素。Algorand其本質是通過密碼學的方法，來做一個隨機數發生器來隨機決定下一個區塊的生成者是誰。如果這個隨機數發生器是完全隨機的，也就是說，任何人（包括上個區塊的釋出者）都無法預測下一個的釋出者是誰，那麼其實這就是一個可用的共識演算法了。
在Algorand演算法裡提出並解決了三個問題，第一個是隨機數發生器，第二個是隨機出來的提案者如何在不洩露自己身份的情況下證明自己，第三個是如何應對不線上的節點。Algorand採用了PoS（Proof of Stake）共識機制的分組方式——包括提案組和驗證組，以解決PoW共識機制所帶來的高能耗問題，並希望同時提升交易效能。
在Algorand方案中，首先每個新區塊是由一個獨立的隨機生成的提案組產生多個提案塊，其成員隨機選擇，期望值為26人。然後再由多個隨機組成的驗證組逐步經多次驗證達成共識。這裡驗證組的個數一般為12組甚至更多，而每組包含2000～4000成員。每個提案組和驗證組都是從所有使用者的集合中隨機選出，以強化去中心化程度。而使用者的賬戶餘額將會影響被選中的概率，並且給予每一個被選中使用者一個優先級別（priority）以及擁有此優先順序的證明。被提議的多個區塊隨後將在全網內通過八卦協議（gossip）傳播，到達下一組進行驗證和共識，直到最終唯一確認，最後唯一獲選的區塊加上各驗證組共識組員簽名信息上鍊。
Algorand的獨特創新是VRF(可驗證隨機函式)和加密抽籤，整體方案具有後驗性。具體而言，使用者是唯一知道自己是否成為某組（某輪的提案組或某步的驗證組）成員的人，他人無法事先獲知，只能等其廣播後驗證，惡意攻擊者甚至無法事先知道組成員是誰，因此不能對他們進行賄賂或發起拒絕服務攻擊，組員間也無法共謀，提高了系統的安全性。
但分析其具體工作機制後，我們發現有以下問題：
1) 簽名資料龐大，造成儲存浪費並影響效能 。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。），遠超一般門限簽名幾十個位元組，嚴重浪費儲存和容量（因每塊儲存的交易量將被佔用，不儲存簽名又會影響安全），不僅造成儲存浪費，而且更影響效能。
2) 演算法對於網路頻寬要求極大，個人使用者很難參與，嚴重影響去中心化特性 。如下圖所示，對照來自於Algorand論文中的公開測試資料，在實驗環境中，Algorand需要讓區塊達到10M大小，才能達到125倍比特幣的效能（約10M-1M=9M，每M儲存的交易數為1萬，則基於Algorand的測試資料，有90000/50=1800TPS，約為比特幣的100多倍）。10M區塊大小意味著要求節點的網路頻寬峰值至少需要80M才能承載，這對目前一般使用者非常困難，影響了系統的效率和去中心化特性。
3) 節點網路規模受限，網路通訊不經濟並影響效能 。當網路規模太小時，將無法組成所需的提案組和驗證組，影響系統正常工作。而網路規模太大時，提案塊（假設大小2M,去除簽名的1M，有效交易儲存空間為1M）和驗證資訊（大小約300K）無法快速傳播到後繼驗證節點，也會影響系統性能。
Algorand即使在驗證環境也需要等待5*10=50s以上（包括等待潛在提案者的時間延遲及其特殊的拜占庭演算法），加上其提案傳播時間10秒，至少需要60秒才能完成一次出塊上鍊。假設一個有效儲存1M（去除簽名後）的塊包含1萬筆交易，則其TPS為10000/60=167。我們預估在全網真實環境下，這個結果會更糟。假設每個驗證組成員為3000個，每次驗證組成員不重複（一般12組甚至更多），則至少需要12*3000=36000個節點。根據下圖所示，一個2M的塊，要傳播到3000個節點，需要36秒，如傳播到36000個節點，可能需要45秒左右甚至更長才能到達第一驗證組。驗證資訊（大小300K）需要9秒左右才能傳播3000個節點，如傳播到36000個節點，可能需要12秒或更久，到達下一驗證組。而其一般要11步或更多才能完成驗證，再加上最後一步，這樣就驗證就需要12*（11+1）=144秒。整個過程需要189秒，其效能僅約53TPS，離專案方宣稱的1000TPS差之甚遠。
4) 賬本資料儲存相對較大 。如前所述，因其採用多步BA共識演算法，其簽名佔據巨大儲存空間，雖然提高了安全性，但影響了效能，也浪費了賬本儲存空間，制約了賬本系統的儲存容量和系統規模。
5) 不具有強的輸出公平性保證 。保證公平性(Bias-resistance)能夠確保協議的輸出不被敵手操縱。然而Algorand為了選擇提案者使用了一個有些偏向的隨機性，使得那些需要真正隨機均勻分佈的應用不適合採用該協議。
總的來說，我們認為Algorand的VRF和加密抽籤後驗性給出了一個解決“三角悖論”的很好設計思想，但其在驗證環節的設計更偏單純的學術化理想化，導致其對網路流量、有效通訊資料等實際工程落地思考不夠，嚴重影響了公鏈執行效能、節點網路規模、賬本儲存容量和去中心化程度。
2. Dfinity共識體系分析
最近一段時間，Dfinity共識體系是被認為較有希望提供高效能交易的區塊鏈公鏈方案之一。為了解決PoW效能低下和高能耗的問題，Dfinity也採用了PoS分組模式。與Algorand不同，Dfinity在Github提供了一個GO語言的概念驗證POC實現。Dfinity用隨機數把礦工分為若干個組，每組400人，組中的一個節點將按順序被選作提案節點，其它節點為驗證節點。每次由隨機數決定下一出塊組，組內隨機輪詢決定下一個出塊提案節點。提案塊全網廣播到同組成員，進行驗證，使用BLS門限簽名來達成組內共識。BLS門限簽名要比Algorand的可擴充套件的拜占庭容錯演算法更有效率，無需像拜占庭容錯演算法那樣多輪的驗證步驟，不但提高了TPS而且還省下了長簽名資料入鏈造成的儲存容量問題。其理論上整個鑄塊時限timeout是10秒，每隔2秒一個提案，且在其testnet上的TPS是2500。我們認為Dfinity在效能方面比Algorand更具優勢。但是因採用了先驗模式，它的安全性不如Algorand。同時其網路通訊效率不高，像比特幣和Algorand一樣，完全靠P2P的傳播，沒有針對分組模式進行設計。容量雖不像Algorand那樣浪費，但最大容量仍受限於全帳節點儲存空間。
1) 不具有後驗性，安全性較差 。雖然有多個組，但各組的成員事先固定，容易被攻擊，也容易組內竄謀，影響安全性。每次出塊組某輪出塊期間只有一個節點被選作提案節點，形成單點故障，又容易受到攻擊，而且無法保證被選提案節點是否線上。同時，組內各成員按順序輪流作提案節點，容易被外界所知，造成安全隱患。因其沒有采用加密抽籤方式，不具有後驗性，因此會受到DDOS攻擊和女巫攻擊。Dfinity也沒有考慮同組的提案人和驗證者聯手共謀的可能，存在被人為控制的隱患。
2) 效能解決方案缺乏魯棒性，而且系統規模受限 。每次隨機抽取的一個提案節點如不線上，需要等待到下一輪，影響出塊速度。提案塊需要廣播到全網，到達同組的其它成員，它們構成了驗證組（400個節點），驗證節點需要等待提案塊的到達，浪費時間而影響效能。驗證組內需要多輪通訊才能達成共識，而400個成員的組內通訊也是依靠P2P的八卦協議，通訊量巨大，效率低下，影響出塊速度和系統性能。假設有10個組，每組400個節點，則系統有4000個節點，按TradeBlock上圖所示，1M的塊需要約18秒傳播到3000個節點，遠超其鑄塊timeout時間，系統無法正常工作，影響系統的穩定性、效能和規模。
3) 網路通訊效率低下 。Dfinity組內的通訊量是O（n^2），400人的組內通訊量大。不論提案塊還是驗證組內共識，亦或是共識塊的上鍊，都依靠P2P的廣播，增加網路傳輸負擔，影響系統效率。
4) 儲存容量受限於單節點的儲存能力 。與比特幣、以太坊和Algorand一樣，其系統容量，受限於單節點的儲存空間，沒有涉及分散式儲存技術的應用和優化。
5) 依賴新的密碼學基（cryptography primitive） 。依賴新的密碼學基（橢圓曲線pairing）和金鑰生成協議，其安全性和效率都有待時間的考驗。
和Algorand對比，Dfinity在效能方面因其分組共識和BLS組簽名有所提高，但其安全性有所下降。其400人分組規模的通訊效率也存在一定問題，我們認為其技術架構和宣稱的去中心化雲服務仍有較大的差距。
3. Thunder共識體系分析
與前兩個專案不同，Thunder是一種Layer2的公鏈解決方案，可用於提升已有的公鏈特性。但與Algorand和Dfinity一樣，Thunder也用分組的方式（其快速通道fast path模式），有1個leader和多個驗證組員，希望提高系統性能，但其選擇leader和組員的方法還在研究中，沒有公開。其快速通道是由系統選出一個leader和多個組員，由leader給出提案塊，然後由組員經BFT驗證達成共識，再由leader傳播全網上鍊。為了彌補安全的不足，它在上面的快速通道模式的基礎上，增加了定期檢查，每次檢查如沒有發現問題，就移動檢查點。一旦發生問題，就在上次的檢查點，啟動慢速通道(慢速通道slow path，比如採用比特幣的POW方式)，讓系統仍能工作，雖然效能低下。
1) 中心化明顯。 Thunder的leader和組員不論如何選取，在被輪換之前，都是固定的，特別是提案、通訊、出塊等都依靠leader，具有濃厚的中心化特徵。
2) 不具後驗性、隨機性不足，且安全性較差 。因為固定的leader和組員，其leader就有作惡的可能，而且成為單點故障。不論組的leader還是組員，都不如Dfinity和Algorand的選取更具隨機性，去中心化不足，因而很容易受到DDOS攻擊和女巫攻擊，同時也沒有考慮提案人leader和驗證者組員聯手共謀的可能。因其組內通訊依靠leader，進一步影響安全性。其安全性要比Algorand和Dfinity稍差。
3) 網路通訊還需要改善 。為了改善組內通訊效率，Thunder所有組內通訊都要經由leader，導致leader的中心化、單點故障（如不線上或作惡），影響通訊效率、效能和安全性。與Algorand和Dfinity一樣，共識塊需要經由P2P全網廣播後上鏈，效率低下。
4) 效能不夠好，儲存容量受限 。因沒有采用組簽名，其儲存效率比Dfinity要差。但因只需一步共識，而且組的規模較小，所以其簽名資料比Algorand要小，儲存效率高於Algorand。其儲存容量也同樣受限於單節點的儲存空間。為保證系統可靠性，一旦檢查出問題，就回退到慢速通道。其慢速通道雖然可以讓系統正常工作，但會影響系統出塊速度，效能較差。
可以看出，Thunder設計了快慢兩種資料同步模式，增加了可靠性，但其去中心化程度、系統安全和交易效能都有所欠缺。
4. 小結和展望
至筆者成文為止，Algorand、Dfinity和Thunder的很多資料還停留在實驗室階段，相關實現程式碼大多沒有公諸於世（除了Dfinity中有的少量PoC部分程式碼開源）。雖然三者都基於各自的學術論文，但其理想化的數學模型，離工程實現和落地相距甚遠。在區塊鏈領域的技術討論中，所謂的“三元悖論”——去中心化、安全和交易效能，這三者只能取其二的說法，並沒有理論邏輯上的支撐，而只是對現有解決方案的觀察。其實，去中心化僅是手段，不是目的。而安全與系統的吞吐能力和容量並不相互矛盾。本文希望就目前當紅明星專案的分析，提出問題，從而可以找出一個融合它們各自優點（如Algorand中後驗的安全性，Dfinity中BLS簽名帶來的效能提高，Thunder的慢速通道的可靠性），形成一個真正可以落地的、更好的解決目前區塊鏈“三元悖論”的共識方法。不僅提高其去中心化、安全性和效能，同時，可以達到規模化應用，突破單節點容量的限制，打造一個“高可用、強安全、高效率”的區塊鏈，真正做到“ 區塊鏈的高可信與中心化的高效率 ”融合並存。此外，我們是否也應該接受不具有同時解決“三元悖論”的理論和技術方法，從而根據具體應用的需求而選擇相應具有特色的共識演算法呢？
ofollow,noindex"> http:// weixin.qq.com/r/X3UXDw7 Ek1PsrUps9yBN (二維碼自動識別)