交易排序中完美公平性的不可能性

數十年來，分散式系統的研究，尤其是在拜占庭共識和狀態機複製（(SMR)）方面，主要集中在兩個目標：一致性和活性。一致性意味著所有節點對相同的交易序列達成共識，而活性則確保系統持續添加新交易。然而，這些屬性並不能阻止惡意行為者在接收交易後改變交易順序。

在公共區塊鏈中，傳統共識保證的這一差距已成為一個嚴重問題。驗證者、區塊建構者或排序者可以利用其在區塊排序中的特權角色牟取經濟利益，這種行為被稱為最大可提取價值（(MEV)）。這種操縱包括有利可圖的先發行、後發行和夾擊交易。由於交易執行順序決定了DeFi應用中的有效性或盈利能力，交易排序的完整性對於維持公平性和信任至關重要。

為了解決這一關鍵安全漏洞，交易排序公平性被提出為第三個基本共識屬性。公平排序協議確保最終的交易順序依賴於外部、客觀的因素，例如到達時間（(或接收順序)）且能抵抗對手的重排序。通過限制區塊提議者重排序交易的權力，這些協議使區塊鏈更接近於透明、可預測且抗MEV。

柯爾多塞悖論與理想公平的不可行性

最直觀且最強的公平性概念是接收順序公平性（(ROF)）。非正式定義為“先接收，先輸出”，ROF規定，如果大多數節點較早收到交易*(tx)，則系統必須在執行前將tx排在tx′*之前。

然而，要實現這一普遍接受的“順序公平”幾乎是不可能的，除非假設所有節點能瞬時通信（即在瞬時同步的外部網絡中運作(）。這一不可能性結果源於與社會選擇理論的驚人聯繫，特別是柯爾多塞悖論。

柯爾多塞悖論說明，即使每個節點內部對交易保持傳遞性排序，系統的集體偏好也可能形成非傳遞循環。例如，大多數節點先收到交易A再B，大多數收到B再C，大多數收到C再A。因此，三個多數偏好形成一個循環（A→B→C→A），這意味著沒有一個一致的交易排序能同時滿足所有多數偏好。

這個悖論展示了在非同步網絡，甚至在共享時鐘的同步網絡中，完美實現接收順序公平性的目標是不可能的。這一不可能性促使人們採用較弱的公平性定義，例如批次排序公平性。

Hedera Hashgraph與中位數時間戳的缺陷

Hedera採用Hashgraph共識算法，試圖逼近強大的接收順序公平性（)ROF(）。它通過將每筆交易的最終時間戳設為所有節點本地時間的中位數來實現。

然而，這本質上容易被操縱。一個惡意節點可以故意扭曲其本地時間戳，甚至在所有誠實參與者都按正確順序接收交易時，逆轉兩筆交易的最終排序。

例如，假設有五個共識節點（)A、B、C、D 和 E(），E節點行為惡意。兩筆交易tx₁和tx₂被廣播到網絡。所有誠實節點都先收到tx₁，再收到tx₂，因此預期的最終順序應為tx₁→tx₂。

![])https://img-cdn.gateio.im/social/moments-854c5145e8da5b71ef535b6e3451bf01(In 在此例中，惡意節點將tx₁的時間戳設為較晚的3（)3(），tx₂的時間戳設為較早的2（)2(），以操縱中位數。

當協議計算中位數時：

• tx₁的時間戳為)1, 1, 4, 4, 3(，中位數為3。
• tx₂的時間戳為)2, 2, 5, 5, 2(，中位數為2。

由於tx₁的最終時間戳（3）大於tx₂（2），協議輸出tx₂→tx₁，反轉了所有誠實節點觀察到的真實順序。

這個範例揭示了一個關鍵缺陷：中位數函數表面上看似中立，但實際上是造成不公平的根源，因為甚至一個不誠實的參與者都能利用它來偏袒最終交易排序。

因此，Hashgraph常被吹捧的“公平時間戳”實則是一個相當脆弱的公平性概念。Hashgraph的共識未能保證接收順序公平性，而是依賴一個權限驗證者集，而非基於密碼學保證。

實用保證的實現

然而，為了繞過柯爾多塞悖論所證明的理論不可能性，實用的公平排序方案必須在某種程度上放寬公平性的定義。

Aequitas協議引入了區塊排序公平性（)BOF(），或稱批次排序公平性。BOF規定，如果足夠多的節點在另一筆交易之前接收交易tx，則tx必須在同一個區塊中或之前被傳遞，意思是沒有誠實節點可以在tx之後再傳遞tx′。這將“必須在之前傳遞”從ROF的“必須先傳遞”放寬為“不得遲於”。

假設有三個共識節點（)A、B 和 C(）和三筆交易：tx₁、tx₂ 和 tx₃。若至少兩個節點（多數）先收到某筆交易，即視為“較早接收”。

![])https://img-cdn.gateio.im/social/moments-bfffc80c88a31d4bd7916ca25d0039ac(If 我們用多數投票來確定全局排序：

• tx₁ → tx₂（由A和C同意)）
• tx₂ → tx₃（由A和B同意(）
• tx₃ → tx₁（由B和C同意)）

這些偏好形成一個循環：tx₁→tx₂→tx₃→tx₁。這種情況下，沒有一個單一排序能同時滿足所有偏好，因此嚴格的ROF無法實現。

BOF通過將所有衝突交易放入同一批或區塊來解決，而不是強制一個在另一個之前。協議直接輸出：

區塊B₁ = {tx₁, tx₂, tx₃}

這表示，從協議角度看，這三筆交易是“同時”發生的。在區塊內，通過一個確定的打破平局的規則（如哈希值）來決定它們的執行順序。這樣，BOF確保每對交易的公平性，並保持最終交易記錄的一致性。每筆交易都不晚於其前一筆。

這一微小但重要的調整，使協議能處理交易排序衝突的情況，通過將衝突交易放入同一區塊或批次來實現。這並不導致部分排序，因為每個節點仍需就一個單一的線性交易序列達成共識。每個區塊內的交易仍按固定順序執行。在沒有衝突的情況下，協議仍能實現更強的ROF屬性。

儘管Aequitas成功實現了BOF，但也面臨重大限制，特別是通信複雜度很高，且只能保證較弱的活性。弱活性意味著交易的傳遞僅在整個柯爾多塞循環完成後才得到保證，如果循環“鏈接”在一起，可能需要很長時間。

為了強化BOF屬性，Themis協議被提出，並改進了通信複雜度。Themis通過三種技術實現：批次解開（Batch Unspooling）、延遲排序（Deferred Ordering）和更強的批內保證（Stronger Intra-Batch Guarantees）。

在標準版本中，Themis要求每個參與者與大多數節點交換消息，通信量隨著網絡節點數的平方而增加。但在優化版本SNARK-Themis中，節點使用簡潔的密碼證明來驗證公平性，無需與每個參與者直接通信，從而將通信負擔降低到線性，實現大規模網絡的高效擴展。

假設有五個節點（(A–E)）參與共識，收到三筆交易：tx₁、tx₂ 和 tx₃。由於網絡延遲，它們的本地排序不同：

As 在Aequitas中，這些偏好形成一個柯爾多塞循環。但不必等待整個循環解決，Themis通過“批次解開”方法保持系統運行。它識別出所有屬於循環的交易，並將它們分組為一個強連通分量（(SCC)）。在此例中，所有三筆交易都屬於同一SCC，Themis將其作為一個進行中的批次輸出，標記為批次B₁ = {tx₁, tx₂, tx₃}。

通過這樣做，Themis允許網絡在內部排序尚未最終確定時，繼續處理新交易，確保系統保持活性，避免停滯。

總結：

在交易排序中追求完美公平的概念看似直觀——誰先到達網絡就先處理。然而，正如柯爾多塞悖論所示，這一理想在實際的分散式系統中是不可能實現的。不同節點看到的交易順序不同，當這些視圖衝突時，沒有任何協議能在不妥協的情況下建立一個“正確”的單一序列。

Hedera的Hashgraph試圖用中位數時間戳逼近這一理想，但這種方法更多依賴信任而非證明。一個不誠實的參與者可以扭曲中位數，逆轉交易順序，證明“公平時間戳”並不真正公平。

像Aequitas和Themis這樣的協議，通過承認可達成的界限，推動了公平性的討論。它們不再追求不可能的目標，而是以在現實網絡條件下仍能保持排序完整性的方式，重新定義了公平。這種演變清楚地劃出了感知公平與可證明公平之間的界線。它表明，去中心化系統中的真正交易排序完整性，不能依賴聲譽、驗證者信任或權限控制，而必須來自協議本身嵌入的密碼學驗證。

本文不構成投資建議或推薦。每一次投資和交易行為都伴隨風險，讀者在做決策時應自行研究。

本文僅供一般資訊，並非法律或投資建議。文中所表達的觀點、思想和意見僅代表作者本人，並不一定反映Cointelegraph的立場。

Cointelegraph不支持本文內容或其中提及的任何產品。讀者在採取任何與文中產品或公司相關的行動前，應自行研究並承擔全部責任。

• #DeFi
• #Hedera
• #驗證者
• #Cointelegraph研究文章