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

数十年来，分布式系统的研究，特别是在拜占庭共识和状态机复制（SMR）方面，主要关注两个目标：一致性和活性。一致性意味着所有节点对相同的交易序列达成一致，而活性确保系统持续添加新交易。然而，这些属性并不能阻止恶意行为者在接收交易后改变交易顺序。

在公共区块链中，传统共识保证的这一差距已成为一个严重问题。验证者、区块构建者或排序者可以利用其在区块排序中的特权角色谋取经济利益，这种行为被称为最大可提取价值（MEV）。这种操控包括盈利的抢跑、回跑和夹击交易。由于交易执行顺序决定了DeFi应用中的有效性或盈利性，交易排序的完整性对于维护公平和信任至关重要。

为解决这一关键安全漏洞，提出了交易顺序公平性作为第三个基本共识属性。公平排序协议确保最终的交易顺序依赖于外部、客观的因素，如到达时间或接收顺序，并且对抗对手的重新排序具有抵抗力。通过限制区块提议者重排交易的能力，这些协议使区块链更接近透明、可预测且抗MEV。

柯尔登悖论与理想公平的不可行性

最直观且最强的公平性概念是接收顺序公平性（Receive-Order-Fairness，ROF）。非正式定义为“先接收，先输出”，ROF规定：如果大多数节点先接收到交易tx，而另一交易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₂。

在这个例子中，恶意节点E将tx₁的时间戳设为较晚的3，将tx₂的时间戳设为较早的2，从而扭曲中值。

当协议计算中值时：

• tx₁的时间戳为1、1、4、4、3，中值为3；
• tx₂的时间戳为2、2、5、5、2，中值为2。

由于tx₁的最终时间戳（3）大于tx₂（2），协议输出的排序为tx₂→tx₁，逆转了所有诚实节点观察到的真实顺序。

这个示例揭示了一个关键缺陷：中值函数虽然看似中立，但实际上是公平性的根源，因为它可以被单一不诚实的参与者利用来偏置最终交易顺序。

因此，Hashgraph所谓的“公平时间戳”实际上是一种相当脆弱的公平性概念。Hashgraph共识未能保证接收顺序公平性，而是依赖于权限验证者集，而非基于密码学保证。

实现实际保障的方法

然而，为了规避柯尔登悖论所证明的理论不可能性，实际的公平排序方案必须在某种程度上放宽公平性的定义。

Aequitas协议引入了区块排序公平性（Block-Order-Fairness，BOF）或批次排序公平性。BOF规定：如果足够多的节点在交易tx′到达之前接收了交易tx，那么tx必须在区块中先于或同时于tx′被交付，也就是说，没有诚实节点可以在tx之后在区块中交付tx′。这将“必须先交付”这一规则从“必须在之前交付”（ROF）放宽为“不得迟于”。

假设有三个共识节点A、B和C，以及三笔交易tx₁、tx₂和tx₃。交易被认为“先接收”如果至少两个节点（多数）观察到它。

通过多数投票确定全局顺序：

• 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，但也面临重大限制，特别是通信复杂度很高，只能保证较弱的活性。弱活性意味着，交易的交付只有在整个柯尔登悖论循环完成后才能保证，如果循环“链式”形成，可能需要很长时间。

为此，Themis协议被提出，以在保证强BOF的同时，改善通信复杂度。Themis通过三种技术实现：批次展开（Batch Unspooling）、延迟排序（Deferred Ordering）和更强的批内保证（Stronger Intra-Batch Guarantees）。

在标准形式下，Themis要求每个参与者与大部分节点交换消息。通信量随着网络节点数的平方增长。然而，在优化版本SNARK-Themis中，节点使用简洁的密码学证明验证公平性，无需与每个节点直接通信，从而将通信负载线性化，支持大规模网络。

假设五个节点A–E参与共识，接收三笔交易tx₁、tx₂和tx₃。由于网络延迟，它们的本地排序不同：

在Aequitas中，这些偏好形成柯尔登循环。但Themis不等待循环全部解决，而是采用批次展开的方法，识别所有属于循环的交易，将它们归入一个强连接分量（SCC），在本例中，所有三笔交易都属于同一SCC，Themis将其作为一个批次输出，标记为批次B₁ = {tx₁, tx₂, tx₃}。

通过这种方式，Themis允许网络在内部排序尚未最终确定时，继续处理新交易，确保系统保持活性，避免停滞。

概述

在交易排序中实现“完美公平”的概念看似简单：谁先到达网络，谁就先被处理。然而，柯尔登悖论证明，在实际的分布式系统中，这一理想无法实现。不同节点看到的交易顺序不同，偏好冲突时，没有任何协议能在不妥协的情况下建立一个“正确”的全局序列。

Hedera的Hashgraph试图用中值时间戳逼近这一理想，但这种方法更依赖信任而非证明。单一不诚实的参与者就能扭曲中值，逆转交易顺序，显示“公平时间戳”并不真正公平。

像Aequitas和Themis这样的协议，推动了对可实现范围的认识，承认在现实网络条件下，公平性必须重新定义。它们不是拒绝公平，而是在其演变中，区分了感知公平和可证明公平。真正的去中心化系统中的交易排序完整性，不能依赖声誉、验证者信任或权限控制，而必须依靠协议内嵌的密码学验证。

本文不提供投资建议或推荐。每项投资和交易都伴随风险，读者应自行研究后做出决策。

本文仅供一般信息参考，不构成法律或投资建议。文中表达的观点仅代表作者个人，不一定反映Cointelegraph的立场。

Cointelegraph不支持本文内容或其中提及的任何产品。读者在采取任何行动前，应自行调查相关信息，并对自己的决策承担全部责任。