What computational mathematics problems that could be used as proof-of-work problems for cryptocurrencies? To make this question easier to answer, I want proof-of-work systems that work in cryptocurrencies that contain many different kinds of proof-of-work problems (the use of many different kinds of proof-of-work problems is more secure than the use of only one type of proof-of-work problem) instead of proof-of-work systems that work in cryptocurrencies with only one kind of proof-of-work problem.
Background
To make things simple, cryptocurrency mining requires one to solve computational problems as a proof-of-work. For example, in Bitcoin, the miners must find data whose SHA-256 hash begins with many zeroes. Unfortunately, solutions to the proof-of-work problem for most cryptocurrencies have no intrinsic value in themselves, and these problems use up great amounts of resources and people have even made malware to solve these proof-of-work problems.
Mathematicians have a limited amount of computational resources and cryptocurrency mining could potentially supply mathematicians with a nearly unlimited amount of computational power. For example, cryptocurrency miners receive an equivalent of millions of dollars in revenue per day and they spend much computational power solving the problems required to mine these cryptocurrencies.
Requirements
Most computational mathematics problems are unsuitable as proof-of-work problems for cryptocurrencies. Here are some requirements and things we would like in such a problem.
-
$\textbf{Verifiable but intractible:}$ The problem must be difficult to solve but easy to verify. Many NP-complete problems will satisfy this requirement.
-
$\textbf{Tunability:}$ The difficulty of the problems must be fine-tunable. There should be a system in place that, given a positive real number $t$, automatically and efficiently selects a problem that can be solved on average in $t$ seconds without actually solving the problem. Optimization problems can easily be made to satisfy this requirement since with an optimization problem one can simply choose the best solution every 5 minutes or so (optimization problems may not be the best for cryptocurrencies though).
-
$\textbf{Intrinsic value:}$ The solution to the problems must have some intrinsic value. These solutions and not just the process of obtaining the solutions should be of a scientific, mathematical or practical interest.
-
$\textbf{Efficient automatic generation:}$ The problems must be automatically generated since cryptocurrencies in-general have no central authorities.
-
$\textbf{Solution tied to block and solver:}$ For example, in Bitcoin the information being hashed includes the person solving the problem along with other information. This way someone cannot steal someone else's solution.
The following traits are necessary only if there is one or a couple kinds of proof-of-work problem per cryptocurrency or there is no process to automatically remove broken proof-of-work problems.
i. $\textbf{Endless problems:}$ There must be a limitless amount of problems to solve so that a new problem could generated every few minutes.
ii. $\textbf{Unbreakability:}$ The class of problems should be “unbreakable”. The security of cryptocurrencies depends on the fact that no party should have a secret algorithm that quickly solves the problems and that no body is likely to develop such a secret algorithm in the future.
iii. $\textbf{Progress freeness:}$ Each individual problem must be “progress-free” in the following sense. If Alice works on the problem from noon and Alice has not found a solution by 12:30, then at 12:30 Alice will have no advantage over another participant who begins working on the problem at 12:30. In other words, the amount of time it takes to solve the given problem follows an exponential distribution.
iv. $\textbf{Pre-computation resistance:}$(observed by Loreno Heer in the comments) The proof-of-work problem should be “pre-computation resistant”. One way to obtain this desired property is to make the proof-of-work problem dependent on random data such as current transactions. One could also make future problems depend on previous solutions.
Other comments
I am slightly more interested in mathematical problems which have or may have future practical applications instead of problems which are only of a purely mathematical interest. In a best case scenario, I would like to see problems which may have cryptographic applications.
This question differs from this previous question since the previous question did not ask for problems which are specifically suitable as proof-of-work problems for cryptocurrency mining (and the answers given are not suitable as proof-of-work problems for cryptocurrency mining either).
Best Answer
Have you considered unknotting knots?
The problem would be finding a sequence of Reidemeister moves for a random link graph that reduces it to the unknot. In some cases, no such sequence would exist, but most random graphs are known to be unknotted under certain knotting algorithms: http://iopscience.iop.org/article/10.1088/1751-8113/49/40/405001/meta
Unknotting itself is in NP, as discussed here: Is there a polynomial-time algorithm for untangling the unknot?
Unknotting has many real-life applications. Furthermore, given a potential sequence of Reidemeister moves that might unknot the knot, it is quite easy to verify that it produces the unknot.
There may be some problems with this (maybe a secret fast algorithm in the works?), but if so, I'm sure someone else will comment.