蕭梓健 唐屹

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

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

DOI：10. 11907/rjdk. 201569 開放科學（資源服務）標識碼（OSID）：

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

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

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

1 理論背景

1.1 有用工作量證明

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

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

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

1.2 SAT問題

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

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

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

2 基本框架

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

2.1 節(jié)點礦工SAT實例生成

每個礦工格子創(chuàng)建區(qū)塊，包含Header頭部信息與當前區(qū)塊難度Difficulty，使用這些參數信息作為輸入值udd=（Header||Difficulty），利用算法1求出SHA256隨機序列進行初始化。使用該輸出值wv作為算法2偽隨機值生成器Hash_DBRG的種子輸入，輸出的r即為隨機整數，wv即可作為下一輪使用Hash_DBRG求隨機值的種子輸入?？梢钥闯雒恳惠嗠S機數均與區(qū)塊信息udd對應。礦工此時可使用區(qū)塊信息udd使算法1初始化，再使用算法2偽隨機值生成器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 基于哈希的隨機數生成算法

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é)點礦工SAT實例求解及廣播

當礦工自行創(chuàng)建困難SAT后，將執(zhí)行算法3，使用WalkSAT求解器[19]對該SAT實例進行求解，盡最大算力找到該SAT最大解。若找到完全解，則立即廣播區(qū)塊B、完全解sB和解的個數sdB;否則，按給定的心跳時間進行求解，再廣播自身的求解狀態(tài)，包含區(qū)塊B、完全解sB與解的個數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證明共識達成

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

算法4 SAT證明共識達成

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ū)塊鏈網絡中，使用基于SAT問題的工作量證明會控制區(qū)塊生成難度，使區(qū)塊以一定的速度生成。在難度控制中，主要在使用CA算法[18]構造SAT實例時進行難度控制，變量越多，子句越多，則SAT實例越復雜，礦工進行求解越困難，生成區(qū)塊越慢。而網絡將根據生成區(qū)塊的速度調整難度，使整個網絡以一定速度生成一個區(qū)塊。

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

3 實驗與測試

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

3.1 SAT問題生成測試

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

3.2 SAT問題求解測試

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

3.3 SAT證明共識達成測試

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

4 結語

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

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

參考文獻：

[1] 沈鑫，裴慶祺，劉雪峰. 區(qū)塊鏈技術綜述[J]. 網絡與信息安全學報， 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)獎懲的分支策略的SAT完備算法[J]. 計算機應用，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] 徐亮，余建平. 改進的驗證正確性ACTL性質的限界模型檢測方法[J]. 計算機科學，2013，040（0z1）：99-102]

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

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

[11] 黃嘉成，許新華，王世純. 委托權益證明共識機制的改進方案[J]. ?計算機應用， 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] 沈雪，陳樹偉，艾森陽. 基于獎勵機制的SAT求解器分支策略[J]. 計算機科學，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算法的研究及應用[D]. 成都：電子科技大學，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.

（責任編輯：江 艷）