一周评：区块链抢先交易太无赖？共识算法引入顺序公平性或可破解

写在前面：

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

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

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

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

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

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

而在硬核技术文章精选部分，我们还会看到关于区块链活性、tBTC、稀疏默克尔树等内容。

另外，在过去的一周当中，比特币还迎来了Bitcoin Core 0.19.1版本客户端、schnorr签名及Taproot方案等更新内容，而以太坊联合创始人Vitalik则发布了新的Gasper共识协议论文。

（图片来自：tuchong.com）

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

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

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

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

1、1 区块链交易的顺序公平性

而这就给定义留下了空间，即对手方可能会控制顺序，然后让所有节点对该结果达成一致。而在所有依赖于指定“leader”节点的现有协议（包括PBFT、FastBFT、HotStuf）中，恶意的leader就可选择以任何顺序提交交易。

为了纠正这个问题，来自康奈尔大学和IC3的Ari Juels教授等人提出了第三种共识属性：交易顺序公平性。

论文链接：https://eprint.iacr.org/2020/269.pdf

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

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

（1）研究了公平交易顺序的自然概念，并说明了它为什么不可能实现；

（2）研究了稍微弱一点的公平排序概念，这些概念是直观的，但却可以实现；

（3）引入了一类新的共识协议，并称之为Aequitas，其实现了公平的区块交易排序，同时也提供了一致性和活性，研究者还讨论了同步和异步的Aequitas协议设置；

1、2 如何避开孔多塞悖论

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

如果所有诚实的节点都认为交易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。

1、3 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提供了一种通用的编译器，其可以将任何标准共识协议转换为提供顺序公平性的协议，如果真正可以实现，这将解决掉区块链金融应用面临的一大难题。

二、硬核技术文章一周精选

2、1 突破区块链不可能三角（六）——吹个关于区块链活性的哨子

maxdeath在这篇文章中，列举出了一系列关于闪电网络和区块链的已知问题。这些都是关于区块链活性安全的哨子，而这些哨子早就被吹过不止一次。作者希望这次，当未来又有人不考虑这些问题设计了某个系统，而有人通过这些问题获益时，请不要再叫它黑客攻击。

文章链接：https://www.8btc.com/media/563994

2、2 tBTC：一种新的比特币侧链设计

tBTC是一种去中心化的、有保障的比特币托管系统，它发行一种叫做TBTC的代币。用户无需信任托管者（称为签名者），因为这些签名者存入的债券价值高于他们托管的比特币的价值。如果他们要转移未经授权的资金，导致未偿的TBTC价值高于托管的比特币，系统将会没收他们的债券，用于购买和抵消市场上等值的TBTC，恢复TBTC和托管比特币价值的平衡。

文章链接：https://www.8btc.com/media/565485

2、3 Core开发者教你如何验证比特币客户端

在这篇文章中，Bitcoin Core开发者Luke Dashjr介绍了如何通过三个步骤来确保自己安装的比特币客户端是安全、未经恶意方修改的。

文章链接：https://www.8btc.com/article/566181

2、4 科普 | 什么是稀疏默克尔树多值证明

以太坊网络是一台富状态（stateful）的世界计算机，其状态包括状态余额、交易流水号（nonce）、合约代码及合约存储内容等。在技术上，这些状态数据是靠一种叫做 “默克尔树” 的结构来组织的，因此，以太坊世界状态及其访问、更新，便可表达为一棵默克尔树及其访问、更新。同样地，所有跟默克尔树相关的数据证明及验证操作，都可以在以太坊协议的语境下被理解为状态的证明及验证操作。实际上，默克尔树是我们理解、利用、改进以太坊协议不可或缺的一环。

文章链接：https://www.8btc.com/article/566768

2、5 除了“减半”，2020年你还需要关注这些比特币技术

在过去的一年时间里，比特币技术已经获得不错的发展，那种这种趋势会在 2020 年继续延续下去吗？MAST、Taproot、Schnorr 签名，以及其他出色的技术是否能进一步改善比特币安全性，并推动其价格升值吗？

文章链接：https://www.8btc.com/article/566236

三、比特币&以太坊 开发更新进展

3、1 比特币开发更新进展

1. Bitcoin Core 0.19.1版本客户端正式发布，修复了一些错误，其中大多数修正涉及钱包/ GUI / RPC；

2. BIP340 schnorr密钥和签名方案的更新，而这也会对BIP341 taproot产生一些影响，对于这些改进，作者Pieter Wuille要求社区提供有关更改的反馈；

3. 关于标准化防泄露随机数协议的提案：Stepan Snigirev在Bitcoin-Dev邮件列表上发起了关于标准化协议的讨论，该协议可防止硬件钱包使用偏斜随机数泄露用户的私钥；

4. Taproot的安全性证明：Lloyd Fournier在两周前的金融密码学会议上发表了他的研究，其描述了Taproot使用的哈希函数中，必须具备哪些属性才能确保Taproot的安全。

5. 闪电网络客户端LND 0.9.1发布，该版本并不包含任何新功能，但修复了多个漏洞，包括可能导致“节点之间强制关闭”的漏洞。

更多关于比特币的技术进展更新内容，可以看这里：https://bitcoinops.org/en/newsletters/2020/03/04/

3、2 以太坊开发更新进展

以太坊1.X更新内容：

1. 以太坊基金会成员Hudson Jameson：ProgPoW不值得，它会死亡；

2. ProgPoW算法被曝漏洞，或无法抗ASIC；

3. Trinity v0.1.0-alpha.35发布；

4. DHT方案或解决无状态以太坊数据检索问题；

以太坊2.0研发更新内容：

1. Prysmatic客户端更新，减少大量RAM，第一次罚没（slashing）成功，已更新至最新规范；

2. Lighthouse客户端更新，区块处理速度提高70%，同步速度为每秒100个区块，内存量大大减少；

3. 用于以太坊2.0 ewasm EE的零知识证明工具；

4. Vitalik等人发表论文，提出新的Gasper共识协议，其结合了Casper FFG以及分叉选择规则LMD GHOST，在不同的假设条件下可证明安全性和活性； （注：Gasper也是以太坊2.0 信标链将采用的版本）

本期的分享就到这里啦，下周再见～