Trias中基於流式圖的DAG結構

買賣虛擬貨幣
在此前的文章:“Trias網路如何用DAG提升吞吐量”中,我們簡要介紹了Trias中DAG的基本資料結構(StreamNet)和交易的實現過程。與鏈式結構相比,DAG結構的交易速率得到了顯著的提升,但隨之而來的問題是,如何選擇未被確認過的新交易(tip)呢?如果採用基本的隨機遊走演算法,會導致新的交易批准老的交易而不被懲罰;而如果採用超權重演算法的話,比如給不同的交易設定一個權值,又會造成新交易始終優先批准高權值交易,很多權值較低的交易永遠也得不到確認。一、DAG中的交易共識目前交易的確認在StreamNet中主要有三種方式:

· 第一種方式:所有tip覆蓋到的公共節點是被完全確認的。舉一個例子,下圖中,tip1引用或間接引用的交易為藍線條和黃線條覆蓋,而tip2引用或間接引用的交易為黃線條覆蓋。那麼被tip1和tip2共同覆蓋到的就是標綠的交易,也就是被完全確認的交易。

· 第二種方式:系統每隔1分鐘會傳送一個Coordinator的tip附著在StreamNet上,這個tip被稱之為里程碑(milestone),所有被Coordinator引用的交易都是被確認的。

· 第三種方式: 蒙特卡洛隨機遊走(MCMC)方式,即使用基本的隨機tip選擇演算法來選擇一個tip,如果一個交易被這個tip引用,那麼它的可信度便增加1,經過N次選擇後如果有M次被引用到了,那麼其可信度便是M/N。

二、StreamNet主要演算法

· 基於中心度的去COO起點選擇演算法

現階段,在DAG中選擇tip的時候,不會從創世交易開始,而是會簡單的以某個Coordinator作為起點出發來選擇tip ,這就會造成一箇中心化的問題。所以在設計StreamNet的時候,首先要考慮的問題就是如何弱化COO而實現真正的分散式DAG,所以我們需要找到一個共識的交易作為起點,而不是由中心化節點強制規定的Coordinator作為起點。

在此我們選擇Katz中心度作為選擇起點的標準。因為StreamNet中的交易是不斷進入到網路中的,如果每一筆新交易的選擇都重新計算一次Katz中心度的話,那計算量會非常大,因此我們採用增量演算法來計算:

其中,A表示交易之間的連結關係,k次方表示k階連結矩陣,α表示重要性權值向量,I是一個全部為1的矩陣。

值得注意的是,在計算的結果中,我們並不需要尋找到Katz中心度最大的交易,因為這永遠是創世交易(Genesis),所以我們應該在Katz中心度和離當下時間最近的交易中找到這個初始節點。

· 考慮邊資訊的交易權值演算法

雙花問題的一個典型場景便是側鏈攻擊,攻擊者往往會在短時間內發出多個交易快速增長側鏈,並在它們相互之間進行批准,一系列的欺騙性側鏈可能就會導致雙花成功。

為阻止這種情況發生,我們在兩個approve交易之間會做加權的set join,而這個權值的判定由邊的資訊所確定,而邊的資訊則由時間來確認。透過使用邊的資訊來對交易進行重調,從而將攻擊效應進行衰減,維護了網路的平穩執行。

· 基於流式圖計算的權值更新演算法

靜態的圖演算法在更新節點權值的時候,需要從初始節點開始從頭計算每個節點的權值,這個計算的複雜度是非常高的。而如果我們把靜態計算的資訊快取起來,只在新的tip加入的時候更新已經快取的資訊,那麼新tip加入時計算的複雜度將會大大降低。 

三、結語

現在DAG的方案已經陸續從研討走向落地,業界有很多新穎的DAG方案正在被提出,從技術角度來說,DAG或許會對現有的區塊鏈專案帶來一次衝擊,一定程度上改變現有的區塊鏈設計思維。

DAG具有速度快,吞吐量高的優勢,隨著越來越多專案參與到DAG的生態發展中來,長期看來,DAG是非常有前景的機制。Trias作為首先採用DAG技術的公鏈,創造性的設計了基於DAG的吞吐快取層,從理論和現實率先做出了突破,在公鏈之爭中佔得先機。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;