公平且穩定的最小值證明共識機制

余本國，弓世明，龐曉瓊，聶夢飛，陳文俊，3，楊 婷

1.中北大學 軟件學院，太原030051

2.中北大學 大數據學院，太原030051

3.中國人民銀行 太原中心支行，太原030001

1 引言

近年來，隨著比特幣[1]等數字貨幣的興起，其底層技術——區塊鏈也逐漸進入人們的視野。區塊鏈的去中心化、不可篡改、可追溯等特性，使它很快在其他方面也展現出驚人的潛力，諸如供應鏈管理、個人信息管理、物聯網、信用征集等[2-5]。隨著區塊鏈技術的快速發展，越來越多的項目落地，區塊鏈的應用領域不斷地被探索擴張。

區塊鏈是一個分布式的鏈式數據庫，它由加入該區塊鏈系統的所有在線全節點共同維護，這些全節點通過P2P 網絡連接在一起，彼此不需要提前取得相互的信任，其中一個或多個節點提議一個數據區塊后，所有節點通過共識機制[6-9]共同參與和認證，對這個數據區塊一致達成協議[10]，若一致通過則將該數據區塊添加到區塊鏈上。由此可見，共識機制是區塊鏈技術中的核心要素，尤其是對于公有鏈來說，共識機制是區塊鏈的靈魂。目前，應用于公有鏈的共識機制主要有工作量證明（Proof of Work，PoW）[1]、權益證明（Proof of Stake，PoS）[11]以及授權股份證明（Delegated Proof-of-Stake，DPoS）[12]等。

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

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

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

綜上所述，PoW 會造成算力浪費和算力中心化，PoS和DPoS會造成權益中心化。為了解決現有應用于公有鏈共識機制中浪費算力、去中心化程度不高的缺點，同時保證共識機制的穩定性，本文提出了新的基于哈希隨機選主的共識機制PoM。PoM 利用哈希算法的單向性和強抗碰撞性隨機選取合法區塊，使得共識過程更公平、穩定。

2 準備知識

2.1 區塊鏈

區塊鏈是由一個個的數據區塊連接而成的數據庫，每一個區塊包含區塊頭和區塊體兩個組成部分。區塊體中以默克爾樹的形式存儲著需要記錄的數據，生成的默克爾樹根則存在區塊頭中以保證區塊頭和區塊體是一體的。

以比特幣為例，其區塊鏈結構如圖1 所示，區塊頭中存有版本號、前一個區塊的哈希值、時間戳、難度值和nonce。其中，前一個區塊的哈希值可以用來連接區塊以此使一個個的區塊連接為鏈式的區塊鏈。時間戳記錄了該區塊生成的時間，由于后一個區塊生成的時間一定是在前一個區塊之后，所以時間戳可以用來判斷區塊的合法性。難度值和nonce用于進行共識。

圖1 比特幣區塊鏈結構示意圖

圖2 PoM區塊鏈結構示意圖

2.2 哈希算法

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

由于哈希算法的這些特點，在區塊鏈中，哈希算法不僅運用在區塊體的默克爾樹中和區塊與區塊的鏈接中，在共識機制中也有很大的作用。

3 PoM

本章主要介紹本文提出的一種新的共識機制PoM。PoM不僅有較高的去中心化程度，還有較高的穩定性。

在使用PoM 共識的區塊鏈網絡中，每個礦工都會實時更新全網礦工的個數，并將礦工的個數記為n，由于每時每刻都有可能有新的礦工加入也有舊的礦工退出，所以n 的值雖然是動態變化的但一般不會出現驟增驟減的情況。

3.1 PoM的區塊結構

PoM的區塊結構如圖2所示，其包含有區塊頭和區塊體兩部分，區塊體利用默克爾樹的結構存儲信息，區塊頭中包含版本號、前一個區塊的哈希值（perHash）、默克爾樹根、時間戳、打包該區塊的礦工的公鑰（pk）、minimum。minimum的計算如等式（1）所示：

3.2 PoM的共識過程

PoM的運行從時間上被劃分為一個一個的周期，每一個周期產生一個區塊，每一個周期又被劃分為兩個階段，每個階段都有對應的時間限制，設第一階段的時間限制為t1，設第二階段的時間限制為t2。其具體架構如圖3所示。

圖3 PoM共識過程示意圖

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

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

當有新的礦工想要加入時，它相鄰的礦工會將自己記錄的區塊鏈中最新的區塊發給新礦工，新礦工將收到的區塊進行對比，選擇最一致的區塊同步其整個區塊鏈，即全網最統一的區塊鏈是合法的。

圖4 PoM空區塊結構示意圖

共識生成區塊的偽代碼算法如下：

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的臨時分叉

在一輪共識中，當出現有不止一個礦工打包了minimum 相同且為最小值的合法區塊時，區塊鏈會發生臨時分叉。

出現臨時分叉的共識過程如圖5所示。

圖5 PoM臨時分叉示意圖

第一階段：各個礦工通過等式（1）計算出本輪共識自己的minimum，當minimum 的前m 位為0 時，則從交易池中篩選合法交易打包區塊并廣播至全網。

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

臨時分叉后，所有的礦工可以在多條鏈上同時進行挖礦，當出現同一高度的不同區塊的minimum 不同時，臨時分叉結束，保留minimum 較小的那一條鏈，其余因為臨時分叉而產生的區塊被視為不合法區塊。以臨時分叉產生兩條鏈為例，如圖5所示，區塊鏈在3號區塊產生了臨時分叉，當出現minimum 不同的兩個4 號區塊時，假設4’號區塊的minimum 比4 號區塊的minimum大，那么上面的區塊被視為非法區塊而被拋棄，下面的區塊被視為合法區塊。

3.4 公平性及穩定性分析及實驗

下面從去中心化程度和穩定性兩個方面對本文方案進行分析。

不同于PoW的算力競爭，PoS和DPoS的權益競爭，在PoM 中，哈希算法的抗碰撞性保證了每個礦工打包區塊的概率是完全一樣的。

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

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

可以看出，當n ≤233時，PoM 臨時分叉的概率無限接近于0。

基于提出的PoM機制，進行仿真實驗。使用golang語言模擬實現了PoM。實驗環境為處理器：2.7 GHz Intel Core i5，內存：8 GB 1 867 MHz DDR3，閃存：121 GB，系統：macOS Sierra 10.12.3（16D32）。驗證PoM 的共識機制的公平性和穩定性。

設置了211個礦工，連續進行了10 000 次PoM 共識，其中有3 次共識出空區塊，沒有出現過臨時分叉，每個礦工成功挖礦次數在0～13 次之間不等，實驗結果如圖6 所示。實驗表明，PoM 具有良好的公平性和穩定性。

圖6 PoM挖礦分布圖

3.5 計算開銷分析

下面，對本文方案進行計算開銷分析，包括計算時間開銷和臨時存儲空間開銷。

3.5.1 符號定義

文中用到的符號定義如表1所示。

表1 符號定義

3.5.2 分析

本文提出的最小值證明共識機制分為兩個階段，第一階段是礦工打包區塊并廣播，第二階段是礦工挑選區塊上鏈。

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

表2 第一階段計算開銷

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

表3 第二階段計算開銷

4 結束語

共識算法是區塊鏈系統的關鍵要素之一，已成為當前信息領域的一個新的研究熱點[13]。共識機制的性能在很大程度上影響著區塊鏈系統的性能。為了解決現有公有鏈的共識機制存在著去中心化程度不高和經常出現臨時分叉這兩個問題。本文提出一種新的應用于公有鏈的共識機制PoM，PoM既保障了礦工在挖礦過程中的公平性，又保障了區塊鏈增長過程中的穩定性。

共識機制只是區塊鏈的一部分，想要完成一個優秀的區塊鏈系統還需要有合適的激勵機制的配合[14]。共識算法規定了礦工為維護區塊鏈賬本安全性、一致性和活性而必須遵守的行為規范和行動次序[13]；激勵機制則規定了在共識過程中為鼓勵礦工忠實、高效地驗證區塊鏈賬本數據而發行的經濟權益，通常包括代幣發行機制、代幣分配機制、交易費定價機制[15]等。只有共識機制與激勵機制聯合優化，才能保障區塊鏈系統健康穩定的運行。