上交所技術(shù)公司? 朱立

Algorand、Dfinity和Ouroboros Praos三個(gè)共識算法（Dfinity雖然是項(xiàng)目名，這里用來稱呼其共識算法也應(yīng)無不妥）近期較受關(guān)注，而且都是基于VRF(Verifiable Random Function) 設(shè)計(jì)，可以對照學(xué)習(xí)。Algorand的版本很多，以下單指?1607.01341v9，暫稱其為Algorand'（筆者手中另有Algorand的最新版本，其中已對下文提及的幾處問題完成了修正，可與本文參看）。

一、VRF的共性

VRF的意義很好理解——用以完成出塊人（群）的隨機(jī)選擇。為此，VRF的返回值應(yīng)盡力難以預(yù)測。先看Algorand'和Dfinity的套路是怎么做的：大體上是先將前一個(gè)隨機(jī)數(shù)（最初的隨機(jī)數(shù)卻是協(xié)議給定的）和某種代表高度、輪次的變量進(jìn)行組合，用某種私鑰對之進(jìn)行簽名（或者是先簽名再組合），最后哈希一下得出最新的隨機(jī)數(shù)。這樣產(chǎn)生的隨機(jī)數(shù)旁人很容易驗(yàn)證其合乎算法，"V"就這樣得到了；而哈希返回值又是隨機(jī)分布的，“R”也因此得到保證。在此過程中，為降低操縱結(jié)果的可能性，有兩個(gè)注意事項(xiàng)：A) 簽名算法應(yīng)當(dāng)具有唯一性，也就是用同一把私鑰對同樣的信息進(jìn)行簽名，只有一個(gè)合法簽名可以通過驗(yàn)證——普通的非對稱加解密算法一般不具備這個(gè)屬性，如SM2。如果用的簽名算法沒有這種uniqueness屬性，那在生成新隨機(jī)數(shù)的時(shí)候就存在通過反復(fù)多次嘗試簽名以挑出最有利者的余地，會降低安全性。B) 避免在生成新隨機(jī)數(shù)時(shí)將當(dāng)前塊的數(shù)據(jù)作為隨機(jī)性來源之一，比如引用本塊交易列表的merkle root值等等，因?yàn)檫@樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產(chǎn)生最有利的新隨機(jī)數(shù)的余地。在設(shè)計(jì)和檢視新的共識算法時(shí)，以上兩個(gè)注意事項(xiàng)是要特別留意的。

考察一下VRF的返回結(jié)果應(yīng)該如何運(yùn)用。目前所見用法中，VRF的返回結(jié)果可以用來公開完成節(jié)點(diǎn)或節(jié)點(diǎn)群體的選擇，也可以私密地完成選擇。以Dfinity為例，它是利用mod操作來唯一、公開地確定一個(gè)Group。Algorand'、Ouroboros Praos是私密選擇的范例，大致套路是對VRF的最新返回值，配上輪次等變量后用私鑰進(jìn)行簽名并哈希，如果哈希值小于某個(gè)閾值，節(jié)點(diǎn)就可以私密地知道自己被選中。這種方法很可能在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較多時(shí)的表現(xiàn)會更穩(wěn)定，否則幸運(yùn)兒個(gè)數(shù)上下波動會較大，進(jìn)而影響協(xié)議表現(xiàn)，包括空塊和分叉。

二、簡評強(qiáng)同步假設(shè)版本的Algorand'

私密選擇提供了較強(qiáng)的抗擊定點(diǎn)攻擊的能力，但由于幸運(yùn)兒的總數(shù)對于任何一個(gè)幸運(yùn)兒都是不能預(yù)知的，也因此給后續(xù)共識算法的設(shè)計(jì)和區(qū)塊鏈的優(yōu)化帶來了困難。Algorand‘采用了很強(qiáng)的同步網(wǎng)絡(luò)假設(shè)（同步網(wǎng)絡(luò)假設(shè)下的共識算法當(dāng)然容易做一些），要求預(yù)先知道網(wǎng)絡(luò)消息傳播時(shí)間的上限：在固定時(shí)間內(nèi)完成對固定比例的用戶的網(wǎng)絡(luò)傳播。比如要知道，1KB消息，在1秒鐘內(nèi)完成全網(wǎng)95%的傳播，而1MB消息需要1.5分鐘完成全網(wǎng)95%的傳播。但這個(gè)傳輸上限應(yīng)該如何選擇？ 通過一段時(shí)間的統(tǒng)計(jì)結(jié)果再乘以一個(gè)系數(shù)這種經(jīng)驗(yàn)統(tǒng)計(jì)？只能說“感覺上可以”，但如果要嚴(yán)謹(jǐn)和安全，Algorand‘算法應(yīng)該補(bǔ)充證明即使在遭遇DDOS或互聯(lián)網(wǎng)擁堵的情況下消息傳播嚴(yán)重超限后算法仍然能夠保證安全——然而這個(gè)證明是缺失的。作為對照，Ouroboros Praos公開承認(rèn)之前在同步網(wǎng)絡(luò)假設(shè)下設(shè)計(jì)的Ouroboros協(xié)議在異步網(wǎng)絡(luò)條件下會出錯(cuò)，所以才又做了Ouroboros Praos；新版本的Algorand承認(rèn)在弱同步網(wǎng)絡(luò)時(shí)會在不同的塊上達(dá)成共識（后續(xù)網(wǎng)絡(luò)恢復(fù)強(qiáng)同步時(shí)分叉可以得到解決）云云，這些都可資參考。

即使我們暫且認(rèn)可Algorand'算法可以通過設(shè)定一個(gè)很大的傳播時(shí)間上限來回應(yīng)上述問題，但隨之而來的是此時(shí)可以看出此算法缺乏一個(gè)非常好的特性：Responsiveness。這個(gè)特性指的是：若一個(gè)協(xié)議被設(shè)計(jì)為在一個(gè)較大的傳播時(shí)間上限D(zhuǎn)ELTA下工作，但若實(shí)際傳播時(shí)間是較小的delta，則協(xié)議的實(shí)際推進(jìn)步調(diào)將只和delta有關(guān)，這種協(xié)議被稱為Responsive的。具有Responsive特性的共識算法再配以同步網(wǎng)絡(luò)假設(shè)會非常理想——出于安全，上限可以設(shè)置很大，然而協(xié)議執(zhí)行速度只和當(dāng)時(shí)網(wǎng)絡(luò)條件有關(guān)。Algorand'并不具有這種特性。平均而言，Algorand'完成共識所需的消息傳送次數(shù)是11輪，每輪如果要確保安全，完成共識的時(shí)間就會很長，單個(gè)分區(qū)的吞吐量就不會太高。當(dāng)然，架構(gòu)設(shè)計(jì)涉及很多取舍，最終評價(jià)一個(gè)算法好還是不好還是要回到初心——準(zhǔn)備拿來實(shí)現(xiàn)的目標(biāo)是什么。上述分析只是嘗試客觀地指出Algorand'算法的幾個(gè)少為人知的固有特征，供讀者自行評估。

三、簡評Dfinity的可擴(kuò)展性問題

私密選擇并且立即上任的做法，也給系統(tǒng)分片帶來了極大挑戰(zhàn)。Dfinity是明確要做分片(Sharding)的，所以必須直面挑戰(zhàn)?？蓴U(kuò)展性問題非常復(fù)雜，完整解決這個(gè)問題需要通盤考慮網(wǎng)絡(luò)、存儲、計(jì)算三方面的可擴(kuò)展性——時(shí)下大多數(shù)區(qū)塊鏈3.0項(xiàng)目只注意到計(jì)算的分片和可擴(kuò)展性，忽略了其余二者，從而不可能真正實(shí)現(xiàn)理想的擴(kuò)展。由于公鏈節(jié)點(diǎn)網(wǎng)絡(luò)帶寬的制約，計(jì)算合約所需的數(shù)據(jù)通常很難迅速地從一個(gè)節(jié)點(diǎn)拷貝到另一節(jié)點(diǎn)，所以就算用VRF實(shí)現(xiàn)了飄忽來去的出塊節(jié)點(diǎn)選擇，存儲節(jié)點(diǎn)是沒法同樣飄逸如風(fēng)的。明顯的選擇有那么幾個(gè)：全部節(jié)點(diǎn)存儲全部數(shù)據(jù)，不同節(jié)點(diǎn)靜態(tài)地分配用來存儲不同分區(qū)。前者的可擴(kuò)展性很差，對于后者而言，如果出塊節(jié)點(diǎn)漂浮不定且出塊節(jié)點(diǎn)還需要完成合約運(yùn)算，就意味著基于P2P網(wǎng)絡(luò)來回遠(yuǎn)程訪問存儲，性能多半急劇下降；動態(tài)決定的出塊節(jié)點(diǎn)只完成排序共識，計(jì)算能力和存儲捆綁，通過靜態(tài)分區(qū)提供可擴(kuò)展性，可能是合理的應(yīng)對。然而，最可恨的就是“然而”二字——即使如此，系統(tǒng)還存在一處對存儲和網(wǎng)絡(luò)構(gòu)成壓力的所在：最終用戶提交的待打包交易。普通公鏈（先不考慮EOS那種）的帶寬有限，如果用戶提交的待打包交易必須粗放型地全網(wǎng)泛濫傳播，那現(xiàn)有網(wǎng)絡(luò)帶寬可以提供多少TPS？如果出塊節(jié)點(diǎn)是靜態(tài)分區(qū)或者至少提前一段時(shí)間公開知曉，事情尚有回旋余地；如果出塊節(jié)點(diǎn)是如此飄忽不定，而且直到最后一刻也只有這些節(jié)點(diǎn)自己知道，那無論是用戶還是出塊節(jié)點(diǎn)候選人看起來最直接的應(yīng)對之道就是全網(wǎng)泛濫傳播全部待打包交易、保存全部待打包交易，這樣帶寬和存儲仍然成為系統(tǒng)瓶頸。

所以這里碰到的，本質(zhì)上還是安全、可擴(kuò)展性、去中心化的不可能三角。

四、簡評Ouroboros Praos

BM懟 Ouroboros的文字已經(jīng)流傳廣泛。BM的話當(dāng)然有些明顯是不對的，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS，但其關(guān)于Pareto分布的評論則值得玩味。如果我們仔細(xì)瀏覽后出的Ouroboros Praos，可以發(fā)現(xiàn)協(xié)議的安全假設(shè)和安全證明完全沒有考慮經(jīng)濟(jì)博弈因素，因此洋洋灑灑的證明很可能會不得要領(lǐng)而錯(cuò)過真正需要防護(hù)的方向——畢竟一直以來POS/DPOS這些協(xié)議的血管里面流淌的就是基于經(jīng)濟(jì)博弈和人性進(jìn)行設(shè)計(jì)的血液。最明顯的例子是在forward secure signature的實(shí)現(xiàn)方法上，協(xié)議目前的設(shè)計(jì)是要求每個(gè)好的節(jié)點(diǎn)自覺主動地安全刪除用過的私鑰，而完全沒有考慮近乎零的私鑰保存成本如何面對bribe attack的誘惑，然而這卻是值得考慮的。除了形式化證明之外，Ouroboros Praos本身并沒有太多值得關(guān)注的協(xié)議特征，總體上就是用VRF抽簽結(jié)合POS算法并針對某些安全假設(shè)進(jìn)行了形式化證明，其做事的態(tài)度是非常值得贊賞的。

五、總結(jié)

這幾個(gè)算法本身頗有創(chuàng)意，也很值得學(xué)習(xí)。與此同時(shí)，在看過以太坊CASPER目前披露的分區(qū)技術(shù)后，筆者的體會是：區(qū)塊鏈3.0的競爭才剛剛開始，從以太坊團(tuán)隊(duì)的技術(shù)路線看，他們的技術(shù)考量和選擇要比很多宣稱要超越以太坊的團(tuán)隊(duì)來得深刻和全面。如果當(dāng)真要超越以太坊，還是應(yīng)該先從理解以太坊開始。

順便感謝趣鏈邱煒偉博士對本文的貢獻(xiàn)！