基于可滿足性問題的有用工作量證明共識機(jī)制

蕭梓健 唐屹

摘 要：為減少在公鏈上基于哈希的工作量證明中無意義計(jì)算消耗，合理利用區(qū)塊鏈網(wǎng)絡(luò)算力，創(chuàng)建一個(gè)促進(jìn)可滿足性問題（SAT）研究的有用工作社區(qū)環(huán)境，基于SAT問題求解，開發(fā)一種有用工作量證明共識機(jī)制，通過競爭解決困難SAT問題的方法獲得區(qū)塊鏈中區(qū)塊構(gòu)造權(quán)，并使各節(jié)點(diǎn)間達(dá)成共識。實(shí)驗(yàn)證明，基于該共識算法的區(qū)塊鏈系統(tǒng)性能穩(wěn)定，且各算法在系統(tǒng)中運(yùn)行平穩(wěn)，基于SAT求解的工作量證明共識機(jī)制有助于解決基于哈希計(jì)算工作量證明的無意義消耗問題，更好創(chuàng)造SAT問題的研究環(huán)境。

關(guān)鍵詞：共識機(jī)制;區(qū)塊鏈;可滿足性問題;有用工作量證明

DOI：10. 11907/rjdk. 201569 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）008-0072-04

Abstract：In order to alleviate the computational waste involved in hashing-based puzzles on the public blockchain， reasonably and meaningfully utilize the computing power of the blockchain network and create a community environment that facilitates useful work for satisfiablity problem（SAT） problem research， this paper presents a proof-of-useful-work blockchain consensus mechanism based on SAT solving. The consensus mechanism achieves distributed consensus among nodes by competing to solve the random difficult SAT， to obtain the structural rights of the blocks in the blockchain. The blockchain system based on this consensus algorithm can run all algorithms stably， and the blockchain system operates steadily. The proof-of-work consensus mechanism based on solving SAT helps to solve the problem of meaningless of proof-of-work based on hashing-based puzzles， and create a better SAT problem research environment.

Key Words： consensus mechanism; blockchain; satisfiability; proof-of-useful-work

0 引言

區(qū)塊鏈技術(shù)是一種去中心化的分布式賬本技術(shù)[1]，源于中本聰發(fā)表的《比特幣：一種點(diǎn)對點(diǎn)式的電子現(xiàn)金系統(tǒng)》[2]?；诠ぷ髁孔C明（Proof-of-work，PoW）的共識機(jī)制是以比特幣為代表的密碼貨幣廣泛使用的共識機(jī)制之一[3]。由于記賬節(jié)點(diǎn)呈分布式，為保證賬本一致性，這些節(jié)點(diǎn)需通過競爭獲得交易的單一記賬權(quán)。比特幣系統(tǒng)中工作量證明基于哈希函數(shù)，節(jié)點(diǎn)間記賬權(quán)競爭通過尋找給定前綴的哈希函數(shù)值展開，由于密碼學(xué)哈希函數(shù)特性，該類尋找計(jì)算沒有啟發(fā)式搜索策略，通常需依賴記賬節(jié)點(diǎn)計(jì)算能力進(jìn)行窮舉式搜索。然而，基于哈希函數(shù)的工作量證明機(jī)制依賴大量的哈希計(jì)算，計(jì)算出的哈希值大都用過即棄，消耗大量能源[4]，除完成工作量證明外，并沒有帶來更多有意義的工作。

可滿足性問題（Satisfiability，SAT）是計(jì)算機(jī)科學(xué)領(lǐng)域經(jīng)典NP完全問題[5]，SAT問題作為第一個(gè)被證明的NP完全問題[6]，所有其它NP問題均可規(guī)約到SAT問題上。在現(xiàn)實(shí)生活中很多實(shí)際問題，如網(wǎng)絡(luò)搜索、城市交通、超大規(guī)模集成電路測試、數(shù)據(jù)挖掘等，均可轉(zhuǎn)化為SAT問題[7-8]。因此，SAT技術(shù)工業(yè)應(yīng)用前景廣闊。

本文提出一種基于SAT問題的有用工作量證明共識機(jī)制，實(shí)現(xiàn)區(qū)塊鏈記賬節(jié)點(diǎn)分布式記賬，與基于哈希函數(shù)的工作量證明相比，能夠更有意義地利用計(jì)算資源，進(jìn)一步完善SAT問題研究。

1 理論背景

1.1 有用工作量證明

比特幣的提出開啟了數(shù)字貨幣新時(shí)代，其支撐技術(shù)區(qū)塊鏈也逐漸受到各界人士重視[9]。繼中本聰在比特幣網(wǎng)絡(luò)系統(tǒng)中使用工作量證明共識算法后，該算法被應(yīng)用于多個(gè)區(qū)塊鏈網(wǎng)絡(luò)。工作量證明基于哈希運(yùn)算，各節(jié)點(diǎn)礦工競爭找到一個(gè)隨機(jī)數(shù)nounce值，并使用加密哈希函數(shù)計(jì)算使用該nounce值自我構(gòu)造的區(qū)塊哈希值，滿足實(shí)時(shí)比特幣網(wǎng)絡(luò)難度要求[10]。由于找到正確的隨機(jī)數(shù)構(gòu)造出的區(qū)塊有經(jīng)濟(jì)性回報(bào)，所以所有礦工都會投入大量計(jì)算資源，通過計(jì)算大量的哈希值競爭解決哈希難題。但對于整個(gè)網(wǎng)絡(luò)，該競爭過程在能源消耗方面是非常昂貴而無意義的[11]。

為避免這種無意義的能源消耗，研究人員在虛擬挖礦層面上針對PoW計(jì)算中資源能耗問題進(jìn)行了研究。點(diǎn)點(diǎn)幣（PeerCoin）創(chuàng)始人 King等[12]提出權(quán)益證明（Proof of Stake，PoS）共識機(jī)制，PoS由系統(tǒng)通過“幣齡”競爭確定具有最高權(quán)益的節(jié)點(diǎn)，從而獲得區(qū)塊記賬權(quán)，不再耗費(fèi)計(jì)算資源即可在區(qū)塊鏈中實(shí)現(xiàn)區(qū)塊生成;比特股（Bitshares）首席開發(fā)者Larimer[13]提出授權(quán)股份證明（Delegated Proof of Stake，DPoS）的共識算法。該算法通過實(shí)施去中心化的民主方式，視每一個(gè)幣為一張選票，而持有幣所有者可根據(jù)自己持有幣數(shù)量將選票投給信任的受托人。PoS與DPoS共識機(jī)制均從虛擬挖礦的層面處理PoW計(jì)算資源能耗問題，但未能有效利用巨大的計(jì)算資源以實(shí)現(xiàn)區(qū)塊鏈穩(wěn)定運(yùn)轉(zhuǎn)。

因此如何利用區(qū)塊鏈中網(wǎng)絡(luò)算力實(shí)現(xiàn)共識的同時(shí)又進(jìn)行有用工作成為研究熱點(diǎn)。2017年Marshall等[14]提出有用工作量證明（Proof-of-Useful-Work）的概念，針對利用耗費(fèi)大量無意義能源的工作量證明的應(yīng)用程序，如比特幣網(wǎng)絡(luò)，通過指定相應(yīng)框架利用這些浪費(fèi)的工作，從而在區(qū)塊鏈中達(dá)成共識并進(jìn)行有用工作;2013年，PPCoin團(tuán)隊(duì)發(fā)布質(zhì)數(shù)幣（Primecoin），嘗試把算力應(yīng)用于數(shù)學(xué)研究中的質(zhì)數(shù)鏈表[15]構(gòu)造中;2019年，F(xiàn)elipe Bravo-Marquez等[16]提出學(xué)習(xí)證明共識算法（Proof-of-learning），通過對給定任務(wù)的機(jī)器學(xué)習(xí)系統(tǒng)進(jìn)行排序以實(shí)現(xiàn)分布式一致，利用工作量證明機(jī)制創(chuàng)建一個(gè)公共的、可驗(yàn)證的、最先進(jìn)的機(jī)器學(xué)習(xí)模型和實(shí)驗(yàn)數(shù)據(jù)庫，推動機(jī)器學(xué)習(xí)和工業(yè)應(yīng)用發(fā)展。本文基于計(jì)算機(jī)的底層問題（SAT問題），給出一種有用的工作量證明共識機(jī)制，提高計(jì)算資源利用率，促進(jìn)SAT問題研究。

1.2 SAT問題

給定布爾變量集合X={x1，x2， ，xn}，|X|=n， 每個(gè)變量可取0或1， 子句集合C={C1，C2，C3， ，Cm}，|C|=m，C=C1∧C2∧ ∧Cm，其中每個(gè)Ci 是由多個(gè)變量組成的析取范式，長度不限，即z1∨z2∨z3 ∨zk。于是SAT問題被定義為：給定一個(gè)布爾變量集合X和子句集合C，是否存在一個(gè)真值賦值，使得C為真，即每個(gè)子句為真。其中，若定義k為3，則該SAT問題稱為3-SAT問題。通常SAT問題可歸約為3-SAT問題。

3-SAT問題求解方法包括兩種：確定性算法和隨機(jī)搜索算法[17]。確定性算法可以判定一個(gè)3-SAT問題是否有解，一旦有解，則可找出該問題的全部解，然而其時(shí)耗較大。與之對應(yīng)，隨機(jī)搜索算法基于局部搜索思想，采用啟發(fā)式搜索策略，一旦3-SAT問題有解，可在更短的時(shí)間內(nèi)找到問題的一個(gè)解。

生成難度可控的3-SAT問題難度不小，基于社區(qū)結(jié)構(gòu)（Community Structure）的隨機(jī)SAT問題生成新模型是一個(gè)可行方案[18]，基于該模型，可在給定變量數(shù)與參數(shù)種子的情況下生成特定難度的困難SAT。

2 基本框架

基于SAT的工作量證明共識機(jī)制運(yùn)用于區(qū)塊鏈中各節(jié)點(diǎn)礦工基本流程如下：①依據(jù)待記賬的數(shù)據(jù)和當(dāng)時(shí)網(wǎng)絡(luò)難度，使用CA算法[18]生成一個(gè)SAT問題;②對該問題求解。若找到完全解，則進(jìn)行廣播，否則按給定的心跳時(shí)間廣播自身的求解狀態(tài);③若收到解且驗(yàn)證成功，則首先找到解的礦工，擁有記賬權(quán);④若問題求解超時(shí)，則統(tǒng)計(jì)近似解，找到滿足子句數(shù)最多的解。若僅一個(gè)礦工得到近似解，則該礦工擁有記賬權(quán);若多個(gè)礦工得到近似解，則計(jì)算該解與礦工標(biāo)識的哈希值，哈希值最大的礦工擁有記賬權(quán)。最后，每個(gè)礦工節(jié)點(diǎn)中的區(qū)塊和區(qū)塊鏈信息如圖1所示。其中，Header頭部信息包括類似于比特幣網(wǎng)絡(luò)區(qū)塊包含的版本號、父區(qū)塊頭哈希值、Merkle根、時(shí)間戳、交易計(jì)數(shù)器、自選網(wǎng)絡(luò)的交易（t1、t2、…、tn）信息;Difficulty信息是當(dāng)前網(wǎng)絡(luò)難度，使用SAT變量數(shù)進(jìn)行控制。Header頭部信息與Difficulty是SAT問題構(gòu)造的參數(shù)。SatAnswer是使用當(dāng)前區(qū)塊構(gòu)造的SAT求出的解，SatNum是SatAnswer解的個(gè)數(shù)。SatAnswer和SatNum是當(dāng)前區(qū)塊構(gòu)造的SAT解。

2.1 節(jié)點(diǎn)礦工SAT實(shí)例生成

每個(gè)礦工格子創(chuàng)建區(qū)塊，包含Header頭部信息與當(dāng)前區(qū)塊難度Difficulty，使用這些參數(shù)信息作為輸入值udd=（Header||Difficulty），利用算法1求出SHA256隨機(jī)序列進(jìn)行初始化。使用該輸出值wv作為算法2偽隨機(jī)值生成器Hash_DBRG的種子輸入，輸出的r即為隨機(jī)整數(shù)，wv即可作為下一輪使用Hash_DBRG求隨機(jī)值的種子輸入?？梢钥闯雒恳惠嗠S機(jī)數(shù)均與區(qū)塊信息udd對應(yīng)。礦工此時(shí)可使用區(qū)塊信息udd使算法1初始化，再使用算法2偽隨機(jī)值生成器Hash_DBRG代入CA算法[18]中，生成難度固定的SAT。

算法1初始化操作

Algorithm 1 Initilzation on Hash_DBRG

Input： the value udd of user build_block B

Output：return working_value wv

1：wv=SHA256（UDD）

2：wv=256（0x00||wv）

3：wv=wv mod 2256

4：return wv

算法2 基于哈希的隨機(jī)數(shù)生成算法

Algorithm 2 Random Inter on Hash_DBRG

Input： input working_value wv

Output：return random value r，working_value wv

1：h=SHA256（0x02||wv）

2：wv=（wv+h）mod 2256

3：h=SHA256（wv）

4：r=leftmost（h，32）//take the left 32 bits of h

5：h=SHA256（0x03||wv）

6：wv=（wv+h）mod 2256

7：return r，wv

2.2 節(jié)點(diǎn)礦工SAT實(shí)例求解及廣播

當(dāng)?shù)V工自行創(chuàng)建困難SAT后，將執(zhí)行算法3，使用WalkSAT求解器[19]對該SAT實(shí)例進(jìn)行求解，盡最大算力找到該SAT最大解。若找到完全解，則立即廣播區(qū)塊B、完全解sB和解的個(gè)數(shù)sdB;否則，按給定的心跳時(shí)間進(jìn)行求解，再廣播自身的求解狀態(tài)，包含區(qū)塊B、完全解sB與解的個(gè)數(shù)sdB。

算法3 礦工求解SAT并廣播解

Algorithm 3 SAT constructing and Solution Broadcasting

Input： the block B to be packed， the time interval t

Output：the solution sB and the solution degree sdB

1：for each miner do

2： ? ? generate SAT on B

3： ? ? fine a solution sB with maxinum solution degree sdB in t

4： ? ? broadcast B，sB and sdB to other miners

5： end for

2.3 SAT證明共識達(dá)成

當(dāng)節(jié)點(diǎn)礦工在網(wǎng)絡(luò)中向其它節(jié)點(diǎn)廣播構(gòu)造區(qū)塊和求得的解，其它節(jié)點(diǎn)在驗(yàn)證廣播的區(qū)塊合法性（如Header頭部字段中的交易合法性）和解的合法性后，會按照以下步驟選擇插入到本節(jié)點(diǎn)區(qū)塊鏈副本區(qū)塊：①收到的第一個(gè)構(gòu)造的合法SAT問題的完全解，該廣播的區(qū)塊具有記賬權(quán);②收到的廣播中，如果構(gòu)造的SAT問題的解都不是完全解，則選擇具有最大解的廣播的區(qū)塊;③若有多個(gè)最大解，則計(jì)算每個(gè)廣播中的SHA256（m_addr，sB），其中m_addr指礦工節(jié)點(diǎn)地址，sB指廣播的解，選擇該哈希值最大的廣播中的區(qū)塊。流程如算法4所示。

算法4 SAT證明共識達(dá)成

Algorithm 4 SAT Consensus Reaching

Input： input sBs and sdBs

Output：packing block

1： for each miner do

2： ? ?Receive sB and sdB form other miners

3： ? ?if sB form M is the first solution them

4： ? ? ? packing block according to M

5： ? ?else

6： ? ? ? MinerSet<-miners with maximun sdB

7： ? ? ? M=argmaxmSHA256（m_addr，sB）|m∈MinerSet

8： ? ? ? packing block according to M

9： end if

2.4 難度控制

在區(qū)塊鏈網(wǎng)絡(luò)中，使用基于SAT問題的工作量證明會控制區(qū)塊生成難度，使區(qū)塊以一定的速度生成。在難度控制中，主要在使用CA算法[18]構(gòu)造SAT實(shí)例時(shí)進(jìn)行難度控制，變量越多，子句越多，則SAT實(shí)例越復(fù)雜，礦工進(jìn)行求解越困難，生成區(qū)塊越慢。而網(wǎng)絡(luò)將根據(jù)生成區(qū)塊的速度調(diào)整難度，使整個(gè)網(wǎng)絡(luò)以一定速度生成一個(gè)區(qū)塊。

在SAT證明難度控制的計(jì)算中，使用求解器WalkSAT在5分鐘（300秒）內(nèi)分別求解使用算法3構(gòu)造的具有遞增變量數(shù)（1 000，1 100，1 200，1 300，…，6 900）與子句數(shù)為4.25乘以變量數(shù)的隨機(jī)SAT實(shí)例。結(jié)果如圖2所示?？梢钥闯?，在該同一算力下，求解平均時(shí)耗會隨著變量數(shù)較為穩(wěn)定地上升。若變量數(shù)大于等于5 200個(gè)時(shí)，在5分鐘內(nèi)基本無完全解?？梢允褂镁€性近似模擬該上升情況，[（300-0）/（52-10）≈7.14]，即增加100個(gè)變量，所用時(shí)間增加7.14秒。若在算力增加情況下，使變量數(shù)增加相同的倍數(shù)，則可使求解速度基本穩(wěn)定，區(qū)塊生成速度也較為穩(wěn)定。

3 實(shí)驗(yàn)與測試

使用Go語言實(shí)現(xiàn)該基于SAT求解的工作量證明，并搭建基于該共識算法的區(qū)塊鏈，可觀察到區(qū)塊鏈系統(tǒng)運(yùn)轉(zhuǎn)穩(wěn)定，且各節(jié)點(diǎn)能平穩(wěn)運(yùn)行算法。

3.1 SAT問題生成測試

區(qū)塊鏈難度Difficulty為3 000、Header頭部信息為“test”時(shí)，使用算法1、算法2、CA算法[18]生成的SAT的cnf文件[20]如圖3所示，變量為3 500，子句為14 875，變量和子句比值為4.25。

3.2 SAT問題求解測試

節(jié)點(diǎn)創(chuàng)建完相關(guān)難度的區(qū)塊后，節(jié)點(diǎn)使用Walksat求解器進(jìn)行求解，心跳時(shí)間為300s。如節(jié)點(diǎn)求解圖3所示的SAT文件，在300s的心跳時(shí)間內(nèi)未能求解成功，輸出相關(guān)數(shù)據(jù)，如圖4。

3.3 SAT證明共識達(dá)成測試

啟動4個(gè)節(jié)點(diǎn)，進(jìn)行共識測試。4個(gè)節(jié)點(diǎn)對圖3所示的SAT文件進(jìn)行求解、廣播和共識協(xié)商。最終達(dá)成共識，此輪4個(gè)礦工共識結(jié)果如圖5所示。本輪由地址為5 080的礦工求得最大解，獲得本輪記賬權(quán)。

4 結(jié)語

本文提出了一種基于有用工作量證明共識算法，該共識算法主要基于可滿足性問題競爭求解，從而有效解決基于哈希計(jì)算工作量證明的無意義消耗問題，有助于更好創(chuàng)造SAT問題的研究環(huán)境，實(shí)現(xiàn)有用工作，對區(qū)塊鏈與理論計(jì)算機(jī)關(guān)聯(lián)研究有一定應(yīng)用價(jià)值。

文中給出了該共識算法在節(jié)點(diǎn)礦工于SAT實(shí)例生成、SAT問題求解、區(qū)塊和解廣播、共識達(dá)成的詳細(xì)過程及算法與網(wǎng)絡(luò)難度控制描述，完整介紹了該共識算法核心內(nèi)容，最后使用Go語言實(shí)現(xiàn)了基于該共識算法的區(qū)塊鏈系統(tǒng)。實(shí)驗(yàn)證明，各節(jié)點(diǎn)可平穩(wěn)運(yùn)行算法，該區(qū)塊鏈系統(tǒng)運(yùn)轉(zhuǎn)穩(wěn)定，從而說明該共識算法可行。若在區(qū)塊鏈公網(wǎng)上使用該共識機(jī)制，將有助于利用算力進(jìn)行SAT問題研究，構(gòu)建更好的SAT問題研究環(huán)境。

參考文獻(xiàn)：

[1] 沈鑫，裴慶祺，劉雪峰. 區(qū)塊鏈技術(shù)綜述[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào)， 2016， 002（11）：11-20.

[2] NAKAMOTO S. Bitcoin： a peer-to-peer electronic cash system[EB/OL]. https：/ /bitcoin.org/bitcoin.pdf.

[3] CONTI M， E KUMAR S， LAL C，et al. A Survey on security and privacy issues of bitcoin[J]. IEEE Communications Surveys & Tutorials， 2018，20（4）： 3416-3452.

[4] SWAN M. Blockchain： blueprint for a new economy[M]. Sebastopol： O'Reilly Media， Inc. "， 2015.

[5] 劉燕麗，徐振興，熊丹. 基于動態(tài)獎(jiǎng)懲的分支策略的SAT完備算法[J]. 計(jì)算機(jī)應(yīng)用，2017，37（12）：3487-3492.

[6] COOK S A. The complexity of theorem-proving procedures[C]. Symposium on The Theory of Computing， 1971： 151-158.

[7] MARQUESSILVA J. Practical applications of Boolean satisfiability[C]. International Workshop on Discrete Event Systems，2008：74-80.

[8] 徐亮，余建平. 改進(jìn)的驗(yàn)證正確性ACTL性質(zhì)的限界模型檢測方法[J]. 計(jì)算機(jī)科學(xué)，2013，040（0z1）：99-102]

[9] 劉懿中，劉建偉，張宗洋，等. ?區(qū)塊鏈共識機(jī)制研究綜述[J]. 密碼學(xué)報(bào)，2019，6（4）：395-432.

[10] ANTONOPOULOS A M. Mastering bitcoin： unlocking digital crypto-currencies[M]. Sebastopol：CA： OReilly，2014.

[11] 黃嘉成，許新華，王世純. 委托權(quán)益證明共識機(jī)制的改進(jìn)方案[J]. ?計(jì)算機(jī)應(yīng)用， 2019（7）：2162-2167.

[12] KING S，NADAL S. PPCoin：peer-to-peer crypto-currency with proof-of-stake[EB/OL]. https：//peercoin.net/assets/paper/peercoin-paper.pdf.

[13] LARIMER D. Delegated proof-of-stake[EB/OL]. https：//steemit.com/bitshares/@testz/bits-hares-history-delegated-proof-of-stake-dpos.

[14] BALL M，ROSEN A，SABIN M，et al. Proofs of useful work[C]. The 38th Annual International Cryptology Conference， 2018： 789-819.

[15] DAN. Primecoin Primer[DB/OL]. https：//letstalkbitcoin.com/primecoin-primer.

[16] BRAVO-MARQUEZ F，REEVES S，UGARTE M. Proof-of-learning： a blockchain consensus mechanism based on machine learning competitions[C]. 2019 IEEE International Conference on Decentralized Applications and Infrastructures， 2019： 119-124.

[17] 沈雪，陳樹偉，艾森陽. 基于獎(jiǎng)勵(lì)機(jī)制的SAT求解器分支策略[J]. 計(jì)算機(jī)科學(xué)，2020，47（7）：42-46.

[18] GIRáLDEZ-CRU J， LEVY J. A modularity-based random SAT instances generator[C]. ?Twenty-Fourth International Joint Conference on Artificial Intelligence，2015：1952–1958.

[19] 陳穩(wěn). ?基于DPLL的SAT算法的研究及應(yīng)用[D]. 成都：電子科技大學(xué)，2011.

[20] EEN N， MISHCHENKO A， SORENSSON N， et al. Applying logic synthesis for speeding up SAT[C]. ?Theory And Applications of Satisfiability Testing， 2007： 272-286.

（責(zé)任編輯：江 艷）