[Chainlink] DAG 上的MEV 阻力


概要

最近關於“DAG 上的最大可提取價值(MEV) 保護”的工作探索了將“盲序公平”(一種用於防止最大可提取價值(MEV) 漏洞利用的措施)集成到基於DAG 的BFT 共識方法中的方法。

為了滿足基於DAG 的BFT 共識的高交易提交吞吐量,Blind Order-Fairness 的性能也需要擴展。如果交易開放落後於共識排序吞吐量,未結算的交易積壓可能會越來越多;並且可以阻止客戶端提交針對最後提交狀態的事務。這篇文章解釋了一個高級解決方案框架,並比較了在其中實現盲/開放的不同選項。

背景

電動車

在過去的幾年裡,我們看到人們對基於它們的加密貨幣平台和應用程序的興趣呈爆炸式增長,例如提供抗審查和開放訪問金融工具的去中心化金融協議;或不可替代的代幣。其中許多系統容易受到MEV 攻擊,其中惡意共識領導者可以注入交易或更改用戶交易的順序以最大化其利潤。因此,與此同時,我們目睹了MEV 專業化的上漲現象,由MEV 機會“搜索者”和合作礦工組成的整個MEV 開發生態系統已經出現,這並不奇怪。

戴安等人。在 [Flash Boys 2.0, S&P 2020] 中引入了一項衡量“可以通過在區塊內包含、排除或重新排序交易獲得的利潤”的衡量標準,稱為衡量礦工可提取價值(MEV)。[MEV-explore] 估計自2020 年1 月1 日以來在以太坊上提取的MEV 金額接近7 億美元。但是,可以安全地假設提取的總MEV 要高得多,因為MEV-explore 將其估計限制為僅一個區塊鏈、幾個協議和有限數量的可檢測MEV 技術。儘管很難說所有的MEV 都是“壞的”(例如,市場套利可以消除市場低效率),但它通常會引入一些負面的外部性,例如:

網絡擁塞:尤其是在低成本鏈上,MEV 參與者經常試圖通過發送大量冗餘交易、向底層點對點網絡發送垃圾郵件來增加利用MEV 機會的機會,
鏈擁堵:很多這樣的交易最後都上鍊了,讓鏈更擁堵,
更高的區塊鏈成本:在爭奪有利潤的MEV 機會的同時,MEV 參與者會出更高的gas 價格來優先考慮他們的交易,這導致普通用戶的總體區塊鏈成本更高,
共識穩定性:一些鏈上交易可以創造如此有利潤的MEV 機會,以至於礦工可能很想用他們提取的此類交易創建替代鏈分叉,這會帶來共識不穩定風險。

公平訂購

在這篇博文中,我們專注於經典(或權益證明)BFT 設置中的共識級MEV 緩解技術,其中一組已知的N=3F+1 方被稱為驗證者。基本上有兩種類型的MEV 抗性Order-Fairness 屬性:

盲序公平。針對MEV 的主要防線源於在不查看交易內容的情況下承諾交易排序。Heimbach 和Wattenhofer 在 [SoK on Preventing Transaction Reordering, 2022] 中使用了這種MEV 阻力概念,在此稱為Blind Order-Fairness,並被定義為

“當任何一方在看到交易內容後不可能包含或排除交易時。此外,任何一方都不應該在其內容已經觀察到的任何交易之前插入他們自己的交易。 ”

基於時間的訂單公平性。MEV 保護的另一個強有力的措施是同時向所有驗證者發送交易,並使用大多數驗證者的相對到達順序來確定最終排序。特別是,這種順序公平的概念確保了

“如果足夠多的各方在另一個tx’ 之前收到一個交易tx,那麼在最終提交順序中,tx’ 不會在tx 之前排序。”

這可以防止可以分析網絡流量和交易內容的強大對手重新排序、審查和驗證器接收的前/後運行交易。此外,基於時間的順序公平對用戶和共識提議者之間的潛在勾結具有更強的保護作用,因為驗證者明確地將相對順序輸入到協議中。基於時間的訂單公平在最近的幾部作品中被用於各種風格,包括 [Aequitas, CRYPTO 2020], [Pompē, OSDI 2020], [Themis, 2021], [Wendy Grows Up, FC 2021] 和 [Quick Order Fairness ,FC 2022]。

文獻中發現的另一個公平概念,不提供秩序公平,圍繞參與公平:

參與公平。一種不同的公平概念旨在確保抗審查或更強的參與公平概念。參與權益保證區塊鏈包含一定部分的誠實貢獻(又名“鏈質量”)。一些BFT 協議解決了參與公平問題,包括 [Prime, IEEE TDSC 2010]、[Fairledger, 2019]、[HoneyBadger, CCS 2016] 等等。在基於分層DAG 的BFT 協議中,例如 [Aleph, AFT 2019]、[DAG-Rider, PODC 2021]、[Tusk, 2021]、[Bullshark, 2022],參與公平基本上是免費的,因為每個DAG 層都必須包含來自2F+1 參與者。值得注意的是,參與權益並不能阻止腐敗方在已經觀察到其他交易後注入交易,

BFT共識中的盲序公平框架

針對MEV 的第一道防線是隱藏事務信息,直到“盲目地”提交提交訂單。這可以防止任何一方在提交排序之前觀察交易的內容,從而滿足盲序公平。我們現在引入一個框架,用於在具有已知N=3F+1 驗證器集的經典(或權益證明)設置中將盲序公平保護集成到BFT 共識中。

核心解決方案是標準的k-of-n 秘密共享方法。對於每筆交易tx,用戶(“Alice”)選擇一個秘密對稱密鑰tx-key,並將用它加密的tx 發送給驗證者。秘密共享允許Alice 與驗證者共享tx-key,這樣重建tx-key 需要F+1 份,並且在它(盲目地)提交到總訂單之前,沒有F 組壞方可以打開它。誠實的驗證者首先等待提交交易的盲序,然後才打開它們。同時,在將交易提交到總排序之前,驗證者確保他們可以打開它。

去中心化/回收。更正式地說,共享協議有兩個抽像功能,“去中心化”和“檢索”。Disperse 允許經銷商將秘密tx-key 的份額分發給驗證者,並提供以下保證:

隱藏:一組F 個壞驗證器無法重建tx-key。
綁定:Disperse(tx-key) 在誠實驗證器上成功完成後,任何一組誠實的F+1 驗證器執行Retrieve(tx-key) 都可以重建tx-key,生成唯一結果。
有效性:如果經銷商是誠實的,那麼任何F+1 誠實驗證者的Retrieve(tx-key) 的結果就是tx-key。

值得注意的是,Disperse/Retrieve 不需要文獻中某些用例可能需要的某些屬性,但這裡的框架不需要:

當Disperse 完成時,它不保證Retrieve 可以重建經銷商承諾的輸出值。
它不要求可以恢復單個股票。
它不需要能夠使用tx-key 來導出其他值,同時保持tx-key 本身的機密性。

放寬這些要求將在下面的方法3 和4 中發揮重要作用。

去中心化/檢索方法

方法1:閾值密碼學

使用閾值加密貨幣實現Disperse/Retrieve 是直接的,這樣用戶就知道公共加密貨幣“E()”,並且在驗證器之間共享私有解密“D()”(在設置時)。回想一下,對於每個tx,用戶選擇一個特定於交易的對稱密鑰tx-key 並發送用它加密的tx。對於Disperse(tx-key),用戶附加E(tx-key),這是使用全局閾值密鑰加密的交易密鑰。一旦一個tx 提交到總排序,Retrieve(tx-key) 由每個驗證器實現,為D(tx-key) 生成其解密共享。驗證者可以嘗試應用F+1 個有效解密份額來解密tx。

綁定源於兩個屬性。首先,誠實方的閾值總是可以成功生成E(tx-key) 的F+1 個有效解密份額。其次,一些閾值加密貨幣方案允許驗證驗證者是否提供了正確的解密份額,因此通過檢索F+1 個有效閾值份額,可以保證唯一的結果。

特性:

需要可信設置或(計算成本高的)分佈式閾值加密貨幣設置。
在標準硬件上使用 [TDH2, EuroCrypt 1998] 的Disperse 大約需要300μs。沒有額外的消息。
在6-out-of-16 方案中檢索大約需要3500μs。

方法2:可驗證的秘密共享(VSS)

用戶去中心化(tx-key)的另一種方法是 [Shamir 的秘密共享方案,CACM 1979]。“vanilla”秘密共享方案有兩個成分:共享函數“SS-share(secret s)”創建N 個值,“SS-combine(F+1 share)”重建秘密s。

為了去中心化(tx-key),用戶使用SS-share(tx-key) 將單獨的tx-key 共享發送給每個驗證者。一組F+1 股東在Retrieve 期間顯示他們的股份,並通過“SS-combine()”組合股份以重建tx-key。

組合份額比閾值加密貨幣快三個數量級,並且在當今的計算環境中需要幾微秒(參見屬性註釋)。但是,在Disperse 完成NF 驗證器之後,“普通”SS-share()/SS-combine() 不保證綁定:首先,並非每組F+1 誠實驗證器都可以持有Disperse 階段的份額。其次,從不同的F+1 驗證器集合中檢索共享可能會導致SS-combine() 的輸出不同。

VSS 方案通過共享VSS-verification(share, commit value) 支持綁定。VSS-verification() 允許驗證器檢查共享是否與提交的值s’ 一致,以便應用於SS-combine() 的任何F+1 共享集都會導致輸出s’。當驗證者收到共享時,它應該在確認之前驗證共享。當有NF 確認可驗證股份時,去中心化完成,證明有效股份由F+1 誠實驗證者持有,並保證F+1 的任何子集的唯一重建。

可以添加份額恢復功能VSS-recovery(F+1 股東) 以允許驗證者在檢索之前獲得其個人份額。

特性:

不需要受信任的設置。
Disperse 的O(N²) 通信複雜度(例如,使用 [hbACSS, NDSS 2022], [eAVSS-SC, CT-RSA 2013])。用戶需要私下將共享發送給各個驗證者。
檢索的O(N²) 通信複雜度。可選的O(N²) 用於F+1 誠實驗證者恢復丟失的份額。

方法3:AVID-M

VSS 提供了比滿足Disperse/Retrieve 綁定要求所需的更強的保證。具體來說,Disperse 只需要保證唯一的秘密重建結果,而不是成功。借用 [DispersedLedger, NSDI 2022] 中的一項稱為AVID-M 的關鍵技術,驗證者可以完全避免在Disperse 期間驗證共享(成本高昂)。相反,他們在檢索期間驗證(整個)共享將具有獨特的結果(便宜)。這工作如下。

對於Disperse(tx-key),用戶使用SS-share(tx-key) 將單個共享發送給驗證者。此外,用戶在Merkle-tree 中組合所有共享,驗證根,並向每個共享發送成員資格證明,即到根的Merkle 樹路徑。當驗證者收到一個共享時,它應該在確認共享之前針對已認證的根驗證Merkle 樹證明。當有NF 確認時,Disperse 完成,保證F+1 誠實驗證者持有未篡改的股份。

在Retrieve(tx-key) 期間,F+1 驗證者顯示單個共享,附加Merkle 樹路徑以證明共享未被篡改。請注意,可以通過僅檢查根上的一個簽名來驗證F+1 共享。驗證器使用SS-combine() 嘗試重建tx-key。

然後他們後驗證發送給驗證者的F+1(未篡改)共享的每個子集都將具有相同的結果。為此,驗證者不需要等待丟失的份額,也不需要嘗試F+1 份額的組合。而且,它不需要與其他人交易所。驗證器只需生成丟失的份額並重新編碼默克爾樹。然後,它將重新生成的Merkle 樹與發送者認證的根進行比較。如果比較失敗,則經銷商有問題,驗證者拒絕tx。綁定之所以成立,是因為驗證後的結果——成功或失敗——在去中心化完成後變得固定。無論輸入F+1(未篡改)共享的哪個子集,每個驗證器都會得出相同的結果,從而確保綁定。

該方案的一個變體是讓用戶提交並去中心化一個簡單的股票哈希向量,而不是Merkle 樹。去中心化散列向量(完全)會導致比去中心化Merkle 根更高的通信複雜度(例如,使用 [hbACSS, NDSS 2022] 的二次方)以及更高的計算成本,但會降低整體檢索複雜度(至二次方)。

特性:

不需要受信任的設置。
Disperse 的總體通信時間約為50μs 和O(N²)(O(N²),帶有哈希向量承諾)。用戶需要將股份私下發送給個人驗證者,並附上Merkle 證明。
在6-out-of-16 方案中,大約50μs 和O(N² * log(N)) 的整體通信用於檢索(O(N²) 與哈希向量承諾),包括驗證後。

方法4:混合

即使在Disperse 完成後,VSS 和AVID-M 都可能需要在檢索期間與一組特定的F+1 誠實驗證者交互。這意味著Retrieve 的延遲受到這組特定的F+1“股東”的影響,而不是最快的F+1 誠實驗證者的速度。使用閾值密碼學消除了這種依賴性,但會產生昂貴的計算。

混合方法結合了閾值加密貨幣和AVID-M 的優點。在Hybrid 中,Retrieve 在穩態期間使用(快速)秘密共享,並回退到閾值加密貨幣,避免在網絡不穩定期間等待特定的F+1 驗證器。

Disperse(tx-key) 分兩部分實現。首先,用戶應用AVID-M 向各方發送個人共享和證明。其次,作為後備,它發送驗證器E(tx-key)。一旦tx 被提交到總排序,Retrieve(tx-key) 有一個快軌和一個慢軌。在快速通道中,每個持有AVID-M for tx-key 的驗證器都會顯示它。一個不持有AVID-M 份額的tx-key 的驗證器會顯示一個閾值密鑰解密份額。在緩慢的軌道上,驗證者可能會放棄等待AVID-M 共享並披露閾值密鑰解密共享,即使他們已經披露了AVID-M 共享。

檢索後的驗證後(快速或慢速路徑)檢查AVID-M 驗證後以及E(tx-key) 是否與AVID-M 去中心化一致。更具體地說,驗證器只需重新​​加密貨幣tx-key 並在重建後重新編碼AVID-M Merkle 樹。它將兩者與發件人的進行比較。如果比較失敗,則經銷商有問題,驗證者拒絕tx。再一次,驗證後的結果——成功或失敗——在去中心化完成時變得固定。無論輸入哪種方案和F+1(未篡改)共享的哪個子集,每個驗證器都會得出相同的結果,從而確保Binding。

特性:

需要可信設置或(計算成本高的)分佈式閾值加密貨幣設置。
在6-out-of-16 方案中,大約360μs 和O(N² * log(N)) (O(N²) 與哈希向量承諾) 的整體通信。用戶需要私下向每個驗證者發送AVID-M 共享。用戶在tx 的廣播中搭載E(tx-key),沒有額外的消息。
大約50μs 和O(N² * log(N)) (O(N²) 與散列向量承諾) 整體通信用於6-out-of-16 方案中的快速檢索,3500μs 用於慢速檢索。兩者的後驗證大約需要400μs。
Retrieve 的速度非常快,此外,它可能會以最快的F+1 誠實驗證者的速度進行。

Fino:DAG 上的盲序公平

在基於DAG 的共識協議(前一篇文章的主題)中,驗證者通過可靠且因果順序的傳輸來廣播尚未確認的交易摘要塊。DAG 方法的出現是每個共識消息都直接用於形成已提交事務的總排序。

DAG 傳輸公開了兩個API,broadcast() 和Deliver()。當驗證者將廣播消息傳遞到其本地DAG 時,它具有以下保證:

可靠性:最終,所有誠實的驗證者都可以下載消息的副本
明確性:每個驗證者的消息都有編號。如果一個誠實的驗證者從特定的發送者那里傳遞了第k 個消息,那麼該消息將由它的發送者進行身份驗證,而其他誠實的驗證者傳遞與發送者的第k 個消息相同的消息。
因果順序:消息包含對發送者先前已傳遞的消息的顯式引用(包括它自己的)。在傳遞消息之前先在本地傳遞前身。

請注意,不同驗證者的DAG 在任何時候都可能略有不同。由於消息調度,這在分佈式系統中是不可避免的。然而,基於DAG 的共識協議允許每個驗證者解釋其本地DAG,從而得出形成總排序的自主結論。

可靠性、明確性和因果排序極大地簡化了盲序公平的實現:

當tx 被廣播時,DAG 傳輸從NF 驗證器收集他們收到tx-key 份額的確認。這保證瞭如果tx 是提交排序的候選者,它已經完成了Disperse 階段。
當驗證者觀察到tx 在其本地DAG 中提交時,Share Retrieve 會自動啟動。
將股票廣播到DAG 允許每個人觀察tx 被打開,即使他們沒有積極參與Retrieve。此外,它允許停止共識進程,直到所有待處理的已提交交易都顯示F+1 份額。

菲諾概述

Fino 將盲序公平保護納入部分同步模型的BFT 協議中,基於DAG 傳輸。

為了在DAG 上構建盲序公平,我們需要一個簡單的基線DAG-BFT 算法基礎。Fino 採用極簡主義和純粹主義的方法,強調以下關鍵原則:

零DAG 延遲——Fino 從不要求DAG 等待取決於共識步驟/計時器的輸入,並避免對DAG 結構(例如分層)的任何嚴格限制。
簡單——Fino 很可能是將BFT 共識嵌入DAG 的最簡單方法。
部分同步——該解決方案保證當網絡穩定時,只需要兩個廣播延遲即可達成共識決策。排序決策會批量提交DAG 中上漲的所有事務。

應該注意的是,我們的去中心化/檢索框架可能建立在其他DAG-BFT 系統上。

意見。該協議以逐個視圖的方式運行。每個視圖都有編號,就像在view(r) 中一樣,並且有一個每個人都知道的指定領導者。

查看變化。當滿足兩個條件viewA 和viewB 時,驗證器進入view(r+1):

當驗證者的本地DAG 包含對提案(r) 的F+1 個有效投票或對view(r) 的2F+1 個有效投訴(r) 時, viewA 得到滿足。
當本地DAG 中的每個已提交事務tx 都完成Disperse(tx-key) 時, viewB 會得到滿足。請注意,viewB 在不打開已提交事務的情況下會阻止進度。

提議。驗證者定期將加密貨幣交易打包成一個批次,並使用DAG 傳輸來廣播它們。當一個領導者進入一個新的視圖(r)時,它的廣播被解釋為提議(r)。隱含地,proposal(r) 建議提交事務總排序提案的因果歷史中的所有消息。如果領導者的提議(r)在進入視圖(r)中是合理的,則它是有效的。

表決。當驗證者看到有效的領導者提議時,它會廣播vote(r)。如果驗證人的投票(r)遵循有效的提案(r),則它是有效的。

承諾。每當領導者的提案(r)在本地DAG 中有F+1 有效票時,該提案及其因果歷史就會被提交。驗證者按如下方式處理已提交的提案(r):

訂購提交。讓r’ 是最高視圖r’ 遞歸地,proposal(r’) 是有序的。尚未排序的proposal(r) 的其餘因果前任被附加到已提交的序列中(在此批次中,可以使用任何確定性規則進行排序,以將部分排序線性化為總排序。)

分享揭秘。對於每個新提交的事務tx,啟動Retrieve(tx-key) 過程。股票依賴於DAG 廣播,這些廣播是根據該決定進行的。成功的Retrieve 會重建tx-key 並使用它來解密tx;如果tx 的發送者行為不端,檢索可能會失敗,在這種情況下,tx 會被拒絕。

抱怨。如果驗證者放棄等待視圖(r)中發生的提交,它會廣播投訴(r)。請注意,如果存在驗證人的投訴(r),則驗證人的投票(r)不會被解釋為有效投票。

關於快樂路徑延遲的註釋。在穩定時期,任何誠實的驗證者都不會抱怨誠實的領導者。如果tx 由view(r) 中的誠實領導者提出,它將獲得F+1 票並在一個網絡延遲內提交。在一個網絡延遲內,誠實的驗證者將發布一條包含tx 份額的消息。每個人都可以申請Retrieve(tx-key) 並打開或拒絕它。總之,在一條幸福的道路上,盲目提交和打開tx 在提交後會發生三個網絡延遲。

示例場景。圖1 說明了幾個Fino 場景。在第一個視圖(view(r)) 中,proposal(r) 被提交。提交為proposal(r)的因果過去中的每個事務tx設置一個排序,並啟用它們的檢索。

view(r+1) 中出現了一個稍微複雜的場景。該視圖到期是因為各方沒有觀察到領導者的提議已被承諾並且他們廣播了投訴。進入view(r+2) 是由2F+1 對view(r+1) 的投訴啟用的。當提案(r+2)本身被提交時,它也間接提交提案(r+1)。此後,為每個待處理的已提交事務啟動檢索,包括提案(r+1)和提案(r+2)中的事務。

說明幾個Fino 場景圖1:proposal(r) 的提交之後是Retrieve。提案(r+2)的提交導致提案(r+1)的間接提交,然後是兩者的檢索。
致謝

特別感謝Nibesh Shrestha 提出在AVID-M 設置中使用哈希向量承諾的想法並探索實現它的方法。

非常感謝Soumya Basu、Christian Cachin、Ari Juels、Mahimna Kelkar、Oded Naor 和Nibesh Shrestha 的評測幫助改進了這篇文章。

資訊來源:由0x資訊編譯自AZCOINNEWS。版權歸作者Chainlink News所有,未經許可,不得轉載

Total
0
Shares
Related Posts