Proof-of-work Mechanism Based On Boolean Satisfiability Problem

Blockchain technology is in a state of rapid development and is hailed as a new disruptive technology.Blockchain technology is used in many fields.Blockchain technology contains many underlying technologies,and consensus algorithms are used to ensure the consistency of the data of the blockchain network nodes in the distributed system.The proof-of-work mechanism is a consensus algorithm commonly used on the public chain of blockchain,and cryptocurrency systems such as the Bitcoin network and the Ethereum network often use the competition of calculation of hash function to complete the proof of work.However,this hashing-based proof-of-work has the problem of relying on a large number of meaningless hash calculations causing energy consumption and waste.Most of the hash values are disposable.In addition to completing the proof of work,it does not bring more meaningful work..In order to reduce the energy consumption of meaningless calculations of the above problems,and the blockchain computing power of the proof-of-work can be used for useful work research,this thesis combines the idea of proof-of-useful-work and proposes satisfiability-problem-based proof-of-work.The satisfiability problem is an important problem in the field of computer science,and the research on the solution method of satisfiability problem has practical application value.Blockchain network nodes generate difficult satisfiability problems that meet industrial requirements through a given framework,and compete to solve the difficult satisfiability problems to complete the proof of work,thereby obtaining the right to generate blocks,the right to keep accounts of transactions,and enable nodes in the network to reach a consensus on the block ledger to ensure the consistency of data information.This mechanism makes the use of computing resources in the network meaningful,and the satisfiability problem can be further studied.This thesis presents detailed design schemes and related algorithms for the network block design,framework design,miner node workflow,etc.of satisfiability-problem-based proof-of-work.And this paper shows the research work and related results of using the number of satisfiability problem variables as the difficulty value of the network to control the generation speed of blocks in the network.Through experimental tests and result analysis,the feasibility of the design scheme of the mechanism and the feasibility of the related algorithms are explained.The simulation experiments are also adopted to simulate the consensus process of the blockchain system nodes using the mechanism,which shows that the miner nodes can effectively reach consensus.