以太幣交易所 以太幣交易所
Ctrl+D 以太幣交易所
ads
首頁 > OKB > Info

Libra 采用的 HotStuff 算法作者親述:「尤物」誕生記_LIB

Author:

Time:1900/1/1 0:00:00

Facebook公布了Libra白皮書和相關技術文檔之后,鏈聞發現了Libra區塊鏈將使用基于拜占庭容錯共識的「LibraBFT」共識算法,而LibraBFT算法則是「HotStuff」的一個變種。之后,鏈聞又順藤摸瓜,找到了「HotStuff」論文的第一作者、美國康奈爾大學大學在讀博士生尹茂帆,請他講述了HotStuff的奧妙。

TedYin今年25歲,目前導師是著名計算機科學家EminGünSirer教授和RobbertvanRenesse教授。他同時也是市場頗為矚目的區塊鏈新項目AvaLabs的聯合創始人和首席系統架構師。

2018年暑期期間,他在VMwareResearch實習時提出了「HotStuff」協議中核心算法,并完成了相關論文。

我們邀請TedYin撰文分享了他提出「HotStuff」核心算法前前后后的經歷。我們希望通過這篇文章,記錄下一個創新性算法被年輕華人研究者提出的背景,一個有可能推動區塊鏈技術發展的基礎性研究工作完成的來龍去脈。我們希望以此幫助讀者更好理解「HotStuff」,更可以激勵區塊鏈行業的研究者和開發者更好地建設。

撰文:TedYin,康奈爾大學博士生,AvaLabs的聯合創始人兼首席系統架構師

TedYin,HotStuff論文第一作者,AvaLabs的聯合創始人和首席系統架構師。

一入系統深似海

沒想到,HotStuff,這個被我中文起名為「尤物」協議的科研成果,或多或少竟源自于我第一個「失敗」的研究。請容我細細說來。

2016年,博士之旅伊始,我的導師EminGünSirer教授便拿出幾份論文讓我細細研讀。其中有:

PaxosMadeModeratelyComplex;

ByzantineQuorumSystems;

ImplementingFault-TolerantServicesUsingtheStateMachineApproach。

這些都是共識協議研究經典中的經典。更沒想到的是,有一天,我竟有幸與ByzantineQuorumSystems的兩位作者合作完成了后來的尤物協議。

Moonbeam與Equilibrium進行跨鏈互連合約集成:5月12日消息,Moonbeam宣布與Equilibrium進行跨鏈互連合約集成,通過Moonbeam將Multichain橋接的跨鏈資產引入Equilibrium。Moonbeam和Equilibrium之間由社區批準的雙向HRMP通道使GLMR、EQ Token和EQD穩定幣能夠在鏈之間移動,并且已支持來自Polkadot生態系統外部的橋接流動性,這展示了Moonbeam互連合約策略的潛力。[2023/5/12 14:59:08]

相較于人工智能的論文,計算機系統相關的研究論文篇幅都較長,一般有十來頁。而共識協議算法的論文每一頁的難度又令人望而卻步。在理解了共識問題的基礎以及經典算法以后,一次開會中,Gün教授開始考我了。本來胸有成竹的我,被他連珠炮一般的問題問得說不出話來。

「看來你需要回去重新讀一遍啦,Ted!」,他淡然一笑,「不必擔心,本來這世界上沒多少人懂Paxos。」

在1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法,很多大型分布式系統都采用Paxos算法來解決分布式一致性問題,Paxos算法被普遍認為難以理解,難以實現。)

我愧色滿面,倉皇逃出了辦公室。于是下決心要把其中邏輯理清,以至無懈可擊。

「異步」難題

共識協議,或者推廣至各種分布式系統的協議,是一類基于時態邏輯的算法描述,其難點在于「異步」。

所謂異步,就是若干個相對獨立邏輯可以同時執行,并且它們之間能夠依據算法發生交互。這里的「異步」與異步協議中異步所指不同,更接近于并發的概念。

其實在日常生活中,我們也無時無刻不進行這種「異步」的操作:我們不會干等一天別人的消息,也不會在整個項目所有的事情做完后才睡覺休息。我們往往是會「同時」處理若干個不同的事務,盡量不會因為一件事沒有做完而被卡住不做后續的所有事情。

這種等待著一件事情完成再處理另一件事情的過程,就可以被稱為「同步」;而把事情做一部分丟給別人,接著馬上進行其他操作的過程中,則產生了「異步」。

正如生活中的多任務同時處理一樣,帶有異步/并發性質的算法設計充滿了挑戰。以Paxos算法為例,它是一種對宕機有一定容忍度的冗余算法。用通俗的話講,也就是我們希望有若干個機器去備份同一個系統狀態。這個狀態可以是用戶的信息、銀行的交易,或者平臺上程序的執行序列。這種「備份」,使得整個系統有一定的抗故障能力——一臺帶狀態副本的機器崩潰之后,我們仍然有別的機器可以使用。

聲音 | 前美財政部長顧問:Libra還只是一個投機性的概念,即使能夠實現也不會是由臉書:金色財經報道,美國財政部部長姆努欽前顧問Craig Phillips在接受專訪時表示,我的職務只是Ripple公司的獨立董事,并不是他們公司的員工或者執行董事。由于我相信區塊鏈的未來,所以我決定加入一個創造了區塊鏈應用場景的公司Ripple。很多人正在討論著區塊鏈,但是Ripple還沒有創造出一個可行的商業模型,讓更多的人愿意使用它。對中國來說,就像我之前說過的,一個財務上穩健的數字貨幣是非常不錯的主意。這樣會在中國的國內產生一個數字貨幣。當人們希望把資金轉出或者轉入中國時,數字化的支付系統將會使這種國際化轉賬變得容易很多。這種轉變對于包括Ripple在內的很多全球區塊鏈參與者來說都是一個正面的信息。Libra現在還只是一個投機性的概念。我認為即使這個概念能夠實現,也應該會是其他公司或者實體,而不是臉書。[2019/11/13]

Paxos作為這類協議的代表已經在業界獲得了廣泛的使用,比如Google的Spanner系統。毫不客氣地說,云服務和大規模數據中心的崛起,重要原因之一就要歸功于此。美國計算機科學家萊斯利·蘭波特提出了Paxos算法,這成為讓他在2013年獲得圖靈獎的重要原因之一——當然,蘭波特有太多的貢獻了,包括后文會提到的拜占庭容錯算法,這里就不一一展開了。

不過,像Paxos這類算法因為需要保證系統各個機器同時處于一致的狀態,以便對外表現為一個不間斷的服務,因而十分難以設計和理解。

當然,我的那個故事的結局是:重新來過,認真鉆研,自信滿滿地再次接受也解答了Gün教授提出的若干個刁鉆的問題,最終通過了他的考驗。

「那么接下來我希望你思考一下能不能基于區塊鏈的結構設計一個CFT算法,打敗Paxos。」Gün教授說。

「好的。」我回答到。

雖萬難吾往矣

就這么簡單的一句話,花去了我整整第一年一個學期的時間。

現在回想,這個過程短暫又漫長,時而枯燥無味,但時而又充滿驚奇。我曾經構想出了一些看似正確的算法,但僅僅過了一天,隨即便發現無法證明,或者算法本身存在錯誤。直到在第一個暑假來臨前,我向導師提交了一份關于這方面研究的報告。

聽證會 | 扎克伯格:若Libra協會投票在美國監管批準前推行Libra,Facebook將被迫退出:金色財經直播報道,在今日聽證會上,密歇根州議員Huizenga提問稱,你說Facebook在獲得美國全面監管批準前不會在任何地區發行,如果Libra協會投票決定無視這一點推行Libra,Facebook會作何決定?扎克伯格表示,如果Libra協會21個成員投票后決定在美國監管批準前推行Libra,那么我想真的到了那個時候Facebook將被迫退出協會。此外,Huizenga表示,在我認為,Facebook是一個工具,加密貨幣也是一個工具,就像其他技術一樣,我們可以就把其看作像汽車、刀具、武器一樣,技術和工具的誕生是為了為人類社會帶來益處,但就像剛才議員提到的,伴隨著這些技術的背后我們面臨著很多非法活動和恐怖主義危機,我很想就這個問題繼續我們的談話,但時間已經用盡。[2019/10/23]

在報告中我分析了嘗試用鏈式結構打敗Paxos的各種大方向。其中主要分為兩種:

一種路線是采取類似原中本聰共識中的概率模型,然后通過隨機的等待時間來建立起一個可以收斂的共識鏈;

另一種截然不同的思路則是像Paxos那樣,使用子集交來把Paxos「編碼」在鏈上。

在報告中,我給出了基于Python快速構建的Raft和第一種路線的性能對比,得出了不成功的結論。而Gün教授對另一個路線并不持樂觀態度——因為Paxos/Raft現在已經被優化得很快了,在這種只有宕機的容錯場景下是不具備優勢的。

我們決定放棄這個CFT相關的研究,我也轉而有了一個新項目,也就是后來的Avalanche協議。它是一種概率安全的拜占庭容錯協議,這里暫不展開。

有趣的是,報告提到的兩條路線中,第一個正好和早期的DPoS思路如初一轍。DPoS是一個備受爭議的協議,它在早期并不是拜占庭容錯的,而且協議本身沒有嚴格的證明或者性能的測試,主要使用它的EOS虛擬貨幣,也淪為了一個高度中心化的系統。而第二個路線,如果將問題的領域由宕機容錯變為拜占庭容錯,Paxos改換成DLS/PBFT,則像極了后來的尤物協議。

一拍即合

聲音 | Calibra首席運營官:愿意接受Libra發薪 但Facebook目前沒有相關計劃:今日,在于以色列特拉維夫舉行的Ethereal峰會上,Calibra首席運營官(COO)Tomer Barel表示,Libra是開源的,不受單一實體的控制,這將使Libra成為一個公用的、非私有貨幣。但Barel也承認,盡管Libra的目標是與Facebook保持一定距離,但讓公眾相信這一點是個挑戰。 Barel還表示,自己“絕對愿意通過Libra獲得薪資”。但他Barel也指出,Facebook目前沒有這樣做的計劃。(Decrypt)[2019/9/15]

17年秋季學期即逝,我向VMwareResearch的首席研究員DahliaMalkhi表達了實習的意向。

當年12月,在清華—康奈爾區塊鏈研討會期間,Dahlia和VMwareResearch的高級研究員IttaiAbraham飛到深圳,短暫參會并作了學術報告。報告內容是關于BFT協議在區塊鏈時代下的新研究課題。期間,他們宣布發現了2007年獲得SOSP最佳論文的ZyzzyvaBFT系統存在的正確性問題,借此說明BFT協議過于復雜和難以理解,以致在業界無數專家審稿的10年以后,仍然可能會發現算法層面的正確性bug。

我們在她宣講的當天吃了早飯,席間她簡短地用了30分鐘問了一些關于我目前科研的問題作為面試。

Dahlia在業界以一針見血和才思敏捷著稱,在挺過了她的一些關于Avalanche協議的一些尖銳問題后,她表達出了對我一開始那個「夭折」CFT項目的濃厚興趣。在次年的遠程交流中,她提到了一個在構想的BFT算法有些類似于我的項目,并且詢問我當初放棄的原因。之后我們一拍即合,去VMwareResearch實習的事情也就這么定了下來。

太平洋的風

實習就這么開始了。從東岸的紐約飛到了西岸的加州。美好的灣區,全新的暑假。烈日下,太平洋的風時而撥弄著我手中的紙頁,我則低頭繼續思考著「誰是壞人,誰是好人,誰又背叛了誰」的問題——拜占庭容錯。

Dahlia告訴我說,一般世界各地的博士生來這里實習的頭一周都不需要做什么,而是應該去嘗試摸清自己的能力,以及尋找感興趣的項目。彼時,她提到希望我能看一下他們于三月份撰寫的文稿。

動態 | 自特朗普發推抨擊Libra后 Facebook的股票一直處于停滯狀態:據CCN報道,自7月11日特朗普發推抨擊Libra以來,Facebook的股票一直處于停滯狀態。上周五收盤后,Facebook股價跌至199.31美元,較7月11日的水平低了約1%。雖然跌幅并不大,但這確實讓Facebook走上了與股市其他公司不同的軌道。納斯達克綜合指數自7月11日收盤以來上漲134.17點,漲幅1.6%,標準普爾500指數上漲25.95點,漲幅0.9%。[2019/7/29]

我喜憂參半。「喜」是因為有明確的文稿可以閱讀,「憂」則是這個預印稿是不是意味著算法已經設計完畢,而我能做的事所剩無幾?

實際上,在「掙扎」著閱讀了一周以后,我發現初稿中描述的算法很是模糊,正確性的證明也是一筆帶過,其中兩個核心引理都是一句話。于是,在商議后,我們做了一個后來覺得極為明智,但對我來說也十分挑戰的決定:我不去看那篇預印稿,而是從一張白紙開始,憑著自己受到的啟發,結合已有的積累,用我的符號系統來重新描述算法,并且嘗試給出嚴格的證明。

整個過程大概又花費了將近一周,最后我將重寫的幾頁稿子交給了Dahlia。令我欣喜的是,得到的反饋非常鼓舞人心。Dahlia說我自己重頭設計的算法在本質上和她當初的構想大體相似。

但是不久她就發現了一個很不一樣的地方:我的協議里面需要的假設比原本的預印稿的要更少。

我的解釋是,原稿里面維護的變量和隱含條件過多,而且有的好像也不是必要。我相信「簡單即是優美」的原則,于是去掉了一些覺得冗余的不變量。

瞬間,Dahlia變得嚴肅認真了起來,直截了當地說,「不,這個簡化會直接破壞協議的正確性」。

好在我已早有準備,向她解釋了這個「重要」條件其實是不必要的。但是她依然堅持。

討論變得逐漸激烈,于是我壯了膽,帶著十足底氣的口吻「挑戰」道:「Ifso,couldyoupleaseshowmeacounterexample?」她立即開始在眼前的白板上寫寫畫畫,我全神貫注,準備迎接對我思維以及口語表達的挑戰。

在她數次嘗試失敗之后,我再次耐心地解釋了一遍無需那個條件的原因。我說,聽上去確實挺反直覺的,我一開始也覺得困惑,但是后來發現證明正確性并不需要它。最后,她將馬克筆緩緩放下,笑著長出了一口氣說,「目前我想不到反對的理由。Ted,你贏了。哈哈。」

證明不是一筆揮就的。我一開始自鳴得意的證明很快就被Dahlia發現了一個致命問題:有一個條件從來沒有用過。和之前我們所爭論的冗余條件不同,我們都意識到這是一個極為關鍵的條件,奈何找遍了整個證明都沒有!

這種感覺就像是修好一個機器后發現手頭多了一些零件,又或是做完手術發現金屬盤里多出了一些器官一般。所幸的是,很快我們發現了其中一句話其實暗含了條件,但欣慰之余又感嘆就算是專業人士,做這種BFT協議也是十分棘手。

隨后,我們計劃將舊稿替換成現在重寫的新稿。

高手過招

Dahlia一直是我最敬重的學者之一,因為她平易近人,跟年輕人打成一片,而在討論學術問題時又有著淵博的知識儲備和學者的嚴肅威嚴,討論細致入微,不讓毫厘。

老實說,在討論中,大多數時候還是她取得了「勝利」。跟高手「過招」,我不得不嘆服她思維的深度、廣度和速度。這也是跟她合作的樂趣:就像是一場賽車比賽,稍一不留神,她就在彎道直接超車,一騎絕塵了;或是在你飛速狂奔而不知其所往時將其橫刀攔下,使之冷靜下來解釋清楚。

不久,坐在旁桌的MikeReiter也加入了我們的討論。我對計算機安全領域的大佬知之甚少,自然也是不知道這位Mike的來頭。只是當時覺得他特別友善,還經常來問我需不需要來看一眼我的稿子,或者討論一下算法問題。

MikeReiter,現為北卡羅來納大學教堂山分校計算機系教授

他也對HotStuff感興趣,于是我們便有了三人的開會小組。再后來我才意識到,原來最早讀的那篇于1998年發表的著名論文「拜占庭仲裁系統ByzantineQuorumSystems」,正是Dahlia和Mike在AT&T實驗室工作時期所合著的成果。那時的我還在幼兒園留著口水,咬著手指。

1998年發表在學術期刊「分布式計算」上的論文「Byzantinequorumsystems」

相比Dahlia,Mike更像是那種深藏不露的掃地僧。他時常會在你作報告加速時打斷,慢條斯理道:「恕我愚鈍,但是我不理解你剛剛說的東西,你能再解釋一遍嗎?」而我逐漸察覺到他懂的其實遠比看上去的多,總能在關鍵的地方提出非常好的問題。一旦他和Dahlia爭論起來,我幾乎無法插嘴,只好在一旁以崇敬的目光看著兩位「神仙大戰」。

猶物之生

Dahlia提起了最初的論文稿其實投了2018年的PODC會議,結果被拒。原因有二:審稿人覺得這論文寫得太籠統,他們沒能理解算法的具體過程,以及證明過于簡陋;另一方面則是他們認為實用拜占庭容錯算法的期刊版本已經在其中「暗示」了可能存在線性復雜度的換屆,所以論文號稱的線性換屆并不是新東西。

Dahlia對第一點心服口服——這也是讓我不看原文重頭寫過的原因之一。但她對第二點不以為然,因為她去找來了那個期刊論文,所謂「暗示」并不可行。

就這一點,我們兩人在一次討論中對PBFT期刊版本的算法進行了剖析,最終得出了一個好消息和一個壞消息:好消息是PBFT的換屆做不到線性,也就是審稿人的說法有誤;但壞消息是,Dahlia的舊稿里面的算法并不符合標題所說的完全線性,而是有更深層次的微妙之處。

就在這次和Dahlia對PBFT期刊版本的討論中,我們得到了新的思路

實際上,為了保證響應度,不得不變成平方復雜度;或者為了線性復雜度而放棄響應度。無論何種取舍,皆使我們的貢獻度大幅縮水——這朵烏云不幸地于周五飄在了頭頂,在這淪為「incrementalwork」的陰霾下我們若有所思地開始了周末。

柳暗花明

山重水復后,我席間提到的一個思路給了Dahlia新的啟發。于是,在那個周日的下午,當我還在家慵懶地用筆記本看新聞時,突然收到了一封她上千字的郵件。

果然,在我們的HotStuff體系中,盡管最初的算法跟Tendermint本質相仿,但還有別的變種可以打破這種壁壘:在保證與PBFT類似響應度的同時,達到線性的消息復雜度下界,即理論最優。值得一提的是,前面提到的Paxos同樣也是線性復雜度。

主要思路就是那天討論中我突發奇想提到的:「如果我們增加一個階段呢?兩個階段的協議變三個階段,但是好像我們可以用中間階段維護的不變量來避免Liveness的問題,從而完全保證響應度。」

于是,便有了第三版的「尤物」,也是Facebook的LibraBFT所基于的那個。

盡管在最終發表的論文中,我被列為第一作者,但是這個算法的提出,與Dahlia和Mike等經驗豐富學者的緊密協作及相互間激發出的靈感密切相關。我也很開心,能夠在VMwareResearch短暫的暑假實習期間完成「尤物」的主體部分算法。

在實習結束之后的半年間,我們堅持不懈地完善理論和代碼,并且也嘗試向業界推廣該成果。我們都對創造可以用于實際系統的協議充滿熱情,也都對理論和系統實踐有著一定經驗。Dahlia顯然比我擁有更多的經驗和更深刻的認識,我從她身上學到了很多。令人感動的是,她對我的思考和每一個建議都認真加以考慮,并且也充分信任我的一些觀點——這使得我憑借自己對系統和這個行業的理解能有所施展。

例如Facebook的Libra技術文檔中反復提到的「起搏器」,就是由我提出并取的名字。當時我看到HotStuff框架提供了一次從算法層面對共識安全和性能的機會,然后在第一次描述算法時就將保證系統安全的部分抽離出來,然后將與具體應用相關的heuristics部分分離成為一個「起搏器」,來拯救Liveness。

這一點,毫無疑問,是談論HotStuff無法避開的有趣話題。

我真心期待這個「尤物」,能夠讓無論是國外還是國內的巨頭,抑或是創業公司,能夠真正構建實際的拜占庭容錯系統。毫無疑問,Facebook首先嘗了鮮。

我們在2018年向他們推薦了「尤物」,而后如技術文檔中所說,在考慮了市面上諸多其他算法后,他們作出了決定。

與此同時,我也向一些國內的創業公司宣傳了算法。遺憾的是我跟國內大公司并沒有機會接觸,只聽說他們在共識上栽了不少跟頭。

諷刺的是,如今的市場上,極大一部分區塊鏈公司并沒有實現所謂的區塊鏈,遑論拜占庭容錯。殘酷的現實就是,就算從Google、Facebook或是阿里、騰訊等公司抓出最優秀的程序員,其中能夠熟練掌握Paxos、且知曉如何從頭構建這樣高效系統的人屈指可數。

但是我們不要感到灰心喪氣,因為這反而是對國內產業的一個前所未有的,趕超世界最領先水平的機遇。除比特幣和以太坊之外,一個合格的、成熟的新BFT容錯系統尚未誕生,誰將摘取這個王冠——更確切的是,哪些公司將彎道超車,這尚未可知。

我希望「尤物」能夠拋磚引玉,為此鋪平道路。

Tags:LIBLIBRADAHACELIBRAFLibra Incentixdah幣最新消息TRACE幣

OKB
重磅|2019年第二季度dapp.com去中心化應用市場報告震撼來襲_DAP

Dapp.com聯合金色財經重磅發布2019年第二季度去中心化應用市場報告!Dapp在第二季度保持強勢,并未受牛市影響增長放慢,而且活躍用戶數、交易金額和交易量達到歷史最高水平.

1900/1/1 0:00:00
Facebook推出穩定幣Libra 北大、人大和浙大的專家們怎么看?_ACE

7月8日,在北京舉辦的數字金融開放研究計劃啟動儀式暨首屆學術研討會上,北京大學數字金融研究中心主任黃益平、中國人民大學中國普惠金融研究院院長貝多廣教授、浙江大學互聯網金融研究院院長賁圣林、上海交.

1900/1/1 0:00:00
全球七成央行都在研究的數字貨幣到底是什么?_CBD

希望, 是藏在群山后的星星。 byTychoBrahe|全球央行都在冒什么險?||你會活在怎樣的未來?|盡管起初帶著濃重的烏托邦DNA,誰也不會否認,今天數字貨幣的發展極大地受到了政府政策和官方.

1900/1/1 0:00:00
交易所如何跟項目方共贏—專訪Bitsdaq創始人兼CEO Ricky Ng_BIT

近日BTC漲幅連創新高,基本站穩了1萬美元,2萬USD站崗的韭菜們眼看似乎就要解套了。隨著市場回暖,新老韭菜又活躍了起來.

1900/1/1 0:00:00
火幣Labs總經理楊錦炎:Libra穩定幣的監管與合規問題研究_LIB

Libra穩定幣的監管與合規問題研究 楊錦炎 Libra穩定幣的出現,使得研究中心化的非主權貨幣如何合規落地到不同主權國家與地區的問題成為迫切.

1900/1/1 0:00:00
ICON即將推出P-Rep節點選舉 重磅開啟全新生態_CON

隨著區塊鏈行業的發展以及行業應用的需求,現有的底層基礎架構,例如比特幣或者以太坊,其實很難實現大規模商業應用.

1900/1/1 0:00:00
ads