區(qū)塊鏈相關(guān)的一些共識(shí)算法介紹

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

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

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

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

相關(guān)共識(shí)算法介紹

PoW，Bitcoin為代表。節(jié)點(diǎn)提供算力，通過(guò)大量的計(jì)算，產(chǎn)生新的block。算力越高，產(chǎn)生block的速度越快。計(jì)算難度每2016個(gè)block調(diào)整一次，保證在全網(wǎng)算力變化的情況下，block時(shí)間間隔保持在10分鐘左右。由于block間隔時(shí)間長(zhǎng)，且每個(gè)block的大小限制在 1 MB，所以當(dāng)交易量大的時(shí)候，網(wǎng)絡(luò)會(huì)發(fā)生嚴(yán)重?fù)矶隆?/p>

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

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

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

SCAR 共識(shí)算法描述

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

SCAR共識(shí)算法由三個(gè)步驟組成：

1. 統(tǒng)計(jì)投票得到所有超級(jí)節(jié)點(diǎn)。

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

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

SCAR共識(shí)算法的優(yōu)點(diǎn)在于：

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

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

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

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

節(jié)點(diǎn)投票

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

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

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

投票的具體流程如下：

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

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

3. 通過(guò)調(diào)用 DGP 合約的相應(yīng)方法，將該提案設(shè)置為待投票的提案，此時(shí)即開(kāi)啟投票；

4. 擁有管理admin和治理gov權(quán)限的地址通過(guò)向投票合約發(fā)送一筆交易來(lái)對(duì)提案進(jìn)行投票；

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

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

7. 節(jié)點(diǎn)可以通過(guò) DGP 合約來(lái)獲取最新的超級(jí)節(jié)點(diǎn)列表。

綜上所述，我們可以在鏈上設(shè)置 DGP 合約，通過(guò) DGP 投票的方式來(lái)決定超級(jí)節(jié)點(diǎn)，并動(dòng)態(tài)地存儲(chǔ)和更新授權(quán)礦工列表。

block 間隔

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

block間隔的計(jì)算公式如下：

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

這樣設(shè)計(jì)公式的意義在于：

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

2. 當(dāng)鏈上交易量 transacTIon_num 趨向于無(wú)窮大時(shí)，block間隔將無(wú)限趨近于 min_interval，此時(shí)將用系統(tǒng)設(shè)置的最短間隔時(shí)間來(lái)盡可能緩解區(qū)塊鏈網(wǎng)絡(luò)的交易擁塞，使得交易更快地被打包進(jìn)區(qū)塊；

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

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

block 產(chǎn)出

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

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

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

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

當(dāng)創(chuàng)建新區(qū)塊時(shí)，礦工會(huì)通過(guò)加密算法簽名這個(gè)區(qū)塊，然后將簽名結(jié)果附加到區(qū)塊中。通過(guò)這種方式，其他節(jié)點(diǎn)可以通過(guò)解密從區(qū)塊中恢復(fù)出礦工的公鑰來(lái)，從而通過(guò)和超級(jí)節(jié)點(diǎn)列表進(jìn)行比對(duì)來(lái)驗(yàn)證該礦工是否有權(quán)創(chuàng)建區(qū)塊。當(dāng)一條鏈被大多數(shù)礦工簽名之后，這條鏈可以被視作為一條永久的鏈。例如在上圖中，從創(chuàng)世區(qū)塊到h3高度的鏈?zhǔn)且粭l永久的鏈，因?yàn)樗呀?jīng)被它接下來(lái)的幾位礦工D、E和A簽名了。如果任何礦工想要在高度h3下面制造分叉，這一分叉則無(wú)法被絕大多數(shù)礦工所認(rèn)同。

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

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

1. 它當(dāng)前是被授權(quán)的；

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

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

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

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

實(shí)現(xiàn)

SCAR算法在Unita的當(dāng)前版本中已經(jīng)實(shí)現(xiàn)。其策略是，只有當(dāng)網(wǎng)絡(luò)中有未確認(rèn)交易的時(shí)候，才會(huì)產(chǎn)生新的block。我們計(jì)劃后續(xù)根據(jù)實(shí)際使用情況進(jìn)行改進(jìn)。

總結(jié)

SCAR在保證區(qū)塊鏈性能的同時(shí)，盡可能節(jié)省了帶寬和硬盤(pán)的消耗，并支持動(dòng)態(tài)調(diào)整鏈上參數(shù)，相比其他共識(shí)算法更加的高效和靈活，在大規(guī)模的商業(yè)應(yīng)用中會(huì)有更大的優(yōu)勢(shì)。