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

写在前面：

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

其衍生出来的意思是，只要一方抢占了先机，就可以立身于不败之地。在现实世界的华尔街，这种抢先交易（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）：所有诚实的节点必须对约定的日志有相同的iew，也就是说，它们必须以相同的顺序输出消息；（2）活性（Lieness）：客户端提交的消息，要在合理的时间内添加到日志当中，不幸的是，一致性（Consistency）和活性（Lieness）都没有在最终日志中说明事务的实际顺序。而一种确保所有节点同意相同顺序的协议，无论其如何去生成顺序，都会被认为是一致的。

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

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

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

1. Bitcoin Core 0.19.1版本客户端正式发布，修复了一些错误，其中大多数修正涉及钱包/ GUI / RPC；
2. BIP340 schnorr密钥和签名方案的更新，而这也会对BIP341 taproot产生一些影响，对于这些改进，作者Pieter Wuille要求社区提供有关更改的反馈；
3. 关于标准化防泄露随机数协议的提案：Stepan Snigire在Bitcoin-De邮件列表上发起了关于标准化协议的讨论，该协议可防止硬件钱包使用偏斜随机数泄露用户的私钥；
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 0.1.0-alpha.35发布；
4. DHT方案或解决无状态以太坊数据检索问题；

以太坊2.0研发更新内容：

1. Pryatic客户端更新，减少大量RAM，第一次罚没（slashing）成功，已更新至**规范；
2. Lighthouse客户端更新，区块处理速度提高70%，同步速度为每秒100个区块，内存量大大减少；
3. 用于以太坊2.0 ewa EE的零知识证明工具；
4.  Vitalik等人发表论文，提出新的Gasper共识协议，其结合了Casper FFG以及分叉选择规则LMD GHOST，在不同的假设条件下可证明安全性和活性； （注：Gasper也是以太坊2.0 信标链将采用的版本）

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