余本國(guó)，弓世明，龐曉瓊，聶夢(mèng)飛，陳文俊，3，楊 婷

1.中北大學(xué) 軟件學(xué)院，太原030051

2.中北大學(xué) 大數(shù)據(jù)學(xué)院，太原030051

3.中國(guó)人民銀行 太原中心支行，太原030001

1 引言

近年來，隨著比特幣[1]等數(shù)字貨幣的興起，其底層技術(shù)——區(qū)塊鏈也逐漸進(jìn)入人們的視野。區(qū)塊鏈的去中心化、不可篡改、可追溯等特性，使它很快在其他方面也展現(xiàn)出驚人的潛力，諸如供應(yīng)鏈管理、個(gè)人信息管理、物聯(lián)網(wǎng)、信用征集等[2-5]。隨著區(qū)塊鏈技術(shù)的快速發(fā)展，越來越多的項(xiàng)目落地，區(qū)塊鏈的應(yīng)用領(lǐng)域不斷地被探索擴(kuò)張。

區(qū)塊鏈?zhǔn)且粋€(gè)分布式的鏈?zhǔn)綌?shù)據(jù)庫(kù)，它由加入該區(qū)塊鏈系統(tǒng)的所有在線全節(jié)點(diǎn)共同維護(hù)，這些全節(jié)點(diǎn)通過P2P 網(wǎng)絡(luò)連接在一起，彼此不需要提前取得相互的信任，其中一個(gè)或多個(gè)節(jié)點(diǎn)提議一個(gè)數(shù)據(jù)區(qū)塊后，所有節(jié)點(diǎn)通過共識(shí)機(jī)制[6-9]共同參與和認(rèn)證，對(duì)這個(gè)數(shù)據(jù)區(qū)塊一致達(dá)成協(xié)議[10]，若一致通過則將該數(shù)據(jù)區(qū)塊添加到區(qū)塊鏈上。由此可見，共識(shí)機(jī)制是區(qū)塊鏈技術(shù)中的核心要素，尤其是對(duì)于公有鏈來說，共識(shí)機(jī)制是區(qū)塊鏈的靈魂。目前，應(yīng)用于公有鏈的共識(shí)機(jī)制主要有工作量證明（Proof of Work，PoW）[1]、權(quán)益證明（Proof of Stake，PoS）[11]以及授權(quán)股份證明（Delegated Proof-of-Stake，DPoS）[12]等。

2008年10月，中本聰發(fā)表了《比特幣一種點(diǎn)對(duì)點(diǎn)電子現(xiàn)金系統(tǒng)》[1]，其運(yùn)用的是PoW 共識(shí)機(jī)制。PoW 是最早且迄今為止最安全可靠的公有鏈共識(shí)機(jī)制，其核心思想是通過各個(gè)全節(jié)點(diǎn)（即礦工）的算力相互競(jìng)爭(zhēng)來解決同一個(gè)求解復(fù)雜但是驗(yàn)證容易的SHA256數(shù)學(xué)難題（即挖礦），最快解出該難題的礦工所打包的區(qū)塊即本輪共識(shí)出的合法區(qū)塊[13]。然而此過程中，礦工求解該難題除了為了爭(zhēng)奪打包合法區(qū)塊所能獲得的比特幣獎(jiǎng)勵(lì)之外，所消耗的算力并沒有為社會(huì)創(chuàng)造實(shí)際價(jià)值，而且對(duì)于算力強(qiáng)大的礦工有利，對(duì)只有平庸的算力的礦工來說不公平，造成了算力中心化的現(xiàn)象。并且在多個(gè)礦工算力較大且相差不大的情況下，會(huì)經(jīng)常發(fā)生臨時(shí)分叉的現(xiàn)象。

2011年7月，PoS共識(shí)機(jī)制被Quantum Mechanic首次在比特幣論壇中提出[11]。PoS中各個(gè)礦工的挖礦難度與其權(quán)益成反比，其中權(quán)益為持幣數(shù)量與持幣天數(shù)的乘積，每挖礦成功后該礦工的權(quán)益清零。雖然PoS不會(huì)造成算力浪費(fèi)和算力中心化，但是卻造成了權(quán)益中心化[13]。并且在多個(gè)礦工權(quán)益較大且相差不大的情況下，會(huì)經(jīng)常發(fā)生臨時(shí)分叉的現(xiàn)象。

2013 年8 月，比特股（Bitshares）項(xiàng)目提出了新的共識(shí)機(jī)制——授權(quán)股份證明機(jī)制（Delegated Proof-of-Stake，DPoS）[12]。DPoS共識(shí)的基本思路類似于“董事會(huì)決策”，即系統(tǒng)中每個(gè)節(jié)點(diǎn)可以將其持有的股份權(quán)益作為選票授予一個(gè)代表，獲得票數(shù)最多且愿意成為代表的前N 個(gè)節(jié)點(diǎn)將進(jìn)入“董事會(huì)”，按照既定的時(shí)間表輪流對(duì)交易進(jìn)行打包結(jié)算，并且簽署（即生產(chǎn)）新區(qū)塊[13]。其雖然降低了算力浪費(fèi)，提高了共識(shí)機(jī)制的速度和穩(wěn)定性，但是持票人參與投票選舉的積極性并不高，造成的權(quán)益中心化會(huì)越來越大。

綜上所述，PoW 會(huì)造成算力浪費(fèi)和算力中心化，PoS和DPoS會(huì)造成權(quán)益中心化。為了解決現(xiàn)有應(yīng)用于公有鏈共識(shí)機(jī)制中浪費(fèi)算力、去中心化程度不高的缺點(diǎn)，同時(shí)保證共識(shí)機(jī)制的穩(wěn)定性，本文提出了新的基于哈希隨機(jī)選主的共識(shí)機(jī)制PoM。PoM 利用哈希算法的單向性和強(qiáng)抗碰撞性隨機(jī)選取合法區(qū)塊，使得共識(shí)過程更公平、穩(wěn)定。

2 準(zhǔn)備知識(shí)

2.1 區(qū)塊鏈

區(qū)塊鏈?zhǔn)怯梢粋€(gè)個(gè)的數(shù)據(jù)區(qū)塊連接而成的數(shù)據(jù)庫(kù)，每一個(gè)區(qū)塊包含區(qū)塊頭和區(qū)塊體兩個(gè)組成部分。區(qū)塊體中以默克爾樹的形式存儲(chǔ)著需要記錄的數(shù)據(jù)，生成的默克爾樹根則存在區(qū)塊頭中以保證區(qū)塊頭和區(qū)塊體是一體的。

以比特幣為例，其區(qū)塊鏈結(jié)構(gòu)如圖1 所示，區(qū)塊頭中存有版本號(hào)、前一個(gè)區(qū)塊的哈希值、時(shí)間戳、難度值和nonce。其中，前一個(gè)區(qū)塊的哈希值可以用來連接區(qū)塊以此使一個(gè)個(gè)的區(qū)塊連接為鏈?zhǔn)降膮^(qū)塊鏈。時(shí)間戳記錄了該區(qū)塊生成的時(shí)間，由于后一個(gè)區(qū)塊生成的時(shí)間一定是在前一個(gè)區(qū)塊之后，所以時(shí)間戳可以用來判斷區(qū)塊的合法性。難度值和nonce用于進(jìn)行共識(shí)。

圖1 比特幣區(qū)塊鏈結(jié)構(gòu)示意圖

圖2 PoM區(qū)塊鏈結(jié)構(gòu)示意圖

2.2 哈希算法

SHA256 是一種哈希算法，在比特幣區(qū)塊鏈中應(yīng)用廣泛[1]。哈希算法是一種可以將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)，而且非常相似的兩個(gè)消息，經(jīng)過哈希運(yùn)算后得到的消息摘要很可能相差很大。如果已知一個(gè)經(jīng)過哈希運(yùn)算后得到的消息摘要，想要求得消息本身是非常困難的，而已知一個(gè)消息，想要求得該消息經(jīng)過哈希運(yùn)算后的消息摘要是非常簡(jiǎn)單的。

由于哈希算法的這些特點(diǎn)，在區(qū)塊鏈中，哈希算法不僅運(yùn)用在區(qū)塊體的默克爾樹中和區(qū)塊與區(qū)塊的鏈接中，在共識(shí)機(jī)制中也有很大的作用。

3 PoM

本章主要介紹本文提出的一種新的共識(shí)機(jī)制PoM。PoM不僅有較高的去中心化程度，還有較高的穩(wěn)定性。

在使用PoM 共識(shí)的區(qū)塊鏈網(wǎng)絡(luò)中，每個(gè)礦工都會(huì)實(shí)時(shí)更新全網(wǎng)礦工的個(gè)數(shù)，并將礦工的個(gè)數(shù)記為n，由于每時(shí)每刻都有可能有新的礦工加入也有舊的礦工退出，所以n 的值雖然是動(dòng)態(tài)變化的但一般不會(huì)出現(xiàn)驟增驟減的情況。

3.1 PoM的區(qū)塊結(jié)構(gòu)

PoM的區(qū)塊結(jié)構(gòu)如圖2所示，其包含有區(qū)塊頭和區(qū)塊體兩部分，區(qū)塊體利用默克爾樹的結(jié)構(gòu)存儲(chǔ)信息，區(qū)塊頭中包含版本號(hào)、前一個(gè)區(qū)塊的哈希值（perHash）、默克爾樹根、時(shí)間戳、打包該區(qū)塊的礦工的公鑰（pk）、minimum。minimum的計(jì)算如等式（1）所示：

3.2 PoM的共識(shí)過程

PoM的運(yùn)行從時(shí)間上被劃分為一個(gè)一個(gè)的周期，每一個(gè)周期產(chǎn)生一個(gè)區(qū)塊，每一個(gè)周期又被劃分為兩個(gè)階段，每個(gè)階段都有對(duì)應(yīng)的時(shí)間限制，設(shè)第一階段的時(shí)間限制為t1，設(shè)第二階段的時(shí)間限制為t2。其具體架構(gòu)如圖3所示。

圖3 PoM共識(shí)過程示意圖

第一階段：各個(gè)礦工通過等式（1）計(jì)算出本輪共識(shí)中自己的minimum，當(dāng)minimum 的前m 位為0 時(shí)，則從交易池中篩選合法交易打包區(qū)塊并廣播至全網(wǎng)。m 的計(jì)算方法如等式（2）所示：

第二階段：各個(gè)礦工比較從第一階段中收到的區(qū)塊，將比較得出的區(qū)塊頭中minimum最小的合法區(qū)塊添加到區(qū)塊鏈中。若第一階段沒有一個(gè)區(qū)塊被廣播，則將一個(gè)空區(qū)塊添加到區(qū)塊鏈中。空區(qū)塊的結(jié)構(gòu)圖如圖4所示，其區(qū)塊體中的交易數(shù)量為0，Merkle根的值為空，打包該區(qū)塊的礦工的公鑰為空，minimum 為空，時(shí)間戳為t1結(jié)束的時(shí)刻。

當(dāng)有新的礦工想要加入時(shí)，它相鄰的礦工會(huì)將自己記錄的區(qū)塊鏈中最新的區(qū)塊發(fā)給新礦工，新礦工將收到的區(qū)塊進(jìn)行對(duì)比，選擇最一致的區(qū)塊同步其整個(gè)區(qū)塊鏈，即全網(wǎng)最統(tǒng)一的區(qū)塊鏈?zhǔn)呛戏ǖ摹?/p>

圖4 PoM空區(qū)塊結(jié)構(gòu)示意圖

共識(shí)生成區(qū)塊的偽代碼算法如下：

Procedure CreatBlock

Input：version：version number of block chain；Bprev：previous block；publicKeyminer：the miner’s public key；

Output：A block with transactions or null

minimum=SHA256（SHA256（Bprev），publicKeyminer）

for placeminimumin m

if placeminimum.number!=0

end procedure

end if

end for

PreviousHash←Bprev

BlockBody←Block.wrap（transaction）

//The miner creates a warpped block that includes as many transcations as it wishes to include

MerkleRoot←HASH（BlockBody）

BlockHeader←（version，PreviousHash，Address，Merkle-Root，Timestamp，publicKeyminer，minimum）

Block←（BlockHeader，BlockBody）

return Block

end procedure

Procedure SelectBlock

Input：Blocks：Receive the legitimate block broadcasted

Output：A block with transactions or a empty block

if length（Blocks）==0

Block←EmptyBlock

return Block

end procedure

end if

Block←Block[0]

for 1≤i＜length（Blocks）

if Block[i].BlockHeader.minimum＜Block[i-1].Block-Header.minimum

Block←Block[i]

end if

end for

return Block

end procedure

3.3 PoM的臨時(shí)分叉

在一輪共識(shí)中，當(dāng)出現(xiàn)有不止一個(gè)礦工打包了minimum 相同且為最小值的合法區(qū)塊時(shí)，區(qū)塊鏈會(huì)發(fā)生臨時(shí)分叉。

出現(xiàn)臨時(shí)分叉的共識(shí)過程如圖5所示。

圖5 PoM臨時(shí)分叉示意圖

第一階段：各個(gè)礦工通過等式（1）計(jì)算出本輪共識(shí)自己的minimum，當(dāng)minimum 的前m 位為0 時(shí)，則從交易池中篩選合法交易打包區(qū)塊并廣播至全網(wǎng)。

第二階段：各個(gè)礦工比較從第一階段中收到的區(qū)塊，若收到有不止一個(gè)minimum相同且為最小值的合法區(qū)塊，則將這些區(qū)塊都鏈接在區(qū)塊鏈的末尾。

臨時(shí)分叉后，所有的礦工可以在多條鏈上同時(shí)進(jìn)行挖礦，當(dāng)出現(xiàn)同一高度的不同區(qū)塊的minimum 不同時(shí)，臨時(shí)分叉結(jié)束，保留minimum 較小的那一條鏈，其余因?yàn)榕R時(shí)分叉而產(chǎn)生的區(qū)塊被視為不合法區(qū)塊。以臨時(shí)分叉產(chǎn)生兩條鏈為例，如圖5所示，區(qū)塊鏈在3號(hào)區(qū)塊產(chǎn)生了臨時(shí)分叉，當(dāng)出現(xiàn)minimum 不同的兩個(gè)4 號(hào)區(qū)塊時(shí)，假設(shè)4’號(hào)區(qū)塊的minimum 比4 號(hào)區(qū)塊的minimum大，那么上面的區(qū)塊被視為非法區(qū)塊而被拋棄，下面的區(qū)塊被視為合法區(qū)塊。

3.4 公平性及穩(wěn)定性分析及實(shí)驗(yàn)

下面從去中心化程度和穩(wěn)定性兩個(gè)方面對(duì)本文方案進(jìn)行分析。

不同于PoW的算力競(jìng)爭(zhēng)，PoS和DPoS的權(quán)益競(jìng)爭(zhēng)，在PoM 中，哈希算法的抗碰撞性保證了每個(gè)礦工打包區(qū)塊的概率是完全一樣的。

當(dāng)1 ≤n ＜24時(shí)。當(dāng)24≤n ＜233時(shí)（世界人口接近于233），0.000 015 2 ＜P1＜0.018 315 7，表明PoM每輪共識(shí)產(chǎn)生空區(qū)塊的概率非常小，且每輪共識(shí)被廣播的區(qū)塊在基本上都在16～32 個(gè)（有一定的隨機(jī)性，有可能小于16 個(gè)，也有可能大于32 個(gè)）。若采用m=，當(dāng)23≤n ＜233時(shí)，0.003 906 2 ＜P1＜0.135 335 3，每輪共識(shí)產(chǎn)生空區(qū)塊的概率較大，穩(wěn)定性下降。若采用，當(dāng)25≤n ＜233時(shí)，0.000 000 000 2 ＜P1＜0.000 336，雖然每輪共識(shí)產(chǎn)生空區(qū)塊的概率很小，但每輪共識(shí)被廣播的區(qū)塊基本上都在32～64 個(gè)，對(duì)網(wǎng)絡(luò)的壓力較大。

PoM 臨時(shí)分叉的概率相當(dāng)于在n 個(gè)0～(2256-1) 的二進(jìn)制隨機(jī)數(shù)中，出現(xiàn)有至少兩個(gè)數(shù)相等且是這n 個(gè)數(shù)的最小值，而且這個(gè)最小值的前m 位均為0 的概率。將PoM臨時(shí)分叉的概率記為P2，其概率算法如等式（4）所示：

可以看出，當(dāng)n ≤233時(shí)，PoM 臨時(shí)分叉的概率無限接近于0。

基于提出的PoM機(jī)制，進(jìn)行仿真實(shí)驗(yàn)。使用golang語言模擬實(shí)現(xiàn)了PoM。實(shí)驗(yàn)環(huán)境為處理器：2.7 GHz Intel Core i5，內(nèi)存：8 GB 1 867 MHz DDR3，閃存：121 GB，系統(tǒng)：macOS Sierra 10.12.3（16D32）。驗(yàn)證PoM 的共識(shí)機(jī)制的公平性和穩(wěn)定性。

設(shè)置了211個(gè)礦工，連續(xù)進(jìn)行了10 000 次PoM 共識(shí)，其中有3 次共識(shí)出空區(qū)塊，沒有出現(xiàn)過臨時(shí)分叉，每個(gè)礦工成功挖礦次數(shù)在0～13 次之間不等，實(shí)驗(yàn)結(jié)果如圖6 所示。實(shí)驗(yàn)表明，PoM 具有良好的公平性和穩(wěn)定性。

圖6 PoM挖礦分布圖

3.5 計(jì)算開銷分析

下面，對(duì)本文方案進(jìn)行計(jì)算開銷分析，包括計(jì)算時(shí)間開銷和臨時(shí)存儲(chǔ)空間開銷。

3.5.1 符號(hào)定義

文中用到的符號(hào)定義如表1所示。

表1 符號(hào)定義

3.5.2 分析

本文提出的最小值證明共識(shí)機(jī)制分為兩個(gè)階段，第一階段是礦工打包區(qū)塊并廣播，第二階段是礦工挑選區(qū)塊上鏈。

在第一階段中，各個(gè)礦工通過等式（1）計(jì)算出本輪共識(shí)中自己的minimum，再通過等式（2）計(jì)算出m ，當(dāng)minimum的前m 位為0時(shí)，則從交易池中篩選合法交易打包區(qū)塊并廣播至全網(wǎng)。開銷如表2所示。

表2 第一階段計(jì)算開銷

在第二階段中，分為三種情況：挑選一個(gè)區(qū)塊添加到區(qū)塊鏈；臨時(shí)分叉；創(chuàng)造一個(gè)空區(qū)塊添加到區(qū)塊鏈。其中臨時(shí)分叉的計(jì)算開銷與挑選一個(gè)區(qū)塊添加到區(qū)塊鏈幾乎相同，且后兩種情況發(fā)生的概率極小。開銷如表3所示。由于，Bnumber×Bs 遠(yuǎn)大于使用堆排序的方法，將所有minimum進(jìn)行排序時(shí)的臨時(shí)存儲(chǔ)空間開銷、通常情況下x ?Bnumber ，且第二階段出現(xiàn)第二、三種情況的概率極小，所以每輪共識(shí)每個(gè)礦工總的計(jì)算時(shí)間開銷為O( )2xBnumber ，臨時(shí)存儲(chǔ)空間開銷為

表3 第二階段計(jì)算開銷

4 結(jié)束語

共識(shí)算法是區(qū)塊鏈系統(tǒng)的關(guān)鍵要素之一，已成為當(dāng)前信息領(lǐng)域的一個(gè)新的研究熱點(diǎn)[13]。共識(shí)機(jī)制的性能在很大程度上影響著區(qū)塊鏈系統(tǒng)的性能。為了解決現(xiàn)有公有鏈的共識(shí)機(jī)制存在著去中心化程度不高和經(jīng)常出現(xiàn)臨時(shí)分叉這兩個(gè)問題。本文提出一種新的應(yīng)用于公有鏈的共識(shí)機(jī)制PoM，PoM既保障了礦工在挖礦過程中的公平性，又保障了區(qū)塊鏈增長(zhǎng)過程中的穩(wěn)定性。

共識(shí)機(jī)制只是區(qū)塊鏈的一部分，想要完成一個(gè)優(yōu)秀的區(qū)塊鏈系統(tǒng)還需要有合適的激勵(lì)機(jī)制的配合[14]。共識(shí)算法規(guī)定了礦工為維護(hù)區(qū)塊鏈賬本安全性、一致性和活性而必須遵守的行為規(guī)范和行動(dòng)次序[13]；激勵(lì)機(jī)制則規(guī)定了在共識(shí)過程中為鼓勵(lì)礦工忠實(shí)、高效地驗(yàn)證區(qū)塊鏈賬本數(shù)據(jù)而發(fā)行的經(jīng)濟(jì)權(quán)益，通常包括代幣發(fā)行機(jī)制、代幣分配機(jī)制、交易費(fèi)定價(jià)機(jī)制[15]等。只有共識(shí)機(jī)制與激勵(lì)機(jī)制聯(lián)合優(yōu)化，才能保障區(qū)塊鏈系統(tǒng)健康穩(wěn)定的運(yùn)行。