Conflux共識演算法解讀

買賣虛擬貨幣
序列交易引發的吞吐量瓶頸上次我們講到GHOST演算法[2],它在中本聰共識的基礎上提出的確定主鏈的演算法,在保障了在高吞吐量的同時還保障了安全性(即不容易分叉,依然保證51%攻擊)。但是GHOST演算法的吞吐量是否還有進一步的提升空間呢?答案是肯定的!Conflux團隊注意到不論是中本聰共識還是GHOST共識,他們都是隻維護一條主鏈,非主鏈的區塊則被拋棄了,因此也就導致了這些被丟棄的塊不能為整個區塊鏈系統提供安全性,並且也降低了吞吐量(因為這些塊被拋棄了,實際上也就是說系統的頻寬被浪費了,因此他們就不能為系統貢獻吞吐量)。並且注意到,比特幣的吞吐量很低的原因是它是序列執行交易的,也就是說交易必須先排好序才能夠執行,這產生了很多不必要的依賴,也是導致分叉的根源。於是Conflux就採用延遲排序交易的方式,先樂觀地並行執行交易(不論是否有依賴或者衝突)和出塊(不論是否會產生分叉),然後經過一段時間再全域性地對所有的交易排序,並刪除哪些衝突的交易。順著這個思路,我們發現最核心的問題就是如何解決並行出塊的時候,還能對區塊的全域性序達成一致,從而保證賬本的不可篡改。那麼Conflux是如何做到的呢?父邊/引用邊與DAG排序
為了並行出塊,就需要把所有的塊納入到整個區塊鏈之中。Conflux採用採用了兩種關係來定義區塊之間的關係:父邊(parent edge)和引用邊(reference edge),參考下圖:•父邊:新出的塊指向祖先塊,類似於比特幣那樣

•引用邊:節點新出的塊發現整個區塊鏈中目前沒有指向他的塊,並建立一條指向他的邊

全域性區塊排序就順利成章了:

1.先按照GHOST規則[3]排序只包含父邊的塊,形成一個樞軸鏈(pivot chain),它類似於比特幣的主鏈,不一樣之處在於它還會引用比特幣系統中丟棄的塊
2.根據樞軸鏈對區塊分成各個紀元(epoch),然後對每個epoch裡面的區塊拓撲排序。確定epoch包含的區塊的劃分原則是需要同時滿足以下兩個條件:

•該區塊可以透過樞軸鏈的父邊或者引用邊遍歷到
•該區塊沒有被之前的epoch包含

3.根據happens-before原則(就是誰在誰前面)對不同epoch之間的塊進行排序

上述內容,可能涉及到一些專業術語 不好理解,舉個排序例子(參考下圖):

先根據最終子樹GHOST原則確定樞軸鏈為G->A->C->E->H->NewBlock,然後由於C引用了B,所以拍B->C;那麼D和F如何排序呢?D的父親是A,F的父親是B,A的epoch大於B,所以D在F前面。按照這樣的順序排完就是:

G->A->B->C->D->F->E->G->J->I->H->K->New Block

當然還有一些細節,比如兩個區塊在同一個epoch內,並且父邊也在一個epoch裡,那麼就根據區塊的hash值id的絕對大小排序,比如假設區塊DD的id是011,FF的是111,011<111,所以DD在FF前面

具體的演算法如下,圖中相關名詞對應的解釋參考其論文《[4]Scaling nakamoto consensus to thousands of transactions per second》[5]:

交易的排序

區塊排好序之後,在每個區塊內,按照交易的出現順序排序,如果有衝突交易,那麼只保留最先出現的那個,丟棄所有衝突的交易。

看起來很厲害是吧,那麼實際實驗結果如何呢?

效能

吞吐量

限制頻寬20M,在4M/5s的出塊速度下,每秒能處理比特幣網路中3200筆交易!

這個還是非常恐怖的數字,要知道以太坊現在每秒才30~40Tps,Visa才6000多Tps。

確認時間

因為交易的序受樞軸鏈影響很大,而樞軸鏈的序是按照GHOST規則來定的,可以證明,Conflux的安全性與GHOST一致。那麼按照攻擊者有20%全網算力,並且只有0.01%的概率(由GHOST安全性計算規則算出)篡改交易的假設,得到的資料是:4M的區塊,5秒出一個塊的話,在保證安全性的同時確認時間也只有10分鐘。

可拓展性

頻寬

頻寬20M時3200Tps,近11分鐘確認時間;

頻寬提升到40M,交易處理速度幾乎線性上升到6400Tps,確認時間也只有5.68分鐘。

節點數目

如下圖,可以看出,隨著節點資料增多,確認延遲幾乎只是隨之線性增長(不像BFT演算法那樣指數增長,受節點資料拓展影響很大)。

因此可見,Conflux提出的共識演算法已經不在是PoW公鏈效能上的共識瓶頸!

未來

如何處理頻寬限制,高吞吐量帶來的儲存問題(20M頻寬就消耗2.88G/h)和交易驗證速度等問題,都是繼續需要解決的問題。

如何應對存活性攻擊等安全性問題,也就是說惡意網路阻塞,也是很值得研究的問題,可參考詳解自適應權重 “GHAST”[6]

References

[1] Johnthan: https://learnblockchain.cn/people/720
[2] GHOST演算法: https://learnblockchain.cn/article/1064
[3] GHOST規則: https://zhuanlan.zhihu.com/p/144428841
[4] 論文《: https://arxiv.org/abs/1805.03870
[5] Scaling nakamoto consensus to thousands of transactions per second》: https://arxiv.org/abs/1805.03870
[6] 詳解自適應權重 “GHAST”: https://zhuanlan.zhihu.com/p/87020193

免責聲明:

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

推荐阅读

;