同步可靠网络环境中区块链系统状态机研究

刘 凤 王 欣

1(河北地质大学信息工程学院 河北 石家庄050000)

2(奥斯特拉发技术大学电气工程与计算机科学学院 捷克 奥斯特拉发 70800)

3(河北软件评测中心 河北 石家庄 050000)

0 引 言

1978年Leslie Lamport将分布式系统定义为,由一组不同的进程组成,这些进程在空间上是分开的,并且通过交换消息彼此通信,如果消息传输延迟与单个进程中事件之间的时间相比不可忽略,则系统是分布式的[1]。自此,分布式系统逐步引起计算机学术界的关注,文献[2-3]提出了分布式系统协议。自2002年起,Peer-to-Peer体系的研究和应用广泛开展[4]。2008年Satoshi[5]提出了基于Peer-to-Peer的电子现金系统——比特币。到2020年,以分布式系统为基础的区块链技术逐步发展,并开始在不同行业应用。Bonnet等[6]在采用SnowWhite、Algorand和Ouroboros协议的PoS机制区块链基础上,提出了基于分布式账本技术(DLTs)状态机模型理论,该模型要求网络节点之间必须建立两两实时互联,存在模型构造单一、设定的前提条件过于理想、与实际应用相差较大的不足。本文在Bonnet提出的基于分布式账本技术(DLTs)状态机模型的基础上进一步抽象建立了离散节点分布网络状态机模型并开展双射证明。新建立的状态机模型可以更广泛应用于不同共识机制的区块链分析,适用性和实用性得到扩展和提升。

1 概 念

1.1 区块链(Blockchain)

区块链没有精准的定义。Satoshi将电子现金定义为数字签名链。即每个拥有者通过数字签名前一个交易的散列和下一个拥有者的公钥并将其添加到现金链的末尾,将现金转移给下一个人,收款人则可以通过验证签名来确定链的所有权[5]。Buterin将其定义为：一种神奇的计算机,任何人都可以上传程序并让程序自动执行,其中每个程序的当前和以前所有的状态均是公开可见的;其具有强大的加密安全保证,且在区块链链上的程序将以协议指定的方式运行[7]。袁勇等[8]将区块链定义为狭义和广义两种,狭义是指一种按照时间顺序将数据区块以链条的方式组合成特定的数据结构,并以密码学方式保证其不可篡改和不可伪造的去中心化共享总账(Decentralized Shared Ledger),能够安全存储简单的、有先后关系的、能在系统内验证的数据。广义的区块链技术则是利用加密链式区块结构来验证与存储数据、利用分布式节点共识算法来生成和更新数据、利用自动化脚本代码(智能合约)来编程和操作数据的一种全新的去中心化基础架构与分布式计算范式。分布式账本(DLT)是区块链的底层核心技术,本文研究的区块链状态机系统是应用DLT对比特币、以太币等应用系统进行模型化抽象,以保证研究结论不受具体应用场景的限制。

1.2 共识机制(Consensus)

分布式系统通过建立所有节点共同遵守的机制,使系统作为一个整体能够在有限数量的子节点出现故障的情况下继续工作。这些制度被称为“共识机制”(也称为“共识协议”),它们负责分布式系统中所有子节点之间的协作[9-10]。区块链的运行规则是共识机制。共识机制一般是由设计分布式系统的团队编制,并开发出相应的程序,提供给节点使用。区块链的共识机制的升级、改变需要所有子节点一致同意,如果不能达成共识,任何参与节点都可以实施硬分叉,另建一条区块链。这也是区块链共识机制的去中心化特性。区块链通过去中心化解决信任问题,基于算法使陌生节点在不借助于第三方的情况下能够达成共识。

1.3 共识算法

共识算法是共识机制的一部分。区块链系统的共识算法首先需要解决非信任网络环境中的拜占庭将军问题(Byzantine General Problem)[11],即区块链网络中存在恶意节点,会主动违反协议或传输错误的数据,从而对整体区块链网络造成干扰和破坏。因此区块链系统必须采用能够容忍拜占庭将军问题的一致性算法(共识算法)。目前最常见的共识算法有Proof of Work、Proof of Stake、Byzantine agreement等。

1.3.1ProofofWork(PoW)

工作量证明协议(PoW)设定发起节点需要进行特定形式的数学运算,只有计算出正确结果的节点才具备访问资源的权力。通过强制节点运行计算程序消耗一定量的电力,造成节点实际付出计算力和能耗成本,从而增加节点进行恶意破坏行为的成本[12-13]。基于PoW协议的区块链是第一种稳定运行的分布式账本(DLT)技术,任何节点都可以自主地选择加入或者离开。包括比特币在内的所有基于PoW协议的区块链都需要运行在同步网络,并假设正确的节点算力大于拜占庭节点[6]。对于Bitcoin、Ethereum所使用的POW共识协议,每个节点都可能取得DLT记账权,在验证工作量证明后,便确定了记账的效力[14]。

1.3.2ProofofStake(PoS)

权益证明协议(PoS)设定验证者不再通过消耗大量的电力进行工作量证明,而是通过投票提出下一个区块,验证者投票的权重取决于其“币龄”的大小[15]。“币龄”被简单地定义为货币数量乘以持有时间。与比特币中的“Coinbase”相似,权益生成过程被称为“Coinstake”,在Coinstake事务中,PoS协议区块的生成类似于PoW的过程,需要进行协议规定的Hash运算。一个重要的区别在于,PoS协议的Hash操作是在很小的搜索空间内进行,而不同于PoW协议的广泛搜索空间,因此能量消耗会显著下降。验证者可以通过消耗“币龄”来减少相应的Hash难度,而PoW协议中的Hash难度相对于每个节点是固定的。因此,在PoS协议中节点持有的“币龄”越多,就越容易生成区块。

1.3.3ByzantineAgreement

拜占庭协议(Byzantine Agreement)也称为拜占庭容错(Byzantine Fault Tolerance,BFT)是分布式计算容错技术。拜占庭问题是对现实问题的抽象表示,指分布式系统由于硬件故障、网络拥塞或中断、遭到恶意攻击等原因,系统可能出现的不可预料行为。BFT技术用于维护在存在拜占庭问题的网络上保持一致状态。它可以容忍系统部分崩溃或拜占庭式的故障,最多可容忍的数量取决于通信的同步性假设。BFT共识算法的目的是在不信任网络(如互联网)中的节点间建立信任。Lamport等[11]证明了在同步环境中算法可行。

1.3.4PracticalByzantineFaultTolerance

实用拜占庭容错算法PBFT(Practical Byzantine Fault Tolerance)是BFT算法的改进,由Castro等[16]提出,解决了BFT算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。PBFT主要针对主节点副本复制为主的分布式系统执行环境,用系统中多数可靠节点来覆盖恶意节点或无效节点的行为。PBFT算法的节点数量固定,一个节点代表一票,以少数服从多数的方式实现了拜占庭的容错演算。至多容错量不超过全部节点数的1/3,即如果有超过2/3的正常节点,整个系统可正常运转。

2 构建状态机模型

2.1 离散态时间点网络

2.2 分布式账本

图2 区块链状态示意图

2.3 状态无关DLT

在区块链系统中,新加入网络的节点会从网络中的其他节点获得当前分布式账本的状态。如果新加入的节点能够根据DLT的初始状态和从当前网络中接收到的信息推断出DLT的当前状态,则这个DLT是状态无关。

定义1(弱状态无关性DLT)如果存在一个函数f,使得f(I,Mt)=St,则DLT为弱状态无关。

定义2(强状态无关性DLT)如果存在一个函数f,使得f(I,Mt)=St,并且对于任意的子集A⊂Mt,f(I,A)=Stor ⊥(⊥表示截短),则DLT为强状态无关。

定义3(随机态DLT)如果存在一个函数f,对于∀k,t,t′∈N,k≤t≤t′,f(I,Mt)-k≤St′的概率大于1-O(e-ck)(O为随机函数),常数c>0,那么DLT是随机态。

3 常见DLTs状态机分析

3.1 工作量证明状态机

证明设f是返回最大PoW(St)的本地状态的函数,f(I,Mt)=argmaxs({PoW(S)|∃u,(u,S)∈Mt})。这样的本地状态可能是由敌对节点产生。如果k表示截断的区块数量来得到前边正确的状态St,当k趋向于无穷时,其可能性呈指数速度降低。实际上,分别使用pt和qt表示在t时间点正确节点的计算力和敌对节点的计算力。假设∀t,pt>qtλt=maxt′≤t(pt′qt′)根据文献[17]推论,在给定的时间点t敌对节点重写最后k个区块的可能性是O(e-cz)c=log(1/(4λt))>0。

3.2 权益证明状态机

定理2在每个时间点即使所有拥有令牌的节点是正确的,PoS DLT也不是弱状态无关的。

3.3 拜占庭协议状态机

当集合C中多数节点是正确节点时,C以外的任意节点u可以通过询问C内的节点获取当前状态。u接收到的当前状态是通过C内多数节点决定的,可保证其正确性。从这里可以推导出下面的定理：

3.4 PBFT状态机

3.5 状态机应用示例

物联网区块链。物联网(IoT)是一个由相互关联的设备、机器、对象组成的系统,嵌入了传感器、软件和其他技术,这些设备具有唯一标识符(UID),并且能够通过网络交换数据,而不需要人与人或人与计算机的交互[18]。由于多种技术、实时分析、机器学习、传感器和嵌入式系统的融合,物联网的定义已经演变,延伸到工业、生活等各方面。在物联网中应用区块链技术,可以实现去中心化,不用中央控制系统来验证,设备之间能互相匿名传输,并管理软件的更新、错误,或者进行能源管理。在物联网中的设备通常是功能简单、算力较弱的节点,不能部署实施复杂协议和策略。通过上述研究,拜占庭状态机为强状态无关,其DLTs状态可以基本不受节点影响,适合在物联网区块链中应用。

4 结 语

通过对区块链使用的常见共识机制底层技术进行状态机分析,本文从底层机制上系统证明了不同的区块链共识机制特性,可以对区块链实际应用提供理论支撑。由于区块链应用正在兴起,对于不同应用场景应采用的共识机制和共识协议,可以使用本文状态机研究成果进行具体分析。目前,区块链状态机研究仍处于初级阶段,还存在应用场景设定苛刻的局限,建议下一步应着重加强宽条件域下区块链状态机充分条件研究。