SRaft:基于Schnorrkel签名和信用值机制的Raft共识算法

陈 鹏,秦伟杰,余肖生

(三峡大学 计算机与信息学院,湖北 宜昌 443002)

0 引 言

从开放程度来看,区块链主要分为公有链、联盟链和私有链等。由于联盟链兼有公有链的扩展能力和私有链的管理便利性,因此其已经成为最具实际应用前景的区块链技术。区块链集群中需要使用某种共识算法来实现集群中节点的分布式一致性[1]。联盟链中的共识算法主要分为两大类:一类是拜占庭容错共识算法,其中具有代表性的有实用拜占庭容错算法(PBFT)及其相关变体,如:可通过动态监管策略实现问题追溯的DDPBFT等[2];另一类则是非拜占庭容错共识算法,具有代表性的有Raft共识算法等。Raft共识算法的强领导性使其在共识过程中具有更高的效率,其简洁的共识过程也让Raft算法具有很好的扩展性[3]。

Raft是一种非拜占庭容错的共识算法。针对此共识算法中的共识效率及拜占庭问题,一些学者先将节点进行分组,组内遵循基于PageRank优化的Raft共识,主节点作为组长参与组间遵循的PBFT共识[4];另外一些学者则将区块链分片后,使用K-medoids聚类算法将节点分为节点簇,簇内部使用带有监督节点的Raft共识,簇中心节点再使用PBFT进行共识[5]。虽然这些改进提高了共识的吞吐量和共识效率,且具备了一定的拜占庭容错能力,但是Raft在选举阶段因冲突而引发的选举效率问题及主节点的隐私安全性问题并未得到有效解决。针对这两个问题,该文提出了结合Schnorrkel签名和信用值机制的共识算法,即,在主节点选取阶段引入了信用值机制和日志复制阶段引入了Schnorrkel聚合签名。节点通过在共识过程中的表现改变其信任值,进而调节随机超时时长的上下限值,在增大优质节点当选概率的同时能够有效避免选举冲突的发生,提升选举阶段的效率[6];通过日志复制阶段的聚合签名的生成,能够隐匿主节点的公钥信息,同时从节点可以验证消息信息中的客户端签名,确保消息未被主节点篡改,实现了部分拜占庭容错。实验证明,SRaft算法能够筛选出优质节点,并提升其作为主节点的概率;在节点数量较大的情况下,SRaft算法能够有效避免选举冲突的发生,并提升了选举阶段的效率。

1 相关工作

1.1 Schnorrkel签名算法

Schnorrkel签名算法是由Claus Schnorr于1989年提出的Schnorr签名算法的变体之一。由于该算法能够进行线性计算,便于生成聚合签名,在性能、交易体积和隐私性方面具有优势,所以Schnorrkel签名在区块链中已得到广泛的应用。Schnorrkel签名使用一个随机数k以及椭圆曲线G和标量s来生成签名,如式(1)(2)所示[7-8]。

R=k·G

(1)

s=k+H(P,R,M)·sk

(2)

其中,sk为私钥,P为公钥,m为消息,H()表示哈希运算。

签名的有效性验证,采用式(3)来完成:

s·G=R+H(P,R,M)·P

(3)

在生成Schnorrkel签名的基础上,通过节点间相互交换公钥信息,多个Schnorrkel公钥可以以线性加和的方式进行组签,形成新的聚合签名。聚合签名可以被其余节点进行验证,并且无法从聚合签名中反向推导出参与节点的公钥信息[9]。

对一组私钥(n个)生成签名后得到n个签名。且这n个签名可以通过线性相加,最终得到一个聚合签名,过程如图1所示。一旦聚合签名通过验证,则代表n个私钥的签名全部通过验证[10]。

图1 Schnorrkel签名聚合过程

Schnorrkel签名中,可利用一对私钥(Sk1,Sk2)和随机数k1、k2通过公式(4)(5)分别得到相应的签名,将得到的签名S1、S2通过线性运算相加生成共享签名S[11]。

P=P1+P2=Sk1·G+Sk2·G

(4)

Si=Ki+H(P,R,M)·Ski

(5)

其中,参与方彼此间需要先交换R值,然后再进行各自的签名。通过线性运算得到的聚合签名,生成过程简单,且能够隐藏参与生成签名的节点信息。

1.2 Raft共识算法

Raft算法是一种有代表性的Paxos共识算法的变体,并且是一种具有强领导性的共识算法,主节点的安全隐私性也是算法整体的安全瓶颈。集群中的所有节点被分配到随机时长进行超时选举,完成随机选举超时(Randomize Election Timeout,RET)的节点可向其余节点索票,获得集群中半数以上节点的票,则当选为主节点,并向其余从节点发送心跳间隔检测(Append Entries)。当客户端发送消息更新的请求后,主节点将向全网发送更新指令,收到半数以上从节点的回复后,则进行日志更新并复制给所有从节点[12]。

Raft是一种更易于理解的分布式共识协议,它加强了日志项之间的串行性,简化了协议的设计。Raft中的每个节点都维护一个递增的变量,称为任期(term)。任期本质上是节点共同维护的逻辑时钟。通过任期,节点可以发现过时的消息。具体而言,节点间发送消息时,需要携带自身当前的任期。如果节点收到的消息携带的任期值小于该节点自身当前的任期值,则拒绝接受该消息;否则,更新自身当前的任期值[13]。节点向日志添加新的日志项时,会将自身当前的任期值也保存在日志项中,这将成为该日志项的任期。

Raft共识算法中的主节点(Leader)、从节点(Follower)、候选节点(Candidate)等角色转变如图2所示。初始状态下,所有的节点都是从节点,通过选举超时产生主节点,任期结束后,重新进入选举阶段[14]。

图2 Raft算法节点角色转变

2 结合聚合签名和信用值模型的SRaft共识算法

目前,在Raft共识的研究中,通过将分层后的节点分别使用PBFT与Raft共识,实现拜占庭容错,而重复的选举过程降低了算法整体的选举效率[15];通过在共识算法的网络层结合双层Kademlia路由协议来优化算法的选举过程,其提升选举效率的同时也增加了网络开销[16];信用值模型提升了算法中优质节点当选主节点的概率,却无法保证主节点本身的安全隐私性[17]。

该文提出了一种结合Schnorrkel签名以及信用值模型的SRaft算法,其流程如图3所示,在选举阶段(a)结合信用值机制,筛选出优质节点作为领导,提高系统的效率和安全性;在日志复制阶段(b),结合Schnorrkel签名算法,隐匿主节点信息,并对客户端消息进行验证,避免拜占庭主节点。

图3 SRaft算法流程

如图3,任期开始时,首先根据节点在共识过程中的表现情况实现信用值动态更新,获取节点在本任期内的RET超时范围。选举阶段,优先完成超时的节点向其余节点索票,得到半数以上投票后当选为主节点。接收到客户端信息后进入日志复制阶段。日志复制阶段中,得到信息的主节点将选取若干从节点共同生成一个Schnorrkel聚合签名,参与生成聚合签名的从节点可以验证信息中客户端的签名,确保主节点未篡改客户端信息。验证通过后将信息全网广播并更新日志。

由于信用值较高的节点能够分配到更短的超时时长,完成选举超时(Election Timeout),为了保证选举的随机性,该文采取了优增劣减的信用值机制,即所有节点的初始信用值相同,根据节点在每个任期(term)内的表现,进行信用值的增减。通过一个较长周期来筛选出一部分高质量节点,从概率角度缩小主节点的候选范围,尽可能地使表现良好的节点当选为主节点。

在主节点进行心跳间隔检测以及从节点进行回复(Append Entries Response)的过程中,通过Schnorrkel签名算法能够隐匿所有节点的个人信息,从而提升主节点的隐私安全性,降低集群系统被外界攻击的风险,同时能够保证来自客户端的信息在传递过程中没有被主节点进行篡改。在安全和稳定的基础上,加入信用值机制,筛选出部分表现优良的节点作为主节点的候选节点,得到一个效率和稳定性相对平衡的共识模型。

2.1 信用值机制的实现

每个节点的信用值以任期(Term)为周期进行更新。在任期中,影响节点信用值变更的因素主要有两种:时长(Time)、失效次数(Failure Times)。前者用于评定节点完成指令的效率高低,后者判定节点是否能够完成指令。

时长是指完成客户端指令的时间长度。对于主节点(Leader)而言,是指将客户端发送的信息变更请求通过心跳间隔(Append Entries)发送给从节点,收到回复并完成日志更新的时长;对于从节点(Follower)而言,则指从收到心跳间隔开始,到发送给主节点回执(Response)的时长。

失效次数是指节点的宕机次数,即在某一任期中,节点未能对指令做出响应的次数。对于主节点而言,是指未能将客户端发来的消息请求更新到日志内的次数;对于从节点而言,则指未能对主节点发来的心跳间隔发送回执的次数。

根据在共识过程中不同身份的节点的表现情况,动态调整其信任值[18]。每个新加入的节点都将被分配到一个相同的初始信任值r。每当该节点在共识过程中出现宕机情况,将依照不同的权值公式对其信任值进行扣分。信任值越低的节点获得的RET时长上限将会提升,即低分节点需要更长的时间完成选举超时,当选为领导者节点的概率更低。

r={leader,follower}

(6)

式中,Δcredit为主节点在任期内的信任值变更量,E(tr)表示平均时长的期望值,ti表示节点执行一笔任务(验证和传播共识)的实际时长。当实际时长大于期望时长,则数值为负,本次共识过程为信用值减分项;反之,若实际时长小于期望时长,数值为正,本次共识过程为信用值加分项。S表示信任值变更的速度,是一个系统常数,可以根据集群内参与共识的节点数量进行调整[19]。D为负值,其绝对值表示角色职责系数,主、从节点的职责系数不同,主节点的职责系数绝对值更大,对信用值的影响更显著。MF表示主/从节点在参与共识的过程中出现的宕机次数。

该文设定集群中所有节点的信用初始值C均为50,根据信用值变更公式(7),节点在第n个周期的信用值为:

(7)

在整体的共识过程中,无论以何种身份参与的节点,在不同的任期中都可能会出现信任值的消耗和提升。在某一任期结束后,根据信任值的变更量来修改选举超时范围的上、下限。根据节点角色的不同,信用值的变更权值也有差异,主节点的扣分权值相对更高,表现良好的从节点得分权值较高。

在一定周期后,主节点选举(Leader Selection)阶段,每个节点根据之前周期中的表现,获得各自的信用值。该文设定节点信用值范围是0～100,且所有节点的初始信用值均为50。在若干任期后,RET的范围会随信用值的变化而变化。信用值高的节点,其RET范围的上下限值将整体降低;而信用值低的节点,其RET范围的上下限值将整体提高。RET区间更短,更容易完成选举超时成为候选节点。

2.2 主节点选举

当某个共识周期开始时,集群中的所有节点,首先需要获取其当前的信用值,而新加入节点则获得初始信用值。根据信用值分配随机超时时长范围,完成主节点的选举。

设定Timemax、Timemin分别为该节点当前超时时长的上限和下限;Tmax、Tmin分别是该节点上一周期中的超时时长的上限和下限;Δcredit表示此节点在两个周期的信用值变化量;N为该集群中包含的节点总数;k表示RET上下限值的变化参数。

当一个任期结束后,节点的信用值产生变化,导致节点的RET的上下限值也会随之变化,当Δcredit>0时,两者间的关系满足公式(8)(9)。

Timemax=Tmax-Δcredit·N·k

(8)

Timemin=Tmin-Δcredit·N·2k

(9)

当Δcredit<0时,关系满足公式(10)(11)。

Timemax=Tmax-Δcredit·N·2k

(10)

Timemin=Tmin-Δcredit·N·k

(11)

根据信用值的增减情况调整上下限的变化幅度,可以降低选举冲突发生的概率。

经过某一共识周期后,若某节点的信用值增加,系统则降低其RET的时长上限值以及下限值,并使其能够更快完成超时,成为候选者节点;节点的信用值降低,此时的Δcredit为负值,系统则提高其RET的时长的上限值以及下限值,使其完成超时所需的时间更长,难以成为候选者节点。

通过节点在共识过程中的表现,如能否对接收到的消息请求做出响应以及响应的时长,来判断其信用值在该周期内的增减情况。当下一周期开始时,将继承该周期的信用值进入选举阶段。

2.3 日志复制

在日志复制(Log Replication)阶段,该文结合了Schnorrkel签名算法。如图4所示,当客户端向主节点发送信息请求(Request)时,客户端需要对消息内容进行数字签名。当主节点接收到带有客户端数字签名的消息后,主节点与部分高信用值从节点通过Schnorrkel算法生成新的聚合签名,同时,参与Schnorrkel的从节点会通过客户端公钥验证消息内容是否被主节点篡改。确认后,主节点向其余从节点发送带有信息的心跳间隔,当收到半数以上从节点的反馈信息后,主节点提交日志,并且全网广播进行日志复制。

图4 日志复制过程

日志复制过程中,从节点能够保证客户端发来的消息请求是未经主节点篡改的,并且参与了Schnorrkel签名的生成。由于聚合签名的隐私性,外界攻击者无法从聚合签名中得到主节点的公钥及相关信息,从而确保主节点的隐私安全性。

2.4 算法描述

输入:集群节点信息,信用值变动参数k

Step1:主节点选举。

(2)根据得到的节点信用值,计算节点的RET超时范围上限值Timemax和下限值Timemin,当Δcredit>0,上限值Timemax=Tmax-Δcredit·N·k,下限值Timemin=Tmin-Δcredit·N·2k。当Δcredit<0,上限值Timemax=Tmax-Δcredit·N·2k,下限值Timemin=Tmin-Δcredit·N·k。

(3)节点在对应的超时范围内随机获得一个时长,进行超时选举,完成超时的节点向其余节点索票,首先获得N/2以上票数的节点当选为主节点。

Step2:日志复制。

(1)当主节点接受到客户端发来的消息,根据P=P1+P2=Sk1·G+Sk2·G和Si=Ki+H(P,R,M)·Ski,向部分高信用值从节点发起生成聚合签名S的申请。

(2)从节点接收申请后,利用客户端的公钥验证消息中客户端的签名是否正确,正确则参与生成聚合签名S;不正确则中止该任期,并重新进入选举阶段。

(3)主节点使用聚合签名S对消息签名,并进行全网广播,收到广播的节点更新本地文件,并给主节点反馈信息。

(4)主节点得到N/2以上的节点反馈后,更新日志,并向客户端发送回复。

3 仿真实验

该文使用go语言实现Raft算法,通过结合Schnorrkel签名和信用值模型实现了SRaft算法。在Windows环境下,通过本地多节点进行了较长周期的模拟实验,得到选举阶段时长(包括主节点宕机后重新选举),日志复制时长,以及多个任期中主节点的当选情况等关键数据。最后通过对比实验分析SRaft在各方面的性能。

3.1 实验环境

实验中选用的测试平台的开发环境为ubuntu 16.02,Golang1.17。实验的主要测试目标是该共识算法机制完成每个共识周期的时长,节点信用值变更情况以及算法出现选举冲突的次数和选举阶段时长。

3.2 信用值变更

该文使用了不同的参数来调节不同节点数量的集群中信用值变化的幅度,且不同角色的节点参数也会有所区别。实验选取了节点在不同节点数量下参与共识的信用值变化过程。

由于集群内的节点数量可能变动,该文的信用值变动参数也与集群内的节点总数有关。当集群内节点数量较少时,信用值的变动参数值较大,能够在短期内筛选出表现良好的节点;当集群内节点数量较多时,信用值的变动参数值较小,避免个别节点信用值增长过快导致选举失去随机性。

在5个、10个、20个节点的集群环境下,节点在25个共识周期中的表现以及各自的信用值变更情况,如图5所示。通过计算每个任期中节点的平均信用值,可以发现在节点初始信用值均为50的情况下,集群中节点信用的平均值呈上升趋势,并且集群内节点数量越多,节点的平均信用值增长速率越慢,当节点数量大于10个后,集群平均信用值增长速率趋于稳定,保障了系统的稳定性,避免部分节点信用值增长过快危及算法的随机性。

图5 节点数量-信用值趋势

3.3 主节点当选的概率

在SRaft共识算法中,节点按照各自的角色正常进行共识,自身的信用值会保持相对稳定的增长速度。当节点的执行效率降低,则会相应降低其信用值;若在某周期内出现了恶意主节点,即不响应客户端信息请求或篡改信息内容的主节点,则立刻停止当前任期,并重新进入选举环节。

SRaft算法能够通过节点自身具有的信用值的差异,影响选举超时的时长,从而调控其当选为主节点的概率。一段时间后,集群中的高效和低效节点的当选概率会出现明显差异。以此对节点进行筛选,使得高效节点更容易成为主节点,提高集群整体的效率和稳定性。

本实验中,A节点模拟发生过宕机且响应速度较慢的情况;B、C、D、E节点正常参与共识过程,其中B节点的响应速度更快。5个节点在50个共识周期中当选为主节点的次数,如图6所示。由图6可知,在前20个共识周期中,5个节点当选为主节点的次数相当,即每个节点的当选概率比较接近。在30个共识周期后,发现节点A和节点B当选的概率出现明显差异。表明集群筛选出了高效和低效节点,并调控了其当选为主节点的概率。

图6 节点当选分布

3.4 选举冲突时长

Raft共识算法中,主节点的选取是通过RET完成的。当集群内的节点数量较多时,可能出现若干节点的随机超时时长非常接近的情况。这些节点几乎同时完成RET成为候选者节点,并向网络内其余节点发送投票申请(Request Vote)。此时可能发生选举冲突,即进行全网索票的多个候选者节点没有一个能获得半数以上的选票。这种情况下只能通过一定的等待时间再次进行RET,并且依然有较大概率出现选举冲突的情况。

SRaft共识算法中,信用值机制能够在较大程度上解决选举冲突问题,当各个节点的信用值出现差异后,每个新任期的选举阶段,不同节点都会分配到不同区间的随机超时时长,可以有效避免选举冲突的情况,显著减少选举阶段的时长。

在10个节点的集群中,设定RET的范围为1 000 ms ～5 000 ms,通过主节点宕机模拟了20次重新选举主节点的情况,实验结果如图7所示。选举用时时长超过3 500 ms即发生选举冲突。在20次实验中,原Raft算法共计发生7次选举冲突,SRaft算法无选举冲突产生,且比较发现SRaft整体的平均选举时长均低于原Raft算法。通过对节点分配不同区间的超时时长可以显著减少选举阶段冲突情况的产生,并且由于Schnorrkel聚合签名的匿名性,主节点的信息安全性也得到了保证。

图7 选举时延

3.5 安全性分析

Raft算法的强领导性使得主节点的安全性问题成为了集群整体安全性的短板,针对主节点信息的隐私安全性,该文在SRaft算法的日志复制阶段结合了Schnorrkel聚合签名。主节点在广播消息前,需要与其余n个从节点共同形成一个聚合签名。由于椭圆曲线上的点可满足乘法结合律,设椭圆曲线上存在两点X、Y,两点对应的标量x、y作为它们的私钥,以及原点G,可得:

X+Y=x·G+y·G=(x+y)·G

(12)

对于Schnorrkel聚合签名的验证,可将验证方程相加:

S1=s1·G+s2·G+…+sn·G=

(s1+s2+…+sn)·G

(13)

对于验证者而言,Schnorrkel聚合签名和一般Schnorrkel签名并无区别,其中节点的公钥和签名都不会暴露,可有效隐匿主节点的公钥信息[20]。

在生成聚合签名的过程中,从节点对客户端消息的签名进行验证,确保主节点未篡改信息内容,实现了主节点的拜占庭容错能力。同时Schnorrkel聚合签名能够完全隐匿主节点的个人信息,保证主节点的安全性,减少受到外界攻击的概率,从而提升算法整体的安全性。

4 结束语

SRaft算法是一种融入信用值机制和Schnorrkel聚合签名的Raft算法,在选举阶段,根据节点表现,动态变更其信用值,使之获得不同范围内的随机超时时长;在日志复制阶段,主节点与部分高信用值从节点生成Schnorrkel聚合签名,隐匿主节点信息,避免拜占庭错误。SRaft算法能在监管主节点的同时,筛选出部分优质节点作为候选主节点,能在一定程度上解决了Raft的主节点拜占庭容错问题,降低了投票冲突导致的选举阶段时长。通过实验对比能够发现,SRaft算法实现了更高的稳定性,隐私性以及高效率的平衡。