江雨燕，邵 金，呂 魏

(安徽工業(yè)大學管理科學與工程學院,安徽馬鞍山243032)

自2008年Satoshi發(fā)表《Bitcoin:A peer-to-peer electronic cash system》以來，比特幣在全球逐漸發(fā)展、穩(wěn)定運行，其底層技術“區(qū)塊鏈”也逐漸引起業(yè)界關注。區(qū)塊鏈的去中心化特性使數(shù)據(jù)的驗證、記賬、存儲、維護和傳輸?shù)冗^程為分布式系統(tǒng)結(jié)構(gòu)，使用純數(shù)學方法替代中心機構(gòu)建立分布式節(jié)點間的信任關系。區(qū)塊鏈類型可分為公有鏈、私有鏈和聯(lián)盟鏈。公有鏈服務對象是任何人，并且沒有設置訪問權(quán)限，任何人都可成為節(jié)點記賬人；私有鏈與中心化數(shù)據(jù)庫相似，不同點在于系統(tǒng)內(nèi)部每個節(jié)點依然是去中心化的；聯(lián)盟鏈一般針對的是特定的組織，節(jié)點的數(shù)量通常是固定的，接入的管理較為嚴格。針對供應鏈溯源應用，最適合的是聯(lián)盟鏈。隨著供應鏈上的企業(yè)逐漸增多，供應鏈結(jié)構(gòu)更加復雜。供應鏈上的信息分布在不同供應鏈成員手中，信息共享程度較低，信息的真實、可靠性難以保證。王志鏵等提出農(nóng)產(chǎn)品柔性可信溯源系統(tǒng)，利用區(qū)塊鏈構(gòu)建其溯源模型，結(jié)合區(qū)塊鏈去中心化的特點滿足農(nóng)產(chǎn)品溯源的靈活性需求。針對供應鏈上下游交易溯源存在的問題，郭珊珊提出區(qū)塊鏈上可信溯源解決方案，將區(qū)塊鏈分為數(shù)據(jù)層、存儲層、應用層3個層次結(jié)構(gòu)，在底層P2P(peer to peer lending)網(wǎng)絡中每個交易角色進行交易，并對區(qū)塊進行驗證；每個節(jié)點在存儲層存儲該鏈上通過驗證的區(qū)塊信息；在應用層進行交互，實現(xiàn)信息可查詢、不可篡改。李明佳等提出基于區(qū)塊鏈的食品安全溯源體系，結(jié)合區(qū)塊鏈隱私保護、分布式容錯提供食品運轉(zhuǎn)信息，定位發(fā)生問題環(huán)節(jié)，實現(xiàn)即時溯源，可有效提高食品安全的可靠性。趙公民等提出基于區(qū)塊鏈的供應鏈信任機制，將區(qū)塊鏈與供應鏈硬性、柔性管理機制相融合，助于建立供應鏈高度的信任氛圍。以上文獻將各種基于區(qū)塊鏈的模型架構(gòu)應用于區(qū)塊鏈溯源，很少考慮到共識算法存在的問題。鑒于此，文中考慮到實用拜占庭容錯算法中主節(jié)點傳遞消息可能是惡意傳遞或是節(jié)點故障兩種情況，提出基于改進算法的供應鏈溯源模型，以更好契合實際應用，提高共識效率。

1 PBFT算法及改進

1.1 PBFT算法

圖1 一致性協(xié)議執(zhí)行過程Fig.1 Conformance agreement execution process

實用拜占庭容錯(practical Byzantine fault tolerance,PBFT)共識算法是一種基于狀態(tài)機副本復制的分布式一致性算法。要求各節(jié)點發(fā)送消息時均需簽名，其他節(jié)點無法修改別的節(jié)點消息，在收到客戶端請求后，只有經(jīng)過全網(wǎng)廣播完成上一個請求，才會發(fā)送下一個請求執(zhí)行，這與供應鏈溯源應用相契合。PBFT算法由一致性協(xié)議、視圖切換協(xié)議、檢查點協(xié)議組成。其中一致性協(xié)議提出若總節(jié)點數(shù)為N，拜占庭節(jié)點數(shù)目為f（可以容忍的最大數(shù)目），正常節(jié)點至少為f+1個，即N ≥3f+1,因此在PBFT算法中拜占庭節(jié)點的數(shù)量f ≤(N-1)/3。該算法的一致性協(xié)議中提出了3 個階段：預準備階段、準備階段、確認階段，執(zhí)行過程如圖1。

圖中“Client”為客戶端，“Primary”為主節(jié)點，“Replica1”和“Replica2”為從節(jié)點，“Replica3”為故障節(jié)點?！癛equest”為從客戶端發(fā)出的請求。

1)預準備階段(Pre-prepare) 主節(jié)點收到客戶端請求后，生成并向所有廣播節(jié)點發(fā)送一個預準備消息，消息格式為＜＜Pre,V,n,d＞,M＞，V 為視圖編號，d 為計算出的相應哈希值，n 為消息編號，M 為客戶端消息。

2)準備階段(Prepare) 節(jié)點i 收到預準備消息生成準備消息，將預準備消息和準備消息寫入日志，將準備消息廣播至所有備份節(jié)點，消息格式為＜Prepare,V,n,d,i＞，其中i 為節(jié)點編號，若有f+1 個節(jié)點確認該消息真實，達成共識，則進入確認階段。

3)確認階段(Commit) 節(jié)點i 確認收到消息后，會向其他備份節(jié)點廣播該消息，消息格式為＜Commit,V,n,i＞，各節(jié)點對收到的消息進行驗證，驗證成功后,(2n+1/3)個節(jié)點會發(fā)回相同結(jié)果，則該請求完成待執(zhí)行。

PBFT算法要求總節(jié)點數(shù)為N ≥3f+1(其中f為拜占庭節(jié)點)，一致性協(xié)議中的預準備和準備階段都是副本節(jié)點接收主節(jié)點發(fā)送的序列，讓所有共識節(jié)點認可這個序列后方可按照序列執(zhí)行，若副本節(jié)點檢查消息時發(fā)現(xiàn)主節(jié)點為拜占庭節(jié)點，則會發(fā)起視圖切換協(xié)議，當2f+1 個節(jié)點確認視圖切換，則選舉出新的主節(jié)點p=v+1 mod|R|。

PBFT算法是聯(lián)盟鏈常用的算法，對區(qū)塊鏈共識過程的改善很大，但往往按照編號順序依次選取主節(jié)點，主節(jié)點為惡意節(jié)點的可能性不確定，且當節(jié)點數(shù)越多，節(jié)點之間的共識效率越低，造成較高的通訊開銷。若連續(xù)選取的主節(jié)點為惡意節(jié)點，不停地觸發(fā)視圖切換協(xié)議，則會造成極大的系統(tǒng)資源消耗，降低系統(tǒng)安全性。

1.2 改進的PBFT算法

供應鏈成員中企業(yè)出現(xiàn)惡意動機的情況不多見，但不排除網(wǎng)絡波動導致無法通信等情況，主節(jié)點一般會出現(xiàn)兩種錯誤情況：主節(jié)點因故障未發(fā)生響應；主節(jié)點是拜占庭節(jié)點，惡意篡改客戶端發(fā)送的消息。針對實際應用中主節(jié)點會發(fā)生變化，提出一種基于PBFT改進的算法—動態(tài)實用拜占庭容錯算法(dynamic practical Byzantine fault tolerance,DPBFT)。DPBFT算法設置計分機制，每個節(jié)點初始分數(shù)為0分，第一種未響應的主節(jié)點扣5分，第二種作惡的主節(jié)點扣10分。若節(jié)點誠實，成功完成共識過程則為節(jié)點加1分。當所有節(jié)點分數(shù)相同，隨機抽取一個作為主節(jié)點；當分數(shù)不同，選取分數(shù)最高的作為主節(jié)點，DPBFT算法流程如圖2。

圖2 DPBFT算法流程Fig.2 Process of DPBFT algorithm

假設在共識機制中有4個節(jié)點，分別為n,n,n,n。其中n,n,n為誠實節(jié)點，n為拜占庭節(jié)點，交易向量為 S，則n發(fā)送給n的交易向量為S，n發(fā)送給n的交易向量為S，則G 需要滿足以下條件：

G(S)=false 表示通過與其他節(jié)點發(fā)送的消息核對后，從x 節(jié)點發(fā)送到y(tǒng) 節(jié)點的消息是異常的，兩者存在一個拜占庭節(jié)點。為降低主節(jié)點是拜占庭節(jié)點的概率，文中采用計分制定期投票選取主節(jié)點的策略，主要步驟如下：

1)網(wǎng)絡上的所有副本節(jié)點參與投票，選出一個主節(jié)點。每個節(jié)點的初始分數(shù)為0分，每個節(jié)點被選為主節(jié)點的概率相等，投票決定主節(jié)點。后續(xù)選擇主節(jié)點優(yōu)先從分數(shù)最高的節(jié)點中抽取。

2)客戶端發(fā)送請求后，分為3類情況：主節(jié)點發(fā)送錯誤消息、主節(jié)點無響應、主節(jié)點誠實。若主節(jié)點無響應，則對該節(jié)點扣5分并觸發(fā)視圖切換協(xié)議，視圖切換消息格式為＜Viewchange,n,C,P,i＞；若主節(jié)點發(fā)送錯誤消息，即收到請求后，主節(jié)點在全網(wǎng)絡進行廣播，廣播消息的格式為＜＜Pre,V,n,d＞,M＞，惡意分配錯誤序號，其他從節(jié)點無法驗證通過，則對該節(jié)點扣10分，并進入視圖切換協(xié)議，發(fā)送視圖切換消息；若主節(jié)點為誠實節(jié)點，并成功完成一次共識過程，則為共識過程各節(jié)點加1分，將各節(jié)點確認的消息驗證、記錄并寫入?yún)^(qū)塊。

3)為防止誠實共識節(jié)點在系統(tǒng)正常運行后發(fā)生改變或宕機，按照步驟1)的方式重新選取新的主節(jié)點，每次根據(jù)實時節(jié)點分數(shù)選取，以降低作惡節(jié)點成為主節(jié)點的概率。

2 基于DPBFT算法的供應鏈溯源模型

區(qū)塊鏈的基礎架構(gòu)模型包含數(shù)據(jù)層、網(wǎng)絡層、共識層、激勵層、合約層和應用層。數(shù)據(jù)層封裝數(shù)據(jù)區(qū)塊，并包含鏈式結(jié)構(gòu)、時間戳、哈希函數(shù)等；網(wǎng)絡層包括P2P網(wǎng)絡、數(shù)據(jù)傳播機制等；共識層包括工作量證明機制、權(quán)益證明機制、股份授權(quán)證明機制和實用拜占庭容錯法等各類共識算法；激勵層通過經(jīng)濟因素獎勵區(qū)塊鏈上率先完成算法工作的節(jié)點。合約層封裝各類算法與腳本，是區(qū)塊鏈的核心，使區(qū)塊鏈具可編程性。

針對供應鏈溯源應用，文中將模型架構(gòu)分為數(shù)據(jù)層、合約層、應用層，具體如圖3。相對于公有鏈，聯(lián)盟鏈的控制權(quán)更易設定，擴展性較好，聯(lián)盟成員共同維護供應鏈鏈上的信息安全，影響到每一成員的自身利益。因此在設計架構(gòu)時不涉及激勵層，同時將共識層中共識算法融合到數(shù)據(jù)層，與合約層對接。

圖3 供應鏈溯源模型架構(gòu)Fig.3 Supply chain traceability model architecture

1)數(shù)據(jù)層 主要定義數(shù)據(jù)結(jié)構(gòu)和存儲數(shù)據(jù)，節(jié)點與節(jié)點之間通過哈希函數(shù)所求的結(jié)果，將某特定時間內(nèi)收到的交易記錄封裝在一個帶有時間戳的數(shù)據(jù)區(qū)塊中，這些交易記錄通過Merkle樹的哈希過程生成Merkle根存儲在區(qū)塊頭，區(qū)塊頭包含哈希值、時間戳、Merkle樹根和區(qū)塊高度等數(shù)據(jù)。共識過程的核心是選主和記賬兩部分，從輸入數(shù)據(jù)節(jié)點之間的交易數(shù)據(jù)到封裝好的數(shù)據(jù)區(qū)塊，分為選主、造塊、驗證、記賬4個階段，每執(zhí)行一輪便生成一個新的區(qū)塊，區(qū)塊結(jié)構(gòu)如圖4。其中：Nonce為隨機數(shù)；TX為Transaction交易名，HASH為每筆交易特有的哈希值，HASH12為交易1，2的哈希值；HASH3，HASH4為串聯(lián)兩個交易記錄之間的哈希值。數(shù)據(jù)層中的鏈式結(jié)構(gòu)從創(chuàng)世塊到新增區(qū)塊形成的一條最長主鏈，記錄鏈上的歷史數(shù)據(jù)，決定其可溯源的特性。

圖4 區(qū)塊結(jié)構(gòu)Fig.4 Block structure

2)合約層 封裝算法、腳本以及智能合約，是實現(xiàn)操作數(shù)據(jù)的關鍵。供應鏈的參與成員共同制定合約內(nèi)容，并使用腳本代碼嵌入系統(tǒng)，一旦滿足合約條件即自動執(zhí)行，外界無法參與其中，也可有效避免各成員出現(xiàn)拖欠付款的情況，實現(xiàn)合約執(zhí)行的智能化。共識算法是保證區(qū)塊鏈網(wǎng)絡不被惡意節(jié)點攻擊、篡改數(shù)據(jù)的核心，在合約層封裝執(zhí)行改進的DPBFT算法，可減少節(jié)點與節(jié)點之間的通信以及主節(jié)點出現(xiàn)問題時交易的延遲。數(shù)據(jù)層將數(shù)據(jù)記錄在區(qū)塊后，通過合約層DPBFT算法驗證，若各節(jié)點驗證正確并將消息返回到客戶端，表示新的交易被確認，則增加鏈的長度，不可對前面的數(shù)據(jù)進行修改，保證數(shù)據(jù)的完成性。

3)應用層 用戶與應用程序的交互層，區(qū)塊鏈網(wǎng)絡在合約層實現(xiàn)讀寫接口以供調(diào)用，生產(chǎn)商、供應商、分銷商、零售商等通過搭建的區(qū)塊鏈網(wǎng)絡進行存儲交易信息并記錄，作為消費者，通過掃描產(chǎn)品的二維碼，獲取產(chǎn)品的從生產(chǎn)商到零售商的完整流通信息；作為生產(chǎn)商、供應商等供應鏈上游成員，注冊身份信息申請成為區(qū)塊鏈網(wǎng)絡中的節(jié)點，與區(qū)塊鏈網(wǎng)絡保持同步。在生產(chǎn)、加工、包裝、配送、分銷、零售產(chǎn)品的同時，將相關流轉(zhuǎn)的數(shù)據(jù)添加進區(qū)塊中，寫入?yún)^(qū)塊鏈。由于區(qū)塊鏈本身的不可篡改性和加密技術，可保證產(chǎn)品流轉(zhuǎn)過程信息的可追溯性和真實性。

以食品溯源為例，將其供應鏈分為生產(chǎn)環(huán)節(jié)、加工環(huán)節(jié)、流通環(huán)節(jié)、銷售環(huán)節(jié)、市場監(jiān)管等步驟。

1)生產(chǎn)環(huán)節(jié) 從生產(chǎn)過程開始記錄產(chǎn)品的品種、數(shù)量、生長條件、發(fā)貨日期等，于特定時間將該批次的產(chǎn)品信息錄入本地生產(chǎn)數(shù)據(jù)庫同時生成加工批次碼，將信息上鏈。

2)加工環(huán)節(jié) 記錄產(chǎn)品收貨時間、產(chǎn)品種類名、加工時間、加工溫度、發(fā)貨數(shù)量、發(fā)貨時間等，根據(jù)產(chǎn)品的加工批次碼進行加工，加工結(jié)束后將批次碼、加工時間、發(fā)貨人、發(fā)貨時間寫入?yún)^(qū)塊鏈系統(tǒng)。

3)流通環(huán)節(jié) 記錄收貨數(shù)量、收貨人姓名、收貨日期并通過溫度傳感器記錄流通過程中的產(chǎn)品溫度，生成運輸批次碼。尤其在全球疫情期間，要加入進口冷凍食品核酸檢測信號，一旦發(fā)現(xiàn)冷凍食品出現(xiàn)問題及時迅速上報，將更新的運輸產(chǎn)品數(shù)量寫入?yún)^(qū)塊鏈系統(tǒng)。

4)銷售環(huán)節(jié) 食品通過物流運輸?shù)竭_經(jīng)銷商后，經(jīng)銷商記錄收貨時間、入庫時間、出庫時間、銷售地點，上傳到區(qū)塊鏈系統(tǒng)。通過網(wǎng)絡、店面等方式銷售到消費者手中，消費者掃描二維碼可獲得產(chǎn)品的所有流通信息，從生產(chǎn)環(huán)節(jié)的加工批次碼到銷售環(huán)節(jié)的運輸批次碼，可清晰準確了解產(chǎn)品來源。

5)市場監(jiān)管 食品監(jiān)管部門在檢查食品安全時掃描二維碼查看相關數(shù)據(jù)是否符合產(chǎn)品本身信息，完成對整個食品供應鏈全生命周期的監(jiān)控，實現(xiàn)對整個溯源流程把控。

3 實驗與結(jié)果分析

實驗測試設備為AMD Ryzen 2600X 處理器、16 GB 內(nèi)存的Windows 10 系統(tǒng)的PC 機，開發(fā)環(huán)境為JetBrains GoLand 2019.2.3 x64，通過GO程序語言實現(xiàn)DPBFT算法。通信開銷和交易延遲是體現(xiàn)算法效率、衡量共識算法的重要指標，通信開銷指網(wǎng)絡節(jié)點在共識過程產(chǎn)生的通信量，交易延遲指從客戶端發(fā)送交易請求到客戶端確認收到共識消息的過程中交易時長。為驗證DPBFT算法的有效性，文中選取DPBFT及PBFT兩種算法的通信開銷和交易延遲指標進行比較分析。

PBFT算法的通信時間復雜度為O(N)，假設整個網(wǎng)絡節(jié)點數(shù)為n，則完成一次一致性協(xié)議的通信次數(shù)為2n(n-1)。節(jié)點數(shù)較大時，通信量較大，造成共識效率低下。當主節(jié)點為惡意節(jié)點或未響應，會進行視圖切換協(xié)議，向各副本節(jié)點廣播視圖變更消息，其通信次數(shù)為n(n-1)。假設PBFT算法執(zhí)行視圖切換協(xié)議的概率為p，則發(fā)生視圖切換后的通信次數(shù)T 為

DPBFT 算法通過計分制降低主節(jié)點為惡意節(jié)點的概率，節(jié)點數(shù)增加時，減少惡意節(jié)點參與共識過程。將完成一次過程后的計分情況全網(wǎng)廣播，通信次數(shù)為(n-1)。假設DPBFT算法執(zhí)行視圖切換協(xié)議的概率為q，且q ＜p，則在DPBFT算法中發(fā)生視圖切換的通信次數(shù)L 為

DPBFT算法的通信復雜度也是O(N)，通過計分制使投票選出的主節(jié)點作惡或無響應的概率大大降低，即第二項系數(shù)q 小于p。發(fā)生視圖變更概率變小，在節(jié)點數(shù)增多的情況下，系數(shù)對通信復雜度的影響更大。兩種算法通信開銷比M=T/L，計算式如式(5)。

DPBFT算法面對主節(jié)點不同情況時有不同程度的扣分機制，在一輪共識過程結(jié)束選取新的主節(jié)點時提升主節(jié)點誠實的概率，觸發(fā)視圖切換協(xié)議的頻率降低。q 值越小，M 值越大，網(wǎng)絡中節(jié)點數(shù)不斷增長時，DPBFT 通信開銷相較PBFT 算法越來越小，當p =0.324，q=0.215時，兩種算法的通信開銷比M 如圖5。

分別以4，8，12，16個節(jié)點為例，為不失一般性，取50次實驗的平均值。兩種算法的通信開銷和交易延遲結(jié)果如圖6，7。

圖5 兩種算法的通信開銷比Fig.5 Communication cost ratio of the two algorithms

圖6 兩種算法的通信開銷Fig.6 Communication volume of the two algorithms

圖7 兩種算法的交易延遲Fig.7 Transaction delay of the two algorithms

由圖6可看出：節(jié)點為4個時，DPBFT算法與PBFT算法的通信開銷差距不大，DPBFT算法完成一次共識過程的通信開銷平均為41 次，PBFT 算法平均56 次；當節(jié)點增加到16 個時，DPBFT 算法通信開銷平均422次，PBFT算法通信開銷平均366次，通信開銷顯著降低。

由圖7可看出，PBFT算法的延遲較高，DPBFT在降低主節(jié)點為拜占庭節(jié)點的概率后，其交易延遲有所降低，節(jié)點為16個時，PBFT算法的平均交易延遲109 ms，DPBFT算法的平均交易延遲99 ms。

4 結(jié) 論

針對供應鏈溯源模型中PBFT算法存在通信開銷大、系統(tǒng)消耗高的問題，提出一種改進的PBFT算法—DPBFT算法。設置計分機制，根據(jù)計分情況選取主節(jié)點，降低主節(jié)點為拜占庭節(jié)點的概率，優(yōu)化共識過程；針對供應鏈溯源特點，利用區(qū)塊鏈技術設計三層供應鏈溯源模型架構(gòu)，將DPBFT算法融合于模型合約層，解決傳統(tǒng)溯源系統(tǒng)存在的數(shù)據(jù)不安全、易被篡改等弊端。實驗結(jié)果表明：節(jié)點數(shù)較少時，DPBFT與PBFT算法的通信開銷相似，但DPBFT算法的交易延遲有所降低；節(jié)點數(shù)增多時，DPBFT算法可減少通信開銷與在網(wǎng)絡交易過程中的交易延遲，提升共識效率，加快系統(tǒng)運轉(zhuǎn)速度。