來(lái)源：大算投

Aleo的共識(shí)機(jī)制,，顯然受到了Sui的Narwhal與Bullshark協(xié)議的深刻影響,，可以認(rèn)為其設(shè)計(jì)靈感幾乎完全來(lái)源于此,。Narwhal與Bullshark的核心優(yōu)勢(shì)在于它們能夠智能地區(qū)分并高效處理各類(lèi)交易類(lèi)型,。

前言

重點(diǎn)概要

涉及個(gè)人資產(chǎn)的交易,，如支付或NFT的鑄造與轉(zhuǎn)移,，可以靈活地獨(dú)立處理,，而不必嚴(yán)格遵循序列化規(guī)則,。相對(duì)地，對(duì)于涉及共享資源的交易,，去中心化交易所（DEX）中的流動(dòng)性池操作或訂單匹配,，就需要按照特定的執(zhí)行順序來(lái)進(jìn)行，以確保在多用戶環(huán)境中實(shí)現(xiàn)公平性和一致性,。

這種設(shè)計(jì)理念賦予了Aleo在處理不同交易需求時(shí)的靈活性和高效性,，確保了其共識(shí)機(jī)制的安全性和效率。

創(chuàng)新共識(shí)設(shè)計(jì)：Aleo的技術(shù)靈感

大算投，探索數(shù)字經(jīng)濟(jì)的奧秘,，洞察區(qū)塊鏈的未來(lái)趨勢(shì)

01

Narwhal通過(guò)創(chuàng)新性地重新定義了分布式賬本的構(gòu)建策略，其關(guān)鍵在于將內(nèi)存池的數(shù)據(jù)流通職責(zé)與共識(shí)層的數(shù)據(jù)排列機(jī)制進(jìn)行了精細(xì)的分離,。

在傳統(tǒng)模式中,，交易需要經(jīng)過(guò)兩次廣播過(guò)程：首先是到達(dá)各個(gè)驗(yàn)證者的內(nèi)存池，然后由區(qū)塊提議者在共識(shí)過(guò)程中進(jìn)行匯總廣播,，這一過(guò)程存在冗余且效率不高,。

Narwhal通過(guò)明確的職責(zé)劃分，消除了重復(fù)傳播的需要,，從而實(shí)現(xiàn)了賬本構(gòu)建的高效率和流暢性,。

與傳統(tǒng)系統(tǒng)相比，基于有向無(wú)環(huán)圖（DAG）的Narwhal與Bullshark共識(shí)架構(gòu),，為每個(gè)驗(yàn)證者提供了獨(dú)立廣播交易批次的能力,，利用Narwhal技術(shù)來(lái)填充其內(nèi)存池。

驗(yàn)證者在接收到交易批次后,，將其作為一個(gè)節(jié)點(diǎn)嵌入到本地DAG結(jié)構(gòu)中,，并通過(guò)對(duì)先前節(jié)點(diǎn)的認(rèn)可與投票來(lái)構(gòu)建節(jié)點(diǎn)間的連接。

這種獨(dú)特的共識(shí)機(jī)制使得驗(yàn)證者能夠基于本地DAG結(jié)構(gòu)自主進(jìn)行交易排序,，而無(wú)需承擔(dān)額外的通信成本,。這一創(chuàng)新設(shè)計(jì)確保了DAG共識(shí)邏輯的高效運(yùn)行，同時(shí)有效控制了通信成本,。

交易處理革新：Narwhal的內(nèi)存池策略

大算投,，探索數(shù)字經(jīng)濟(jì)的奧秘，洞察區(qū)塊鏈的未來(lái)趨勢(shì)

02

Narwhal架構(gòu)是內(nèi)存池的基礎(chǔ)，精心組織每一輪驗(yàn)證者的DAG（有向無(wú)環(huán)圖）結(jié)構(gòu),。這個(gè)DAG由節(jié)點(diǎn)（代表交易批次）和連接它們的邊（指向前一輪父節(jié)點(diǎn)的引用）組成,，如圖1所示,。

驗(yàn)證者之間頻繁交換節(jié)點(diǎn)和邊的信息，以便在本地構(gòu)建一個(gè)一致的DAG視圖,。Narwhal專(zhuān)注于DAG的構(gòu)建,，而其上的共識(shí)機(jī)制負(fù)責(zé)解析其深層含義并作出決策。

圖1展示了基于圓形的DAG組件,，包括頂點(diǎn)（藍(lán)色框）和傳出邊（綠色箭頭表示）

考慮到一個(gè)n3f+1系統(tǒng)，設(shè)計(jì)目的是容忍多達(dá)三分之一的拜占庭節(jié)點(diǎn),。在Narwhal中,，每個(gè)驗(yàn)證者由一個(gè)工作器和一個(gè)主節(jié)點(diǎn)組成。工作器有兩項(xiàng)職責(zé)：

1.將交易批次流式傳輸?shù)较鄳?yīng)的驗(yàn)證器工作器（例如,，Worker1與其他驗(yàn)證器的Worker1共享批次,，如圖2所示）。

2.將批次的摘要（哈希）發(fā)送到各自的主節(jié)點(diǎn),。每個(gè)驗(yàn)證器的主節(jié)點(diǎn)使用這些摘要來(lái)運(yùn)行Narwhal內(nèi)存池協(xié)議,，并在其自己的視圖中形成基于回合的本地DAG,。

圖2說(shuō)明了每個(gè)驗(yàn)證器的內(nèi)部工作原理，它由工作器和主驗(yàn)證器組成

由于工作節(jié)點(diǎn)的獨(dú)立運(yùn)行模式,，系統(tǒng)可以靈活擴(kuò)展數(shù)據(jù)處理能力,，通過(guò)增加更多節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)傳播的橫向擴(kuò)展。盡管主節(jié)點(diǎn)成為處理瓶頸,，因?yàn)樗?dú)自承擔(dān)內(nèi)存池協(xié)議運(yùn)行的責(zé)任,，但這種設(shè)計(jì)策略具有顯著優(yōu)勢(shì)。

通過(guò)將數(shù)據(jù)傳播與DAG結(jié)構(gòu)的構(gòu)建分離,，主節(jié)點(diǎn)可以自由構(gòu)建DAG,，不受傳播速度的限制。同時(shí),，利用工作節(jié)點(diǎn)提供的批次概要而非完整交易集,，主節(jié)點(diǎn)運(yùn)行內(nèi)存池協(xié)議的效率顯著提高，顯著降低了帶寬消耗,。

為了構(gòu)建DAG,，每個(gè)驗(yàn)證者在第r輪遵循以下步驟：

1.每個(gè)驗(yàn)證者的主驗(yàn)證者向所有其他驗(yàn)證者發(fā)送一條消息，包括：

a.來(lái)自其工作者的一批交易摘要,。

b.來(lái)自上一輪（r-1）的nf證書(shū)（引用）,。

2.收到消息后，主接收者通過(guò)確保以下內(nèi)容來(lái)驗(yàn)證消息：

a.該消息與接收者來(lái)自同一輪,。

b.接收方在第r輪中第一次從發(fā)送方主節(jié)點(diǎn)接收到該消息,。

c.其工作人員已將與指定摘要相對(duì)應(yīng)的批次存儲(chǔ)在消息中,。

3.如果檢查通過(guò)，驗(yàn)證者將通過(guò)發(fā)回其簽名來(lái)為該消息投票,。

4.發(fā)送者匯總來(lái)自不同接收者的nf簽名以創(chuàng)建證書(shū),，并將此證書(shū)發(fā)送回所有其他主節(jié)點(diǎn)。然后,，接收者可以使用此證書(shū)以及相關(guān)的消息摘要在各自的本地DAG中創(chuàng)建頂點(diǎn),。

5.一旦主節(jié)點(diǎn)可以形成nf個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)都有一個(gè)證書(shū),，它就可以進(jìn)入下一輪,，即r+1。

圖3：驗(yàn)證者廣播其頂點(diǎn)并將其他驗(yàn)證者的DAG添加到其本地DAG的流程

圖4顯示了每個(gè)驗(yàn)證者的工作器和主驗(yàn)證器的職責(zé)

圖5：DAG構(gòu)建

Narwhal架構(gòu)作為內(nèi)存池的基礎(chǔ),，精心構(gòu)建了每輪驗(yàn)證者的DAG結(jié)構(gòu),。

這個(gè)DAG由代表交易批次的節(jié)點(diǎn)和指向前一輪父節(jié)點(diǎn)的邊組成，如圖1所示,。驗(yàn)證者之間頻繁交換節(jié)點(diǎn)和邊信息,，以便在本地構(gòu)建一致的DAG視圖。

Narwhal專(zhuān)注于DAG的構(gòu)建,，而共識(shí)機(jī)制則負(fù)責(zé)解析其深層含義和決策,。在Narwhal中，每個(gè)驗(yàn)證者由一個(gè)Worker和一個(gè)主節(jié)點(diǎn)組成,。

Worker負(fù)責(zé)將交易批次流式傳輸?shù)较鄳?yīng)的驗(yàn)證者Worker,，并將其批次的摘要（哈希）發(fā)送到各自的主節(jié)點(diǎn)。

每個(gè)驗(yàn)證者的主節(jié)點(diǎn)使用這些摘要來(lái)運(yùn)行Narwhal內(nèi)存池協(xié)議,，并形成基于輪次的本地DAG,。

排序機(jī)制突破：Bullshark的零通信成本排序

大算投，探索數(shù)字經(jīng)濟(jì)的奧秘,，洞察區(qū)塊鏈的未來(lái)趨勢(shì)

03

整合了DAG架構(gòu)之后，Bullshark協(xié)議得以在其上施展特有的排序技術(shù),，這一過(guò)程無(wú)需任何額外的通信成本,，實(shí)現(xiàn)了所謂的“零通信開(kāi)銷(xiāo)”。這意味著,，驗(yàn)證者無(wú)需進(jìn)行額外交流,，僅需依賴(lài)本地的DAG視圖和Bullshark共識(shí)機(jī)制來(lái)獨(dú)立解釋節(jié)點(diǎn)與邊的關(guān)系，并形成一致的交易序列,。

盡管網(wǎng)絡(luò)環(huán)境可能不穩(wěn)定,，且拜占庭節(jié)點(diǎn)可能引發(fā)DAG形態(tài)在不同驗(yàn)證者間的不一致,，Bullshark仍能確保誠(chéng)實(shí)的驗(yàn)證者能夠達(dá)成一致的總體排序共識(shí)。

Bullshark共識(shí)機(jī)制包括同步版和部分同步版兩種版本,，本文將聚焦于部分同步版,。這一版本通過(guò)實(shí)施一種垃圾回收策略，巧妙地控制內(nèi)存消耗,，使其保持在可管理的范圍內(nèi),。這種精心設(shè)計(jì)將在后續(xù)內(nèi)容中進(jìn)一步探討。

Bullshark的運(yùn)作機(jī)制就像一場(chǎng)精心編排的舞蹈,，將DAG的輪次分為奇數(shù)和偶數(shù),，形成一個(gè)復(fù)雜但有序的格局。

以n=4, f=1（遵循n3f+1原則）為例,，在奇數(shù)輪次中,，設(shè)置的“錨點(diǎn)”如同閃耀的綠寶石，引導(dǎo)排序的方向,。而在偶數(shù)輪次中,，則成為決定錨點(diǎn)重要性的關(guān)鍵舞臺(tái)。

圖6展示了錨點(diǎn)及其因果歷史

在偶數(shù)輪中,，對(duì)上一奇數(shù)輪中的錨點(diǎn)的投票通過(guò)與之相連的邊完成。如果一個(gè)錨點(diǎn)在下一個(gè)偶數(shù)輪中獲得至少f+1票,，它就會(huì)被確認(rèn)提交,。

例如,，在圖7中,，第3輪的錨點(diǎn)A2因?yàn)樵诘?輪獲得了三票，超過(guò)了f+1=2的閾值,，所以被提交,。相反，A1只獲得一票,，因此仍未提交,。

圖 7 說(shuō)明了偶數(shù)輪中的頂點(diǎn)如何為上一奇數(shù)輪中的錨點(diǎn)投票

然而,，考慮到網(wǎng)絡(luò)的異步特性,，我們不能忽視A1。不同的驗(yàn)證者在其本地視圖中可能擁有不同的DAG,。

如圖8所示,，當(dāng)驗(yàn)證器2嘗試追趕驗(yàn)證器1時(shí)，它會(huì)提交錨點(diǎn)A1,，即使驗(yàn)證器1沒(méi)有提交,。當(dāng)驗(yàn)證器2趕上驗(yàn)證器1時(shí),，就會(huì)出現(xiàn)問(wèn)題，因?yàn)轵?yàn)證器2會(huì)先提交A1,，然后是A2,。

圖 8：不同驗(yàn)證者對(duì) DAG 的不同看法

Bullshark設(shè)計(jì)了一種機(jī)制,，以確保即使DAG視圖不同,，驗(yàn)證者間也能就節(jié)點(diǎn)的全序達(dá)成一致。

關(guān)鍵在于,，如果存在從已確認(rèn)的未來(lái)錨點(diǎn)到歷史錨點(diǎn)的路徑,，且后者已獲確認(rèn)，則前者也必須獲確認(rèn)且位于后者之前,。

如果不滿足此條件,，則可以安全地忽略舊錨點(diǎn)。驗(yàn)證者遵循這一邏輯遞歸追溯,，直到達(dá)到已確認(rèn)的起點(diǎn),。一旦錨點(diǎn)被穩(wěn)固提交，驗(yàn)證者就可以使用明確的規(guī)則（如拓?fù)渑判蚧蚧趃as費(fèi)用的排序）,，為所有已確認(rèn)錨點(diǎn)及其因果脈絡(luò)建立統(tǒng)一的全序,。

圖9展示了錨點(diǎn)A3的因果脈絡(luò)，以綠色標(biāo)識(shí)的區(qū)塊清晰呈現(xiàn),。

圖 9 展示了 Bullshark 全序錨點(diǎn)及其因果歷史

圖9直觀地展示了承諾過(guò)程和全排序。在第6輪中,，驗(yàn)證器提交錨點(diǎn)A3,，因?yàn)樗@得了三票，超過(guò)了f票的閾值,。然后,，驗(yàn)證器遞歸地回顧其歷史記錄以提交并確定較舊錨點(diǎn)的順序。

由于沒(méi)有從A3到A2的路徑,，因此跳過(guò)A2被認(rèn)為是安全的,。當(dāng)驗(yàn)證器回到A1時(shí)，它會(huì)立即提交并將A1排序在A3之后,，因?yàn)榇嬖趶腁3到A1的路徑,。

A3以及錨點(diǎn)A1和A3的因果歷史是有序的，如圖9底部所示,。此過(guò)程從第1輪重新開(kāi)始，驗(yàn)證器繼續(xù)回顧直到找到先前提交的錨點(diǎn),，這意味著其所有歷史數(shù)據(jù)都已排序,。

值得注意的是，如果錨點(diǎn)具有從已承諾的未來(lái)錨點(diǎn)到它們的路徑,，則承諾錨點(diǎn)被認(rèn)為是安全的，該路徑來(lái)自群體交集,。

深入分析Bullshark機(jī)制，我們發(fā)現(xiàn)它通過(guò)創(chuàng)新的垃圾回收策略,，巧妙地解決了內(nèi)存管理難題,，并在DAG架構(gòu)的共識(shí)體系中確保了公平性,。

在區(qū)塊鏈?zhǔn)澜缰校叫允敲總€(gè)節(jié)點(diǎn)都能在共識(shí)進(jìn)程中發(fā)聲的理想追求,。然而，當(dāng)嘗試將每個(gè)節(jié)點(diǎn)的歷史頂點(diǎn)無(wú)縫融入全網(wǎng)DAG結(jié)構(gòu)時(shí),，網(wǎng)絡(luò)的異步特性讓這一過(guò)程的時(shí)間框架變得不可預(yù)測(cè)。

為確保低速節(jié)點(diǎn)不被邊緣化,，所有節(jié)點(diǎn)不得不維護(hù)大量舊數(shù)據(jù)和證書(shū),，但這可能導(dǎo)致DAG無(wú)限擴(kuò)張，最終耗盡內(nèi)存資源,。因此，垃圾收集機(jī)制應(yīng)運(yùn)而生,，它精準(zhǔn)地識(shí)別并清除冗余歷史數(shù)據(jù),，為DAG的可持續(xù)成長(zhǎng)鋪平道路。

垃圾回收機(jī)制相當(dāng)于內(nèi)存領(lǐng)域的回收站,，旨在回收未使用的內(nèi)存空間,，為未來(lái)程序運(yùn)行騰出資源。

它通過(guò)清理DAG中不再需要的歷史數(shù)據(jù)來(lái)實(shí)現(xiàn)內(nèi)存的有效釋放,，從而維護(hù)內(nèi)存資源的有限性和寶貴性,。然而，垃圾回收與公平性之間的張力如同一對(duì)矛盾體,。

對(duì)舊DAG數(shù)據(jù)的回收可能意味著某些歷史信息的訪問(wèn)變得不那么方便,，尤其是對(duì)于運(yùn)行速度較慢的節(jié)點(diǎn),。因此，垃圾回收與公平性似乎難以兼得,。

Bullshark項(xiàng)目通過(guò)調(diào)整公平性的定義范圍，僅在同步過(guò)程中確保公平性,，巧妙地解決了這一難題,。這種策略使得Bullshark的部分同步版本在市場(chǎng)上更受歡迎,。其部分同步模型被劃分為異步和同步兩個(gè)階段。

在異步階段,，系統(tǒng)像自由市場(chǎng)一樣運(yùn)作,，消息可能因網(wǎng)絡(luò)延遲或惡意攻擊而延遲,。但最終會(huì)迎來(lái)“全球穩(wěn)定時(shí)刻”（GST），此時(shí)系統(tǒng)恢復(fù)平靜并高效同步運(yùn)行,。

簡(jiǎn)單來(lái)說(shuō)，在部分同步模型中,，系統(tǒng)在GST之前保持異步運(yùn)行,，之后同步運(yùn)行。垃圾收集過(guò)程很簡(jiǎn)單：驗(yàn)證器在廣播頂點(diǎn)時(shí)為其添加時(shí)間戳。提交錨點(diǎn)時(shí),，會(huì)為其分配一個(gè)時(shí)間戳，該時(shí)間戳計(jì)算為其父節(jié)點(diǎn)（錨點(diǎn)具有強(qiáng)邊指向的頂點(diǎn)）的中位數(shù),。

現(xiàn)在錨點(diǎn)的歷史記錄已準(zhǔn)備好排序，驗(yàn)證器會(huì)回顧錨點(diǎn)的歷史記錄,，同時(shí)使用該輪頂點(diǎn)時(shí)間戳的中位數(shù)計(jì)算每輪的時(shí)間戳,。一旦達(dá)到某個(gè)輪次的GCround,，其時(shí)間戳比錨點(diǎn)時(shí)間戳小超過(guò)預(yù)定義的時(shí)間，則該GCround及其下面的輪次都會(huì)被垃圾回收,。

圖 10：Bullshark 如何垃圾收集舊歷史并實(shí)現(xiàn)公平的過(guò)程

圖10展示了Bullshark如何進(jìn)行垃圾收集和實(shí)現(xiàn)公平性的過(guò)程,。在此圖中，定義為2,，錨點(diǎn)A（綠色）的時(shí)間戳計(jì)算為5,。因此,，可以還原并發(fā)現(xiàn)GCround時(shí)間戳的閾值為5-2，結(jié)果為3,。因此,，任何時(shí)間戳在3和5之間的頂點(diǎn)都可以包含在DAG中，即使它到達(dá)的時(shí)間晚于其他頂點(diǎn),。

如圖10所示,，來(lái)自驗(yàn)證器4的頂點(diǎn)（標(biāo)記為時(shí)間戳4）可以添加到DAG中，盡管它比其他頂點(diǎn)到達(dá)得晚,。時(shí)間戳低于3的輪次將被垃圾收集。然而,，僅添加驗(yàn)證器4的頂點(diǎn)并不能保證公平性,，因?yàn)闆](méi)有從錨點(diǎn)到該頂點(diǎn)的路徑,。

因此,，在全序過(guò)程中將忽略該頂點(diǎn)。為了解決公平性問(wèn)題,，引入了“弱鏈接”或“弱邊”的概念,。與迄今為止討論的邊（稱(chēng)為強(qiáng)邊，將第r輪中的頂點(diǎn)與緊接在前一輪（第r-1輪）中的頂點(diǎn)連接起來(lái)）不同,，弱邊將第r輪中的頂點(diǎn)與第r-1輪以下的頂點(diǎn)連接起來(lái),。

它們?cè)诠沧R(shí)邏輯中不計(jì)入投票；相反,，它們的目的是幫助創(chuàng)建通往慢速驗(yàn)證器頂點(diǎn)的路徑,，以確保其他誠(chéng)實(shí)的驗(yàn)證器最終將它們添加到DAG中。因此,，垃圾收集和弱鏈接的結(jié)合可以在同步期間確保公平性，同時(shí)限制內(nèi)存使用,。

總結(jié)

總而言之

本文深入探討了Narwhal和Bullshark在共識(shí)協(xié)議中處理共享對(duì)象的基本思想,。Narwhal的設(shè)計(jì)將內(nèi)存池功能與共識(shí)機(jī)制分離，通過(guò)工作節(jié)點(diǎn)以網(wǎng)絡(luò)速度傳播批量交易,，并將批量摘要轉(zhuǎn)發(fā)給主節(jié)點(diǎn)以形成基于輪次的DAG。

這種設(shè)計(jì)允許系統(tǒng)通過(guò)增加工作節(jié)點(diǎn)來(lái)水平擴(kuò)展數(shù)據(jù)處理能力,。而B(niǎo)ullshark則在DAG之上構(gòu)建共識(shí)邏輯,，無(wú)需在驗(yàn)證者之間發(fā)送額外消息，實(shí)現(xiàn)了數(shù)據(jù)的快速傳播,。

同時(shí),，Bullshark提供了垃圾收集和公平性解決方案，解決了基于DAG的共識(shí)所面臨的內(nèi)存和公平性問(wèn)題,。