基于改进PageRank算法的跨链公证人机制评价模型

戴炳荣，姜胜明，李顿伟，李 超

（1.上海海事大学信息工程学院，上海 201306；2.上海计算机软件技术开发中心，上海 201112）

0 概述

区块链技术因具有去中心化、可追溯、不可篡改等优点而被应用到越来越多的领域，但区块链本身存在低吞吐量、网络孤立和缺乏有效监管等问题，其中区块链网络孤立问题尤为严重，在通常情况下每一条区块链都是独立的，它们之间无法直接通信。因此，当区块链之间需要信息交互时，即产生跨链需求［1］。

根据区块链底层平台的差异，可以将跨链信息交互分为同构链和异构链，同构链之间底层技术一致，区别在于应用和数据不同；而异构链之间的底层技术如共识算法、安全机制等都可能存在差异。同构链之间跨链交互较为简单，而异构链之间跨链交互需要有特定的技术辅助支撑［2］。

到目前为止，区块链跨链方法可以分为哈希锁定、侧链/中继链和公证人机制等类型［3-4］。

哈希锁定主要是通过严格执行含有哈希密码锁定的智能合约来实现资产交换［5-6］，它的交换思路是一方基于哈希值锁定资产，设定规定时间内如果能提供原哈希数，则可获取资产，另一方使用同样的哈希值锁定资产，也设置同样的解锁条件，即一方使用哈希数解锁获取资产，另一方利用同样的哈希数获取资产，哈希锁定只能做到交换而不能做到资产或者信息的转移，因此其使用场景有限。典型实现是哈希时间锁定合约（Hashed Time Lock Contract，HTLC）。

侧链是指完全拥有某链功能的另一条区块链，侧链可以读取和验证主链上的信息［7-8］。主链不知道侧链的存在，由侧链主动感知主链信息并进行相应的动作，而中继链则是侧链和公证人机制的结合体，中继链具有访问需要和验证进行互操作的链的关键信息，而且还能对两条链的跨链消息进行转移。因此，中继链也是一种去中心的公证人机制。

公证人机制又叫见证人机制，其实质上类似于现在银行所进行的交易［9］。它的核心思想是假设存在链A、B，它们使异构链无法直接进行信息交互，假设存在一个可信的第三方C能同时被链A、B所接受，则由可信的第三方C负责链A、B之间的消息传递。公证人机制的优点是能够支持多种不同的异构链，但它的缺点是过于中心化。

公证人机制模式目前仅能够支持资产的交换，且资产交换的原子性、安全性完全由中心化的交易所保障，所以也存在较大的中心化风险。目前迭代发展出的多重签名和分布式签名的方案弱化了中心化组件的特性，其能够从多种角度提高系统的安全性［10-11］。

分布式签名方案是利用密码学的原理将密钥分别拆分成多个密钥加密后的密文（单个公证人无法拥有全部的密钥），并随机分发给公证人（所用的密文合并起来也无法推断出完整的密钥），设定允许一定数量的公证人在他们共同签名之后可以合成完整的密钥，完成了去中心化“数据采集验证”的过程［12-13］。

多重签名是指跨链交易需要多个公证人签名，交易才能被确认。通常它是由公证人在各自的账本上签名，当签名的数量达到预先设定好的数量时才能达成交易，这里的每个公证人都拥有独立的密钥［14-15］。

在应用公证人机制的跨链项目中，Interledger项目在早期发展中以公证人机制实现不同异构链的跨链，后续发展可结合哈希锁定技术来实现跨链交互；corda［16-17］项目可以实现交易双方自由选择公证人。无论是哪一种方案，都需要参与方公证人可信［18-19］。为解决公证人可信问题，本文构建一种基于改进PageRank算法的跨链公证人评价模型。该模型通过基于其他公证人节点评价和该节点历史交易评价来对公证人节点进行信用度排序，剔除信用度排名靠后的节点来保证系统整体的信用度。

1 公证人机制

传统的公证人机制是基于中心化交易中介方所得跨链资产交换［20］，这种跨链的方式比较单一，只支持资产的交换，图1演示了分别位于链A、B的用户a、b通过交易中介方进行跨链资产交换的过程。

图1 公证人机制交换过程Fig.1 Process of notary mechanism exchange

公证人机制交换过程如下：

1）用户a通过交易中介方钱包将自己的资产充入交易中介方的地址。

2）用户a在交易中介方挂出卖单交易信息A。

3）用户b需要将自己的资产充入交易中介方的地址。

4）用户b在交易中介方挂出卖单交易信息B。

5）交易中介方将用户a的卖单和用户b的卖单进行撮合。

6）交易中介方将用户a在交易中介方存储资产转移给用户b在链A的地址。

7）交易中介方将用户b在交易中介方存储的资产转移给用户a在链B的地址。

至此完成了用户a、b资产的交换（案例中省去了交易中介方的服务费）。

2 节点评价模型

2.1 评价模型

2.1.1 评价模型流程

本文通过构造一个动态的公证人节点评价模型来保证公证人机制的安全性。该模型由其他公证人节点评价和该节点历史交易评价进行协作，最终通过本文模型给出一个动态的节点信用值排序，剔除排名在后的节点。本文模型在排序时考虑下列因素：

1）节点的信用值应由与其有过交易的用户和替他节点共同评价。

2）替他节点在评价时只需给出自己信任的节点；替他节点在评价时只需给出自己信任的节点记录；历史交易评价需考虑交易处理效率、用户反馈、负面交易信息等因素。

3）节点内部优秀交易的次数越多，该节点的信用值越高。

4）节点信用值是一个逐渐积累的过程，持续诚信交易的积累才能获得高信用值。

本文模型在规定的某时间内对现有的节点进行信任度评价，系统向存在的节点发出评价信号并广播系统公钥及地址；各个节点收到信号后，使用系统的公钥进行加密并使用自己的私钥加密签名；系统会收集各个节点的加密数据并使用系统私钥解密，最终形成信任关系图并广播出去；系统在规定时间内如果未收到异议信息则进行下一步计划，如果有则重新投票；系统会自动收集各个节点历史交易信息并使用改进PageRank算法进行信用度排序，并将结果及计算过程公布；在规定时间内，系统若未收到任何异议信息，则根据流程自动剔除排名在后的节点。节点评价模型如图2所示。

图2 节点评价模型Fig.2 Node evaluation model

节点历史交易信息中用户反馈评价是指最终完成交易后用户对其进行评价，分数值从1～5由低到高；节点交易处理效率是指用户从发起交易到最终确认交易中介方需要的时间；负面交易信息包括交易未完成情况、存在欺诈等行为的交易。

2.1.2 评价系统

各个品种的鸡均有易感性，10～56日龄的鸡发病率和致死率都较高，10日龄以内的雏鸡由于有母源免疫力的保护，很少发生球虫病，成年鸡对球虫有一定的抵抗力。病鸡是主要传染源，凡被带虫鸡污染过的饲料、饮水、土壤和用具等，都有卵囊存在，鸡感染球虫的途径主要是吃了感染性卵囊。

本文评价系统由广播板、节点模块、数据采集模块、数据存储模块和信用排序模块组成，评价系统工作过程如图3所示。

图3 评价系统工作过程Fig.3 Working process of evaluation system

评价系统主要包括以下5个模块：

1）广播板：用于显示投票内容、评价内容及公告信息的模块。投票内容包含节点投票的信息、投票人的签名和广播板的签名；评价过程包含评价内容及评价结果；公告信息包含参与投票的节点的地址及投票开始及结束时间。

2）节点模块：用于节点填写投票信息及验证的模块，包含节点登录验证模块和信息填写模块。

3）数据采集模块：用于采集节点评价信息及历史交易评价信息。

4）数据存储模块：用于存储节点信息及信用排序信息。

5）信用排序模块：基于改进PageRank算法对节点信用度进行评价的模块，该模块中所有运算步骤都将在广播板显示出来。

评价系统在某一时间点时，将在广播板广播参与投票的节点及投票截止时间；节点收到投票信息将登录并验证自己的信息，填写信任的节点并签名，再把信息传到广播板，广播板显示节点传递的信息；当投票时间结束后，系统将调用改进PageRank算法对投票信息进行信用度排序，并把结果及计算过程在广播板进行展示。节点可以查看所有的投票信息及运算过程。

数据存储中包含节点的基本信息（如节点的公钥、IP地址）、节点交易的历史信息及节点投票的信息，节点可以随时查看。

2.2 改进PageRank评价算法

2.2.1 PageRank算法

PageRank算法是谷歌公司用于网页重要性评价的一种方法。其核心思想是利用网页链接到替他页面和替他页面链接到本页面的情况来计算页面的分值，并对其进行分值排序［12-14］。

在使用PageRank算法对网页重要性进行排序时，一般会假设2个前提：

1）数量假设：假设存在一个网页，如果有大批的链接与它相连，则表示这个页面非常重要，本文中的节点假设有大量的替他节点与它相连，则表示该节点非常受到信任。

2）质量假设：在互联网中，各网页的内容质量参差不齐，如果一个高质量的页面与该页面相连，则传递给该页面的权重应该很高；同样，如果有一个信任度很高的节点信任本节点，则传递给本节点的权重就会很高。

基于这2个假设，算法基于式（1）对页面等级进行评估时，对于每一个页面的权重赋予相同的值，然后通过不断地递归迭代计算，更新每一个页面的得分，直到页面得分稳定。

其中，L（ν）表示网页ν的出链数量，PR（ν）表示网页ν的PageRank值，Bu表示网页u的入链集合。从式（1）可以看出，每个页面的PageRank值是由其所有入链网页的PageRank值累加得到。

PageRank算法规定一个页面只能对其他页面进行一次投票，如图4所示。图4中节点B只能给节点A投半票，即节点B只能将它链接权重值的一半赋予节点A。同理，节点D只能将其链接权重值的1/3赋予节点A。

图4 节点拓扑结构Fig.4 Node topology

图4中节点D的PR值计算公式如下：

在现实的互联网中还存在许多页面没有链接到其他任何页面的情况，即这一页面的出链数为0（如图4中节点C），这种页面被称为孤立网页。基于这种问题，谷歌公司修订了原先的PageRank计算公式，在原先的公式上引入阻尼系数d（damping factor），根据实验，该阻尼系数一般取0.85。该系数为用户在某一时刻使用该节点后从该节点跳转到替他节点的概率。当阻尼系数为0.15时，表明用户不在通过节点跳转到另一节点，改进后的PageRank算法的计算公式如式（3）所示：

从图4可以看出：节点A有节点B指向的链接；节点B有节点A、节点D指向的链接；节点C有节点A、节点D指向的链接；节点D有节点A、节点B指向的链接。假设初始链接概率相等，则存在转移矩阵N：

其中，Ni，j表示用户从节点j跳转到节点i的概率。

假设节点的初始概率为1/n，n为节点数量，则初始概率矩阵为：

根据式（5）进行迭代，当最终结果变化在某个区间内时，结束迭代，则最终节点重要度排序为：

2.2.2 改进PageRank算法的公证人节点评价模型

每个节点的历史交易信息会对其信用评估产生内在的影响。假设存在节点A及它的一个正向链接节点B，若节点A交易处理效率高于节点B，则用户对节点A的反馈评价要高于对节点B的反馈评价；若节点A交易处理效率高于节点B，则用户对节点A的反馈评价要高于对节点B的反馈评价；负面交易信息越少，那么节点A分配给节点B的权重越高。

下文给出计算节点A、B信用度的步骤：

1）建立节点历史交易信息的交易处理效率、用户反馈、负面交易信息的集合：

2）确定用户整体评价的位置权重，引入分段函数来表征本文收集到的用户整体评价信息，分交易处理效率、用户反馈、负面交易信息3个部分计算［20］：

3）用户反馈评价值计算，计算公式如下：

其中，Qpeople代表节点总体用户反馈评价值，weightpeople代表节点用户反馈权重，gradej代表用户历史评价值。

4）交易处理效率值计算，计算公式如下：

其中，Qtime代表节点交易处理效率值，weighttime代表节点交易处理权重，timej代表节点交易处理时间。

5）节点负面消息评价值计算，计算公式如下：

其中，Qreverse代表节点负面消息评价值，weightreverse代表节点负面消息评价权重，number代表节点负面消息评价数量。

6）最终得出节点交易处理效率、用户反馈、负面交易信息评价值，计算公式如下：

7）本文通过使用向量空间模型（Vector Space Model，VSM）［14-15］来计算节点M、N相似度，即：

8）最终得到改进后的PageRank算法如式（14）所示：

如果某一节点并无历史交易信息，则：

3 实验测试

本文对某交易中介方使用的跨链交易系统的100个节点进行评价，首先节点各自填写评价表，包括所有节点之间的信任关系（谁信任谁）。然后使用0～99之间的连续整数对100位节点分别进行编号，并利用所有人之间的信任关系组织成一张节点关系，如图5所示。其中信任关系依靠有向箭头表明，例如“2→3”表示2号节点信任3号节点。

图5 部分公证人节点信任关系Fig.5 Node trust relationship of some notaries

表1为某节点历史交易信息，主要包含交易是否成功状态、交易效率和用户评价3个指标。其中如果交易失败，则缺少交易效率和用户评价。用户反馈评价值从1～5依次递增；交易状态分为成功和失败两种。本文收集了某证券交易所200个节点交易的前100条交易信息。

表1 某节点历史交易信息Table 1 Some historical transaction information of certain node

本文基于收集到的节点信任关系及各节点交易信息进行仿真测试，基于传统PageRank算法和改进PageRank算法进行仿真比较，结果如图6所示。

图6 传统PageRank算法和改进PageRank算法仿真结果对比Fig.6 Comparison of simulation results of traditional PageRank algorithm and improved PageRank algorithm

根据PageRank算法，最终的信用度值会在0～1范围内，从图6可以看出，同一个节点基于传统PageRank算法计算出的信用度值和改进后的信用度值有所差距，这是因为改进的PageRank算法考虑了节点与节点之间的历史交易信息，最终导致结果有所差异。

根据本文设定程序，最终会剔除排名靠后的节点，本次实验选定剔除排名在后10位的节点，基于传统PageRank算法剔除的节点信用度值和基于改进后的PageRank算法剔除的节点信用度值如图7所示。

图7 传统PageRank算法和改进PageRank算法最终剔除节点的信用度结果Fig.7 Credit degree results of nodes being removed by traditional PageRank algorithm and improved PageRank algorithm

本文预先针对收集到的用户历史评价信息进行平均值计算，计算出每个节点用户评价信用度值并对其进行排序，选出排名最低的节点如表2所示。表2给出了基于改进PageRank算法和传统PageRank算法所剔除的节点，结合图7和表2可以看出，改进后的PageRank算法剔除了用户评价较低的节点（如节点78、节点70），说明改进后的算法有效地结合了用户历史评价信息。

表2 需剔除的节点Table 2 Nodes to be removed

4 结束语

本文针对跨链技术中常用的公证人机制节点信用监督不足的问题，提出一种基于改进PageRank算法的评价模型。该模型对公证人节点信用评价进行优化，计算得到高可信的节点，在一定程度上保障了跨区块链系统交换资产的安全。实验结果表明，该模型能够较好地解决传统节点评价过于主观性的问题，通过节点评价和交易评价两者之间相互制衡，保证评价的公正性，在动态的交易过程中去除信任度低的节点，最终使整个系统的信任度得到提高。下一步计划将公证人机制与侧链技术、哈希锁定技术相结合，以弱化公证人机制过于中心化的问题。