一种使用量子随机数的拜占庭容错机制

2019-04-18汤红波

网络安全技术与应用 2019年4期

◆任明汤红波王理

（信息工程大学河南 450001）

0 引言

随着区块链技术在最近几年的快速发展，该领域内的应用项目也在逐步增多。包括金融、物联网、医疗在内的诸多行业，都已经开始在各自的业务内使用区块链技术。区块链技术通过使用加密技术，可以为多种形式的业务场景提供可溯源。由于其具有不易篡改的特性，能够在非信任的条件下为业务的参与者们提供可信的业务环境，有效地提升了业务逻辑的可信程度。

共识机制是区块链技术中的重要组成部分之一。随着区块链技术的快速发展与应用项目的逐步增多，在最初比特币[1]系统中使用的 PoW(工作量证明)机制远不能达到业内人士对于网络性能的期望。因此，学者们陆续提出了不少关于共识机制改进和优化的方案。比较典型的包括PoS机制[2]、DPoS机制[3]、Raft协议[4]、Ripple协议[5]、SCP[6][7]，等等。拜占庭容错(BFT)算法也是其中之一，用来解决在网络通信可靠、但是节点自身可能出现问题的情况下如何达成共识的问题，该类算法的可靠性可以通过严格的数学证明作为保障。但是，所有的BFT问题的解决方案都存在复杂度过高而难以实现的问题。在2002年Castro与Liskov提出的PBFT算法[8]虽然将拜占庭容错算法的复杂度由指数级降低到了多项式级别，但是其实现的复杂度仍然较高。同时，在Hyperledger Fabric项目V0.6版本中对其的应用中，有研究学者发现PBFT算法的网络扩展能力会受到很大的限制[10]。因此，本文基于PBFT算法，提出一种简易的拜占庭容错共识协议来提升网络中的共识效率。与此同时，将量子随机数的概念引入共识机制的设计中，用来解决传统的伪随机数在共识参与者选择过程中的伪造问题以及控制共识过程的安全问题。

1 PBFT算法

拜占庭容错算法起源于1980年Leslie Lamport等人发表的论文《Polynomial Algorithms for Byzantine Agreement》，文中提出了针对拜占庭问题[9]的容错算法。这种算法既要在保证节点间网络状态一致，同时也要确保记录数据的正确性。

PBFT算法在一定程度降低了算法复杂度的同时，在密码学方面引入了 RSA签名算法与消息验证的编码、摘要技术来保证信息在传递的过程中不会受到恶意的篡改和破坏。此算法具有1/3的容错率，当出现不超过1/3的失效节点时，该算法可以保证网络的安全性与活跃程度。事实上，即使有超过1/3的节点联合作恶，虽然有可能因此造成系统出现分叉，但是仍然在密码学方面会留下可溯源的证据。

在共识过程中，PBFT算法通过轮换或者随机算法选择主节点，在主节点没有更换的时间段内系统的配置信息称作一个视图（view）。通过三个阶段的协议过程，PBFT算法能够保证请求的发送顺序在同一个视图内是正确的，并且可以确保在不同的视图之间对请求进行确认的顺序是具有确定性的。结果会在所有节点处理完请求之后返回给客户端。在客户端，将会检查来自不同节点产生相同结果的数量，验证该数量是否大于f+1（f为系统允许的最大失效节点数量）。如果满足这个条件，就把它作为最终的排序结果。这个结果会通过有记账功能的节点写入区块链。该算法的共识过程如图1所示。

PBFT机制出现在包括联盟链和私有链在内的权限链场景中。这是因为PBFT算法重点解决的是对请求的排序共识问题。当排序过程完成之后，网络中的状态已经具有确定性，任何区块都是最终确定的，不会产生分叉。因此，参与网络的节点仅需要按照这个确定的排序结果，在处理完请求之后将最终结果记入本地账本即可。当网络规模过大，需要经过对共识机制进行一定程度的调整，才能够使用这种算法。在共识过程开始之前，首先通过选举或者随机算法选择出一定数量的共识参与者(本文中称为group)，这个数量可以通过其他机制进行确认，并且 group的成员可以进行更替。之后，共识过程将在group内进行，其他的网络节点可以通过广播的方式从记账节点获取最终产生的区块即可。

已经有学者对PBFT进行过简化[11][12]。这两种方案都是在提升了对网络环境信任程度之后进行的简化，特别是文献[12]的方式，基本需要建立在完全可信的环境中。他们在提升网络吞吐量的同时，增加了较强的限定条件或者预先设定好的节点身份，这在网络规模的扩展方面会产生不利影响。

2 随机数和随机性

随机数很早就已经得到业内人士的重视，在学者们对它的研究过程中诞生了不少产生随机数的方法。这些产生随机数的方法被统称为随机数发生器。在现代社会中的仿真学、物理学、密码学等诸多领域中，随机数都存在着重要的应用，其本身应当具有不可预测的特性。目前，在上述领域实际的应用中，通常会使用具有确定性的算法，通过随机种子来产生随机数。这种由算法产生的随机数，其熵含量在很大程度上依赖于种子序列的熵值。虽然看似是均匀分布的，但是在这些随机数之间存在自相关性，导致产生结果仍然是可以被预测的。随着科技水平以及计算机计算能力的不断提升，使用此类方式生成的伪随机数会导致相关系统的安全性受到严重的威胁。不论是在密码学，还是在区块链的共识机制当中，都会存在被破解、被利用的隐患。

目前，量子技术已经成为密码学和网络安全业内的热门技术，在很多的应用中都被认为能够起到重要作用。由于很难证明已经形成的随机数序列是否具有真正的随机性，所以需要在随机数的产生源头及产生过程之中予以保证。随机序列需要实现包含有最大熵含量的真正不可预测特性。量子随机数的随机特性是基于量子物理自身的不确定性，是能够通过信息论进行证明的。因此，通过物理随机现象产生真正的随机数来保证系统安全是可行的有效方式。

在区块链技术中，随机数能够起到至关重要的作用，使用量子随机数可以有效提升网络中的安全性。从密码学角度看，随机数的可靠性会严重影响区块链系统中密钥体系的安全问题。共识机制作为区块链技术的一个重要组成部分，同样可以通过使用随机数的方式提升网络性能。一些共识机制为了提升网络的可扩展能力，会利用随机数选择共识协议的参与者，这样既不会降低共识效率，也使网络的扩展能力得到有效提升。在这个过程中，可以利用量子物理学的理论生成真正的随机数。此外，在主节点的更替机制中，量子随机数同样能够发挥作用。

在对生成序列进行随机性检测的问题研究中，有学者提出使用复杂度量化[13]以及其他一些统计测试方式进行保证。但是，这些方式的核心思想是通过观测进行判断，并不能有效检测到恶意的人为设定。在一篇关于随机数发生器的研究[14]中作者认为，真正的随机性只能通过物理原理上内在的随机性来进行保证，可以利用量子测量中固有的随机性来产生真随机数；同时，可以通过量子信号与经典噪声的信噪比来估算真随机性的大小。

3 解决的问题

在目前使用拜占庭容错算法的共识机制中，存在以下三点关键的性能问题。

（1） BFT算法普遍复杂度高，通信开销大

虽然业内对BFT算法的研究已经持续了将近四十年的时间，但是，其中大多数的研究长期停留在理论阶段，缺少与之相符的程序代码。这是由于 BFT算法普遍复杂度过高，难以实现造成的。虽然PBFT算法已经在前人研究的基础上明显降低了算法的复杂度，但是在完成共识的过程中会产生大量的通信开销。在网络带宽固定的条件下，当网络扩展到一定规模之后，会由于节点间的通信开销过大导致出现网络拥塞，造成共识失败，使得网络的扩展能力受到限制。同时，在现有的PBFT算法实现中，其复杂度依然相对较高。在确认算法安全程度的前提下，简化节点之间的通信过程，对共识协议进行优化等方式可以有效解决这类问题，使参与共识节点规模的扩展能力得到提升。

（2）随机数的可靠性

使用传统随机数发生器产生的随机数通常会使用长度有限的种子序列及确定性的算法生成。通过使用量子随机数发生器，产生具有真正随机性的随机数。使用量子随机数的共识机制能够得到更高的可靠性。

（3） BFT算法的网络扩展能力

BFT算法的主要作用是解决请求的排序共识问题，通常是在强一致性要求下的联盟链和私有链场景中使用。但是，随着业务规模的发展，网络中的节点数量也会越来越多。在这种情况下，当参与共识的节点的数量达到一定规模的时候，共识效率会由于通信过程开销过大造成的网络拥塞，进而造成共识失败[15]。因此，当网络规模达到一定程度的时候，共识过程并不一定需要全部的节点参与。可以通过事先约定的机制对共识参与者进行选择，这个group的成员规模可以在确定节点间彼此信任的条件下尽可能小，以此来保证共识效率，并有效降低通信开销。

4 基于量子随机数的拜占庭容错机制

4.1 量子随机数发生器

量子随机数发生器能够为区块链技术中的共识机制带来多角度可靠性的提高。

通过理论建模的随机数发生器可以实现较高的随机数产生速率。但是，这种方式仍然依赖于随机数发生器设备的可信程度，恶意的制造商仍然可以提前通过提前内置的字符串预测随机数的输出情况。

基于设备的可信度，量子随机数发生器（QRNG）可以分为三类。第一类是建立在完全可信设备上的实用QRNG，通常可以通过对设备进行适当程度的校准和建模高速生成随机数。第二类是自我测试QRNG，它是在不信任设备的情况下生成随机性可验证的随机数，其生成速率可能会受到信任条件的限制。第三类是半自测QRNG，它是一种在设备的可信程度和随机数生成速率之间进行一定程度权衡之后的中间产物。

4.2 QRBFT机制

QRBFT(Quantum Random Byzantine Fault Tolerance)是为区块链技术服务的一种共识机制。提出此共识机制的目的是在网络的扩展能力以及共识效率的提升方面做出平衡。通过在协议中使用量子随机数，能够有效提升选取共识参与者的随机性，能够保证在非完全可信的网络环境中参与共识过程节点的可靠性。

QRBFT机制可以分为两个子过程：选举和共识。

4.2.1 选举过程

在当前区块链技术的研究过程中，也存在不少通过选举过程生成区块的共识协议。但是，它们大多采用选举产生leader负责区块生成的方式。这种方式在一定程度上确实能够提升共识效率。但是，通常在使用此类方案的同时，也必须要配合使用leader的更替机制来解决可能发生的记账节点崩溃等问题。

而在BFT算法中，解决的是共识与一定程度的容错问题，在共识协议的扩展能力方面会受到限制，这在其本身的算法中很难得到有效的解决。为了使 BFT算法能够在更大规模的网络环境中使用，同时，希望在尽可能多地让网络节点在参与共识过程的前提下不再引入其他额外的协议，提出将选举过程与 BFT算法结合使用的共识机制。在此机制中，选举过程将为BFT算法过程提供共识的参与者。

在超级账本（Hyperledger）的子项目Sawtooth中使用了PoET共识机制[16]，节点上会部署统一的可靠计时器，基于对时间消逝的证明选择记账节点。我们在此基础上进行了思路的拓展，使用量子随机数的方式对共识参与者进行group的选取。当新一轮共识过程开始前，全部的网络节点通过各自的量子随机数发生器生成一个随机数，以广播的方式发送给网络中的其他节点。在一个时间周期内，系统将直接选择中间若干个随机数对应的节点作为共识过程的参与者，若干轮共识过程结束之后会重新要求节点生成随机数，实现对 group的成员进行更替。当网络中出现延迟，一些随机数无法在指定的时间周期内到达其他节点，节点间对选举过程可能因此无法达成一致，即不同的网络节点可能选择了不同的group。因此，在节点选择出group之后，会将group的信息形成摘要，发送给其他节点，收到此信息的节点将进行验证。只有在确认group信息得到全网一半以上节点的情况下，该group的成员才能够开始共识过程。此外，也可以引入检查点机制来进行一致性校验和全网状态的同步，但这样做会带来额外的开销。

4.2.2 共识过程

当选举过程结束之后，网络将进入共识过程。在对PBFT算法的优化方案中，文献[11]在没有收到信息的前提下使节点根据之前计算产生的结果直接进行后续计算，副本节点不经过共识过程直接执行请求，也不需要考虑系统中的一致性问题，如图2所示。文献[12]则是通过指定一个区块生成者（block generator）负责收集并验证网络中提出的交易信息，周期性地将它们批量打包成一个新的区块提案。共识过程由区块生成者和指定的区块签名者（小部分）依照配置好的规则完成，而其他的区块签名者（大多数）负责验证区块提案，并通过使用数字签名批准该提案。

图2 Speculation Byzantine Fault Tolerance算法示意

在QRBFT的共识过程中，由选举产生的共识group成员之间通过与选举过程相同的随机数方式选举产生 leader。leader的更替采用轮换制度。因为参与共识过程的group是通过选举过程产生的，因此可以认为 group的成员是可以信任的。同时，QRBFT在算法中也进行了相应的调整。副本节点在收到来自leader节点的排序请求后，将会依据事先约定的规则对排序信息的合法性进行验证（如图3所示）。如果排序信息符合条件，则可以确认该排序是合法的；否则，副节点将向主节点重新请求排序信息。

图3 QRBFT共识过程

4.3 QRBFT机制的性能

（1）算法复杂度

QRBFT算法针对PBFT算法在共识过程中复杂的通信开销进行了适度的简化，将两次的提交确认过程转变为对信息规则与格式的校验。该验证过程在节点本地进行，不与其他节点进行通信。在减少算法逻辑步骤的同时，也可以大幅度降低共识过程中的通信开销。

（2）安全性

由于在共识机制中引入了量子随机数，本地节点在选举过程中无法预测其他节点产生的随机数，并且在生成随机数的过程中不可能进行人为干预。所以，选举group成员的过程与leader选举的过程中，所有节点都是在公平可靠的环境中进行的。由选举产生的 group成员是真正随机、无法被预测的，共识过程中的leader也是可靠的、可以被信任的。因此，在QRBFT共识机制中可以避免出现拜占庭问题，系统只需要解决leader节点出现故障情况下的更换问题。

（3）扩展能力

在 BFT算法进行之前增加选举过程的目的是提升网络的扩展能力。传统的BFT算法，特别是PBFT算法，不仅算法复杂度过高，而且共识过程繁杂的通信过程会使网络规模受到非常严重的限制。通过引入选举过程，可以使参与共识过程的节点规模得到有效控制，减少系统内总体的通信次数，使由于通信信息占据的内存尽可能降低，从而在保证网络吞吐量的前提下使网络的扩展能力得到有效提升。