基于PageRank改进的公证人节点信用排序算法

蒋楚钰 方李西 朱建明

(中央财经大学信息学院 北京 102206)

(cyu_jiang@163.com)

“十四五”规划和2035年远景目标纲要将区块链纳入数字经济重点产业，区块链将在我国数字经济发展过程中发挥重大作用的同时也带来了风险[1].习近平总书记在中央政治局第十八次集体学习中强调了区块链技术在未来产业变革中的重要程度，指明了区块链技术未来的发展方向.这都体现了党和国家领导人对区块链发展的高度重视.而在区块链系统中，信息只在各自链上流通，链与链之间垂直发展.但对于大部分应用场景而言，链与链之间需要信息交互与价值流通.为了避免数据孤岛现象的出现，跨链技术成为当前研究的热点.

跨链技术主要包括侧链技术、哈希锁定以及公证人机制等.其中，公证人机制指的是一个受信任的实体或者联盟告诉一个链，在另一个链上发生的事件或者关于这个链的声明是真实的.公证人机制允许参与者无须彼此信任的前提下就能够完成跨链的资产信息交互，有助于跨链交互效率的提高.公证人机制包括中心化公证人机制和多重签名的公证人机制[2].前者存在单点故障的风险，而后者是由随机选取的1组公证人构成的，虽然在一定程度上弱化了中心化问题，却也引申出了另外一个问题，即公证人机制存在节点信用监督不足的问题，也可能有潜在作恶的风险[3].随机选取的公证人节点中可能会出现恶意节点，虽然现有的算法在一定程度上能够规避这一问题，但不可否定的是，并没有从源头判断一个公证人节点是否诚实，以便在开始进行随机选取时就可以避免选到可信度较低的节点，以维护系统的稳定性和可信度.

本文在PageRank算法和保证金池的基础上，提出了一种公证人节点信用排序改进算法.首先需要收集所有节点的相关信息，包括各个节点在2条链上单独的交易信息以及跨链交互中充当公证人的交易信息.其次将公证人节点信用值刻画分为2个部分：一个是节点的自身固有价值，该部分是由节点在源链或目标链上的单链历史交易评估得到；另一个是节点充当2条链之间的公证人获得的价值.另外，为了解决PageRank算法中的偏重旧节点的问题，考虑在PageRank算法中对阻尼系数d进行调整，将原有的d与时间因子结合得到新的阻尼系数.阻尼系数的提出可根据充当公证人节点时间长短的不同，给予公证人节点的自身固有价值以及充当公证人获取价值在节点信用值评估中赋予不同的权重，对于新充当公证人的节点能够对自身固有价值赋予更大的权重值，以修正补充该节点较为匮乏的充当2条链之间的公证人经历，以获得合适的价值.最后将根据计算出的信用值剔除末20名的节点，将剩余的节点构成候选公证人组，后续可从中根据算法选取部分节点构成正式公证人组实现跨链交互.

改进的PageRank算法解决了传统算法中的“主题漂移”以及偏重旧节点的问题，并且利用新旧公证人节点不同的时间积淀，使用不同的方法刻画其价值，优化了节点信用值排序的结果.另外，节点信用值是一个逐渐积累的过程，持续诚信交易的积累才能获取较高的信用值，进而成为高可信的公证人节点.为了获得充当公证人节点的机会，节点需要督促自己诚信地完成每次交易，有利于更好地维护区块链系统的安全稳定.再者，通过将源链和目标链单链上的交易信息以及充当公证人交易信息进行综合分析计算得到节点的信用值，并且引入了保证金池和公证人进出管理机制，使得公证人机制更加安全可信.

区别于现有的研究成果，本文的主要贡献有以下2点：一是从公证人节点的自身固有价值以及充当公证人获取价值2方面进行节点信用值评估；二是由于新旧节点充当公证人时间存在差异而导致的节点信用值排序不合理现象，这是因为新加入的公证人节点相对已经扮演一段时间公证人角色的节点(简称为“旧公证人”节点)来说，虽然都没有很好地充当公证人的成功经历，但可以知道的是：“旧公证人”节点是由于自身办事不妥帖等原因才不被重视，导致信用值不高，而新公证人节点还没有接受时间的考验，二者并不能用同样的信用值进行评估.

1 相关研究

1.1 公证人机制

公证人机制是指有交易需求的双方分别位于不同的区块链上，只需要在双方之间引入一个共同信任的公证人来验证交易信息的一致性以及合法性.而“中心化”是公证人机制的一大争议，这与区块链的“去中心化”思想相悖[4].学者们通过研究提出了改进算法以提高区块链公证人节点的信用值和区块链吞吐量，进而优化跨链交互的效率.戴炳荣等人[5]通过收集多种公证人节点相关信息，利用改进的PageRank算法对公证人节点进行信用计算，得到高可信的公证人节点，进而保证区块链系统安全稳定.刘桂华[6]针对公证人机制中存在的信用监督不足的问题和保证跨链交互的安全性，提出了一种基于公证人组的2阶段跨链协议实现跨链交互以及基于保证金池和激励措施来维护跨链交互过程系统的稳定性.赵涛等人[7]提出了基于聚类簇中心的共识跨链交换模型，将节点分为共识服务节点、跨链交换节点和应用节点3类，有效地解决了区块链网络中单次同步区块数据过大的问题.

基于公证人机制的代表项目主要有Interledge，PalletOne和Corda.Interledger提供了一个被称为“连接器”的顶级加密托管系统，允许资金在不同的区块链之间流动[8].PalletOne的所有服务是基于智能合约实现的，在共识协议中引入2类共识节点即陪审团以及调停中介，能够作为不同类型区块链之间的信息交互以及资产转移的中间渠道[9].在Corda项目中，交易双方共同选择公证人，负责验证审核交互信息，确保信息的可用性和无篡改性[10].

由此看来，公证人机制能够有效地帮助实现跨链交互，但是在跨链交互中引入公证人机制需要解决节点信用问题，公证人的可靠性存在隐患.而在公证人机制中，公证人存在监听、查看、验证和审核等功能，节点承担了太多的功能，导致带来安全性和可维护性等多方面的问题[11].为了防止公证人中存在恶意节点以及使用公证人机制存在的中心化问题，希望能够尽可能弱化公证人节点在跨链机制中需要发挥的职能和增强公证人节点的可信程度.

1.2 PageRank算法

1.2.1 PageRank算法简介

PageRank算法最初是由Google公司提出，旨在于按照重要程度对网页计算PageRank值(即PR值)从而进行排名.核心思想是先对所有网页赋予相同的权重值，然后每个页面根据出链的数量将权重值平均地传递给下一个页面，通过不断递归迭代计算，直到页面PR值趋于稳定.计算公式如下：

(1)

其中L(v)为网页v的出链数量，PR(u)为网页u的PR值，PR(v)为链接到网页u的PR值.d被称作阻尼系数，经验值为0.85或0.5，主要功能是用来解决算法中由于垂悬链接所带来的PR值滞留的问题，保证PR值能够一直顺利地传递下去.阻尼系数d的理论意义是指用户通过点击指向页面u的超链接访问到页面u的概率，而1-d指的是用户从其他页面随机跳转到页面u的概率.

对应于公证人节点信任列表，若节点i到节点j存在指向关系，即节点i是信任节点j的.假设1个节点的PR值是1，该节点有n个信任的节点，其平均分配给其信任的节点的PR值就是1/n，即意味着该节点以1/n的投票数额支持其所信任的每一个节点充当公证人.

1.2.2 PageRank算法存在的不足

传统的PageRank算法的不足主要表现在3个方面：

第一是算法偏重于旧节点，一个节点的PR值的高低主要取决于其反向链接的数量，即多少节点对他进行了投票.这就存在一个问题，当一个新的节点产生之后，与那些早就存在的且有一定关系网的节点来说，基本上是不可能获得反向链接的.因此，基于PR值排序之后，那些充当公证人时间越长久的节点，越容易在信用值排序中排在前面.而对于新的节点来说，存在时间较短，反向链接数量较少，导致PR值低，只能被排序在低位，进而在排序结果中更加偏向于旧节点，而有些新节点可能在源链或者目标链单链上的交易表现良好，可能更适合充当公证人节点，因而这样排序的结果不一定准确.

第二是忽视了不同节点的质量之差，而是平均地把PR值分配给所信任的节点.这在一定程度上会使排序结果产生偏差，影响排序质量.

第三是查询主题的偏移.在进行排序时，主要依赖于节点之间的指向关系，并没有对节点内容与所指向节点的内容之间的匹配度进行分析，即并没有考虑公证人节点之间的交易信息的匹配度.而每个节点的历史交易信息会对公证人节点的信用评估产生影响.

1.2.3 PageRank算法的改进

在网页的链接分析中，PageRank算法的思想取得了一定的成果[12].与链接分析类似，学术引文分析也可以借鉴类似的研究思想.1篇文献被引用的次数越多，说明其参考价值越大.与参考文献引用类似，一个公证人节点被信任的次数越多，说明这个节点相对越可靠.因此，在实验中，我们需要搜集其他节点的信任节点列表，如果一个节点A的信任列表中存在指向另一个节点B的信任信息，则可以看作是节点A对节点B的1次引用.基于这种相似性，从节点信任列表入手，可以分析节点的信用值.

相对来说，关于跨链交互公证人节点的信用值改善问题研究较少.但关于文献价值排序算法研究较为丰富，在本文的研究中可以借鉴参考.库珊等人[13]提出了改进PHIA算法，先使用根集中所有网页的PR值作为Hub和Authority初始迭代值，然后根据Markov Chain来获取网页排名的静态分布，有助于提高网页排序算法的正确率.考虑到新旧论文价值评估的不公平现象依旧存在，孙泽锋等人[14]结合PageRank算法以及引入文献的自身固有价值，并利用时间因子改进阻尼因子，以使得新旧文献在价值评估时有不同的侧重，使得价值评估更具备公平性.华一雄等人[15]提出了一种基于PageRank算法的文献搜索方法，利用WMD算法计算出文献间的文本相似度，修正了不同文献在赋予PR值时的权重值.

由此，在文献价值排序算法中，大多使用改进的PageRank算法，并对文献的价值赋予改进过后的权重值.另外，戴炳荣等人[5]在进行公证人节点信用排序时采用改进的PageRank算法，该算法通过计算节点之间的内容相似性，在一定程度上解决了传统算法中“主题漂移”的问题，但并没有考虑到算法本身偏重于已经扮演公证人角色很长时间的旧节点，可能会导致排序结果的不准确.再者，在刻画公证人节点信用值的过程中，文中并没有考虑到有些节点一开始只在源链上交易且自身信誉较高，但当他在拥有目标链的账户之后想成为公证人节点较为困难，因为该节点缺乏充当公证人的成功经历，在节点信用值评分中分数不高，但理论上而言这部分的节点更为靠谱.因此，需要对这2部分的价值加以区分，并赋以不同的权重.另外，文献[5]中并没有考虑到公证人节点合理的进出管理机制.合理的公证人管理机制能够更加有效地保障系统的顺利运行.因此，本文结合现有的研究现状，提出了如下的节点信用值计算方案.

2 公证人节点信用值计算流程

2.1 公证人节点信用值评估流程

借鉴Kotulski等人[16]的节点信誉评估流程，本文的信用值评估流程如图1所示:

图1 公证人节点信用值评估流程

步骤1.选取一个国家认证的机构如央行充当节点信用值计算的“领导者节点”.该领导者节点在规定某时间段内对所有符合条件的公证人节点计算信任度，该领导者节点会向这些节点发出评价信号，收集节点之间的信任列表并广播自己的公钥和信息收集的截止时间；普通公证人节点如果错过收集时间，则取消这一轮被选为公证人节点的资格.为了防止女巫攻击，引入保证金池，即每个节点在充当候选公证人组之前，需要缴付一定的资金抵押，待交易完成之后与手续费一并返还.

步骤2.各个节点看到信任列表的收集消息之后，将所需要呈报的消息使用自己的私钥Sigi进行签名，并用该领导者节点的公钥KL进行加密，将加密过后的数据发送给领导者节点.该领导者节点收到消息之后，先用自己的私钥解密，再用普通公证人节点的公钥验证签名，确保消息是由该普通公证人节点发送的且未经篡改.将从所有普通公证人节点发送的消息整合，最终形成信任关系图并广播出去，这条消息将附带一个时间戳T1；领导者节点在规定时间内若未收到异议则继续推进，否则再次核实计算.

步骤3.领导者节点会自动收集各个节点在2条链上单独的交易信息以及跨链交互中充当公证人的交易信息，并使用改进的PageRank算法计算每个节点的信用值之后，将结果及计算过程附上一个时间戳T2后公布；领导者节点在规定时间内若未收到异议则自动剔除排名末20名的节点，信用值排序流程结束，剩余未被剔除的节点构成候选公证人组.

2.2 公证人组的管理

公证人节点管理流程如图2所示.

图2 公证人节点管理流程

2.2.1 公证人组的加入

同时拥有源链和目标链账户的节点可以申请加入公证人选举，但是需要预先缴纳一部分的保证金，以防止女巫攻击，否则攻击者可能会伪造生成大量的节点来干扰公证人选举进程[17].在所有申请加入的节点中，通过前面所述的算法计算出所有节点的信用值，并剔除尾部排序较低的节点，剩余的节点组成一个公证人候选预备组.若不设置保证金池，恶意节点可能会伪造大量地址凑数，这些地址由于没有交易表现，无法进行评估，因此信用值计算值较低.恶意节点最终能够通过增加低信用值节点的个数，以保证自身不被信用值排序算法剔除，则设置保证金池是必要的.由于候选公证人组中已剔除了一些信用值排序较低的节点，从而在候选公证人组中根据算法随机选取正式公证人组时，能在一定程度上确保公证人组的可靠性，有利于维护跨链交互的正常运作.

2.2.2 公证人组的退出

公证人节点的退出机制分为自愿退出和被迫退出2种情况.

1) 自愿退出.节点因为自身原因自愿申请退出公证人组的选举.在这种情况下，节点需要完成手头上所有充当公证人的交易，且没有任何不诚信行为.否则，需要给予适当的惩罚，在保证金池中扣除一定的违约金.

2) 被迫退出.节点因为不诚信等原因被领导者节点取消参与公证人选举的资格或者是叫停充当公证人交易的过程.

对于第1种情况，因为节点有过不诚信交易等原因，领导者节点有权取消该节点的评选资格；而对于第2种情况，在节点充当公证人的交易过程中，其他公证人可向领导者节点举报该公证人节点，领导者节点一旦核实了该节点的不诚信行为，就有权叫停交易过程并重新更换新的公证人节点.在被迫退出的情况下，都将直接没收保证金作为惩罚.而参与举报其他节点违规行为的公证人节点将会受到一定程度的代币奖励.

公证人信用评估计算过程都在链外进行.在数据计算结束之后，将结果输入到区块链，广播给所有节点，进行所有节点的消息确认.将信用评估计算过程放在链外进行，只需要将最后的结果与区块链交互，既不需要占用区块链内存又不会影响区块链的运行速率.最后将所有节点按照信用值排序，剔除未排名20%的节点将剩余的节点组成一个候选公证人组，以备在正式的跨链交互中从里面随机选出若干节点构成正式公证人组.

2.3 改进的基于PageRank的公证人节点信用排序算法

公证人节点信用值排序算法流程如图3所示：

图3 公证人节点信用值排序算法流程

算法1.改进的基于PageRank的公证人节点信用排序算法.

步骤1.所有公证人节点给出自己信任的节点，这种信任关系可能来源于之前一起充当正式公证人组参与交易时的经历感受或者是在单链上参与交易时的交易体会.然后领导者节点收集所有普通公证人节点的信任关系评价表，将所有节点之间的信任关系组织成一张节点关系图并广播给所有节点以待确认.

步骤2.收集节点在充当公证人经历中的历史交易评价表，包括交易处理效率time、用户反馈grade、交易是否成功statue等因素.节点完成交易越高效，其信用值越高；引入分段函数(如式(2)所示)确定历史交易评价表的权重[18]，根据式(3)～(5)分别得到节点的交易是否成功值Qsuccess，交易处理效率Qtime以及用户反馈评价值Qassess，组成向量A=(Qsuccess,Qtime,Qassess):

(2)

(3)

(4)

(5)

(6)

其中Nu为对于节点u而言在源链以及目标链上的交易总数，Scorei为每笔交易的评分值.

步骤4.考虑到PageRank算法中存在“主题漂移”的现象，能够有效避免“主题偏移”的改进方法之一是计算节点之间的关联性，即引入余弦相似度，考虑节点之间的交易表现对传播权重的影响.从2个节点之间的交易情况来看，若二者之间都是交易效率高、用户反馈评价好以及诚信充当公证人确保交易成功的节点，那二者的相似度很高，当一个节点的PR值较高时，理应传递给该节点更多的PR值，而不是平均分配，即拥有优秀表现的节点将会获得更高的PR值.节点M与节点N之间的相似度计算公式为[19]

(7)

利用前面收集到的信息和余弦相似度计算公证人节点两两之间的相似度，得到Puv，进而算出节点充当公证人获得的价值Gainvalue.其中w∈F(u)指的是所有指向节点u的节点.

(8)

步骤5.将二者按照公式线性加和，得到PR(u).这里阻尼系数d表示一个节点的自身固有价值和通过充当公证人节点获得的价值各自所占的比重.而改进后的阻尼系数d(tu)=d×Tu加了时间因子进行调节，缓解了传统算法中偏重于旧节点的问题.借鉴王德广等人[20]采用分段函数对偏重旧节点的现象进行改进，其中Tu如式(10)所示.阻尼系数的提出可根据充当公证人节点时间长短的不同，给予公证人节点的自身固有价值以及充当公证人获取价值在节点信用值评估中赋予不同的权重，对于新充当公证人节点能够对自身固有价值赋予更大的权重值，以修正补充该节点较为匮乏的充当2条链之间的公证人经历，以获得合适的价值.

PR(u)=(1-d(tu))×Fixvalue(u)+
d(tu)×Gainvalue(u)，

(9)

(10)

3 方案论证、分析与比较

本文首先部署了100个公证人节点，以0～99之间的连续整数对这100个节点进行编号，并收集了节点之间的信任评价表，即一个节点对另一个节点是否信任，如果存在信任关系，即存在一个节点指向另一个节点，即“0→4”表示节点0信任节点4.部分公证人节点之间的信任关系图如图4所示:

图4 部分公证人节点信任关系图

然后收集所有公证人节点在源链和目标链上参与的每笔交易是否成功的信息，以及收集节点在充当公证人交易中的历史交易信息，包括交易是否成功、交易处理时间和用户反馈评价信息，其中在充当公证人交易信息中，交易状态为1表示交易成功，为0则表示交易失败.若交易没有成功即交易状态为0时，交易处理时间和用户反馈评价为缺失值.节点0在单链上的交易信息如表1所示，在充当公证人中的交易信息如表2所示.另外还收集了节点充当公证人的时长.

表1 节点0在单链上历史交易信息

表2 节点0充当公证人历史交易信息

本文基于收集到的节点信任关系图以及节点的历史交易信息进行仿真测试，分别计算出算法1、戴炳荣等人[5]改进的算法以及传统PageRank算法三者对应的PR值，其结果如图5和图6所示.可以看出，3种算法的PR值在数值上存在差异.戴炳荣等人[5]改进算法相对于传统的PageRank算法而言，考虑到节点之间的历史交易信息，较好地解决了传统算法存在“主题偏移”的问题，进而影响PR值的度量结果.而与传统PageRank算法的排序结果以及戴炳荣等人[5]的算法结果作比较，算法1除了解决传统算法中存在的“主题偏移”问题之外，将时间因子引入阻尼系数，从单链上的交易表现以及充当公证人的交易表现2个维度出发，调节2种交易模式下的权重值，致力于解决传统PageRank算法中偏重于旧节点的问题.因此，3种计算节点PR值的度量结果会有所区别.

图5 传统PageRank算法和算法1仿真结果信用值对比

图6 戴炳荣等人[5]改进算法和算法1仿真结果信用值对比

计算出PR值之后，将根据PR值排序结果先剔除排名在末20名的节点，然后将剩余的节点组成候选公证人组.基于传统的PageRank算法，戴炳荣等人[5]改进的算法与算法1剔除的末20名的节点信用值如图7和图8所示.

图7 传统PageRank算法和算法1末20名节点的信用值

图8 戴炳荣等人[5]改进算法和算法1末20名节点的信用值

剔除的具体节点列表如表3所示.从表3可以看出，戴炳荣等人[5]改进的算法剔除了公证人交易中用户评价较低的节点，包括节点4，88，56等，说明该算法较好地结合了用户充当公证人的历史评价信息.而算法1不仅剔除了公证人交易中用户评价较低的节点(如节点41，60，16等)，还剔除了单链上的用户评价信息较低的节点(如节点68，44，83等).具体来看，对于排名末20名的节点，传统的PageRank算法在该次仿真实验中，剔除的节点中有3个是公证人交易用户评价较低的节点，有3个单链上评价较低的节点.而对于戴炳荣等人[5]改进的算法，剔除的节点中有5个是公证人交易用户评价较低的节点，有4个单链上评价较低的节点.对于算法1而言，剔除的节点中有11个是公证人交易用户评价较低的节点，有8个单链上评价较低的节点.由此可以看出，新提出的改进算法较好地综合了节点在单链以及充当公证人的历史交易信息，对于缺少公证人交易信息的节点，能够更客观地结合单链信息综合评定.对于节点67来说，在戴炳荣等人[5]算法中的信用评分较低，可能是充当公证人交易表现一般，但是在单链上交易表现排名较高(7/100)，综合二者的表现，节点67相对较为靠谱，不需要被剔除，可以加入候选公证人组，因此在算法1中并未将其剔除.另外，算法1用时间因子改善了阻尼系数，旨在于解决传统PageRank算法中带来的偏重于旧节点的问题，改善信用值排序结果.比如对于节点25而言，在仿真实验中充当公证人的时长相对较短，资历排名为80/100，在戴炳荣等人[5]算法和传统的PageRank算法中节点信用值排名分别为96，99，而算法1中却跃升到第63名，查看节点25的历史交易信息，在单链上的交易表现排名为33/100，在充当公证人交易中打分排名为65/100，该节点交易表现良好，算法1在一定程度上改善了新节点在排序时信用值被低估的现象.

表3 被剔除的节点

4 结 论

基于公证人机制中存在的“单点故障”和“信用监督不足”等问题，本文通过改进的PageRank算法与保证金池，将时间因子引入阻尼因子中，从单链以及充当公证人的交易表现2个维度对节点的信用值进行评估，旨在更公平客观地计算公证人节点的信用值以及防止女巫攻击.实验结果表明，本文算法有效地结合了节点在单链以及在充当公证人交易中的历史信息，并且完善了传统PageRank算法的缺陷，即偏重旧节点以及“主题偏移”现象，相对客观地对公证人节点进行评价，提高了节点信用值评估的公平性以及能够较为有效地剔除恶意节点.另外，实验剔除了信用值排序较低的节点构成候选公证人组，有助于在候选公证人组中根据算法合理选出一些公证人节点组成正式公证人组参与跨链交互，使得整个公证人组信用度得以提升，以便提高跨链交互中公证人机制的可靠程度和系统的稳定性.