N3的合约运行时随机数｜Neo专栏

为N3我们设计了一种为智能合约在运行时提供随机数的解决方案，该系统结构框图如图 1所示，由防范MEV攻击的交易列表生成单元和基于BLS的随机数生成单元组成。

在初始化阶段，共识节点执行 BLS 阈值设置过程以生成 BLS私钥并广播相应的 BLS 公钥。在每一轮共识周期之前，共识节点从整个网络里收集交易，并验证签名，然后将有有效签名的交易按照先入先出的顺序推入交易池中，而无效的交易将被丢弃直接丢弃。在新的共识周期开始时，每个共识节点生成一个交易列表，其中包含从交易池中弹出的交易哈希值，然后签署由交易哈希值构成的交易列表。与此同时，共识节点生成一个BLS签名，使用在初始化阶段生成的BLS私钥对前一个区块的哈希值进行签名。一旦节点完成生成交易列表和BLS签名的工作，节点就会向共识网络广播一条包含这两组数据的消息。

图1 运行时智能合约随机数系统结构图

防御MEV攻击的交易列表生成单元。在运行时为智能合约提供随机数的最大挑战之一是 MEV 攻击，它允许攻击者提前预测甚至直接获取随机数。并且一旦随机数泄露，攻击者可以比其他智能合约用户获得不公平的优势。因此，在我们甚至可以为智能合约生成随机数之前，解决MEV攻击至关重要。

MEV攻击之所以存在，是因为交易顺序在一定程度上几乎可以被任何人操纵。对于议长节点，即生成新块的节点，它可以控制交易顺序。它可以从区块交易列表中删除一个有效的交易，临时构造一个新的交易并将其插入到区块交易列表中，或者简单地改变交易顺序。即使是普通用户也可以通过改变交易费用来发动MEV 攻击，例如三明治攻击。因此为了解决 MEV 攻击，我们必须解决交易排序的公平性问题。

图2 存在MEV攻击的随机数生成器

图3 抵抗MEV攻击的随机数生成器

交易排序算法在以下情况下实现公平排序：

当议长共识节点收到来自其他共识节点的节点交易列表时，它尝试聚合来自共识节点的节点交易列表最终交易列表, 聚合出的区块交易列表对其他公式节点来说是可验证的，因此议长共识节点在生成区块交易列表时无法作恶。该单元共有两个组成模块。一个是FIFO的交易缓存池，另一个是公平排序的交易列表聚合器。

FIFO交易缓存池是一个先进先出的交易缓存池，存在于每个共识节点中。缓存池本质上是一个交易队列，节点从网络中获取到的交易将从队列的尾部推送入缓存池，然后从队列前端弹出交易，从而实现对，交易实现先入先出的排序逻辑。此外，在把交易推入缓存池之前，节点会验证交易的数字签名以及节点本身的账户余额。只有那些通过了签名验证并且有足够的余额支付手续费的交易，才会被推入缓存池中。而那些验证失败的交易，将会直接被丢弃。在每轮共识开始的时候，节点会从缓存池中获取一定数量的交易并将这些交易打包成节点交易列表。这些节点交易列表将会被广播到网络中。议长节点将会监听网络中的这些包含了节点交易列表的信息。

交易列表聚合器。实现公平的交易排序是防御MEV攻击的关键所在，而交易列表聚合器，则是每个节点都可以收集网络中的交易。原则上每个节点都有交易节列表聚合器且在每一轮共识周期里都以可以对来自于网络中的交易列表进行聚合，但是为了简化系统复杂度，在每一轮共识周期里，只有议长节点需要从网络中收集交易列表并且聚合。在实现聚合器的时候有几个前提假设。首先假设所有在共识网络中所有的正常节点，都可以正常的与其他节点进行通信，也就是说正常节点都可以收到其他正常节点的交易列表。此外，还假设，如果一笔交易是正常的并且满足被打包的条件，那么它将一定会被所有的正常节点包含在交易列表里。当满足以上两个假设条件的情况下，我们可以说所有正常的节点的交易列表将是差不多的。

有一个方案为基于拜占庭容错共识机制的解决方案，因此我们假设正常的节点将会超过总共识节点数量的2/3。也就是说，如果一笔交易满足所有被打包的条件，并且不是来自于一个恶意的攻击者，那么我们会在超过2/3个节点交易列表中看到这笔交易。而且由于我们假设正常节点的网络状态不受干扰，因此我们也可以假设，这笔来自正常节点的交易，将在所有超过2/3个正常节点交易列表中，拥有着几乎相同的交易排序。

基于以上分析，我们在聚合节点交易列表的时候，先判断一笔交易是否同时存在于超过2/3个节点共识交易列表中。我们只会考虑聚合那些同时存在于超过2/3个节点共识交易列表中的交易，同时考虑到整个系统中还有不超过1/3的恶意节点。这些恶意节点，可能会恶意地构造交易列表。如果我们将这些来自于恶意节点的交易列表也考虑到最终的聚合系统中，那么我们的系统将会把这些恶意的攻击带入到我们最终的聚合结果中。因此在聚合这些交易列表的时候，我们还需要对其离群值进行判断。因为我们没有办法直接的去判断哪些节点交易列表来自于正常节点，哪些节点交易列表来自于恶意节点，因此我们只能整体的对交易的排序来进行离群值的计算。

在我们的方案中，我们从超过2/3个节点交易列表中获取到一笔交易的所有的下标，然后然后计算每个下标与其他下标之间的距离，当一笔交易在某一个节点，交易列表的下标。与其在其他节点交易列表中的下标的距离过远时，我们将认定其为离群值。由于没有办法去判断整个聚合过程中有多少恶意节点的参与，因此我们将离群值的数量定义为不超过1/3的节点数量。例如当我们一共有七个共识节点的时候，我们在聚合交易列表的时，只需要获取五个节点交易列表，而在计算聚合结果的时候，我们还要从这五个节点交易列表中，计算出不超过1/3个恶意节点的数量，也就是说两个离群值，因此我们在最终聚合的时候，将会是有三个节点交易列表参与到最终的区块交易列表聚合。而最终的区块交易列表将会和由生成他它的节点取关列表，一起被广播到整个网络中，其他的共识节点在收到这个信息的时候，也可以根据相同的逻辑自己去生成区块交易列表来验证来自于议长节点的区块交易列表是否为真。由于该方案具有可验证性，并且聚合结果来自于整个共识网络。该方案实现了可验证的，并且具有公平性的交易列表。

由于本方案的区块交易排序算法不是按交易费排序，而是使用FIFO机制来管理交易池中的交易并且使用将以列表聚合的机制来生成最终的区块交易列表，使得攻击者无法通过支付大量交易费来改变交易顺序。在区块交易列表的聚合过程中，每笔交易的排序由其在节点交易列表中整体位置计算决定而来，因此没有人可以决定它。

区块交易列表生成之后，共识节点还会对生成的区块交易列表进行验证，如果交易的排序或交易数未通过验证，那么本轮共识节点会失败，并触发视图更改，从而进行下一轮新的共识。

BLS的随机数生成单元。在区块链这种去中心化的环境中生成一个公平的随机数是非常困难的。它与传统的服务器-客户端模式不同。我们没有一个中心化的服务器，可以为我们生成随机数。与此相反，区块链网络中的节点是平等的，相互之间没有信任的存在，任何节点，都可能是一个恶意的节点。因此，我们没有办法依赖于任意一个节点去为我们生成随机数。虽然我们可以在可信执行环境中生成随机数，例如SGX，可是研究证明可信执行环境存在着各种各样的侧信道攻击使得可信执行环境本身并不安全。

在运行时为智能合约生成随机数则更加艰难。因为随机数本身将会被用来作为执行的输入参数。随机数这个值本身将会被直接用来影响智能合约以及交易的执行结果。因此我们认为随机数不应该由任何人个人决定，否则决定随机数的人可以利用这种力量产生一个对自己最有利的价值。而且随机数不应该被公众知道，无论如何都不能改变交易状态，这样就没有人可以利用这个数字。随机数应该是可验证的、无偏见的和唯一的。最重要的是，随机数应该是不可预测的。

我们认为一个公平的随机数算法应该满足以下几个条件：

经过谨慎选择，本方案使用的是基于BLS聚合签名算法的随机数生成方案。随机数生成共分为两个步骤。在每一轮共识开始的时候，每个节点将使用自己本地的BLS私钥来对上一轮共识结果的区块的哈希值进行签名，并把签名的结果结果广播到整个共识网络中。所有的共识节点将会在网络中监听来自于别的共识节点的BLS签名，当签名的数量收集到一定的阈值的时候，就可以用来对这些签名进行聚合，聚合的结果会作为随机数的生成种子。当一个共识节点从共识网络接收到足够多的BLS签名时，它会调用BLS聚合算法将这些BLS签名聚合成一个最终的签名，并且这个最终的签名被用作随机数，因为所有共识节点运行相同的BLS算法，因此所有共识节点生成的随机数是相同的。

考虑到整个网络是基于拜占庭容错共识算法，我们将BLS签名聚合的阈值设为超过所有共识节点数量的1/3。举例说明，当我们的网络中有七个共识节点的时候，那么我们只需要收集到三个共识节点的签名，就可以聚合成最终的签名，也就是我们的随机数种子。之所以考虑到设置节点数量为超过1/3，是因为如果我们把阈值设为小于共识节点的1/3，那么恶意节点将会可以联合起来，构造虚假的聚合签名。

该方案为一种去中心化的智能合约随机数解决方案，在本方案执行的时候，逻辑由系统内的共识节点一起协作完成。基于BFT类的共识算法，本方案的共识节点分为两类，一种是普通的共识节点，另一种是负责区块生成的议长（primary）共识节点。

图4 单节点执行流程图

在共识周期的间隙，共识节点将会持续从网络中获取到来自于用户的交易，并把这些交易放到自己的交易缓存池中。在每一轮共识开始的时候，所有的共识节点都将会生成自己本地的BLS签名，并且生成自己的节点交易列表。如果这个交易节点是普通的共识节点，那么他将在发送完自己的BLS签名和节点交易列表之后，将会开始对网络进行监听，以获取来自于其他共识节点的BLS签名，并且如果收到的签名数量超过了阈值，将会直接进行签名的聚合。而如果当前节点是一个议长节点，那么他将会从网络中不停地监听这些包含了BLS签名和节点交易交列表的消息并且判断这些消息的数量是不是超过了阈值。当议长节点收到了超过2/3的节点交易列表之后，它将会启动交易列表的聚合过程，同时也会聚合BLS签名。

当议长节点完成了对BLS签名和对节点交易列表的聚合之后，会生成一个最终的BLS签名以及一个区块交易列表，基于这些数据他将会生成一个新区块提案并发布到整个网络中。普通的共识节点将会收到新区块的提案，并对这个提案进行验证，主要是验证区块交易列表是否真实以及BLS签名是否真实.如果一个新的区块提案通过了验证，那么当前的共识节点将会确认新的区块提案,否则共识节点将会发起投票以更新视图并开启新的共识。

但是基于回调机制的随机数方案本身存在一些问题。比如延迟很高，需要等待至少两个区块时间才能获取到一个随机数；链上开销很高，需要额外的交易来把随机数写入区块链；手续费昂贵，用户需要支付两笔交易的手续费，并且还要支付随机数服务费；信任问题，回调机制往往需要引入可信的第三方来生成随机数。因此为了解决以上问题，我们需要能够为智能合约在运行时提供随机数。

图 5 完整共识流程

由于该方案是基于拜占庭容错共识协议，为了增强随机数算法的公平性, 我们对现有的共识协议做出了改进。如图三所示, 本方案的共识是基于实用拜占庭容错共识算法更改而来。在传统的实用拜占庭容错共识协议的基础之上，我们增加了两个步骤。一个步骤是用于收集各个节点的BLS签名以及用于防范MEV攻击的节点交易列表，另一个步骤只是对收集到的BLS签名和节点交易列表进行聚合。当我们已经有了合法的BLS签名以及区块交易列表之后，我们就可以按照原本的实用拜占庭容错的共识算法，由议长节点将新区块的提案来广播到整个网络中并发送pre-prepare的消息来通知其他的节点来对新区块的提案进行验证。而共识节点将会将其验证的结果广播到整个网络中以作为回复。当共识节点收到超过2/3个其他共识节点的回复之后，新区块就会被确认。相较于拜占庭协议，我们只是在协议开始的时候，增加了两个步骤,完全不会影响整个共识协议原本的安全假设.

为了评估性能，我们使用FAST-BLS来做BLS的签名和聚合，用Fisher–Yates shuffle来做交易列表的公平排序。此外我们还实现了几个智能合约来对随机数的调用开销做测试，尤其是我们实现了一个合约来模拟基于回调机制的操作流程，并且与运行时随机数的调用过程进行比较。

 BLS聚合时间 

 运行时随机数和回调机制下的随机数方案GAS手续费消耗的比较 

 几种使用运行时随机数的合约GAS消耗 

 公平排序的时间开销 

 运行时随机数相较于回调机制下的随机数方案少写入区块链的数据量