Proposal for NP-Complete Problem Refinement Smart Contract

Carlos Oliver, Alessandro Ricottone, Pericles Philippopoulos

Contact: cgoliver[at]protonmail[dot]com

The Ethereum network ¹ has shown great promise in de-centralizing a wide range of computations. This advance is being followed by an explosion of Dapps (decentralized applications) being developed in the past few months. While some Dapps have been designed to allow for the sharing of computational resources and super-computing ², there there do not exist any Dapps that directly reward users for working on specific computational puzzles. In particular, we focus on the class of problems known as NP-complete problems. For such problems, identifying a globally optimal solution is NP-Hard. Therefore, most approaches can only produce sub-optimal solutions. However, in many instances of such problems, the decision problem of “does there exist a solution with score X to the given problem?” is NP-complete ³. That is, given a solution to the problem, verifying whether its ‘quality score’ is above or below a given target can be done in polynomial time. Meanwhile, no polynomial time algorithms exists for identifying the solution in the first place. Many instances of this class of problem arise in the real world, for which the allocation of computational resources to improving current solutions can be highly valualbe. Such problems include (but are by no means limited to): DNA multiple sequence alignment, graph coloring, protein folding, travelling salesman problem, etc.

The ability to rapidly verify a solution to a difficult problem naturally lends itself to blockchain approaches (see Proof-of-Work). Several other blockchains have been developed to exploit this property of similar problems such as finding prime numbers (Primecoin⁴) , protein folding (CureCoin⁵), and DNA alignment (Coinami⁶). However, they have all proposed independent blockchains and in most cases depend on some level of centralization. Taking advantage of the wide use of Ethereum Smart Contracts, and its sibling decentralized storage network Swarm⁷, we propose a framework for incentivizing and verifying work on NP-complete problems in a fully de-centralized manner.

We call this new framework, crick.

crick

The main idea is to issue a token as a reward for the submission of valid improvements to existing solutions and updating the store of solutions accordingly in a fully de-centralized manner.

Data

One of the most popular tools available for the de-centralized storage of large datasets is Swarm. At genesis time, a large set of problems and their current quality scores are collected from publically available databases. One can apply heuristics to assess whether each instance of the problem is likely to be outside an optimum. For example, when dealing with DNA alignments, one can scan many available alignment databases and identifying regions of low confidence using a metric of alignment quality. Such regions of low quality can be extracted, indexed, scored, and stored in the Swarm network.

Any user on the network can download one of these puzzles and begin working on improving their score using whatever solver they wish to employ. Once they believe they have found an improved alignment they can execute the crick smart contract by paying the required amount of gas and submitting their solution.

Verification

The crick smart contract will accept the following:

• Index of proposed problem
• Improved solution
• Address of submitter (given by the msg.sender field

The smart contract will then:

• Verify that the submitted solution is compatible with the one stored in the database,
• Execute scoring function on the proposed puzzle. The scoring function can be any agreed upon measure of solution quality that can be computed efficiently.
• If the solution is a valid improvement, the solution is stored in the Swarm network and a number of crick tokens is awarded to the smart contract caller.
• Else the smart contract terminates producing an error.

Token distribution

The simplest approach to addressing the economics of the token is to make available a fixed number of tokens that are locked into the smart contract. Once a solution is found, a number of ‘reward’ tokens is transferred from the contract to the address of the problem solver. If the currency holds value, it can then be traded for Ether, Bitcoin, and eventually fiat currency. It is clear that crick tokens will hold intrinsic value in that they can be produced only as a consequence of investing computational work. In this manner the token behaves in a similarly to Bitcoin. Furthermore, Bitcoin also imposes a hard limit on the nubmer of tokes that will ever reach circulation. In order to pace the minting of tokens, we can implement a similar strategy to Bitcoin by adjusting the reward size in time. However, it is also possible to implement an unlimited number of tokens that can be minted minted. In this case, inflation could be held back as the difficulty of finding new solutions will naturally increase as solutions become more optimal.

Caveats

Bubka Attack

It is possible that a user may take advantage of the network by obtaining a solution to a puzzle that is better than the one known by the network by some substantial margin. The user can then keep this solution to him/herself and by slightly perturbing the solution, submitting, and repeating, the attacker will receive many rewards for essentially the same sub-optimal solutions. This attack is named after Ukrainian pole vaulter, Sergey Bubka who repeatedly broke his own records by small margins to claim a new prize each time.

While we expect that the occurence of such cases will be rare and become more rare as problems become more difficult, a potential solution is to limit the ability of the user to choose which problems to work on. The smart contract could pseudo-randomly (based on address hashes and timestamps) assign a set of valid problems that can be accepted by the contract at a certain time. Therefore, if someone secretly has a sequence of valid solutions to a puzzle, they would have to wait a substatial amount of time before they could claim the reward; during which time another user may beat them to the prize.

Problem depletion

An obvious question that can be raised is what to do when the working set of problems becomes too difficult for any further improvements? The natural solution would be to allow for some mechanism by which new problems can be introduced into the set of puzzles. The main challenge with implementing such a system in a de-centralized context is to ensure that problems being submitted are a) valid in format b) of interest c) relatively un-worked. In particular we stress condition c) as a malicious user would benefit by working on a puzzle offline and obtaining a solution in secret and then submitting the puzzle to the network. The malicious user would then be able to immediately publish a solution to the puzzle and claim the reward while never allowing other users the opportunity to solve the puzzle.

There are two possible solutions to this problem.

1. Group consensus on adoption of new problem set.

   An interesting feature of Ethereum is the ability to create decentralized autonomous organizations (DAO) which have been used to arrive at consensus in the absence of a central authority. Ultimately the a DAO is a collection of smart contracts which can be used to decide how investors distribute funds through an auditable voting system. In a similar manner, crick users can be allowed to propose problem sets to publish and a consensus can be reached by users if a representative majority agrees that the problem set would be a fair addition to the network.

   We note that this process can also be employed at the stage of selecting the initial problem set to make the contract fully de-centralized.

2. Fee based individual submission.

   Alternatively, one could allow users to submit their own problems which they wish to see worked on by the network. However, to prevent spamming, we introduce a submission fee. The idea here is that a ‘submission smart contract’ would accept a puzzle, check it for format and valididty (is it a true instance of the contract problem?) and store the fee in crick tokens. The puzzle would then be stored for any user to attempt a solution. These tokens will then be used as rewards for that puzzle. If a malicious submitter had solutions to that puzzle prepared, he or she would simply recuperate their initial deposit and have consumed gas for no gain. A user could potentially submit a puzzle that he or she knows to be un-solvable or very close to optimal which would potentially waste other users time. However, the submitter would be initially discouraged from doing this as the submission fee should be sufficiently high to prevent large scale attacks of this sort. An advantage of this method is that it allows for the re-circulation of crick tokens back into the economy. Users can obtain the coins by solving other users problems and re-invest their coins by having their own problems solved.

Conclusion

This is a general initial outline of the first Ethereum based and fully de-centralized mathematical puzzle solving framework. As currently proposed, the token would be given to users who solve an instance of the same problem (e.g. DNA multiple sequence alignment, or graph coloring). However, it would be simple to create several contracts that can each verify different types of problem to allow for the network to handle a diversity of computational problems. A more detailed version of the framework with in depth analysis of each component will follow.

Bibliography