相关阅读：《Front Running：去中心化交易的阿喀琉斯之踵》

原文标题：《洒脱喜一周评 | 区块链抢先交易太无赖？共识算法引入顺序公平性或可破解》
撰文：Ari Juels 等
编译：洒脱喜

「天下武功 , 唯快不破」，这句话经常会出现在武侠作品当中。

其衍生出来的意思是，只要一方抢占了先机，就可以立身于不败之地。在现实世界的华尔街，这种抢先交易（Front Running）的现象就普遍存在着，这就好比两个人比武，其中一方先朝对方脸上打上一拳，然后耍赖迅速溜掉……

在审视金融系统时，对公平交易顺序的需求，是显而易见的。因为交易的执行顺序，可以确定给定交易的有效性或盈利能力。比方说 Bob 有 0 美元，并且有两笔交易发生了：其中 tx0 是 Alice 将 5 美元发送给 Bob，而 tx1 则是 Bob 将 5 美元发送给 Carol。

如果 tx0 的顺序是在 tx1 之前，那么这两笔交易都会是有效的，而相反的顺序，则会导致 tx1 失效。

而最近的研究表明，在基于共识算法的无许可区块链中，这种现象也是很常见的。Daian 等人的论文提到，机器人对以太坊网络中的交易进行了猖獗的对抗性操作，然后从单纯的用户那里获取了超过 600 万美元的收入。

那这种抢先交易「无赖功夫」有破解之道吗？本周的学术话题，我们就来分享来自康奈尔大学教授 Ari Juels 等人的最新研究《拜占庭共识的顺序公平性》。

图片来自：tuchong.com

Aequitas 协议：区块链共识不仅仅需要一致性和活性，还需要顺序公平性

在过去的三十年中，研究者们在密码学和分布式系统文献中对状态机复制的抽象概念进行了大量研究。

在高层次上，状态机复制协议的目标，是让一组节点同意不断增长的、线性排列的消息（事务）日志。

这样的协议需要满足两个属性：（1）一致性（Consistency）：所有诚实的节点必须对约定的日志有相同的 view，也就是说，它们必须以相同的顺序输出消息；（2）活性（Liveness）：客户端提交的消息，要在合理的时间内添加到日志当中，不幸的是，一致性（Consistency）和活性（Liveness）都没有在最终日志中说明事务的实际顺序。而一种确保所有节点同意相同顺序的协议，无论其如何去生成顺序，都会被认为是一致的。

区块链交易的顺序公平性

而这就给定义留下了空间，即对手方可能会控制顺序，然后让所有节点对该结果达成一致。而在所有依赖于指定「leader」节点的现有协议（包括 PBFT、FastBFT、HotStuf）中，恶意的 leader 就可选择以任何顺序提交交易。
为了纠正这个问题，来自康奈尔大学和 IC3 的 Ari Juels 教授等人提出了第三种共识属性：交易顺序公平性。

直观地讲，顺序公平表示这样一种概念：如果大量节点在另一笔交易 tx2 之前接受交易 tx1，那么这应该以某种方式反映在最终的顺序中。

而这篇论文的主要贡献有三个方面：

1. 研究了公平交易顺序的自然概念，并说明了它为什么不可能实现；
2. 研究了稍微弱一点的公平排序概念，这些概念是直观的，但却可以实现；
3. 引入了一类新的共识协议，并称之为 Aequitas，其实现了公平的区块交易排序，同时也提供了一致性和活性，研究者还讨论了同步和异步的 Aequitas 协议设置。

如何避开孔多塞悖论

顺序公平的性质是对共识问题有效性的自然模拟，即将拜占庭协议扩展到多轮。

如果所有诚实的节点都认为交易 tx1 先于另一笔交易 tx2，那么通过与有效性的自然类比，最终输出日志应该在 tx2 之前对 tx1 进行排序。因此，研究者认为，交易顺序公平性是共识文献中具有独立理论利益的自然属性。

定义顺序公平性和不可能结果：为了对共识协议进行建模，研究者使用了一种方法，其中协议节点从客户端接收交易，并需要以满足一致性和活性的方式输出或交付它们。

定义 1.1 （接收顺序的公平性，正式定义在原论文第 4.1 节），如果足够多的节点（至少γ百分比）在另一笔交易 tx0 之前接收到交易 tx，那么所有诚实的节点必须在 tx0 之前输出 tx。

虽然这个定义是直观的，但事实证明，除非我们假设具有非常强的同步性，或者不存在恶意对手方，否则就不可能实现这点。

这一结果来自社会选择理论中与选民偏好的令人惊讶的联系。为了用一个简单的例子来强调这一点，我们可以考虑三个节点 A，B 和 C，然后每个节点会接收 3 笔交易 x, y 和 z。

其中 A 按 [x，y，z] 的顺序接收它们，而 B 按 [y，z，x] 的顺序接收它们，C 按 [z，y，x] 的顺序接收它们。

请注意，大多数节点收到的是（x 后于 y），（z 后于 y）以及（x 后于 z）！这种情况通常被称为孔多塞悖论（也称投票悖论），即使所有的局部顺序都是可传递的，也可能导致非传递性的全局顺序。

而这对于接收顺序公平概念而言是有问题的。

定理 1.2 给出了关于不可能结果的非正式描述。

定理 1.2 （接收顺序公平的不可能性，正式定理描述在原论文 4.4 节）。考虑一个有 n 个节点的系统，其中外部网络（用户和协议节点之间）是异步的，或者最大延迟δ至少为 n 轮。这样，任何协议都无法同时实现一致性、活性及接收顺序的公平性。

鉴于这种不可能的结果，研究者考虑了接收顺序公平性的一种自然放松状态，并称之为区块顺序公平性。要理解这两个定义之间的主要区别，我们来看一下两笔交易 tx 和 tx'，其中有足够多的节点在 tx' 之前已接收 tx。接收顺序公平性要求 tx 必须在 tx' 之前输出，而区块顺序公平性则将条件放宽为「之前或同时」。

这里指的便是在同一「区块」中同时进行交付的交易。

定义 1.3 （区块顺序公平性，正式定义在原论文 4.7 节）：如果有足够多的节点（至少γ百分比）在另一笔交易 tx' 之前接收到交易 tx，则诚实节点无法在 tx' 之后的区块中交付 tx。

正是这种微小的放松调整，使得我们可以通过一个简单的技巧来回避康多塞悖论：将矛盾的顺序放在同一区块中。这里强调了区块顺序公平性，并不意味着交易是部分有序的。一致性仍然要求所有节点以相同顺序（在或不在同一区块内）输出交易。唯一的区别是，在研究者的定义中，只要这些交易出现在同一区块中，就被认为是公平的。

也就是说，研究者注意到，虽然不可能去实现接收顺序的公平性，但区块顺序的公平性却是可以实现的，对此，他们提出了可保证这一点的协议，并称之为 Aequitas。

Aequitas 协议的 4 种实现

Aequitas 协议以黑盒方式使用了两个基本原语：（1） FIFO 广播（FIFO-BC），它是标准可靠广播的基本扩展；（2） Set 拜占庭共识协议 (Set-BA)，其定义在原论文第 3 节，这可以通过拜占庭共识协议来实现。

注意，这些都是弱原语，任何（实现一致性和活性的）标准共识协议，也可以用于构建 FIFO-BC 和 Set-BA 原语。这产生了一个有趣的观察结果：Aequitas 技术提供了一种通用编译器，其可以将任何标准共识协议转换为提供顺序公平性的协议。

简单来看，Aequitas 协议被分为三个主要阶段。而每笔交易 tx 在交付之前，都要经过这些阶段。

阶段 1 Gossip:节点 gossip 交易按其接收顺序进行。也就是说，每个节点都在流传其本地交易的顺序。

为此，研究者使用了 FIFO 广播原语（FIFO-BC），FIFO-BC 保证诚实节点的广播由其他诚实节点，以和广播相同的顺序传递。即使发送方不诚实，FIFO-BC 也能保证所有诚实节点均以相同顺序传递消息。而这样做的结果是，节点对其他节点的交易顺序会具有一致的看法。

阶段 2 协定（Agreement）：节点在同意决定特定交易的全局顺序时应考虑其本地顺序的节点集。

阶段 3 终结（Finalization）：节点使用在协定阶段确定的一组本地排序，来最终确定交易处理的全局排序。

需要指出的是，前两个阶段（gossip 和协定）是易理解且易于实现的，而第三个阶段则很复杂，因为它需要避免康多塞悖论，同时继续保持一致性和顺序公平性。

对此，研究者分别提出了基于 leader 和无 leader 的共识协议，然后设有同步和异步设置，因而共有 4 种协议。这些协议均提供了一致性、区块顺序公平性，以及某种程度的活性。下图是这 4 种协议的比较结果。

洒脱喜简评：Aequitas 协议的思路，简单看，就好比规定两人比武只能同时出手，这就确保了双方之间的公平性，而其背后的理论，其实非常复杂，另外，根据论文介绍，Aequitas 提供了一种通用的编译器，其可以将任何标准共识协议转换为提供顺序公平性的协议，如果真正可以实现，这将解决掉区块链金融应用面临的一大难题。

(责任编辑：admin)