基于可满足性问题的有用工作量证明共识机制

萧梓健 唐屹

摘 要：为减少在公链上基于哈希的工作量证明中无意义计算消耗，合理利用区块链网络算力，创建一个促进可满足性问题（SAT）研究的有用工作社区环境，基于SAT问题求解，开发一种有用工作量证明共识机制，通过竞争解决困难SAT问题的方法获得区块链中区块构造权，并使各节点间达成共识。实验证明，基于该共识算法的区块链系统性能稳定，且各算法在系统中运行平稳，基于SAT求解的工作量证明共识机制有助于解决基于哈希计算工作量证明的无意义消耗问题，更好创造SAT问题的研究环境。

关键词：共识机制;区块链;可满足性问题;有用工作量证明

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 引言

区块链技术是一种去中心化的分布式账本技术[1]，源于中本聪发表的《比特币：一种点对点式的电子现金系统》[2]。基于工作量证明（Proof-of-work，PoW）的共识机制是以比特币为代表的密码货币广泛使用的共识机制之一[3]。由于记账节点呈分布式，为保证账本一致性，这些节点需通过竞争获得交易的单一记账权。比特币系统中工作量证明基于哈希函数，节点间记账权竞争通过寻找给定前缀的哈希函数值展开，由于密码学哈希函数特性，该类寻找计算没有启发式搜索策略，通常需依赖记账节点计算能力进行穷举式搜索。然而，基于哈希函数的工作量证明机制依赖大量的哈希计算，计算出的哈希值大都用过即弃，消耗大量能源[4]，除完成工作量证明外，并没有带来更多有意义的工作。

可满足性问题（Satisfiability，SAT）是计算机科学领域经典NP完全问题[5]，SAT问题作为第一个被证明的NP完全问题[6]，所有其它NP问题均可规约到SAT问题上。在现实生活中很多实际问题，如网络搜索、城市交通、超大规模集成电路测试、数据挖掘等，均可转化为SAT问题[7-8]。因此，SAT技术工业应用前景广阔。

本文提出一种基于SAT問题的有用工作量证明共识机制，实现区块链记账节点分布式记账，与基于哈希函数的工作量证明相比，能够更有意义地利用计算资源，进一步完善SAT问题研究。

1 理论背景

1.1 有用工作量证明

比特币的提出开启了数字货币新时代，其支撑技术区块链也逐渐受到各界人士重视[9]。继中本聪在比特币网络系统中使用工作量证明共识算法后，该算法被应用于多个区块链网络。工作量证明基于哈希运算，各节点矿工竞争找到一个随机数nounce值，并使用加密哈希函数计算使用该nounce值自我构造的区块哈希值，满足实时比特币网络难度要求[10]。由于找到正确的随机数构造出的区块有经济性回报，所以所有矿工都会投入大量计算资源，通过计算大量的哈希值竞争解决哈希难题。但对于整个网络，该竞争过程在能源消耗方面是非常昂贵而无意义的[11]。

为避免这种无意义的能源消耗，研究人员在虚拟挖矿层面上针对PoW计算中资源能耗问题进行了研究。点点币（PeerCoin）创始人 King等[12]提出权益证明（Proof of Stake，PoS）共识机制，PoS由系统通过“币龄”竞争确定具有最高权益的节点，从而获得区块记账权，不再耗费计算资源即可在区块链中实现区块生成;比特股（Bitshares）首席开发者Larimer[13]提出授权股份证明（Delegated Proof of Stake，DPoS）的共识算法。该算法通过实施去中心化的民主方式，视每一个币为一张选票，而持有币所有者可根据自己持有币数量将选票投给信任的受托人。PoS与DPoS共识机制均从虚拟挖矿的层面处理PoW计算资源能耗问题，但未能有效利用巨大的计算资源以实现区块链稳定运转。

因此如何利用区块链中网络算力实现共识的同时又进行有用工作成为研究热点。2017年Marshall等[14]提出有用工作量证明（Proof-of-Useful-Work）的概念，针对利用耗费大量无意义能源的工作量证明的应用程序，如比特币网络，通过指定相应框架利用这些浪费的工作，从而在区块链中达成共识并进行有用工作;2013年，PPCoin团队发布质数币（Primecoin），尝试把算力应用于数学研究中的质数链表[15]构造中;2019年，Felipe Bravo-Marquez等[16]提出学习证明共识算法（Proof-of-learning），通过对给定任务的机器学习系统进行排序以实现分布式一致，利用工作量证明机制创建一个公共的、可验证的、最先进的机器学习模型和实验数据库，推动机器学习和工业应用发展。本文基于计算机的底层问题（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问题是否有解，一旦有解，则可找出该问题的全部解，然而其时耗较大。与之对应，随机搜索算法基于局部搜索思想，采用启发式搜索策略，一旦3-SAT问题有解，可在更短的时间内找到问题的一个解。

生成难度可控的3-SAT问题难度不小，基于社区结构（Community Structure）的随机SAT问题生成新模型是一个可行方案[18]，基于该模型，可在给定变量数与参数种子的情况下生成特定难度的困难SAT。

2 基本框架

基于SAT的工作量证明共识机制运用于区块链中各节点矿工基本流程如下：①依据待记账的数据和当时网络难度，使用CA算法[18]生成一个SAT问题;②对该问题求解。若找到完全解，则进行广播，否则按给定的心跳时间广播自身的求解状态;③若收到解且验证成功，则首先找到解的矿工，拥有记账权;④若问题求解超时，则统计近似解，找到满足子句数最多的解。若仅一个矿工得到近似解，则该矿工拥有记账权;若多个矿工得到近似解，则计算该解与矿工标识的哈希值，哈希值最大的矿工拥有记账权。最后，每个矿工节点中的区块和区块链信息如图1所示。其中，Header头部信息包括类似于比特币网络区块包含的版本号、父区块头哈希值、Merkle根、时间戳、交易计数器、自选网络的交易（t1、t2、…、tn）信息;Difficulty信息是当前网络难度，使用SAT变量数进行控制。Header头部信息与Difficulty是SAT问题构造的参数。SatAnswer是使用当前区块构造的SAT求出的解，SatNum是SatAnswer解的个数。SatAnswer和SatNum是当前区块构造的SAT解。

2.1 节点矿工SAT实例生成

每个矿工格子创建区块，包含Header头部信息与当前区块难度Difficulty，使用这些参数信息作为输入值udd=（Header||Difficulty），利用算法1求出SHA256随机序列进行初始化。使用该输出值wv作为算法2伪随机值生成器Hash_DBRG的种子输入，输出的r即为随机整数，wv即可作为下一轮使用Hash_DBRG求随机值的种子输入。可以看出每一轮随机数均与区块信息udd对应。矿工此时可使用区块信息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 节点矿工SAT实例求解及广播

当矿工自行创建困难SAT后，将执行算法3，使用WalkSAT求解器[19]对该SAT实例进行求解，尽最大算力找到该SAT最大解。若找到完全解，则立即广播区块B、完全解sB和解的个数sdB;否则，按给定的心跳时间进行求解，再广播自身的求解状态，包含区块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证明共识达成

当节点矿工在网络中向其它节点广播构造区块和求得的解，其它节点在验证广播的区块合法性（如Header头部字段中的交易合法性）和解的合法性后，会按照以下步骤选择插入到本节点区块链副本区块：①收到的第一个构造的合法SAT问题的完全解，该广播的区块具有记账权;②收到的广播中，如果构造的SAT问题的解都不是完全解，则选择具有最大解的广播的区块;③若有多个最大解，则计算每个广播中的SHA256（m_addr，sB），其中m_addr指矿工节点地址，sB指广播的解，选择该哈希值最大的广播中的区块。流程如算法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 难度控制

在区块链网络中，使用基于SAT问题的工作量证明会控制区块生成难度，使区块以一定的速度生成。在难度控制中，主要在使用CA算法[18]构造SAT实例时进行难度控制，变量越多，子句越多，则SAT实例越复杂，矿工进行求解越困难，生成区块越慢。而网络将根据生成区块的速度调整难度，使整个网络以一定速度生成一个区块。

在SAT证明难度控制的计算中，使用求解器WalkSAT在5分钟（300秒）内分别求解使用算法3构造的具有递增变量数（1 000，1 100，1 200，1 300，…，6 900）与子句数为4.25乘以变量数的随机SAT实例。结果如图2所示。可以看出，在该同一算力下，求解平均时耗会随着变量数较为稳定地上升。若变量数大于等于5 200个时，在5分钟内基本无完全解。可以使用线性近似模拟该上升情况，[（300-0）/（52-10）≈7.14]，即增加100个变量，所用时间增加7.14秒。若在算力增加情况下，使变量数增加相同的倍数，则可使求解速度基本稳定，区块生成速度也较为稳定。

3 实验与测试

使用Go语言实现该基于SAT求解的工作量证明，并搭建基于该共识算法的区块链，可观察到区块链系统运转稳定，且各节点能平稳运行算法。

3.1 SAT問题生成测试

区块链难度Difficulty为3 000、Header头部信息为“test”时，使用算法1、算法2、CA算法[18]生成的SAT的cnf文件[20]如图3所示，变量为3 500，子句为14 875，变量和子句比值为4.25。

3.2 SAT问题求解测试

节点创建完相关难度的区块后，节点使用Walksat求解器进行求解，心跳时间为300s。如节点求解图3所示的SAT文件，在300s的心跳时间内未能求解成功，输出相关数据，如图4。

3.3 SAT证明共识达成测试

启动4个节点，进行共识测试。4个节点对图3所示的SAT文件进行求解、广播和共识协商。最终达成共识，此轮4个矿工共识结果如图5所示。本轮由地址为5 080的矿工求得最大解，获得本轮记账权。

4 结语

本文提出了一种基于有用工作量证明共识算法，该共识算法主要基于可满足性问题竞争求解，从而有效解决基于哈希计算工作量证明的无意义消耗问题，有助于更好创造SAT问题的研究环境，实现有用工作，对区块链与理论计算机关联研究有一定应用价值。

文中给出了该共识算法在节点矿工于SAT实例生成、SAT问题求解、区块和解广播、共识达成的详细过程及算法与网络难度控制描述，完整介绍了该共识算法核心内容，最后使用Go语言实现了基于该共识算法的区块链系统。实验证明，各节点可平稳运行算法，该区块链系统运转稳定，从而说明该共识算法可行。若在区块链公网上使用该共识机制，将有助于利用算力进行SAT问题研究，构建更好的SAT问题研究环境。

参考文献：

[1] 沈鑫，裴庆祺，刘雪峰. 区块链技术综述[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] 刘燕丽，徐振兴，熊丹. 基于动态奖惩的分支策略的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] 刘懿中，刘建伟，张宗洋，等.  区块链共识机制研究综述[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] 陈稳.  基于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.

（责任编辑：江 艳）