區(qū)塊鏈相關的一些共識算法介紹

諸如PoW（Proof of Work）、PoS（Proof of Stake）等傳統(tǒng)的區(qū)塊鏈公式算法，為了減少分叉保證網(wǎng)絡的穩(wěn)定性，通常區(qū)塊的間隔在10秒以上。例如Ethereum的區(qū)塊間隔時間是15秒，Qtum是144秒，Bitcoin是10分鐘。過高的區(qū)塊間隔時間，導致了用戶等待交易確認的時間較長，不利于實時支付等應用。

而一些聯(lián)盟鏈的共識算法，例如EOS的DPoS ［1］（Delegated Proof of Stake）、Parity的Aura ［2］（Authority Round）等，通過投票選出超級節(jié)點來執(zhí)行共識算法，可以將區(qū)塊間隔時間降到甚至1秒以內(nèi)。但這樣帶來的問題就是block的數(shù)量過多，對網(wǎng)絡帶寬和數(shù)據(jù)存儲都帶來了很大的壓力。運行一個全節(jié)點，甚至僅下載block header的輕節(jié)點，都對節(jié)點設備的性能有較高的要求。

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

因此，我們提出了 SCAR（Scalable Consensus Algorithm）可伸縮共識算法。SCAR的思想是根據(jù)區(qū)塊鏈網(wǎng)絡的負載，動態(tài)地調(diào)節(jié)參數(shù)，在高性能和低負載之間找到平衡，從而實現(xiàn)性能可伸縮。

相關共識算法介紹

PoW，Bitcoin為代表。節(jié)點提供算力，通過大量的計算，產(chǎn)生新的block。算力越高，產(chǎn)生block的速度越快。計算難度每2016個block調(diào)整一次，保證在全網(wǎng)算力變化的情況下，block時間間隔保持在10分鐘左右。由于block間隔時間長，且每個block的大小限制在 1 MB，所以當交易量大的時候，網(wǎng)絡會發(fā)生嚴重擁堵。

PoS，Qtum為代表。節(jié)點提供token，通過少量計算，產(chǎn)生新的block。token數(shù)額越大，產(chǎn)生block的速度越快。計算難度也會定期調(diào)整，保證block時間間隔在144秒左右。PoS相對PoW而言，降低了對算力的要求，節(jié)省了能源。但是由于block間隔和block大小限制仍然是固定的，網(wǎng)絡的負載固定，無法避免交易量大時候的擁堵。雖然Qtum目前可以使用DGP ［3］（Decentralized Governance Protocol）協(xié)議手動地去調(diào)整block大小限制，但是這種方式略微繁瑣。

PoW和PoS中，全網(wǎng)的所有節(jié)點都會參與到共識的競爭中來，所以區(qū)塊間隔不能設置得過小。如果過小，則很容易產(chǎn)生分叉。即，如果計算難度設置得過低，則很容易出現(xiàn)多個節(jié)點在同一時刻產(chǎn)出新的block的情況。

DPoS、Tendermint等聯(lián)盟鏈共識算法，則通過投票得到的超級節(jié)點來執(zhí)行共識。由于參與共識的節(jié)點數(shù)較少，則區(qū)塊間隔可以設置得很小。比如EOS的block間隔就設置成了0.5s。過短的區(qū)塊間隔對帶寬和硬盤都是很大的壓力，在交易量少的時候也是一種資源浪費。EOS從今年6月9日上線以來，block數(shù)量至今已達1200萬，而9年前開始的Bitcoin至今也才50萬個block。

SCAR 共識算法描述

以下將介紹SCAR算法的一種實現(xiàn)方式。這種實現(xiàn)方式在聯(lián)盟鏈的基礎上，通過交易量來動態(tài)地更新區(qū)塊間隔，從而實現(xiàn)了區(qū)塊鏈性能的可升縮。需要注意的是，SCAR算法的核心思想是根據(jù)負載動態(tài)地調(diào)整區(qū)塊鏈的性能，所以實現(xiàn)方式并不局限于本文所提出的這種，更多的實現(xiàn)有待進一步地探索。

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

1. 統(tǒng)計投票得到所有超級節(jié)點。

2. 根據(jù)網(wǎng)絡負載計算block間隔。

3. 間隔時間到后，超級節(jié)點按照優(yōu)先級產(chǎn)出block，一旦一個新的block產(chǎn)出，回到步驟1。

SCAR共識算法的優(yōu)點在于：

1. 由超級節(jié)點執(zhí)行共識，block間隔可以極大程度縮短，交易確認快。

2. block間隔根據(jù)網(wǎng)絡負載動態(tài)調(diào)整，空閑時候間隔變長，降低帶寬和硬盤壓力。

3. 當?shù)陀诎霐?shù)的超級節(jié)點出現(xiàn)故障的時候，新的block仍然能夠產(chǎn)出，系統(tǒng)魯棒性強。

以下將分別描述SCAR算法的三個步驟。

節(jié)點投票

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

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

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

投票的具體流程如下：

1. 收集新的超級節(jié)點的提案，向社區(qū)公布并收集反饋；

2. 根據(jù)社區(qū)反饋調(diào)整超級節(jié)點列表，并通過智能合約存儲到區(qū)塊鏈中，作為新的提案；

3. 通過調(diào)用 DGP 合約的相應方法，將該提案設置為待投票的提案，此時即開啟投票；

4. 擁有管理admin和治理gov權限的地址通過向投票合約發(fā)送一筆交易來對提案進行投票；

5. 若提案未獲得足夠投票則被否決，不執(zhí)行修改；

6. 若提案通過，新超級節(jié)點列表的存儲地址會記錄進DGP合約，并在一定數(shù)量的區(qū)塊后生效，以防止出現(xiàn)不必要的分叉。

7. 節(jié)點可以通過 DGP 合約來獲取最新的超級節(jié)點列表。

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

block 間隔

block的間隔需要根據(jù)網(wǎng)絡的負載情況動態(tài)調(diào)整，網(wǎng)絡空閑時候間隔變長，網(wǎng)絡繁忙時候間隔變短，從而實現(xiàn)動態(tài)可伸縮。這里我們提出一種block間隔的計算方法，根據(jù)近期的交易數(shù)量來進行計算，交易多則間隔變短，交易少則間隔變長。

block間隔的計算公式如下：

區(qū)塊鏈相關的一些共識算法介紹

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

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

1. 當交易量 transaction_num 為0時，block間隔將調(diào)整為 max_interval，此時將用系統(tǒng)設置的最長間隔時間來盡量在一個區(qū)塊內(nèi)打包更多交易，避免了存儲空間的浪費；

2. 當鏈上交易量 transaction_num 趨向于無窮大時，block間隔將無限趨近于 min_interval，此時將用系統(tǒng)設置的最短間隔時間來盡可能緩解區(qū)塊鏈網(wǎng)絡的交易擁塞，使得交易更快地被打包進區(qū)塊；

3. max_interval 和 min_interval 可以根據(jù)實際情況進行設置（例如用戶容忍的交易延遲、超級節(jié)點的網(wǎng)絡環(huán)境和存儲性能等）。

采用這種根據(jù)網(wǎng)絡狀態(tài)動態(tài)調(diào)節(jié)區(qū)塊出塊時間的共識算法 SCAR，可以有效的避免在交易量小時浪費存儲空間，也可以在交易量大時增大區(qū)塊產(chǎn)生速率，及時將交易打包進區(qū)塊鏈上，保證交易更快地被確認。鏈上參數(shù)的動態(tài)調(diào)整也使得區(qū)塊鏈系統(tǒng)變得更加靈活，提高治理效率，降低治理難度和代價。

block 產(chǎn)出

當超級節(jié)點和block間隔都確定之后，節(jié)點就可以在間隔時間之后輪流產(chǎn)出新的block。

在某一區(qū)塊鏈高度上，若超級節(jié)點的數(shù)量為 n 個，則 SCAR 會為每個超級節(jié)點分配不同的出塊時間 block_time如下：

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

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

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

共識算法可以有效地避免分叉的發(fā)生，但至少需要 n/2+1 位超級節(jié)點保持公式算法的正常運行（n 是超級節(jié)點數(shù)量，n/2 是整數(shù)除法）。共識算法對允許創(chuàng)建下一個區(qū)塊的礦工做出了以下定義：

一個礦工在以下情況可以創(chuàng)建新的區(qū)塊：

1. 它當前是被授權的；

2. 最近的n/2個塊不是由它創(chuàng)建的。

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

由上圖過程選出了 B、C、D 三個可創(chuàng)建下一區(qū)塊的節(jié)點后，我們只需要將超級節(jié)點列表設置為有序列表，指定它們的優(yōu)先級先后，就可以避免它們?yōu)楫a(chǎn)出下一區(qū)塊而競爭。公式中的 miner_index 即為排序后的礦工列表的優(yōu)先級索引，排序更前的超級節(jié)點將被分配更早的 block_time，每個超級節(jié)點使用被分配的 block_time 創(chuàng)建新的區(qū)塊，并在 block_time 到來前保持等待狀態(tài)。

但超級節(jié)點模式的聯(lián)盟鏈也面臨著一個問題：部分節(jié)點的故障會導致網(wǎng)絡效率驟降甚至癱瘓。為了避免部分節(jié)點的故障導致系統(tǒng)停止運行，共識加入以下策略來確保正常出塊。我們在系統(tǒng)參數(shù)中設置了 timeout ，若一個超級節(jié)點由于故障未能成功廣播新的區(qū)塊，則下一個超級節(jié)點會在 timeout 時間之后取代它并正常產(chǎn)出區(qū)塊。如下圖所示，在上述5個超級節(jié)點的情況下，礦工 B 在產(chǎn)出高度為 h2+1 的區(qū)塊時發(fā)生故障。隨后，B 在超級節(jié)點列表中的下一位C ，將會在其 parent_block_time 的 block_interval+timeout 時間之后，廣播其創(chuàng)建的新區(qū)塊。