基于IOTA區塊鏈的一種新型Tips選擇算法的研究

張秀賢,馬莫凡,楊佳源,王君羽,江軍熠

(南京曉莊學院 電子工程學院,江蘇 南京 211171)

隨著物聯網的發展,越來越多的設備連接到互聯網,例如智能汽車、智能家居設備、安防監控設備、智慧醫療設備、智能電網監控設備、智能交通設備等[1]。這些設備會產生大量的數據,如果能夠有效地利用這些數據,將會產生巨大的利用價值。而區塊鏈技術開放、透明、可追溯、防篡改,無論是人還是機器,都可以通過區塊鏈系統實現可信的價值交換和數據共享[2]。目前,區塊鏈已經被大量應用在金融、健康醫療、供應鏈、資產管理等諸多領域。

然而,傳統的區塊鏈共識時間長,吞吐量低,無法滿足大規模物聯網的需求,而專為物聯網開發的IOTA區塊鏈,打破了傳統區塊鏈的鏈式結構,采用有向無環圖(DAG)的存儲方式,允許所有的節點隨時,隨地,并發地向分布式賬本Tangle中寫入數據,且寫入賬本中的數據不再由區塊鏈中的節點驗證,而是由后續的交易驗證,使得IOTA打破了區塊鏈的“不可能三角”,同時達到了安全、去中心化和可擴展三方最優,它具有0交易費用、資源占用低、共識時間短,網絡吞吐量大,抗量子級加密等優點。然而,由于IOTA的交易是由后續交易驗證前面的交易,因此,交易的選擇至關重要,傳統的IOTA交易選擇只與交易的權重即PoW的難度值有關會產生較多的孤兒,且容易受到寄生鏈攻擊。另外,不同的用戶時間敏感度不同,所能容忍的共識時間也不同。

因此,為了解決這個問題,我們綜合考慮了用戶時間敏感度,以及孤兒的數量,提出了一個新的Tips選擇共識算法。1)按用戶的時間敏感度將用戶劃分優先級,優先處理時間敏感度要求高的用戶;2)為了降低孤兒的數量,優先選擇先上傳到區塊鏈上的交易;3)為了解決寄生鏈攻擊問題,將區塊鏈上的交易按入度值排序,優先選擇入度值大的交易。

1 Related Work

區塊鏈技術作為一種去中心化,公開透明的分布式賬本技術,將為6G提供強有力的安全保障。但是,由于傳統區塊鏈吞吐量低,共識時間長,可擴展性差等原因,目前,對于小額交易比較頻繁的大規模物聯網領域,共識時間短,零交易費,即插即用,吞吐量高以及抗量子級的加密技術使得IOTA作為區塊鏈的一種替代方案受到越來越多研究人員的關注。論文[2]分析Tangle的共識算法比PoW和PoS更適合于物聯網系統。論文[3]研究了IOTA的核心Tips選擇方法針對寄生鏈攻擊的漏洞,并提出了新的算法。論文[4]提出了一個基于IOTA區塊鏈的物聯網頻譜共享框架。論文[5]提出了一種基于IOTA Tangle網絡的物聯網架構,解決了物聯網存儲在云中的集中化問題。論文[6]提出并分析了一種維持IOTA-tangle穩定性的策略。論文[7-9]對IOTA-tangle的性能進行了仿真。論文[10]為了提高系統的穩定性和安全性,提出了一種新的選擇父節點的算法。論文[11]對Tangle的Tips選擇機制進行了修改。保證了所有的事務在有限的時間內被驗證,并且保留了蒙特卡羅選擇算法的基本特征。論文[12]對加權隨機漫步和隨機漫步兩種Tips選擇算法的差別進行了分析。論文[13]以離散時間形式分析了平均未確認交易數量和平均確認交易時間。論文[14]分析了給定Tips將被遺留下來的概率和將成為永久Tips的概率。論文[15]研究了隨機漫步Tips選擇算法中,寄生鏈在Tangle中被吸收的概率。然而這些研究都沒有考慮用戶的時間敏感度,以及孤兒的數量,因此,本文提出了一種新的共識算法,滿足不同時間敏感度的用戶需求。

3 IOTA簡介

圖1 Tangle中交易共識過程示意圖

IOTA的交易結構采用Tangle的形式,Tangle是一種特殊的有向無環圖(DAG),如圖1所示。DAG中的頂點即為存儲的交易,有向邊為驗證關系,后面的交易驗證前面的交易,其中,被驗證過的DAG的頂點稱為Sites,沒有被驗證過的交易稱為Tips。即交易為DAG的頂點,其中包括Sites和Tips。當節點有交易需要寫到Tangle時,由節點按照隨機漫步或加權隨機漫步的算法選擇Tangle中的兩個Tips,并對Tips進行檢測,然后再做一定難度的PoW,最后將交易及所選的Tips在區塊鏈中廣播同步到其他節點,并更新本地Tangle。新存儲到Tangle的交易作為新的Tips被后面的交易驗證,當某個交易被所有的Tips可見時,稱此交易完成共識,此時交易不可更改。如圖1所示,圖中的交易0—4都是共識完成的交易,因為,這幾個交易都可以被Tip 9、Tip 10看到,但是交易5—8是沒有完成共識的交易。

4 系統模型

圖2 系統模型

如圖2所示,系統主要分為兩層,通信網絡和由通信網絡映射的區塊鏈網絡,通信網絡即為大規分布式物聯網,由智能終端、邊緣網關、基站以及邊緣服務器等組成;而區塊鏈網主要用來保證數據的安全可信共享,采用IOTA共識算法實現。IOTA共識算法分為四部分:1)將交易寫入本地Tangle;2)選擇Tips并驗證所選的Tips;3)做PoW計算;4)將交易、交易所選的Tips以及PoW的計算結果廣播到網絡的各個節點;5)等待被驗證。而不同的Tips選擇算法,對共識時間,系統吞吐量,孤兒的數量等的影響較大,而目前的隨機選擇或加權隨機選擇算法,很難滿足不同的應用,因此,本文對Tips的選擇算法進行了改進。

5 Tips選擇算法

網絡中的用戶有些是時間敏感的,比如控制信息,報警信息等,有些則對時間要求不是很高的,比如視頻流量,交易信息等,因此,本文將不同的時間敏感用戶分為不同的優先級,時間敏感的用戶優先處理。另外,為了降低孤兒的數量,優先選擇先上傳到區塊鏈上的數據。為了解決寄生鏈攻擊問題,將區塊鏈上的交易按入度值排序,優先選擇入度值大的交易。具體算法如下:

輸入:Tipsall={Tip1,Tip2,,Tip3,…,Tipn};

輸出:Tipssel;

1)檢測Tips中是否含有寄生鏈,并將寄生鏈對應的Tips刪除, 得到不包含寄生鏈的Tips集合:Tipsnopara;

2) 檢查Tips中是否含有懶惰節點,將懶惰節點去除,得到Tips集合:Tipsnopl;

3) 根據共識時間敏感度將Tips分為兩個優先級Htips,Ltips;

4) 分別統計Htips和Ltips中每個Tips直接或間接驗證的所有未達成共識的Site的時間戳,計算數據寫到Tangle的平均時間t,按t由大到小的順序排序;

5) if length(Htips)>2

for i=1∶2

Tips_sel (i)=Htips(i);

end

else if 0

for i =1∶length(Htips)

Tips_sel (i)=Htips(i);

endfor

for j = length(Htips):2

Tips_sel (j)=Ltips(j)-length(Htips);

endfor

else

for i = 1∶2

Stips(i)=Ltips(i);

endfor

endif

6) return Tips_sel

首先,將寄生鏈對應的Tips以及懶惰節點刪除,按時間敏感度將Tips分為高優先級Htips和低優先級Ltips;分別統計Htips和Ltips中每個Tips直接或間接驗證的所有未達成共識的Site的時間戳,計算數據寫到Tangle的平均時間t,按t由大到小的順序排序;若判斷高優先級Htips中元素個數是否大于Tips的選擇個數(tips的選擇個數一般為2),若大于2,則選取Htips中前兩個Tips來驗證,若小于2,則選取Htips中元素,剩下的從Ltips中選取。

圖3 懶惰節點示意圖

5.1 懶惰節點檢測算法

如圖3所示,以Tip 9為例,Tip 9驗證了Site 2和Site 6。1)驗證Site 2的還有Site 5和Site 6,倘若Site 5 和Site 6 的時間戳與Tip 9 的時間戳的差值超過2h,則認為Tip 9 為懶惰節點。2)驗證Site 6的Tips有Tip 10和Tip 9,倘若Tip 10和Tip 9的時間戳差值小于2h,則認為兩個節點都不是懶惰節點。只要被判斷一次為懶惰節點的Tips則從待選Tips中刪除。 具體算法如下:其中Tipshash為所有Tips 哈希值的集合,hashself的Tips本身的哈希值,hashfa1,hashfa2為Tips對應的兩個父節點的哈希值,T為交易的時間戳, Tipsnopl為沒有懶惰節點的Tips集合。

輸入:Tipshash={hash1,hash2,,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T};

輸出:Tipsnopl;

1) 計算num=Tipshash;

2) for i=1∶num

查找Tipshashi中每個Tips的父節點hashfa1,hashfa2;

for j=1∶2

hashchildj=checkchild(hashfaj);

childnumj=lenth(hashchildj);

將hashchildj按時間從大到小的順序排列hashchildjT=sort(hashchildj);

for k=2∶childnumj

tdi=hashchildjTk-hashchildjT1;

if tdi<2h

Tipsnopl= Tipsnopl∪ Tipi;

endif

endfor

endfor

endfor

3) return Tipsnopl;

輸入:Tipshash={hash1,hash2,,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T},hashfa

輸出:hashchild

1) for i=1∶num

for j=1∶2

if hashfa==hashi.hashfaj

hashchild= hashchild∪ hash1;

endif

endfor

endfor

2) return hashchild;

5.2 寄生鏈檢測算法

在t-h時刻,Tangle中的Tips總個數為L0=2λh[4],其中,λ為網絡中總的事件到達率,在t時刻Tangle中Tips的個數也為L0,而在h時間間隔內,事件的到達個數為λh,因此,所有被選中的Tips個數為λh才可以使得在t時刻Tips的總個數仍為L0;另外對于λh個新到事件,每個事件會選擇2個Tips作為父節點,相當于在λh個Tips中選2λh次,則每個Tips被選中的平均次數為2。因此,每個Site的出度和入度都為2。當前Tips的前N個Site的出度值為:深度為N的滿2叉樹的節點個數2N-1, 出度總和為2*(2N-1),當出度值大于2α*(2N-1)時,判定Tips不是寄生鏈的Tips,其中α為系數。

假設每個交易最少選2個Tips進行驗證,則前N層Site的出度計算算法如下:

輸入:Tipshash={hash1,hash2,hash3,…,hashnum} ,

hash1={hashself,hashfa1,hashfa2,T},...,hashnum={hashself,hashfa1,hashfa2,T};

輸出:Tipsnopara

1)for i=1∶num

for j=1∶N

for k=1∶2j

if hashik.hashfa1!=0

outdegreei = outdegreei+1;

if hashik.hashfa2!=0

outdegreei = outdegreei+1;

endif

endif

hashik=hashik.hashfa1∪ hashik.hashfa2

endfor

if outdegree<2α*(2N-1),

Tipsall=Tipsall/Tipsi;

endif

endfor

endfor

2)Tipsnopara=Tipsall;

3)return Tipsnopara;

6 仿真評估與分析

本文使用Matlab對傳統IOTA Tips選擇算法和文章提出的Tips選擇算法進行了仿真分析,如圖4所示,本文對網絡中不同Tips數量時,孤兒的數量進行了仿真,由圖可以看出,傳統的隨機選擇算法,當網絡中Tips數量增加時,被遺留下的孤兒數量增加,而對于本文提出的算法,由于在Tips選擇時,增加了寫入網絡中的時間因素,寫入網絡時間越早,被選中的概率越大,因此,本文提出的Tips選擇算法,被遺留下的孤兒數量顯著降低,有效的解決了孤兒的遺留問題。

同時,假設網絡中時間敏感數據占10%的情況下,對時間敏感問題是否及時解決進行了仿真,如圖5所示,時間敏感的Tips在本文提出的Tips共識算法中,被選中所用的周期數明顯降低,主要是因為,在我們提出的算法中,時間敏感的數據有優先選擇權,保證了時間敏感數據可以快速達成共識。

圖4 孤兒數量仿真

圖5 時間敏感Tips被選中所需的周期數

7 結 論

本文對在現有的IOTA區塊鏈中,Tips選擇選擇算法進行了改進,本文綜合考慮孤兒的數量,用戶的時間敏感度,設計了新的Tips選擇算法。并針對新的Tips選擇算法設計了懶惰節點識別和防止寄生鏈攻擊算法。仿真和分析結果表明,本文提出的算法明顯降低了孤兒的數量,更好的滿足不同時間敏感度的用戶需求。