上交所技術(shù)公司? 朱立
Algorand、Dfinity和Ouroboros Praos三個(gè)共識(shí)算法（Dfinity雖然是項(xiàng)目名蘑险，這里用來(lái)稱呼其共識(shí)算法也應(yīng)無(wú)不妥）近期較受關(guān)注，而且都是基于VRF(Verifiable Random Function) 設(shè)計(jì)，可以對(duì)照學(xué)習(xí)。Algorand的版本很多绷柒，以下單指?1607.01341v9，暫稱其為Algorand'（筆者手中另有Algorand的最新版本涮因，其中已對(duì)下文提及的幾處問(wèn)題完成了修正废睦，可與本文參看）。
一养泡、VRF的共性
VRF的意義很好理解——用以完成出塊人（群）的隨機(jī)選擇嗜湃。為此，VRF的返回值應(yīng)盡力難以預(yù)測(cè)澜掩。先看Algorand'和Dfinity的套路是怎么做的：大體上是先將前一個(gè)隨機(jī)數(shù)（最初的隨機(jī)數(shù)卻是協(xié)議給定的）和某種代表高度购披、輪次的變量進(jìn)行組合，用某種私鑰對(duì)之進(jìn)行簽名（或者是先簽名再組合）肩榕，最后哈希一下得出最新的隨機(jī)數(shù)刚陡。這樣產(chǎn)生的隨機(jī)數(shù)旁人很容易驗(yàn)證其合乎算法，"V"就這樣得到了株汉；而哈希返回值又是隨機(jī)分布的筐乳，“R”也因此得到保證。在此過(guò)程中乔妈，為降低操縱結(jié)果的可能性蝙云，有兩個(gè)注意事項(xiàng)：A) 簽名算法應(yīng)當(dāng)具有唯一性，也就是用同一把私鑰對(duì)同樣的信息進(jìn)行簽名褒翰，只有一個(gè)合法簽名可以通過(guò)驗(yàn)證——普通的非對(duì)稱加解密算法一般不具備這個(gè)屬性贮懈，如SM2匀泊。如果用的簽名算法沒有這種uniqueness屬性优训，那在生成新隨機(jī)數(shù)的時(shí)候就存在通過(guò)反復(fù)多次嘗試簽名以挑出最有利者的余地，會(huì)降低安全性各聘。B) 避免在生成新隨機(jī)數(shù)時(shí)將當(dāng)前塊的數(shù)據(jù)作為隨機(jī)性來(lái)源之一揣非，比如引用本塊交易列表的merkle root值等等，因?yàn)檫@樣做會(huì)給出塊人嘗試變更打包交易順序躲因、嘗試打包不同交易以產(chǎn)生最有利的新隨機(jī)數(shù)的余地早敬。在設(shè)計(jì)和檢視新的共識(shí)算法時(shí)，以上兩個(gè)注意事項(xiàng)是要特別留意的大脉。
考察一下VRF的返回結(jié)果應(yīng)該如何運(yùn)用搞监。目前所見用法中，VRF的返回結(jié)果可以用來(lái)公開完成節(jié)點(diǎn)或節(jié)點(diǎn)群體的選擇镰矿，也可以私密地完成選擇琐驴。以Dfinity為例，它是利用mod操作來(lái)唯一、公開地確定一個(gè)Group绝淡。Algorand'宙刘、Ouroboros Praos是私密選擇的范例，大致套路是對(duì)VRF的最新返回值牢酵，配上輪次等變量后用私鑰進(jìn)行簽名并哈希悬包，如果哈希值小于某個(gè)閾值，節(jié)點(diǎn)就可以私密地知道自己被選中馍乙。這種方法很可能在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較多時(shí)的表現(xiàn)會(huì)更穩(wěn)定布近，否則幸運(yùn)兒個(gè)數(shù)上下波動(dòng)會(huì)較大，進(jìn)而影響協(xié)議表現(xiàn)丝格，包括空塊和分叉吊输。
二、簡(jiǎn)評(píng)強(qiáng)同步假設(shè)版本的Algorand'
私密選擇提供了較強(qiáng)的抗擊定點(diǎn)攻擊的能力铁追，但由于幸運(yùn)兒的總數(shù)對(duì)于任何一個(gè)幸運(yùn)兒都是不能預(yù)知的季蚂，也因此給后續(xù)共識(shí)算法的設(shè)計(jì)和區(qū)塊鏈的優(yōu)化帶來(lái)了困難。Algorand‘采用了很強(qiáng)的同步網(wǎng)絡(luò)假設(shè)（同步網(wǎng)絡(luò)假設(shè)下的共識(shí)算法當(dāng)然容易做一些）琅束，要求預(yù)先知道網(wǎng)絡(luò)消息傳播時(shí)間的上限：在固定時(shí)間內(nèi)完成對(duì)固定比例的用戶的網(wǎng)絡(luò)傳播扭屁。比如要知道，1KB消息涩禀，在1秒鐘內(nèi)完成全網(wǎng)95%的傳播料滥，而1MB消息需要1.5分鐘完成全網(wǎng)95%的傳播。但這個(gè)傳輸上限應(yīng)該如何選擇艾船？ 通過(guò)一段時(shí)間的統(tǒng)計(jì)結(jié)果再乘以一個(gè)系數(shù)這種經(jīng)驗(yàn)統(tǒng)計(jì)葵腹？只能說(shuō)“感覺上可以”，但如果要嚴(yán)謹(jǐn)和安全屿岂，Algorand‘算法應(yīng)該補(bǔ)充證明即使在遭遇DDOS或互聯(lián)網(wǎng)擁堵的情況下消息傳播嚴(yán)重超限后算法仍然能夠保證安全——然而這個(gè)證明是缺失的践宴。作為對(duì)照，Ouroboros Praos公開承認(rèn)之前在同步網(wǎng)絡(luò)假設(shè)下設(shè)計(jì)的Ouroboros協(xié)議在異步網(wǎng)絡(luò)條件下會(huì)出錯(cuò)爷怀，所以才又做了Ouroboros Praos阻肩；新版本的Algorand承認(rèn)在弱同步網(wǎng)絡(luò)時(shí)會(huì)在不同的塊上達(dá)成共識(shí)（后續(xù)網(wǎng)絡(luò)恢復(fù)強(qiáng)同步時(shí)分叉可以得到解決）云云，這些都可資參考运授。
即使我們暫且認(rèn)可Algorand'算法可以通過(guò)設(shè)定一個(gè)很大的傳播時(shí)間上限來(lái)回應(yīng)上述問(wèn)題烤惊，但隨之而來(lái)的是此時(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特性的共識(shí)算法再配以同步網(wǎng)絡(luò)假設(shè)會(huì)非常理想——出于安全雄右，上限可以設(shè)置很大剥啤，然而協(xié)議執(zhí)行速度只和當(dāng)時(shí)網(wǎng)絡(luò)條件有關(guān)。Algorand'并不具有這種特性不脯。平均而言府怯，Algorand'完成共識(shí)所需的消息傳送次數(shù)是11輪，每輪如果要確保安全防楷，完成共識(shí)的時(shí)間就會(huì)很長(zhǎng)牺丙，單個(gè)分區(qū)的吞吐量就不會(huì)太高。當(dāng)然复局，架構(gòu)設(shè)計(jì)涉及很多取舍冲簿，最終評(píng)價(jià)一個(gè)算法好還是不好還是要回到初心——準(zhǔn)備拿來(lái)實(shí)現(xiàn)的目標(biāo)是什么。上述分析只是嘗試客觀地指出Algorand'算法的幾個(gè)少為人知的固有特征亿昏，供讀者自行評(píng)估峦剔。
三、簡(jiǎn)評(píng)Dfinity的可擴(kuò)展性問(wèn)題
私密選擇并且立即上任的做法角钩，也給系統(tǒng)分片帶來(lái)了極大挑戰(zhàn)吝沫。Dfinity是明確要做分片(Sharding)的，所以必須直面挑戰(zhàn)递礼〔蚁眨可擴(kuò)展性問(wèn)題非常復(fù)雜，完整解決這個(gè)問(wèn)題需要通盤考慮網(wǎng)絡(luò)脊髓、存儲(chǔ)辫愉、計(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)了飄忽來(lái)去的出塊節(jié)點(diǎn)選擇痰腮，存儲(chǔ)節(jié)點(diǎn)是沒法同樣飄逸如風(fēng)的。明顯的選擇有那么幾個(gè)：全部節(jié)點(diǎn)存儲(chǔ)全部數(shù)據(jù)涛贯，不同節(jié)點(diǎn)靜態(tài)地分配用來(lái)存儲(chǔ)不同分區(qū)诽嘉。前者的可擴(kuò)展性很差蔚出，對(duì)于后者而言弟翘，如果出塊節(jié)點(diǎn)漂浮不定且出塊節(jié)點(diǎn)還需要完成合約運(yùn)算，就意味著基于P2P網(wǎng)絡(luò)來(lái)回遠(yuǎn)程訪問(wèn)存儲(chǔ)骄酗，性能多半急劇下降稀余；動(dòng)態(tài)決定的出塊節(jié)點(diǎn)只完成排序共識(shí)，計(jì)算能力和存儲(chǔ)捆綁趋翻，通過(guò)靜態(tài)分區(qū)提供可擴(kuò)展性睛琳，可能是合理的應(yīng)對(duì)。然而，最可恨的就是“然而”二字——即使如此师骗，系統(tǒng)還存在一處對(duì)存儲(chǔ)和網(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)自己知道，那無(wú)論是用戶還是出塊節(jié)點(diǎn)候選人看起來(lái)最直接的應(yīng)對(duì)之道就是全網(wǎng)泛濫傳播全部待打包交易厂置、保存全部待打包交易菩掏，這樣帶寬和存儲(chǔ)仍然成為系統(tǒng)瓶頸。
所以這里碰到的昵济，本質(zhì)上還是安全智绸、可擴(kuò)展性、去中心化的不可能三角访忿。
四传于、簡(jiǎn)評(píng)Ouroboros Praos
BM懟 Ouroboros的文字已經(jīng)流傳廣泛。BM的話當(dāng)然有些明顯是不對(duì)的醉顽，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS沼溜，但其關(guān)于Pareto分布的評(píng)論則值得玩味。如果我們仔細(xì)瀏覽后出的Ouroboros Praos游添，可以發(fā)現(xiàn)協(xié)議的安全假設(shè)和安全證明完全沒有考慮經(jīng)濟(jì)博弈因素系草，因此洋洋灑灑的證明很可能會(huì)不得要領(lǐng)而錯(cuò)過(guò)真正需要防護(hù)的方向——畢竟一直以來(lái)POS/DPOS這些協(xié)議的血管里面流淌的就是基于經(jīng)濟(jì)博弈和人性進(jìn)行設(shè)計(jì)的血液。最明顯的例子是在forward secure signature的實(shí)現(xiàn)方法上唆涝，協(xié)議目前的設(shè)計(jì)是要求每個(gè)好的節(jié)點(diǎn)自覺主動(dòng)地安全刪除用過(guò)的私鑰找都，而完全沒有考慮近乎零的私鑰保存成本如何面對(duì)bribe attack的誘惑，然而這卻是值得考慮的廊酣。除了形式化證明之外能耻，Ouroboros Praos本身并沒有太多值得關(guān)注的協(xié)議特征，總體上就是用VRF抽簽結(jié)合POS算法并針對(duì)某些安全假設(shè)進(jìn)行了形式化證明亡驰，其做事的態(tài)度是非常值得贊賞的晓猛。
五、總結(jié)
這幾個(gè)算法本身頗有創(chuàng)意凡辱，也很值得學(xué)習(xí)戒职。與此同時(shí)，在看過(guò)以太坊CASPER目前披露的分區(qū)技術(shù)后透乾，筆者的體會(huì)是：區(qū)塊鏈3.0的競(jìng)爭(zhēng)才剛剛開始洪燥，從以太坊團(tuán)隊(duì)的技術(shù)路線看磕秤，他們的技術(shù)考量和選擇要比很多宣稱要超越以太坊的團(tuán)隊(duì)來(lái)得深刻和全面。如果當(dāng)真要超越以太坊捧韵，還是應(yīng)該先從理解以太坊開始市咆。
順便感謝趣鏈邱煒偉博士對(duì)本文的貢獻(xiàn)！
