區塊鏈技術資源分享
追尋中本聰先生的腳步
?

SCAR靈活共識算法_Qtum量子鏈_Scalable Consensus Algorithm_一種可伸縮共識算法

日前,Qtum量子鏈針對區塊鏈可擴展性問題以及交易處理效率低下的問題,提出了名為“SCAR”的區塊鏈擴容共識算法,能夠進一步降低區塊鏈底層網絡的要求,該算法已公布便引起海外近萬名區塊鏈開發者的關注以及轉發。

據悉,SCAR可以找到用戶體驗與資源存儲之間的平衡點,使之與其他共識算法相比擁有更高的效率及靈活性。

SCAR靈活共識算法_Scalable Consensus Algorithm_一種可伸縮共識算法_Qtum量子鏈

共識算法介紹

諸如PoW(Proof of Work)、PoS(Proof of Stake)等傳統的區塊鏈公式算法,為了減少分叉保證網絡的穩定性,通常區塊的間隔在10秒以上。

例如Ethereum的區塊間隔時間是15秒,Qtum是144秒,Bitcoin是10分鐘。過高的區塊間隔時間,導致了用戶等待交易確認的時間較長,不利于實時支付等應用。

而一些聯盟鏈的共識算法,例如DPoS 通過投票選出超級節點來執行共識算法,可以將區塊間隔時間降到甚至1秒以內。但這樣帶來的問題就是block的數量過多,對網絡帶寬和數據存儲都帶來了很大的壓力。運行一個全節點,甚至僅下載block header的輕節點,都對節點設備的性能有較高的要求。

對于區塊鏈的大多數商業應用而言,如征信上鏈、商品溯源等,對于區塊鏈的寫操作通常是周期性的。即每天的部分時間交易量較大,其余時間交易量小。對于這樣的場景,如果始終維持高速的區塊產出,對于網絡和存儲資源都是較大的浪費,而僅需要保證在網絡高峰時段系統有較高的性能即可。

因此,我們提出了 SCAR(Scalable Consensus Algorithm)可伸縮共識算法。

SCAR的思想是根據區塊鏈網絡的負載,動態地調節參數,在高性能和低負載之間找到平衡,從而實現性能可伸縮。

SCAR 共識算法描述

以下將介紹SCAR算法的一種實現方式。

這種實現方式在聯盟鏈的基礎上,通過交易量來動態地更新區塊間隔,從而實現了區塊鏈性能的可升縮。需要注意的是,SCAR算法的核心思想是根據負載動態地調整區塊鏈的性能,所以實現方式并不局限于本文所提出的這種,更多的實現有待進一步地探索。

SCAR共識算法由三個步驟組成:

SCAR共識算法投票

SCAR共識算法投票

SCAR共識算法根據網絡負載計算block間隔

SCAR共識算法根據網絡負載計算block間隔

SCAR共識算法超級節點按照優先級產出block

SCAR共識算法超級節點按照優先級產出block

以上可得SCAR共識算法的優點在于:

  1. 由超級節點執行共識,block間隔可以極大程度縮短,交易確認快。
  2. block間隔根據網絡負載動態調整,空閑時候間隔變長,降低帶寬和硬盤壓力。
  3. 當低于半數的超級節點出現故障的時候,新的block仍然能夠產出,系統魯棒性強。

節點投票

投票選出超級節點可以有多種設計。比如EOS是所有用戶都能參與投票,Aura是當前的超級節點可以投票選出下一輪的超級節點。這里我們提出一種基于Qtum DGP協議的投票策略。

區塊鏈初始化時在鏈上部署 DGP 的智能合約,在合約內初始化了管理席位 admin 和治理席位 gov,均以地址的形式存儲。DGP 協議支持在鏈上通過管理席位 admin 和治理席位 gov的投票,來決定超級節點是否改變。

首先我們對管理席位和治理席位的權限和修改策略做個介紹。管理席位 admin 在決定權限時具有最多的權力,它可以參與投票增加和刪除 admin,同時可以投票任命 gov;而 gov只能參與到超級節點的修改投票中。即所有提案只有具備管理席位的 admin地址才能設置,具有治理席位的 gov地址僅可參與超級節點投票。

投票的具體流程如下:

  1. 收集新的超級節點的提案,向社區公布并收集反饋;
  2. 根據社區反饋調整超級節點列表,并通過智能合約存儲到區塊鏈中,作為新的提案;
  3. 通過調用 DGP 合約的相應方法,將該提案設置為待投票的提案,此時即開啟投票;
  4. 擁有管理admin和治理gov權限的地址通過向投票合約發送一筆交易來對提案進行投票;
  5. 若提案未獲得足夠投票則被否決,不執行修改;
  6. 若提案通過,新超級節點列表的存儲地址會記錄進DGP合約,并在一定數量的區塊后生效,以防止出現不必要的分叉。
  7. 節點可以通過 DGP 合約來獲取最新的超級節點列表。

綜上所述,我們可以在鏈上設置 DGP 合約,通過 DGP 投票的方式來決定超級節點,并動態地存儲和更新授權礦工列表。

block 間隔

block的間隔需要根據網絡的負載情況動態調整,網絡空閑時候間隔變長,網絡繁忙時候間隔變短,從而實現動態可伸縮。這里我們提出一種block間隔的計算方法,根據近期的交易數量來進行計算,交易多則間隔變短,交易少則間隔變長。

block間隔的計算公式如下:

block間隔的計算公式

其中,min_interval 為最小的block時間間隔,max_interval 為最大的block時間間隔。transaction_num 為最近 m 個區塊內的平均交易數,這里 m 可以為大于等于1的整數。 m、min_interval 以及 max_interval 通過共識算法預先設定或者智能合約設置。

這樣設計公式的意義在于:

  1. 當交易量 transaction_num 為0時,block間隔將調整為 max_interval,此時將用系統設置的最長間隔時間來盡量在一個區塊內打包更多交易,避免了存儲空間的浪費;
  2. 當鏈上交易量 transaction_num 趨向于無窮大時,block間隔將無限趨近于 min_interval,此時將用系統設置的最短間隔時間來盡可能緩解區塊鏈網絡的交易擁塞,使得交易更快地被打包進區塊;
  3. max_interval 和 min_interval 可以根據實際情況進行設置(例如用戶容忍的交易延遲、超級節點的網絡環境和存儲性能等)。

采用這種根據網絡狀態動態調節區塊出塊時間的共識算法 SCAR,可以有效的避免在交易量小時浪費存儲空間,也可以在交易量大時增大區塊產生速率,及時將交易打包進區塊鏈上,保證交易更快地被確認。鏈上參數的動態調整也使得區塊鏈系統變得更加靈活,提高治理效率,降低治理難度和代價。

block 產出

當超級節點和block間隔都確定之后,節點就可以在間隔時間之后輪流產出新的block。

在某一區塊鏈高度上,若超級節點的數量為 n 個,則 SCAR 會為每個超級節點分配不同的出塊時間 block_time如下:

scra區塊間隔時間

其中,parent_block_time 為上一個block的出塊時間,block_interval 為動態計算出的區塊間隔。timeout 為超時時間,用來防止某些超級節點出現故障長時間無法出塊,miner_index 為索引值,在同一區塊高度下,不同的授權節點miner_index 不同。下面將對具體的參數設置原因和用途做出解釋。

如下圖所示,假定有5個被授權的超級節點 A、B、C、D、E,他們的公鑰被存儲在有序列表中,即上文提及的由 DGP 投票選出并可動態維護的超級節點列表(也即礦工列表)。假定在區塊鏈高度h1時,有序礦工列表是 [pubkey_A, pubkey_B, pubkey_C, pubkey_D, pubkey_E] ,這五個超級節點會輪流創建新的區塊。
SCRA區塊超級節點

當創建新區塊時,礦工會通過加密算法簽名這個區塊,然后將簽名結果附加到區塊中。通過這種方式,其他節點可以通過解密從區塊中恢復出礦工的公鑰來,從而通過和超級節點列表進行比對來驗證該礦工是否有權創建區塊。當一條鏈被大多數礦工簽名之后,這條鏈可以被視作為一條永久的鏈。例如在上圖中,從創世區塊到h3高度的鏈是一條永久的鏈,因為它已經被它接下來的幾位礦工D、E和A簽名了。如果任何礦工想要在高度h3下面制造分叉,這一分叉則無法被絕大多數礦工所認同。

共識算法可以有效地避免分叉的發生,但至少需要 n/2+1 位超級節點保持公式算法的正常運行(n 是超級節點數量,n/2 是整數除法)。共識算法對允許創建下一個區塊的礦工做出了以下定義:

一個礦工在以下情況可以創建新的區塊:

  1. 它當前是被授權的;
  2. 最近的n/2個塊不是由它創建的。

由上述定義可得到真正被允許創建下一區塊的超級節點的方式:從當前礦工列表中去掉為最近 n/2 個塊簽名的節點即可。例如,在區塊高度 h2 上,下一區塊的礦工列表如圖計算得到。

image

由上圖過程選出了 B、C、D 三個可創建下一區塊的節點后,我們只需要將超級節點列表設置為有序列表,指定它們的優先級先后,就可以避免它們為產出下一區塊而競爭。公式中的 miner_index 即為排序后的礦工列表的優先級索引,排序更前的超級節點將被分配更早的 block_time,每個超級節點使用被分配的 block_time 創建新的區塊,并在 block_time 到來前保持等待狀態。

但超級節點模式的聯盟鏈也面臨著一個問題:部分節點的故障會導致網絡效率驟降甚至癱瘓。為了避免部分節點的故障導致系統停止運行,共識加入以下策略來確保正常出塊。

我們在系統參數中設置了 timeout ,若一個超級節點由于故障未能成功廣播新的區塊,則下一個超級節點會在 timeout 時間之后取代它并正常產出區塊。如下圖所示,在上述5個超級節點的情況下,礦工 B 在產出高度為 h2+1 的區塊時發生故障。隨后,B 在超級節點列表中的下一位C ,將會在其 parent_block_time 的 block_interval+timeout 時間之后,廣播其創建的新區塊。

scra超級節點模式的聯盟鏈


SCAR在保證區塊鏈性能的同時,盡可能節省了帶寬和硬盤的消耗,并支持動態調整鏈上參數,相比其他共識算法更加的高效和靈活,在大規模的商業應用中會有更大的優勢。

分享到:更多 ()
0
區塊鏈神吐槽
pi幣注冊流程教程圖解中文版

來評論吐槽 搶沙發

評論前必須登錄!

 

區塊鏈資源分享聯系我

區塊鏈資源分享聯系我首頁更多新聞
做滴滴代驾还是开滴滴那个赚钱