基于PSO優(yōu)化博弈的區(qū)塊鏈共識算法

孫 晶 徐曉雅 趙會群

(北方工業(yè)大學信息學院 北京100144)(北方工業(yè)大學大規(guī)模流數據集成與分析技術北京市重點實驗室 北京100144)

0 引 言

隨著區(qū)塊鏈技術的發(fā)展，共識機制作為區(qū)塊鏈的核心技術，受到人們的廣泛關注[1]，典型的共識算法有以下幾種。Paxos算法[2]是一種基于消息傳遞的分布式一致性算法，通過準備階段和協(xié)議階段的執(zhí)行，為系統(tǒng)選出唯一的提案，來保證每個節(jié)點執(zhí)行相同的命令序列，此算法被廣泛應用在Chubby、Zookeeper分布式系統(tǒng)中。Raft算法[3]是另外一種共識算法，通過選舉一個全局的leader生產日志，并與follower進行心跳同步達成一致，其過程是對Paxos選擇提案過程的重新簡化。這兩種算法解決的都是非拜占庭問題，而區(qū)塊鏈技術的原理延伸到互聯(lián)網中可歸納為拜占庭將軍問題，即在缺少可信任的中央節(jié)點和通道情況下，分布式網絡中的各節(jié)點如何達成共識。拜占庭容錯算法[4]作為經典分布式共識算法被很多區(qū)塊鏈采用, 其過程為客戶端向主節(jié)點發(fā)送調用服務操作請求，主節(jié)點廣播請求給副節(jié)點，副節(jié)點執(zhí)行請求并向客戶端返還結果，此種情況下，若客戶端收到f+1個副節(jié)點發(fā)回相同的消息，則可以作為整個操作的最終結果。這種算法無需信任單個節(jié)點，還能創(chuàng)建網絡的共識，并且保證安全性和有效時間約束[5]。上述三種共識算法都是以“少數服從多數”的投票機制來達成共識。中本聰在設計比特幣區(qū)塊鏈網絡的共識機制時提出了創(chuàng)新的PoW(Proof of Work)工作量證明機制[6]，網絡中的節(jié)點通過復雜的哈希運算來完成工作量，從而確定節(jié)點獲得區(qū)塊的概率，這種機制耗費大量資源，共識周期較長，并且在目前的發(fā)展來看，算力集中在幾大礦池使得算力中心化違背了區(qū)塊鏈去中心化的初衷。之后又提出了PoS(Proof of Stake)股權證明機制[7]，區(qū)塊鏈系統(tǒng)要求用戶持有一定數量的加密貨幣并且具有所有權，依靠幣齡來決定記賬權。這種機制不再需要消耗大量能源去挖礦，雖然改善了資源浪費的缺點，但是權益容易集中在少數人的手里達成壟斷,這也是此機制的弊端[8]。這類共識機制的特點是通過控制算力或是股權來達成目的，對于大多數節(jié)點來說，只是接受了共識的結果，而沒有真正意義上實現系統(tǒng)的共識。Hyperledger Fabric項目是一個旨在推動區(qū)塊鏈跨行業(yè)應用的開源項目，此項目提供了兩種共識方式：solo模式的單點共識方式無容錯性，只能在測試時使用；Kafka模式的共識是一種支持多通道分區(qū)的集群時序服務，其本質還是依賴于Zookeeper進行Paxos算法選舉。此外在一些供應鏈金融區(qū)塊鏈系統(tǒng)[9]中，由一些核心企業(yè)作為系統(tǒng)共識節(jié)點，很少考慮中小企業(yè)或小微企業(yè)的收益，由此可見全局的共識不一定適用于個體。

共識機制的設計著重于系統(tǒng)和體系的建立，其目標是讓一個多樣化群體在不發(fā)生沖突的情況下做出決策，使系統(tǒng)達成一致。然而區(qū)塊鏈最顯著的特點是去中心化，其技術是追求各節(jié)點的公平與公正，這種追求與博弈論機制最為相似，參與人具有不同的目標或利益，通過博弈制約的規(guī)則來選取對自己最為有利或最為合理的方案。對每個參與人來說，博弈公平的規(guī)則產生公正的制衡結果。受到博弈論思想的啟發(fā)，共識機制的設計可以建立在系統(tǒng)參與各方的力量均衡上，這種均衡應該是在博弈規(guī)則制約下的一個可以量化的結果[10]。所以用博弈論原理建立均衡規(guī)則來設計區(qū)塊鏈的共識機制是本文的一個研究主題。

最理想的共識機制是系統(tǒng)中的節(jié)點達成的共識是一個納什均衡，即單方面改變自己的策略不會增大自己的效益。不僅內部狀態(tài)達成穩(wěn)定共識，而且對于每個節(jié)點來說都是最公正的結果。本文將尋找系統(tǒng)的納什均衡點作為系統(tǒng)的共識節(jié)點，采用納什均衡的共識算法能夠快捷準確地為整個區(qū)塊鏈系統(tǒng)推薦出幾個能夠作為打包交易信息的中心節(jié)點，來保持系統(tǒng)中節(jié)點之間的收益均衡，并使系統(tǒng)快速達到共識的狀態(tài)。然而納什均衡的求解一直以來都是一個難點問題，利用劃線法或反應函數交叉法只能求解二人博弈或三人博弈，利用同倫算法或者全局牛頓算法求解時計算復雜且難于實現。隨著智能算法的發(fā)展，依賴粒子群優(yōu)化算法尋優(yōu)，成為本文求解納什均衡的一種途徑。

1 相關工作

國內外學者已經展開了對共識機制的研究，Shi等[11]研究了多集群網絡上的約束共識問題，提出了多聚類約束一致性算法，給出了算法的一致性分析和收斂速度分析。Wang等[12]通過設計多智能體通信系統(tǒng)來研究分布式最優(yōu)共識問題，提出了二階優(yōu)化一致性算法，將平衡點作為此算法最優(yōu)點，并且在給定條件下證明算法是漸近穩(wěn)定的。張仕將等[13]提出了一種基于Gossip協(xié)議的拜占庭共識算法，提高了系統(tǒng)的穩(wěn)定性和容錯性，系統(tǒng)可以容忍小于一半的節(jié)點成為拜占庭節(jié)點。以上三種方法雖然達成了系統(tǒng)共識，但依舊沒有將博弈規(guī)則的制衡作用考慮進去。

在非合作博弈中，納什均衡是一個最重要的概念，計算納什均衡解的方法有很多。在許多博弈的經濟模型中，均衡被看成多項式方程組的解，所以納什均衡的求解就轉化成多項式的求解。Nabatova等[14]將Lemke-Howson算法用于求解雙矩陣決策中的納什均衡，找到了純策略和混合策略納什均衡，保證算法收斂于雙矩陣博弈解，但計算量很大，不適用于多人多策略博弈。

另外一些工作主要集中于將非合作博弈納什均衡延伸為分布式控制技術，將博弈論與多智能體系相結合起來。Xu等[15]設計了相應的分布式算法來解決納什均衡問題，將搜索納什均衡解與搜索梯度解聯(lián)系在一起。Ye等[16]通過結合梯度和共識方案，設計了分布式納什均衡搜索算法，對參與人行為與納什均衡的收斂性進行了分析，并為這種算法提供了數值例子。Zhu等[17]也給出了基于梯度算法被設計用于解決納什均衡計算的想法。Salehisadaghiani等[18]提出了一種基于gossip異步的算法和一種利用乘數的交替方向在部分決策信息下尋求分布式納什均衡的算法[19]，博弈中的參與人通過信息交換，用于在分布式多節(jié)點網絡中查找游戲的納什均衡，通過成本函數收斂減少步長來證明算法的有效性。文獻[20-21]設計了一種基于次梯度的算法來計算子網零和游戲中的納什均衡，并進一步研究多人非合作博弈中的納什均衡計算。以上這類算法設計復雜、適應性不強。

依賴智能算法求解納什均衡成為一種新途徑。Beiranvand等[22]采用遺傳算法來解決一個新的分布式優(yōu)化問題，使用世代種群進化的方法來逼近求納什均衡解，但用遺傳算法求解納什均衡的交叉、變異操作產生的解可能不滿足博弈的行為特征。隨后王志勇等[23]提出一種改進的蟻群尋優(yōu)思想來解決有限n人非合作博弈的納什均衡算法，提高了搜索解的能力和精確性。文獻[24-25]提出了一種基于粒子群優(yōu)化算法的算法，該算法能夠在局部最優(yōu)的博弈中找到全局納什均衡，但未給出明確的適應度函數。

本文的目標是為系統(tǒng)找到可以作為共識的納什均衡點，將求解納什均衡轉化為求解最優(yōu)化問題，用改進的粒子群優(yōu)化算法實現求解納什均衡，以此作為分布式系統(tǒng)中共識算法所選擇的主節(jié)點。

2 算法研究

本文設計并實現一個面向組合投資的區(qū)塊鏈原型系統(tǒng)，商業(yè)銀行是此系統(tǒng)的備用主節(jié)點，投資公司可以根據商業(yè)銀行的貨幣政策計算投資回報。共識機制就是在商業(yè)銀行中選擇使得每個投資公司都能獲得最佳效益的一個或者幾個商業(yè)銀行，即滿足納什均衡的商業(yè)銀行作為主節(jié)點，負責區(qū)塊鏈的打包上鏈管理。

2.1 Affnity Propagation聚類算法應用研究

由于在博弈中參與人的數量和決策數量很大程度地影響了博弈的復雜程度，為了解決這一問題，本文首先將數據進行聚類，把聚好的類作為博弈局勢中參與方的一類，這樣不但簡化了博弈的過程，還保留了數據原有的結構和屬性。參與人依賴聚類后的結果來觀察每一簇數據的特征，對特定聚簇集合進一步分析后做出決策。

本文使用AP聚類算法(Affinity Propagation Clustering Algorithm)對投資公司聚類。與K-Means不同，AP聚類不需要預先指定簇的數量，而是將點k稱為參考度的實際值S(k,k)作為輸入，不同參考度將導致不同的聚類結果，具有較大參考度的點更可能被選為聚類中心[26]。初始的AP聚類將參考度默認設置為相似矩陣的中位數，但是聚類效果不佳。因此，本文采用不同的參考度值應用于AP聚類，并使用Silhouette Coefficient(SIL)輪廓系數作為有效評估函數來識別最優(yōu)的分類。輪廓系數是常用的評價聚類內聚度和分離度的有效性指標之一，對于點i，定義為：

(1)

式中：a(i)表示點i與其所在類中其他點之間的平均距離，表示內聚度；b(i)表示點i與其最近的類之間的平均距離，表示分離度。由式(1)可知-1≤s(i)≤1,輪廓系數越大說明聚類效果越好，考慮不同參考度值所對應的輪廓系數來評估聚類質量。

由于商業(yè)銀行對不同行業(yè)的投資業(yè)務發(fā)布的貨幣政策不同，因此可以將銀行的貨幣政策作為聚類特征為投資公司進行行業(yè)聚類。本文提出AP聚類行業(yè)個數確認算法(見算法1)，并用輪廓系數評估聚類效果。

算法1AP聚類行業(yè)個數確認算法

輸入：投資公司的利率，漲跌幅，參考度p。

輸出：行業(yè)個數和聚類圖。

1 BEGIN

2 FOR每一個數據點對

3 計算s(i,k)；

/*用負歐氏距離計算相似度*/

4 初始相似度矩陣S；

5 END FOR

6 FORi-1 ton

7 計算r(i,k),a(i,k)；

/*吸引度矩陣，歸屬度矩陣*/

8 更新ri+1(i,k),ai+1(i,k)；

/*引入阻尼系數δ避免震蕩*/

9 計算max(r(i,k)+a(i,k))；

/*最大的值對應的k為點i的聚類中心*/

10 END FOR

11 輸出Exemplar

/*聚類中心對應的投資公司*/

12 確認聚類個數m；

13 FORitom

14 連接數據對[i,Exemplar]；

15 構造稀疏圖結構G=[I,E]；

/*數據點集I，邊集E*/

16 END FOR

17 用式(1)計算輪廓系數；

18 投資行業(yè)個數=m；

19 輸出圖結構；

20 END

2.2 改進的粒子群算法求解納什均衡

聚類分析后，需要從算法1中得到的每類行業(yè)中選擇納什均衡解，找到最優(yōu)策略。本文采用最優(yōu)的思想尋求最優(yōu)解，用改進的粒子群算法得到全局最優(yōu)的資源分配，設計求解每一類行業(yè)中的納什均衡解。算法中每個粒子的位置代表投資公司進行博弈的一個局勢，該局勢設置成投資公司與銀行之間所貸款的金額和貸款時的利率，由于策略的選擇為概率，算法中把所有的粒子初始位置映射到[0,1]，依據式(2)確定粒子的初始位置。

(2)

式中：Nmax與Nmin分別為映射的下限1和0;Omax和Omin分別為貸款金額和貸款利率的最大值和最小值；Ox,y表示當前粒子對應投資公司的貸款金額及貸款時的利率。在博弈局勢中，參與人所采取的策略都是其他參與人所采用策略的最優(yōu)反應，所以具有最優(yōu)適應度的粒子代表了博弈中的納什均衡。根據納什均衡的定義與性質，在有限n人非合作博弈的戰(zhàn)略式表述G={s1,s2,…，sn;u1,u2,…,un}中，ui表示為：

ui=max{sregi-(E(x)-Eavg),0}

(3)

式中：sregi=|Ei-Eavg|代表每一家投資公司的收益與平均收益Eavg的差值;E(x)代表納什均衡解下的公司收益。通過式(3)可知，當混合局勢為納什均衡解時，ui才能取得最小值0，而混合局勢為非納什均衡解時，ui取得較大值。為了使所求解接近納什均衡得到近似納什均衡解，本文設計投資公司博弈局勢中的適應度函數:

f(x)=minuii∈(1,2,…,n)

(4)

在博弈的策略組合空間內，f(x)適應度越小，該公司的收益越接近均衡值。

在算法的迭代中，每家投資公司會根據迭代中的個體最優(yōu)值Pbest和群體最優(yōu)值Gbest發(fā)生移動，不斷調整自己的策略，然而在群體迭代過程中，容易陷入局部最優(yōu)解，導致求解的納什均衡不準確。針對這一問題，本文提出一種基于擁擠距離的粒子群算法求解納什均衡。擁擠距離(Deterministic crowding,DC)表示個體周圍其他個體的疏密程度，擁擠距離越大，說明個體分布得稀疏，多樣性越大。依據擁擠度的方法選出全局最優(yōu)位置，引導粒子向處于較稀松區(qū)域進行搜索，避免陷入局部最優(yōu)值，提高了解的多樣性，最終趨向博弈的均衡點，并且此行為符合博弈行為。擁擠距離的計算步驟如下：

Step1對于每個個體，初始化擁擠距離為di=0。

Step2對適應度函數f(x)，根據適應度函數的數值大小, 對每個個體排序;對于每個個體，計算擁擠距離：

di+1=di+(f(i+1)-f(i-1))

(5)

Step3對于邊緣上的個體給予其選擇優(yōu)勢，將其擁擠距離設置成較大值。

Step4選擇時優(yōu)先選擇較大的擁擠距離。

PSO優(yōu)化時需要時間代價，當遇到大規(guī)模數據累積或復雜程度增大的情況，就會影響算法的性能。對于單一智能算法而言，進行數據處理的能力有限、精度不足，本文利用引力搜索算法Gravitational Search Algorithm (GSA)改進粒子群算法來提高全局的尋優(yōu)能力。GSA是一種新的啟發(fā)式方法，粒子運動遵循動力學規(guī)律，粒子朝著質量大的粒子方向進行運動，質量最大的粒子占據著最優(yōu)的位置，從而得出問題的最優(yōu)解[27]。在GSA中，假設在一個系統(tǒng)中有N個粒子，定義粒子i的位置xi，速度為vi，通過評價粒子的適應度函數值，確定每個粒子的質量和受到的力，計算加速度，并更新速度和位置。這幾個參數的計算步驟如下[28]：

Step1計算質量。粒子i的質量定義：

(6)

(7)

式中：fiti(t)和Mi(t)分別表示第t次迭代時第i個粒子的適應度值和質量；best(t)和worst(t)表示適應度的最優(yōu)和最差值。

Step2計算引力。粒子j對粒子i的引力：

(8)

式中：G(t)表示萬有引力常數的取值；Mpi(t)表示被作用粒子i的慣性質量；Maj(t)表示作用粒子j的慣性質量，ε是一個小常數，避免分母為0。

那么，施加給粒子i的合力:

(9)

式中：rand是一個隨機數且0≤rand≤1。

Step3計算加速度。根據牛頓第二運動定律，粒子i的加速度為：

(10)

Step4更新速度和位置。

vi(t+1)=rand×vi(t)+ai(t)

(11)

xi(t+1)=xi(t)+vi(t+1)

(12)

本文在粒子群算法求解納什均衡解中，結合計算擁擠距離的方法引導粒子的搜索過程，并且使用一種結合PSO和GSA的新型優(yōu)化方法，主要思想是將PSO的尋優(yōu)行為和GSA的研究定位能力結合起來，以創(chuàng)建功能強大的優(yōu)化算法。此時PSOGSA混合算法的速度更新公式如下：

vi(t+1)=rand×vi(t)+c1r1ai(t)+

c2r2(Gbest-xi(t))

(13)

式中：c1、c2是學習因子；r1、r2為[0,1]區(qū)間內相互獨立的隨機數。

由擁擠距離和GSA改進的粒子群算法求解博弈問題納什均衡解的算法如算法2所示。

算法2改進的粒子群算法求解納什均衡算法

輸入：投資公司向銀行貸款數據，粒子速度上限vmax，粒子速度下限vmin，慣性因子，隨機初始化粒子加速度。

輸出：最優(yōu)局勢，近似納什均衡解。

1 BEGIN

2 FOR每一個粒子i

3 用式(2)初始化粒子的初始位置

/*貸款金額和利率映射投資公司所對應的位置pi*/

4 用式(4)計算適應度函數，評價優(yōu)化目標值；

5 用式(5)計算擁擠距離度量；

6 設置pbest=xi；

/*找到當前最優(yōu)解*/

7 END FOR

8Gbest=min{pbest}；

9 WHILE NOT STOP

10 FORi-1 ton

11 更新best(t)、worst(t)、Gbest；

12 用式(7)、式(9)更新粒子質量和受力；

13 用式(10)更新粒子加速度；

14 用式(13)更新粒子的速度；

15 更新粒子的位置pi=pi+vi；

16 計算擁擠度距離di重新評價博弈局勢；

17 IFdi(xi)

18pbest=xi；

/*基于DC排序更新每個粒子局部最優(yōu)值*/

19 IFdi(pbest)

20Gbest=pbest；

/*基于DC排序更新粒子全局最優(yōu)值Gbest*/

21 END FOR

22 END WHILE

23 輸出Gbest作為近似納什均衡解；

24 END

2.3 基于納什均衡的共識算法

基于以上兩個算法可以求出納什均衡的近似解，將其對應的商業(yè)銀行作為區(qū)塊鏈共識過程中的主節(jié)點，負責區(qū)塊鏈的打包上鏈管理。Fabric項目的共識過程包括3個階段：背書、排序和校驗，本文只在排序這個部分做出改進，接受被認可的交易并且將其進行排序，確保交易順序的一致性，并且將商業(yè)銀行設置為orderer節(jié)點負責打包排序，投資公司設置為peer節(jié)點進行數據交易，結合已求得的納什均衡近似解來設計基于博弈的區(qū)塊鏈共識算法，如算法3所示。

算法3Nash-consensus算法

在Fabric網絡剛啟動時，orderer節(jié)點進入備選狀態(tài)，同時創(chuàng)建計算時間超時定時器。

Orderer端：

輸入：納什均衡解下所對應的商業(yè)銀行節(jié)點，客戶端(peer節(jié)點)發(fā)送交易信息，BatchSize，BatchTimeout。

輸出：數據區(qū)塊。

BEGIN

1 orderer節(jié)點：

2 orderer節(jié)點進入備選狀態(tài)；

3 納什均衡解下對應的第一個商業(yè)銀行orderer節(jié)點作為leader，其余解作為備份節(jié)點；

4Term=1；

5 IFtime>超時定時器時間

6 選擇下一個備選節(jié)點作為leader；

7Term++；

8 其他orderer節(jié)點收到leader消息后，回到備選狀態(tài)；

9 Leader通過recv接口，監(jiān)聽peer節(jié)點發(fā)送過來的交易信息；

10 IF 區(qū)塊大小>=BatchSize

11 BlockCutter；

/*切塊*/

12 IF 時間>=BatchTimeout

13 CreatNextBlock；

/*創(chuàng)建塊*/

14 將區(qū)塊寫入Ledger中；

15 返回處理信息并進行廣播；

16 END

Peer端：

在Fabric網絡剛啟動時，peer節(jié)點連接orderer節(jié)點，同時創(chuàng)建計算時間超時定時器。

輸入：獲取leader排序后生成的區(qū)塊。

輸出：交易信息。

BEGIN

1 Peer節(jié)點：

2 IF Peer節(jié)點通過GRPC連接到leader排序節(jié)點

3 發(fā)送交易信息；

4Term=1；

5 IFtime>超時定時器時間

6 繼續(xù)等待；

7Term++；

8 Peer通過deliver接口，獲取leader排序后生成的區(qū)塊數據；

9 檢查交易是否滿足背書策略； /*簽名版本號等是否正確*/

10 END

綜上所述，將納什均衡解作為共識算法的主節(jié)點分為兩個部分，第一部分對于投資公司進行聚類，用AP算法將投資公司分成不同的簇，并用輪廓系數評價聚類效果，將所聚出的簇作為博弈的一類投資人，用改進的粒子群優(yōu)化算法求解納什均衡。第二部分將所求解下對應的商業(yè)銀行作為超級賬本中的orderer節(jié)點，按照順序依次作為系統(tǒng)的共識節(jié)點。若orderer節(jié)點被選為共識主節(jié)點，其他的orderer節(jié)點則被認作備用主節(jié)點，當共識主節(jié)點出現安全和可靠性失敗時，由備用主節(jié)點接管其業(yè)務。將納什均衡解下對應的商業(yè)銀行節(jié)點設置成超級賬本網絡中的共識節(jié)點，負責對交易信息的打包上鏈管理，其過程大致分成四個步驟，如圖1所示。

圖1 共識過程示意圖

Step1peer節(jié)點通過broadcast接口將交易信息收集，提交給leader主節(jié)點。

Step2leader主節(jié)點將交易信息復制給作為備份的orderer節(jié)點，以防數據丟失。

Step3備份orderer節(jié)點返還確認接收的消息，leader主節(jié)點對交易信息進行切塊處理。

Step4leader主節(jié)點將處理后的信息進行廣播。

3 實驗與結果分析

本文設計的區(qū)塊鏈系統(tǒng)中，投資公司希望在銀行貨幣政策下獲得最大效益，而這些投資公司彼此之間并不了解對方的收益，所以可以認定投資公司之間的博弈是非合作的靜態(tài)博弈，由于任何投資公司在特定的銀行的貨幣政策下，不可能改變投資的效益比率，所以投資環(huán)境滿足博弈論中納什均衡的條件。其中投資環(huán)境如圖2所示，商業(yè)銀行在中央銀行的指導下，發(fā)布自己的貨幣政策，投資公司與商業(yè)銀行有貨幣業(yè)務往來，如貸款、儲蓄等。

圖2 投資環(huán)境示意圖

本文將實驗結果和分析分成三部分，分別對應第2節(jié)中提出的三個算法：用投資公司在銀行購買債券的利率和漲跌幅作為聚類特征，使用AP聚類訓練數據得到聚類結果；對每一類的數據，分析銀行利率和收益之間的關系，用基于擁擠距離的粒子群算法求解類所在的納什均衡的近似解，將求得的納什均衡解所對應的貸款銀行作為共識算法的主節(jié)點，應用到Hyperledger Fabric網絡中，負責區(qū)塊鏈的打包上鏈管理。

3.1 親和力傳播算法聚類結果

隨著金融科技和量化投資的發(fā)展，傳統(tǒng)的營銷方法很難獲得長期穩(wěn)定的收益，投資公司投資某項目時已不是簡單和被動地對市場需求作出反應，而是更加趨向于將自己的業(yè)務托管到金融公司來減少投資風險，金融公司為一類行業(yè)的投資公司提供高效安全、快捷周到的服務。

本文依據金融政策對投資公司的影響情況，運用聚類分析將這些投資公司進行分類，更加精準地掌握投資公司的特征，確定投資的范圍。分類后的結果即為投資公司對應行業(yè)所在的金融公司。本文選擇公司在銀行購買債券的利率和漲跌幅這兩項財務指標作為聚類的特征，對這些投資公司進行了聚類分析，為每家投資公司確定其所屬的簇群。其中部分數據如表1所示，數據來源于CSMAR國泰安經濟金融數據庫、中國債券市場研究數據庫。

表1 債券交易數據文件(部分)

3.1.1參數優(yōu)化

本文使用AP聚類對上述數據進行訓練，得到初始的參考度值為-1.3。根據第2節(jié)所述，參考度的值會極大影響聚類的性能，本文將參考度初始值作為參考，選擇附近的一組值[-2.3,-0.5]重新聚類，依據SIL索引的最佳值，確定最佳簇數。圖3說明了不同參考度對于聚類結果的影響，大于中位數值的參考度聚類后輪廓系數較小，聚類效果不佳；小于中位數值的參考度聚類后輪廓系數逐漸增大，并逐漸趨于平穩(wěn)(圖3(a))；同時參考度的不同影響了最終聚類的簇數結果，參考度在-2附近時，聚類簇數較為穩(wěn)定(圖3(b))。輪廓系數越大，其相應的聚類效果越好，最終選擇參考度為-2.1時，輪廓系數為0.575 5，簇數為12的結果作為本文最佳的聚類效果。

(a) 不同參考度對輪廓系數的影響

(b) 不同參考度對聚類個數的影響圖3 不同參考度對聚類效果的影響

圖4所示輪廓系數評估聚類質量效果圖，橫坐標為輪廓系數，縱坐標為簇數所含樣本點的多少，虛線表示輪廓系數的均值，以此可以判斷聚類模型的性能。

圖4 SIL均值評估聚類質量

3.1.2聚類結果

聚類結果為12個類，即將投資公司分類成12個類，每一類都有對應行業(yè)的金融公司接管子投資公司的業(yè)務，聚類結果如圖5所示，展示了AP聚類訓練樣本點過程的主要步驟。訓練數據集包含上述數據來源的數據點，每一個數據點代表一家投資公司(圖5(a))；AP聚類將這些樣本分配到12個子簇中，節(jié)點顏色表示公司所屬的類別，用來區(qū)分公司所屬的簇群，其中節(jié)點的相關性用線條來表示，線條越短，表示投資公司之間的關聯(lián)性越強(圖5(b))；為簇群獲得相應的子簇邊界，每個簇群都有一個聚類中心，用公司標簽顯示出來(圖5(c))。聚類結果如表2所示。

(a) 原始數據 (b) AP聚類結果

(c) 增加輪廓的聚類結果圖5 投資公司聚類后的結果

表2 聚類結果

可以看出，使用此聚類方法可以挖掘出數據潛在的關系，所得到的結果與投資公司實際業(yè)務和經營狀況基本符合。例如：Cluster1，將電子科技類的投資公司分成一類；Cluster3，將建筑材料的投資公司分成一類。聚類分析可直觀顯示各種投資公司的歸屬，為金融公司接管投資公司業(yè)務提供了一種途徑和技術支持。

3.2 粒子群求解納什均衡算法結果分析

本節(jié)使用改進的粒子群算法求解一類投資公司在貸款政策下的納什均衡解，即算法最終給出的最優(yōu)點坐標。所用的數據為上一步聚類所得第一類金融公司向銀行貸款的數據如表3所示，數據來源于CSMAR國泰安經濟金融數據庫。

表3 上市公司向銀行貸款數據(部分)

在算法2的實現中，初始點位置根據式(1)映射生成148個點，即第一類金融公司所包含的業(yè)務數，每個粒子代表其當前局勢，粒子的速度隨機生成，保證在速度的上下限內，設置速度上限0.5，下限-0.5，慣性因子0.8?；趽頂D距離和GSA的粒子群算法求解納什均衡迭代過程如圖6所示，展示了不同迭代次數粒子向最優(yōu)解移動的過程，每個投資公司通過迭代不斷調整自己的策略，向能使整個金融公司收益效益最好的空間不斷移動，最終趨向博弈的均衡點。在本文算法中，博弈問題可能有一個或者多個納什均衡解，若有多個納什均衡解，則其對應的貸款銀行可作為共識算法的備用主節(jié)點。

(a) 第1次迭代 (b) 第20次迭代

(c) 第30次迭代 (d) 第40次迭代圖6 改進的粒子群算法求解納什均衡迭代過程

本文通過比較普通粒子群算法(PSO)、基于擁擠距離的粒子群優(yōu)化算法(DC-PSO)、基于擁擠距離和GSA改進的粒子群算法(DC-GSAPSO)三種算法進行對比,如圖7所示，可以看到DC-GSAPSO在求解博弈的均衡解過程中比普通粒子群算法收斂得更快，解的質量具有更小的適應度值。

圖7 適應度函數隨迭代次數的變化

為了進一步分析改進算法的穩(wěn)定性和有效性，本文采用初始數量為300個粒子對三種算法進行驗證，通過計算邊緣粒子坐標的總個數與粒子總數的比值來計算覆蓋率，依據覆蓋率隨迭代次數的變化來評價算法的有效性，如圖8所示，可以明顯看出,DC-GSAPSO每次迭代所產生的解均要優(yōu)于其他兩種算法。

圖8 邊緣坐標覆蓋率隨迭代次數的變化

第一類金融公司依據算法搜索到的納什均衡解如表4所示，展示了解的適應度值大小、邊緣坐標、所對應的投資公司和貸款銀行，可以看到適應度越小越接近納什均衡解。算法找到了三個納什均衡解，在銀行的選取上，本文選擇第一個解對應的中國建設銀行作為此類金融公司的主節(jié)點。

表4 第一類金融公司確定的納什均衡解

此外的12類金融公司依據同樣的方法所選擇出的銀行如表5所示。表5中通過眾數來選擇排名前三的銀行為：中國建設銀行、中國銀行和中國工商銀行。依據順序選擇中國建設銀行作為此系統(tǒng)模型的共識主節(jié)點負責區(qū)塊的排序和打包上鏈，中國銀行和中國工商銀行作為系統(tǒng)的備份主節(jié)點，當主節(jié)點安全性和可靠性失效時，使用容錯算法替換成備份主節(jié)點。

表5 面向組合投資模型的納什均衡解

在組合投資方面，如果合理利用組合投資的方式，不但可以把風險控制在合理范圍內，而且可以獲得收益。依據投資組合優(yōu)化理論選取標準和得到的納什均衡解，考慮投資者之間的影響關系，降低投資風險來提高盈利的準確性。由于聚類后得到的12類投資公司之間的相關性降低，符合投資組合優(yōu)化理論，所以本文選擇表5中利用基于擁擠距離的粒子群算法求出的納什均衡解對應的12家投資公司(北方創(chuàng)業(yè)、長江投資、北新建材、百利電氣、廣博股份等)作為此次計算的組合投資方案，這樣做不但減少了投資者的投資范圍，而且可以讓投資者重點關注處于納什均衡解附近的穩(wěn)定性公司。

為了驗證算法2求解納什均衡解的正確性和可行性，本文采用博弈中的一個經典的雙矩陣對策例子Rock-Scissors-Paper，對本文理論進行驗證。Rock-Scissors-Paper中兩個人的支付矩陣如表6所示。

表6 Rock-Scissors-Paper支付矩陣

運用A和B的支付矩陣，用改進的粒子群算法隨機生成粒子來解決此問題，如表7所示。

表7 Rock-Scissors-Paper的納什均衡解

納什均衡解為x=[x1,x2]T,其中x1=[0.33,0.33,0.33]T，x2=[0.33,0.33,0.33]T。這符合我們的常識，即游戲中的兩個玩家隨機出剪刀石頭布，每種策略概率為1/3，滿足每個人的最大化利益，即達到納什均衡，且驗證了算法2求解的正確性。

3.3 系統(tǒng)共識實驗

根據以上兩節(jié)我們求得了納什均衡近似解，并將均衡解作為共識主節(jié)點，本節(jié)將提出的共識算法應用于一個面向組合投資的區(qū)塊鏈原型系統(tǒng)，基于Hyperledger Fabric 1.0來實現系統(tǒng)的共識機制。

3.3.1實驗數據

共識節(jié)點需要將交易信息進行切塊打包成區(qū)塊，這里的數據主要是peer節(jié)點之間的交易信息，利用peer之間進行頻繁的轉賬操作生成交易信息。交易依據中國上市公司關聯(lián)交易數據庫，此數據庫包含以上兩個實驗中投資公司交易的基本情況和相關信息，收集了投資公司的基本信息、資金往來等數據，如表8所示。

表8 中國上市公司關聯(lián)交易數據庫(部分)

由于數據庫包含數據量很大，而共識實驗只需要驗證交易信息是否達成一致，不需要全部的數據量為依靠，本文選擇投資公司交易量大于100條交易的14家公司作為系統(tǒng)的peer節(jié)點，從數據庫中為每家公司隨機抽取4條交易數據作為打包上鏈的交易信息，這樣做不僅減少了數據量，而且數據庫結構合理，客觀反映了關聯(lián)交易的實質性內容。表9所示為選擇的投資公司交易數據量的大小。

表9 公司交易數據量大小

3.3.2實驗場景及過程

基于官方給出的Fabric1.0版本，在examples/e2e_cli案例基礎之上進行二次開發(fā)。在e2e_cli基礎上更改系統(tǒng)的結構：3個peer組織即14個投資公司peer節(jié)點如圖9所示；3個orderer商業(yè)銀行節(jié)點，指定中國建設銀行作為主orderer，中國銀行和中國工商銀行作為備用orderer。

圖9 Peer Graph

首先使用cli工具將peer節(jié)點和主orderer以及備用orderer加入同一通道，進行chaincode安裝以及實例化，目的是制定peer之間正常交易的規(guī)則，模擬peer之間的正常轉賬場景，通過SDK或者cli工具調用兩個peer之間的轉賬操作，為主orderer產生需要排序打包的交易數據。通過接收時間的先后生成了消息序列，之后依據提出的共識算法Nash-consensus，主orderer對消息序列打包成block，記錄交易數據共識成區(qū)塊的各項信息。

3.3.3實驗結果

用中國建設銀行作為主節(jié)點共識上鏈，設置最大消息計數為15，區(qū)塊最大字節(jié)數為98 KB，BatchTimeout為10 s，打包上鏈的區(qū)塊信息結果如表10所示。

表10 BLOCK信息

分別對Solo、Kafka、基于納什均衡的共識算法Nash-consensus進行對比，分別從有無博弈思想、安全性、擴展性、性能效率、資源消耗五方面進行比較，結果如表11所示。其中：安全性指共識算法是否有容錯性；擴展性指是否支持節(jié)點的擴展。

表11 三種共識算法對比

4 結 語

現代計算機技術中，各類共識算法都有其適用的場景，并不存在絕對優(yōu)劣之分。為了保證區(qū)塊鏈系統(tǒng)中各節(jié)點的利益，本文精心設計一個區(qū)塊鏈共識算法，從博弈的角度入手，利用納什均衡理論使系統(tǒng)達成一致，均衡結果作為系統(tǒng)的共識機制。在對納什均衡問題的求解上，將其轉化為最優(yōu)問題，用聚類算法對系統(tǒng)中各節(jié)點進行分類，而后用粒子群優(yōu)化算法求解納什均衡近似解，將納什均衡解下對應的節(jié)點應用于一個面向組合投資的區(qū)塊鏈原型系統(tǒng)中，作為系統(tǒng)的共識節(jié)點，使系統(tǒng)達成共識。總體來說，本文為從博弈方向設計區(qū)塊鏈共識算法提供了新的思路。