基于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算法的缺陷，即偏重舊節點以及“主題偏移”現象，相對客觀地對公證人節點進行評價，提高了節點信用值評估的公平性以及能夠較為有效地剔除惡意節點.另外，實驗剔除了信用值排序較低的節點構成候選公證人組，有助于在候選公證人組中根據算法合理選出一些公證人節點組成正式公證人組參與跨鏈交互，使得整個公證人組信用度得以提升，以便提高跨鏈交互中公證人機制的可靠程度和系統的穩定性.