萧梓健 唐屹

摘 要：为减少在公链上基于哈希的工作量证明中无意义计算消耗，合理利用区块链网络算力，创建一个促进可满足性问题（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]，除完成工作量证明外，并没有带来更多有意义的工作。……