基于改進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算法的評價模型。該模型對公證人節點信用評價進行優化，計算得到高可信的節點，在一定程度上保障了跨區塊鏈系統交換資產的安全。實驗結果表明，該模型能夠較好地解決傳統節點評價過于主觀性的問題，通過節點評價和交易評價兩者之間相互制衡，保證評價的公正性，在動態的交易過程中去除信任度低的節點，最終使整個系統的信任度得到提高。下一步計劃將公證人機制與側鏈技術、哈希鎖定技術相結合，以弱化公證人機制過于中心化的問題。